The problem
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", "eight" and ". ", ""," ", ""," 6 ", ""], [" 8", ""," ", ""," 6 ", ""," ", ""," 3 "], [" 4 ", ""," ", "eight" and ". ", "3", ""," ", "1"]. [" 7 ", ". ", ""," ", "2", ""," ", ""," 6 "], [". ", "6", ""," ", ""," ", "2", "eight", ""], [".", ""," ", "4", "1", "9", ""," ", "5"]. [".",".",".",".","8",".",".","7","9"] ] Output: [[" 5 ", "3", "4", "6", 7 ", "eight" and "9", "1", "2"], [" 6 ", "7", "2", "1", "9", "5", "3", "4", "eight"], [" 1 ", "9", "eight", "3", "4", "2", "5", "6", "7"]. [" 8 ", "5", "9", "7", "6", "1", "4", "2", "3"], [" 4 ", "2", "6", "eight" and "5", "3", "7", "9", "1"], [" 7 ", "1", "3", "9", "2", "4", "eight" and "5", "6"]. [" 9 ", "6", "1", "5", "3", "7", "2", "eight", "4"], [" 2 ", "eight", "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:Copy the code
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit or'. '.- It is guaranteed that the input board has only one solution.
Idea one
If you have friends who like to play Sudoku, you will be as happy to see this question as I am, thinking that the previous experience of playing Sudoku can be useful. But when I finished that is not the same as I thought, there is no place -_ – | | |. Computers excel at exhaustion, and it’s the programmer’s job to make it do it intelligently. Without further ado, this article will give two solutions, one is exhaustive, and the other is intelligent exhaustive.
Those of you who have done sudoku should know that at the beginning of the problem, a space often has multiple possible candidate numbers. We need to analyze the constraints between each node, remove some candidate numbers, until each space has only one candidate, then we can get the final solution.
The idea of solution 1 is simple and clear:
- Loop until you hit a space
'. ' - Try all the candidate numbers, and if you find one, fill it into the sudoku table and move on to the next blank
'. ', repeat this step - If there are no candidate numbers, return to the previous space and reset it to
'. ', proceed to Step 2 in the previous column and try other possible candidate numbers - If all Spaces are processed in Step 2, the sudoku solution succeeds
It’s just going back and forth trying. The recursive function doSolve(char[][] board, int row, int col) is defined to handle a node. Starting with board[0][0], recursive functions are called on the elements of board one by one in left-to-right and top-to-bottom order. The recursive function doSolve returns a failure when no further attempts are made in step 3 above. If you can continue, success is returned. The solution succeeds when all Spaces have been accessed by the recursive function.
Solution one, although accepted by LeetCode, was slow to execute, beating only 14% of competing solutions.
Reference answer 1
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; }}Copy the code
Problem number two
This solution is also known as Lee Hsien Loong algorithm, yes! You read that right, that Lee Hsien Loong, the current prime minister of Singapore, son of former Prime Minister Lee Kuan Yew. He wrote the algorithm in C when he was a mathematics student at Cambridge. This Mr Li is probably the best programmer and programmer among the prime ministers. P.
Before we get into this algorithm, let’s go over bit operations. Remember the following operators?
&:Bitwise and010&110 = 010|:Bitwise or, e.g. 010 | 110 = 110~:According to the not~010 = 101& =:Bitwise and allocationA = 11110, b = 1000, a = 10110 after executing a &= ~b| =:By bit or assignment= 10110, e.g. A, b = 1000, after performing a | = b, a = 11110<<:shift1 << 4 = 10000-:Negative transformationIn Java, it is expressed as complement code, i.e., inverse code +1. -10110 = 01001 +1 = 01010
Going back to this algorithm, what’s so good about it? In fact, the general idea of it is similar to solution 1, are exhaustive, but some of the operations are optimized with bit operations. The specific optimization is as follows:
The occupation of digits in the ninth grid
In solution 1, the original board[][] is used to record the occupation of numbers.
Solution 2 uses a Bitmap to represent the number in a row, column, or house that has been occupied. For example, int[9] rowBitmap, colBitmap, cubeBitmap; , the Bitmap contains 10 bits, the lowest bit (the rightmost bit) is always 0, and the remaining bits from lowest to highest indicate whether the numbers 1 to 9 are available, 1 indicates that the corresponding number is available, and 0 indicates that the number has been occupied. For example, 0B1000000010 indicates that the corresponding row, column, or palace is not occupied by 1 and 9.
In addition, Bitmap is used to represent alternate numbers in a space. For example, an int cellBitmap value of 0B1000000010 indicates that 1 and 9 do not appear in the row, column, or cell where the space resides.
Look for candidate numbers in the space
Solution 1 uses a layer of for loop to find the unused number in the corresponding row, column, or circle when looking for a blank candidate number.
CellBitmap = rowBitmap[row] & colBitmap[col] & cubeBitmap[cube]; cellBitmap = rowBitmap[row] & colBitmap[col] & cubeBitmap[cube]; A bit operation is taken away. This is the subtlety of Lee hsien Loong’s algorithm!
Processing priority
Solution 1 does not set the order of precedence, but processes the Spaces in the natural order in which they appear.
The second solution, from simple to complex, starts with the least number of candidates, reducing the number of series that may need to be returned if the attempt fails. To construct the priority, a two-dimensional nine-grid int[9][9] board is converted into a one-dimensional array int[81] entry.
Meanwhile, int[81] sequence is used to represent the priority order of processing, and its value corresponds to the one-dimensional coordinates in entry. The known numbers in the board are placed first, and whitespace is processed, starting with the least 1 whitespace in cellBitmap. We can easily get the number of 1s using the Java provided function integer.bitcount (cellBitmap).
Coordinate transformation
Int [81] squareToRow, squareToCol, squareToCube; Save coordinate maps to avoid double calculations.
Use of other bit operations
Conversion between board and entry
To facilitate bit calculation, numbers are represented by Bitmap in entry, that is, board[I][j]==3 is represented as entry[I *9+j]== 0B1000. To convert 3 to 0 b1000 displacement operation, only need to use 1 < < board [I] [j], and converting 0 b1000 into 3, can be in Java provides the function of Integer. NumberOfTrailingZeros (entry [I * 9 + j]).
Modify or restore the Bitmap
During the attempt, you need to modify the Bitmap corresponding to row, column and palace. If the attempt fails, you need to restore the original Bitmap. Modify the Bitmap using bitwise and allotment rowBitmap [rowIdx] & = ~ nextDigitBit, reduction using bitwise or allotment rowBitmap rowIdx | = nextDigitBit.
Such as: RowBitmap [rowIdx] = 1111111110, nextDigitBit = 1000 RowBitmap [rowIdx] = = 1111110110; And then execute rowBitmap [rowIdx] | = nextDigitBit after reduction, rowBitmap [rowIdx] = = 1111111110.
Get candidate numbers
When we know all the alternative cellbitmaps in a space, how do we pull them out and use them one by one? Negative conversions and bitwise and are required here. NextDigitBit = cellBitmap & -cellbitmap yields the lowest 1 and the 0 after it. CellBitmap = 1001000000 nextDigitBit == 1000000 Then modify cellBitmap &= ~nextDigitBit, set the corresponding Bit to zero, and cycle through all candidate digits until cellBitmap == 0.
That’s it. The solution beat 99.69% of the competing solutions. Prime Minister Lee Hsien Loong please take my knee Orz.
Reference Answer 2
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) {
inttmp = sequence[i]; sequence[i] = sequence[j]; sequence[j] = tmp; }}Copy the code
Expand training
Let’s relax and do a simple sudoku problem that works!
Leetcode.com/problems/va…
Or check out the author’s LeetCode column for additional questions of interest!
Juejin. Cn/column / 6997…
The data link
The original leetcode.com/problems/su…
The solution to the original lee hsien loong facebook www.facebook.com/leehsienloo…