Problems178
Search for a command to run...
Initialization
Scan for the first empty cell, then try digits 1–9 in it. A digit is allowed only if it is absent from that cell's row, its column and its 3×3 box. Place it and recurse; if the rest of the board cannot be finished, take it back and try the next digit.
Backtracking
1function solve(board) {//empty: 92 const n = 9;3 for (let i = 0; i < n; i++) {4 for (let j = 0; j < n; j++) {5 if (board[i][j] === '.') {6 for (let digit = '1'; digit <= '9'; digit++) {7 if (areRulesMet(board, i, j, digit)) {8 board[i][j] = digit;9 if (solve(board)) {10 return true;11 } else {12 board[i][j] = '.'; // undo13 }14 }15 }16 // No digit fits — an earlier choice was wrong17 return false;18 }19 }20 }21 return true; // no empty cells left22}23 24function areRulesMet(board, row, col, digit) {25 for (let i = 0; i < 9; i++) {26 if (board[row][i] === digit || board[i][col] === digit) {27 return false;28 }29 }30 const startRow = Math.floor(row / 3) * 3;31 const startCol = Math.floor(col / 3) * 3;32 for (let i = startRow; i < startRow + 3; i++) {33 for (let j = startCol; j < startCol + 3; j++) {34 if (board[i][j] === digit) return false;35 }36 }37 return true;38}