Sudoku solver

Hard TimeO(9^blanks) SpaceO(blanks)

A Sudoku grid is solved when every row, every column and every 3 × 3 box holds the digits 1 to 9 exactly once, with the digits already present left exactly where they are. Given a partially filled board, fill every empty cell. The puzzle given has a solution.

Examples

Example 1

Input
run()
Output
[3,4,5,2,8,6,1,7,9]
The last row of the solved grid; it arrived as 3, 4, 5, 2, 8, 6, 1, 0, 0 with two blanks.

Example 2

Input
run().slice(7)
Output
[7,9]
The two blanks: 7 and 9 are the only digits the row is missing, and only this order suits the columns.

The Code

function isValid(board, row, col, value) {
  for (let i = 0; i < 9; i++) {
    if (board[row][i] === value) return false;
    if (board[i][col] === value) return false;
  }
  const boxRow = row - (row % 3);
  const boxCol = col - (col % 3);
  for (let r = 0; r < 3; r++) {
    for (let c = 0; c < 3; c++) {
      if (board[boxRow + r][boxCol + c] === value) return false;
    }
  }
  return true;
}
function solve(board) {
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] !== 0) continue;
      for (let value = 1; value <= 9; value++) {
        if (!isValid(board, row, col, value)) continue;
        board[row][col] = value;
        if (solve(board)) return true;
        board[row][col] = 0;
      }
      return false;
    }
  }
  return true;
}
function run() {
  const board = [
    [5, 3, 4, 6, 7, 8, 9, 1, 2],
    [6, 7, 2, 1, 9, 5, 3, 4, 8],
    [1, 9, 8, 3, 4, 2, 5, 6, 7],
    [8, 5, 9, 7, 6, 1, 4, 2, 3],
    [4, 2, 6, 8, 5, 3, 7, 9, 1],
    [7, 1, 3, 9, 2, 4, 8, 5, 6],
    [9, 6, 1, 5, 3, 7, 2, 8, 4],
    [2, 8, 7, 4, 1, 9, 6, 3, 5],
    [3, 4, 5, 2, 8, 6, 1, 0, 0]
  ];
  solve(board);
  return board[8];
}
run();
Done

The first 16 calls, of 440. This one does not fit on a page.

Step through run() call by call

More like this

All backtracking examples (10) →