SUDOKU Solver

For a long time I had resisted getting into the global SUDOKU craze. When I finally tried solving my first, the approach seemed very mechanical and systematic to me. Anything mechanical and systematic meant writing my own simple brute-force solver.

The approach for the solver is basically that which is described here. The entire solution is built using javascript. The interface itself has been built with javascript, making it look a bit different from the usual text-box based options.

Click here for the SUDOKU Solver. You should see it pop-out as a new window, sized appropriately. Try disabling any pop-up blockers if you cannot see the window pop-up. Don't worry, this site has no ads.

Basics: The javascript solver has two main array that store the data required for the solution:

  • A two-dimensional array [the board] storing the actual board with the initial clues. The value of the 2-D array is the clue or the answer for the grid.
  • A three-dimensional array [pencil marks] that stores a 0 or a 1 for each value on every grid location (x,y). Initially, the array is initialized to 1, meaning that every value is potentially possible for every location on the grid. Through the process described below, possibilities are eliminated to eventually identify the final answer for each grid.

Clearing pencil marks: For each clue given, or each new answer identified pencil marks are updated by:

  • Clearing all the pencil marks in the row. For example, if the clue in grid 3,3 is 5, then the marks for 5 are cleared across the entire row 3, and
  • Clearing all the pencil marks in the column. For example, if we identify an answer of 6 in the grid 5,6 then the marks for 6 are cleared across column 6, and
  • Clearing all pencil marks in the sector. For example, if we identify a location for 1 in the first sector, then the pencil marks for all 1s in the first sector are cleared.

This is done once for all the clues provided and repeated for each and every solution identified.

Searching for solutions: There are only three kinds of solutions that can be identified.

  • Only one possible location for a number in a row, or
  • Only one possible location for a number in a column, or
  • Only one possible location for a number in a sector.

A solution is identified when one of the three conditions is satisfied. As soon as such a solution is found, it is marked on the board, then the corresponding pencil marks are cleared as described above

That's it. Repeat these checks with a little bit of loop management, and you will have the solution pretty quickly. A 'difficult' problem was solved in just three iterations of the solving loop.