проблема
Sudoku Solver Hard
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: [
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]
]
Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9board[i].length == 9-
board[i][j]is a digit or'.'. - It is guaranteed that the input board has only one solution.
Идеи решения
Если у вас есть друзья, которые любят играть в судоку, вы должны быть так же рады этому вопросу, как и я, думая, что предыдущий опыт игры в судоку может быть полезен. Но когда я его закончил, то обнаружил, что это не так, как я себе представлял, и вообще бесполезно -_-|||. В чем хороши компьютеры, так это в исчерпании, а работа программиста состоит в том, чтобы сделать его разумно исчерпывающим. Без дальнейших церемоний, возвращаясь к этому вопросу, эта статья даст два решения, одно исчерпывающее, а другое умное исчерпывающее.
Друзья, которые решали судоку, должны знать, что при запуске вопроса часто в пространстве есть несколько возможных чисел-кандидатов.Нам нужно проанализировать отношения ограничений между каждым узлом и удалить некоторые числа-кандидаты, пока в каждом пространстве не останется только один кандидат. чтобы получить окончательное решение.
Идея решения 1 проста и понятна:
- цикл до тех пор, пока не встретится пробел
'.' - Попробуйте все числа-кандидаты, если сможете найти, заполните его в таблице судоку и перейдите к следующему месту.
'.', повторите этот шаг - Если цифр-кандидатов нет, вернитесь к предыдущему пространству и сбросьте его на
'.', перейдите к шагу 2 в предыдущей сетке и попробуйте другие возможные номера-кандидаты - Если все пробелы обработаны на шаге 2, решение судоку успешно
На самом деле это просто попытки туда и обратно. Чтобы выразить рекурсивно, вам нужно определить рекурсивную функциюdoSolve(char[][] board, int row, int col), чтобы обработать узел. отboard[0][0]Начать, по порядку слева направо, сверху вниз, справаboardЭлементы в вызове рекурсивной функции один за другим. При встрече с вышеперечисленнымШаг 3В случае , когда вы не можете продолжать попытки, рекурсивная функцияdoSolveОшибка возврата. Возвращает успех, если он может продолжать попытки. Решение считается успешным, когда рекурсивная функция обращается ко всем пробелам.
Хотя решение 1 принимается LeetCode, его выполнение происходит относительно медленно, опережая только 14% конкурирующих решений.
ссылка ответ один
public class Solution {
public void solveSudoku(char[][] board) {
doSolve(board, 0, 0);
}
private boolean doSolve(char[][] board, int row, int col) {
// if all cells have been solved, then return true
if(row == 9 && col == 0) {
return true;
}
// decide the next row & col to solve
final int nextRow = (col + 1) == 9 ? row + 1 : row;
final int nextCol = (col + 1) == 9 ? 0 : col + 1;
// if current cell has been solved then solve the next one
if(board[row][col] != '.') {
return doSolve(board, nextRow, nextCol);
}
// if current cell hasn't been solved, then try from 1 to 9
for(char num = '1'; num <= '9'; num++) {
if(isValid(board, row, col, num)){
// if the candidate num is valid
// set it to board temporarily
board[row][col] = num;
// then solve the next one
if(doSolve(board, nextRow, nextCol)) {
// if all the rest cells have been solved, return true
return true;
}
// if any rest cells can't be solved, set back to '.' and continue trying
board[row][col] = '.';
}
}
return false;
}
private boolean isValid(char[][] board, int row, int col, char num) {
// the row & col of the first cell in the cube
int cubeRow = (row / 3) * 3;
int cubeCol = (col / 3) * 3;
for (int i = 0; i < 9; i++) {
// if num already exists in the same col
// or num already exists in the same row
// or num already exists in the same cube
if (board[i][col] == num
|| board[row][i] == num
|| board[cubeRow + i / 3][cubeCol + i % 3] == num) {
return false;
}
}
return true;
}
}
Вторая идея решения проблемы
Это решение также было известноАлгоритм Ли Сянь Луна,Да! Вы правильно прочитали, это Ли Сянь Лун, нынешний премьер-министр Сингапура, сын бывшего премьер-министра Ли Куан Ю. Он написал этот алгоритм на языке Си, когда учился на математическом факультете Кембриджского университета. Этот г-н Ли может быть самым искусным в программировании среди премьер-министров и самым искусным премьер-министром среди программистов; П.
Прежде чем расшифровать этот алгоритм, давайте рассмотрим егобитовая операцияБар. Помните следующие операторы?
-
&:побитовое И, Например 010 и 110 = 010 -
|:побитовое ИЛИ, например 010 | 110 = 110 -
~:побитовое отрицание, например ~010 = 101 -
&=:Побитовое И присвоить, например, a = 11110, b = 1000, после выполнения a &= ~b, a = 10110 -
|=:побитовое ИЛИ присваивание, например, a = 10110, b = 1000, после выполнения a |= b, a = 11110 -
<<:смещение, например 1 -
-:отрицательный переход, выраженный как дополнение в Java, то есть дополнение + 1, например -10110 = 01001 + 1 = 01010
Вернемся к этому алгоритму, что в нем хорошего? На самом деле его общая идея такова.Решение первоеПочти исчерпан, но оптимизирована только работа операции. Конкретные оптимизации заключаются в следующем:
Заселенность чисел в сетке из девяти клеток
Решение первоеиспользуя оригиналboard[][]фиксировать занятость номеров.
Решение второе用Bitmap的方式，表示一行，一列或者一宫中已经被占用的数字。 Напримерint[9] rowBitmap, colBitmap, cubeBitmap;, битмап содержит10 бит, младший значащий бит (крайний правый бит) всегда0, а остальные биты представляют от младшего к старшему соответственноДоступны ли номера с 1 по 9,1указывает на то, что соответствующий номер доступен, и0Указывает, что он был занят. Например0b1000000010Указывает соответствующую строку, столбец или дворец,1и9не занят.
Кроме того, растровое изображение также используется для представления альтернативного числа в пространстве, напримерint cellBitmapзначение0b1000000010, Это значит1и9не появляется в строке, столбце или дворце, где расположено пространство.
Найти номера кандидатов в пробелах
Решение первоеСлой используется при поиске номера-кандидата с пробелом вдля петлиИщите неиспользуемые числа в параллельном, столбце и дворце.
Решение второеэто просто,cellBitmap = rowBitmap[row] & colBitmap[col] & cubeBitmap[cube];однобитовая операцияНет, спасибо, что взял. В этом тонкость алгоритма Ли Сянь Луна!
приоритет обработки
Решение первоеВ , порядок приоритета не установлен, но пробелы обрабатываются в естественном порядке их появления.
Решение второеОт простого к сложному, начиная с наименьшего количества кандидатов, уменьшая количество этапов, которые могут потребоваться для возврата в случае неудачной попытки. Для построения приоритета двумерная сетка из девяти квадратовint[9][9] boardПреобразовать в одномерный массивint[81] entry.
В то же время сint[81] sequenceУказывает приоритет обработки, а его значение соответствуетentryОдномерные координаты в .boardВ известных цифровых на фронте, затем пространство обработки, отcellBitmapсередина1Наименьшее количество пробелов для начала обработки. Мы можем использовать функции, предоставляемые JavaInteger.bitCount (cellBitmap)легко получить1количество.
Преобразование координат
Чтобы не повторять преобразование из одномерных координат в двумерные, используйтеint[81] squareToRow, squareToCol, squareToCube;Сохранить координатное отображение, чтобы избежать двойного подсчета.
Использование других побитовых операций
Преобразование между доской и записью
Для облегчения побитовых операцийentryЧисло представлено Bitmap, т.е.board[i][j]==3Выражается какentry[i*9+j]==0b1000. будет3Конвертирован в0b1000Просто используйте операцию смещения,1 << board[i][j], в то время как0b1000преобразовать в3, которая может быть функцией, предоставляемой JavaInteger.numberOfTrailingZeros(entry[i*9+j]).
Изменить или восстановить растровое изображение
В процессе попытки вам необходимо изменить растровое изображение, соответствующее строке, столбцу и дворцу.Если попытка не удалась, вам необходимо восстановить исходное растровое изображение. Используйте побитовое И при изменении растрового изображенияrowBitmap[rowIdx] &= ~nextDigitBitИспользуется при восстановлении распределения битов илиrowBitmap[rowIdx] |= nextDigitBit.
Например:rowBitmap[rowIdx] = 1111111110, nextDigitBit = 1000, воплощать в жизньrowBitmap[rowIdx] &= ~nextDigitBitпосле модификации,rowBitmap[rowIdx] == 1111110110; затем выполнитьrowBitmap[rowIdx] |= nextDigitBitПосле восстановления,rowBitmap[rowIdx] == 1111111110.
получить номера кандидатов
Когда мы знаем все альтернативные числа в пространствеcellBitmap, как их вынуть и использовать по одному? Здесь требуется отрицательное преобразование и побитовое И. воплощать в жизньnextDigitBit = cellBitmap & -cellBitmapсамый низкий возможный1и за ним0. НапримерcellBitmap = 1001000000После выполнения вышеуказанной операцииnextDigitBit == 1000000, разве это не удивительно! затем изменитьcellBitmap &= ~nextDigitBit, установите соответствующий бит в ноль и циклически перебирайте все номера-кандидаты, покаcellBitmap == 0.
Анализ идей здесь, решение, наконец, превзошло 99,69% конкурирующих решений, премьер-министр Ли Сянь Лун, пожалуйста, примите мое колено Орз.
Справочный ответ два
public class Solution {
static final int ALL_ZEROS = 0;
// 0x3fe = 1111111110
static final int ALL_ONES = 0x3fe;
// bitmaps for row/col/cube, 1 means available
int[] rowBitmap, colBitmap, cubeBitmap;
// 1D array to store board nums' pos in bitmap, e.g. board[i][j] == 3, then entry[i*9+j] == 1000
int[] entry;
// 1D array to store the priority of SQUARE index, 0 <= sequence[i] < 81, 0 <= i < 81
int[] sequence;
// always points to the first empty cell's SQUARE index, which is stored in SEQUENCE
int seqStart;
// 1D utility arrays to store mapping from SQUARE to ROW/COLs/CUBES
int[] squareToRow, squareToCol, squareToCube;
public void solveSudoku(char[][] board) {
seqStart = 0;
rowBitmap = new int[9];
colBitmap = new int[9];
cubeBitmap = new int[9];
entry = new int[81];
sequence = new int[81];
squareToRow = new int[81];
squareToCol = new int[81];
squareToCube = new int[81];
// initialize all helping data structures
// all digits are initially all available (marked by 1) in all rows/columns/cubes
for (int i = 0; i < 9; i++) {
rowBitmap[i] = colBitmap[i] = cubeBitmap[i] = ALL_ONES;
}
// sequence stores all SQUARE indices of all cells, with 0..start-1 being all filled cells
// and the rest all empty, initially start = 0
for (int i = 0; i < 81; i++) {
sequence[i] = i;
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// mapping from SQUARE to I/J is also beneficial: avoid calculating I/J from SQUARE later
int square = i * 9 + j;
squareToRow[square] = i;
squareToCol[square] = j;
squareToCube[square] = (i / 3) * 3 + j / 3;
}
}
// fill in the given cells. update the bitmaps at the same time
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int square = i * 9 + j, val = board[i][j] - '0';
// e.g. val = 3, valbit = '1000'
int valbit = 1 << val;
// e.g. bitmap = 1111111110, valbit = 1000, bitmap &= ~valbit makes 1111110110
rowBitmap[i] &= ~valbit;
colBitmap[j] &= ~valbit;
cubeBitmap[(i / 3) * 3 + j / 3] &= ~valbit;
entry[square] = valbit;
int seqIter = seqStart;
// compact non-empty cells to the front
// and use seqStart to mark the first empty cell's position
while (seqIter < 81 && sequence[seqIter] != square) {
seqIter++;
}
swapSeq(seqStart++, seqIter);
}
}
}
// main solver process
boolean success = place (seqStart);
assert success : "Unsolvable Puzzle!";
// dump result back from ENTRY array to BOARD
for (int s = 0; s < 81; s++) {
int i = squareToRow[s], j = squareToCol[s];
board[i][j] = (char) (Integer.numberOfTrailingZeros (entry[s]) + '0');
}
}
boolean place (int seqPos) {
// if all cells have been solved, then return true
if (seqPos >= 81) {
return true;
}
// find the most determinable cell and swap to the front of SEQUENCE
int seqNext = nextPos (seqPos);
swapSeq (seqPos, seqNext);
int square = sequence[seqPos];
int rowIdx = squareToRow[square];
int colIdx = squareToCol[square];
int cubeIdx = squareToCube[square];
int cellBitmap = rowBitmap[rowIdx] & colBitmap[colIdx] & cubeBitmap[cubeIdx];
while (cellBitmap > 0) {
// get each available bit/digit in order
int nextDigitBit = cellBitmap & -cellBitmap;
cellBitmap &= ~nextDigitBit;
entry[square] = nextDigitBit;
// claim this DIGIT is used in row/column/cube
rowBitmap[rowIdx] &= ~nextDigitBit;
colBitmap[colIdx] &= ~nextDigitBit;
cubeBitmap[cubeIdx] &= ~nextDigitBit;
if (place (seqPos + 1)) {
return true;
}
// undo claims in the bitmaps
rowBitmap[rowIdx] |= nextDigitBit;
colBitmap[colIdx] |= nextDigitBit;
cubeBitmap[cubeIdx] |= nextDigitBit;
entry[square] = ALL_ZEROS;
}
swapSeq (seqPos, seqNext);
return false;
}
// find among empty cells the most determinable one: least bits on its bitmap;
int nextPos (int pos) {
int minIdx = pos, minDigitCount = 100;
for (int i = pos; i < 81; i++) {
int square = sequence[i];
// number of bits in cellBitmap is the number of digits that this cell can take
int cellBitmap = rowBitmap[squareToRow[square]]
& colBitmap[squareToCol[square]]
& cubeBitmap[squareToCube[square]];
// counts the '1's, so you know how many digits this CELL can take: we want the minimum one
int numPossibleDigits = Integer.bitCount (cellBitmap);
if (numPossibleDigits < minDigitCount) {
minIdx = i;
minDigitCount = numPossibleDigits;
}
}
return minIdx;
}
void swapSeq (int i, int j) {
int tmp = sequence[i];
sequence[i] = sequence[j];
sequence[j] = tmp;
}
}
Внешняя граница
Приходите расслабиться и решить простую и эффективную задачу судоку!
Или зайдите в колонку автора LeetCode, чтобы узнать, есть ли другие интересные вопросы!
Информационная ссылка
оригинальное названиеLee tco.com/problems/su...
Решение на оригинальном Facebook Lee Hsien Loongwoohoo.Facebook.com/ умирают от голода, ох, ох…