Sudoku rules
In Sudoku games, the classic nine-cage grid consisting of 9×9=81 cells, and also forms 3×3=9 small nine-cage grids. It is required to fill in the numbers 1~9 in 81 small cells, and the numbers cannot be repeated in each row, column and each small nine-cage grid.
Sudoku skills
My thoughts
Solution design and implementation
Only a two-dimensional array is used to store the Sudoku scheme, a one-dimensional array is used as the stack, and a boolean variable is used as the backtrack identification.
1. Variable definition:
var problem = [ //This is the question of difficulty 10.7 mentioned in the book [8,0,0,0,0,0,0,0,0], [0,0,3,6,0,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,0,0,0,0,4,5,7,0,0,0], [0,0,0,1,0,0,0,0,3,0], [0,0,1,0,0,0,0,0,6,8], [0,0,8,5,0,0,0,0,1,0], [0,9,0,0,0,0,0,0,4,0,0,0]] var stack = [],flag = false;
2. Determination of the effectiveness of the plan:
The hashing feature of JavaScript objects is fully utilized. In order to facilitate debugging, the return value of the function is 0 when it is valid, and there are three situations when it is invalid: row conflict, column conflict, and nine-part grid conflict, which return 1, 2, and 3 respectively. I used it in the early judgment, and later added the relevant twenty-frame judgment. This function is no longer used when looking for the answer.
function checkValid(sudo){ let subSudo = {} //Auxiliary variable used to determine whether the ninth grid conflicts for(let i = 0; i<9; i++){ let row = {}, col = {} //Auxiliary variable used to determine whether rows and columns conflicts for(let j = 0; j<9; j++){ let cur1 = sudo[i][j], cur2 = sudo[j][i] //Authorized variable completed row and column judgment at the same time if(row[cur1]) //The current element has appeared in the row, and the judgment of zero is optimized. When the key is 0, the value is 0, no additional judgment is required. Return 1; //Return error code else row[cur1] = cur1 //The current element does not appear in the row and is stored in the auxiliary variable if(col[cur2]) //The judgment of the column is similar to the row. The judgment of zero is optimized. When the key is 0, the value is 0, and there is no need for additional judgment. Return 2; else col[cur2] = cur2; let key = Math.floor(i/3)+'-'+Math.floor(j/3) //The different keys are generated for different nine-client grids if(subSudo[key]){ //The judgment of zero is already there, and the judgment of zero is optimized. When the key is 0, the value is 0, and there is no need for additional judgment if(subSudo[key][cur1]) //The judgment of a nine-client grid is similar to that of row returns 3 else subSudo[key][cur1] = cur1 }else{ //This is the first element in a small nine-dish grid subSudo[key] = {} // Create a new auxiliary variable for the small nine-dish grid and save the first element into it subSudo[key][cur1] = cur1 } } } return 0; //The program can run this, indicating that the plan is valid} 3. Relevant Twenty Category Determination The principle is the same as the overall judgment, and the highlight lies in the positioning of the small nine-cage grid. function check20Grid(sudo,i,j){ let row = {}, col = {}, subSudo = {} //Supply variable for(let k = 0; k < 9; k++){ let cur1 = sudo[i][k], cur2 = sudo[k][j] if(cur1){ //The current element has appeared in the row, and the judgment of zero is optimized. When the key is 0, the value is 0, and there is no need for additional judgment if(row[cur1]) return 1; //Return error code else row[cur1] = cur1 //The current element does not appear in the row, and is stored in the auxiliary variable} if(cur2){ //The judgment of the column is similar to the row. The judgment of zero loss is optimized. The value is 0 when the key is 0. There is no need for additional judgment if(col[cur2]) return 2; else col[cur2] = cur2; } //The coordinates of the conversion loop variable to the ninth grid let key = sudo[Math.floor(i/3)*3 + Math.floor(k/3)][Math.floor(j/3)*3+Math.floor(k%3)] if(subSudo[key]) //The judgment of the ninth grid is similar to the row. The judgment of zero loss is optimized. The value is 0 when the key is 0. There is no need for additional judgment return 3 else subSudo[key] = key } return 0;}4. Traversal solution
Using elements with initial value of zero in element state is a pending feature, and with the assistance of the stack, no additional storage space is opened.
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 of the element to be determined or back to the current position. The two situations seem to be different, but in fact the processing is the same. Add 1 by yourself flag = false; let k = problem[i][j] + 1; //Search to move towards the next legal value while(k<10){ //Loop to find the next legal value problem[i][j] = k; //Fill in if(check20Grid(problem,i,j) == 0){ //Default is legal, and the relevant twenty-frame judgment is stack.push([i,j++]) //Storage the traceback point and step into break; } k++; } if(k>9){ //The legal value cannot be found at the current position, the traceback problem[i][j] = 0; //Return before the traceback let rt = stack.pop(); //Retrieve the traceback information in the stack if(!rt) //No solution judgment, return 0 return 0; i=rt[0] //Travel j=rt[1] flag = true; } }else{ //The current position number is given j++; } } } return 1; //Successfully found a set of solutions}