Sudoku solving
Posted in computers on November 11th, 2011 by karrthOne of our projects for my into to artificial intelligence class this semester was to create a sudoku solver using a MRV (minimum remaining values) heuristic and backtracking. It finds all possibilities for each square, then tries all possibilities for one of the squares with the lowest number of possible values. Here’s an example of it’s use (X6800 cpu):
$ time ./sudoku.pl puzzle.hard.txt
- - 8 7 4 - - - -
- 2 - - - 5 - - 4
- - 3 - - 2 1 - -
0 - - - - 1 2 - -
- 5 - 0 - - 4 - -
7 - - - - - - 0 1
- - - 8 1 - - - 0
- - - - - 0 5 - -
- - - 2 - - - 6 8
Solving...
Solved!
5 1 8 7 4 3 0 2 6
6 2 7 1 0 5 8 3 4
4 0 3 6 8 2 1 7 5
0 8 6 4 7 1 2 5 3
3 5 1 0 2 6 4 8 7
7 4 2 5 3 8 6 0 1
2 6 5 8 1 7 3 4 0
8 7 4 3 6 0 5 1 2
1 3 0 2 5 4 7 6 8
real 0m0.170s
user 0m0.167s
sys 0m0.000s
While it is not the most efficient, it will solve any hard-level sudoku puzzle of any size. It takes the puzzle file as an argument, or it will prompt you for the file path if you don’t include it. It will take puzzles with values that range from 0-9 and A-Z after that.
I’ve included in the tarball 2 harder puzzles that my program does not solve in anything close reasonable time (as in… it didn’t solve either one after running for 24 hours) if you’d like to try and improve the code yourself :). There are many ways you could improve the program, as talked about here (not my school/class). This is the website for the book we use in class – I’d highly recommend it for anybody interested in AI programming. Enjoy!