Posts tagged sudoku

Yesterday I wrote a simple Sudoku solver. I’m thinking of using it to generate sudokus. I’ve run the program against a “very hard” puzzle at http://www.conceptispuzzles.com/index.aspx?uri=picture/1045 and it solves this in ~0.2 seconds on my Macbook. I think this is probably slow. Anyone else made a backtracking Sudoku solver that’s faster?

The brief idea behind a backtracking sudoku solver isn’t to use logic but rather “take a step” and set a square as a number and keep doing this until the puzzle is no longer valid (i.e. a certain square has no possible values). Then obviously the previous step was wrong and so it should be undone and another number should be chosen instead.

It’s essentially like how one would solve a maze. Walk in, make a choice about which way to go and keep doing that. If you get to a dead end, go back to the last choice you made and make the other choice, if that also leads to another dead end, then go back two choices, etc. until you finally get out of the maze.

As for how sudoku generation will work, it will take a valid grid, mix it up quite a bit, then start removing numbers. It’ll keep removing numbers until the puzzle is no longer solvable, then it’ll stop so that the minimum number of clues are there to solve the puzzle.