How the Sudoku Puzzle Solver Works

There are literally hundreds of puzzle solvers on the web. The methods for completing this task are numerous. Some use JavaScript, VB, C++ and many more. Some of the puzzle solvers use only logic and others use brute force to test every single combination.

On this site the solver works by performing the following steps: First it checks each blank square individually. It knows that each square can only contain the numbers 1 to 9. It checks the column and row of the square and reduces the number of possibilities. It reduces the possibilities further by checking what numbers are in the same 3x3 box. If at the end of this there is only one possibility left then the value of that square has been found. This step is repeated for each square, then repeated again as more squares are filled in. The solver also uses backtracking to handle puzzles that cannot be solved by pure logic alone.

I started this project after a suggestion by my 'Old Man' and also my Sudoku crazed family who complete at least 3 or 4 puzzles a day. I originally started with the 6x6 Sudoku to try and understand the best ways of developing the puzzle. Much inspiration came from other websites that I visited where people stated tactics and techniques for solving puzzles.

Below I have included some code snippets of the algorithm used to make the Puzzle Solver:

// Grid is a flat array of 81 cells (0 = empty, 1-9 = filled)
function solve(grid) {
  const empty = grid.indexOf(0);
  if (empty === -1) return grid; // solved

  const row = Math.floor(empty / 9);
  const col = empty % 9;
  const used = new Set();

  for (let i = 0; i < 9; i++) {
    used.add(grid[row * 9 + i]);    // same row
    used.add(grid[i * 9 + col]);    // same col
  }
  // same 3x3 box
  const br = Math.floor(row / 3) * 3;
  const bc = Math.floor(col / 3) * 3;
  for (let r = br; r < br + 3; r++)
    for (let c = bc; c < bc + 3; c++)
      used.add(grid[r * 9 + c]);

  for (let n = 1; n <= 9; n++) {
    if (!used.has(n)) {
      const next = grid.slice();
      next[empty] = n;
      const result = solve(next);
      if (result) return result;
    }
  }
  return null; // backtrack
}

---

4 Comments

Where do I fine hints as to how to do the puzzle. \nI start by looking for pairs but what is next?
Comment 1 by bob. Made on the 2 August 2005.

Congratulations for your superb site. \nI would like to know how many different arrangements of sudokus 9x9 could be constructed. -Is it possible to calculate this mathematically ?
Comment 2 by Leonardo Bitran. Made on the 12 December 2005.

Just thought you might like to know that with a 9 X 9 grid there are 6,670,903,752,021,072,936,960 arrangements. \n \nCould take a while to see them all I think?!! :) \n \nBest wishes & Merry Christmas everyone. \n \nMark \n \n
Comment 3 by Mark Bowen. Made on the 22 December 2005.

exuse me. \ncan you send me on my mail box, a script php and html of solver 9*9 ? \n \nbecease it's dificul for me to creat it whith your php page web
Comment 4 by xorban. Made on the 23 January 2006.