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
  • Enter your email address to follow this blog and receive notifications of new posts by email.

    Join 8 other followers

  • Tweets

    Error: Twitter did not respond. Please wait a few minutes and refresh this page.

  • Recent Posts

  • Archives

  • Blog Stats

    • 3,551 People liked what they saw on this page
  • Advertisements