Recursive Sudoku solver

I got back to coding after a long absence cause mainly by the final exams. My first project was to implement a recursive Sudoku solver.

I had previously written an iterative Sudoku solver that makes use of the same techniques that people do by ruling out what numbers can fit in a cell untill there is only one possible number that can fir. However, this method fails on harder puzzles where a guess has to be made in order to solve the puzzle.

Brute force algorithms enter here. The Sudoku puzzle lends itself well to the classic recursive brute force algorithm,

The step by step algorithm:

  1. If puzzle is solved
    1. End
  2. If puzzle is not valid
    1. End
  3. Find first empty cell : cell that contains 0
  4. While the cell value is less than 10 and while the puzzle is unsolved
    1. Increment cell by 1
    2. Solve
  5. If the cell value is greater than 9
    1. Reset the cell value to 0 : This means that a previous guess was invalid so this ends and the previous cell value is incremented
Advertisements
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: