Skip to content
Tags

Simple Sudoku Solver

January 1, 2014

My first toy algorithm of 2014 was to build a Sudoku Solver (code below) using the brute force, recursive, depth-first search, deterministic, backtracking algorithm employed by many human players. This algorithm operates on N^2 x N^2 grids. So for a typical Sudoku board, N would equal 3.

The algorithm can simply be defined as follows:

  1. Given a row-major formatted puzzle, search for the 1st empty cell.
  2. If there are no empty cells, then simply return “true” as the puzzle is solved.
  3. For every possible value for that cell, check the 3 invariants:
    1. Check that value doesn’t already exist in the NxN grid
    2. Check that the value doesn’t already exist in the same row across the board
    3. Check that the value doesn’t already exist in the same column across the board
  4. If those invariants hold, then set the value for that empty cell to passing value, and recursively call this algorithm by going to Step 1.
  5. If the response is not “true”, then go to Step 3 while there are other possible untried values.

For typical Sudoku puzzles, the code below runs in sub-second time. For a slightly larger Sudoku (N=4) where numbers go from 1 to 16 takes approximately 10 seconds to process with this algorithm.

Advertisements

From → Algorithms, Java

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: