The title
Solving Sudoku – force buckle
Analysis of the
Readers who are not sure about the rules of sudoku can check it out here: Sudoku.
Similar to the previous word search and N Queen problems, the solution to sudoku is also simple and rough:
- Let’s see if we can fill in the current position
- If so, fill in and proceed to the next position
- If you hit a dead end, go back and fill in the other results
This is the core of the backtracking algorithm. Taking Sudoku as an example, we can take a look at the following flow chart to facilitate understanding of the backtracking algorithm:
So we can complete the macro architecture of the code by following this pattern:
var solveSudoku = function (board) {
// iterate over the board
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
// If the current grid is not., it indicates that the grid has already been lowered
if(board[i][j] ! = =".") continue;
for (let value = 1; value <= 9; value++) {
if (canset()) {
// Update the status to go to the next step, rollback the status
board[i][j] = value;
solveSudoku(board);
board[i][j] = "."; }}}}};Copy the code
For the above code, don’t forget to consider boundary conditions:
- When back
- Obviously, it should fall back when all the values in the current grid cannot be filled, so it should return after iterating through the optional values from 1 to 9
false
- Obviously, it should fall back when all the values in the current grid cannot be filled, so it should return after iterating through the optional values from 1 to 9
- When to end
- When the whole board is filled in, that’s when it says you’ve solved the answer and you’re done, so you should return
true
- When the whole board is filled in, that’s when it says you’ve solved the answer and you’re done, so you should return
The code is as follows:
var solveSudoku = function (board) {
// iterate over the board
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
// If the current grid is not., it indicates that the grid has already been lowered
if(board[i][j] ! = =".") continue;
for (let value = 1; value <= 9; value++) {
if (canSet()) {
// Update the status to go to the next step, rollback the status
board[i][j] = value;
+ if (solveSudoku(board)) return true;
board[i][j] = "."; }} +return false; }} +return true;
};
Copy the code
Next comes the implementation in detail: how to determine whether the current grid can be filled with the corresponding number.
It’s not hard to sort out the rules:
- None of the values already in the current row can be equal to value
- None of the values already in the current column can be equal to value
- The current
3 x 3
None of the existing values in the nine cells of value cannot be equal to value
In the first two cases, we need to fix the dead row and col. In the third case, we need to find which nine cells the current cell traversed belongs to.
Here’s a sudoku:
As you can see, the nine squares divide the entire 9 x 9 board into nine pieces, so we can completely ignore the small squares and convert them into a 3 x 3 board.
const x = Math.floor(row / 3) * 3;
const y = Math.floor(col / 3) * 3;
Copy the code
So ok and fixed position is specific 9 palace case.
To sum up, improve canSet code:
const canSet = (board, row, col, value) = > {
const x = Math.floor(row / 3) * 3;
const y = Math.floor(col / 3) * 3;
// There are numbers equal to value
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[x + i][y + j] === value) {
return false; }}}// Rows and columns have numbers equal to value
for (let i = 0; i < 9; i++) {
if (board[row][i] === value || board[i][col] === value) {
return false; }}return true;
};
Copy the code
The results are as follows: