Summary of main ideas of JavaScript traversal in solving Sudoku problem
- 2021-06-28 10:35:25
- OfStack
Sudoku Rule
Sudoku game, classic 9×9 = 81 cells in a 9-cell grid, which also forms 3×3 = 9 small 9 panes, requiring numbers 1-9 to be filled in 81 small cells, and numbers cannot be repeated in each row, column, or in each small 9 pane.
Sudoku Strategies
My thoughts
Scheme Design and Implementation
Only one 2-dimensional array was used to store the Sudoku scheme, one 1-dimensional array as the stack, and one Boolean variable as the backtrace identifier.
1. Variable Definition:
var problem = [ // This is the difficulty mentioned in the book 10.7 Title of
[8,0,0,0,0,0,0,0,0],
[0,0,3,6,0,0,0,0,0],
[0,7,0,0,9,0,2,0,0],
[0,5,0,0,0,7,0,0,0],
[0,0,0,0,4,5,7,0,0],
[0,0,0,1,0,0,0,3,0],
[0,0,1,0,0,0,0,6,8],
[0,0,8,5,0,0,0,1,0],
[0,9,0,0,0,0,4,0,0]
]
var stack = [],flag = false;
2. Scheme validity determination:
Making full use of the hash feature of the javascript object, for debugging convenience, the return value of the function is 0 when it is valid and 3 when it is invalid. Row conflict, column conflict and small 9-grid conflict return 1, 2, 3 respectively.Previous judgment used it, and later added the relevant 210-grid judgment, this function will not be used when finding the answer.
function checkValid(sudo){
let subSudo = {} // Auxiliary variable to determine small 9 Is the palace in conflict
for(let i = 0; i<9; i++){
let row = {}, col = {} // Auxiliary variable to determine whether rows and columns conflict
for(let j = 0; j<9; j++){
let cur1 = sudo[i][j], cur2 = sudo[j][i] //1 Decision of Row and Column Completed Simultaneously by Secondary Inner Loop
if(row[cur1]) // The current element has already appeared in the row, optimizing the zero drop judgment, key by 0 Time value is 0 , no extra judgment is required
return 1; // Return error code
else
row[cur1] = cur1 // The current element does not appear in a row and is stored in an auxiliary variable
if(col[cur2]) // Column decisions are similar to rows, optimizing zero-dropping decisions. key by 0 Time value is 0 , no extra judgment is required
return 2;
else
col[cur2] = cur2;
let key = Math.floor(i/3)+'-'+Math.floor(j/3) // For different small 9 The generation of palaces is different key
if(subSudo[key]){ // Small 9 There are already elements in the palace, optimizing the zero-dropping judgment, key by 0 Time value is 0 , no extra judgment is required
if(subSudo[key][cur1]) // To 1 Small 9 The palace's decision is similar to the row's
return 3
else
subSudo[key][cur1] = cur1
}else{ // This is a small 9 In the palace 1 Elements
subSudo[key] = {} // For small 9 New Palace 1 And 1 Elements stored in
subSudo[key][cur1] = cur1
}
}
}
return 0; // The program runs here, indicating that the scheme is valid
}
3. Relevant 210-grid decision
The principle is the same as the overall judgment, and the highlight is on the positioning of the small 9 palaces.
function check20Grid(sudo,i,j){
let row = {}, col = {}, subSudo = {} // Auxiliary variable
for(let k = 0; k < 9; k++){
let cur1 = sudo[i][k], cur2 = sudo[k][j]
if(cur1){ // The current element has already appeared in the row, optimizing the zero drop judgment, key by 0 Time value is 0 , no extra judgment is required
if(row[cur1])
return 1; // Return error code
else
row[cur1] = cur1 // The current element does not appear in a row and is stored in an auxiliary variable
}
if(cur2){ // Column decisions are similar to rows, optimizing zero-dropping decisions. key by 0 Time value is 0 , no extra judgment is required
if(col[cur2])
return 2;
else
col[cur2] = cur2;
}
// Convert Loop Variable to Small 9 Coordinates of the palace
let key = sudo[Math.floor(i/3)*3 + Math.floor(k/3)][Math.floor(j/3)*3+Math.floor(k%3)]
if(subSudo[key]) //9 The palace judgement is similar to the row, optimizing the zero-dropping judgement. key by 0 Time value is 0 , no extra judgment is required
return 3
else
subSudo[key] = key
}
return 0;
}
4. Traversal Solution
An element with zero initial state is a pending feature, and with the help of the stack, no additional storage space is created.
function findAnswer(){
for(let i = 0; i<9; i++){
for(let j = 0; j<9; ){
if(problem[i][j] === 0 || flag){ // The current position is the first processing or backtracking of the element to be determined. The two situations seem different, but they are actually the same. 1 that will do
flag = false;
let k = problem[i][j] + 1; // Search Down 1 Legitimate value advances
while(k<10){ // Loop Find Down 1 Legal values
problem[i][j] = k; // Fill-in Value
if(check20Grid(problem,i,j) == 0){ // Adjudicate legitimate, relevant 210 Lattice determination
stack.push([i,j++]) // Store backtracking points and step by step
break;
}
k++;
}
if(k>9){ // No legal value found at current location, backtracking
problem[i][j] = 0; // Return to zero before backtracking
let rt = stack.pop(); // Retrieving backtrace information from stack
if(!rt) // No solution, go back 0
return 0;
i=rt[0] // Pass through
j=rt[1]
flag = true;
}
}else{ // Current position number given for title
j++;
}
}
}
return 1; // Successfully found 1 Configuration
}