More than a year ago I’ve read very interesting article in Lamneth blog about MySQL Sudoku solver. I’ve searched for some time, but information was very minimal and I couldn’t find a way to contact original author. So I decided to try it myself and easily found working solution.
Beauty of solving Sudoku puzzle in MySQL is that you don’t need any server-side code (almost) at all. Only thing you need to do is to form a query and then pass it to MySQL server. Tasks list for 9×9 Sudoku puzzle would like this:
- Table will all possible combinations (362880, 9*8*7*6*5*4*3*2*1)
- Query to:
- join combinations table 9 times
- set already known cell values
- get results
It may seem not very clear, but it’s very trivial method. Positions table holds all possible combinations, so you select 9 rows from this table, where each cell is unique in row and column and some predefined cells equal to given values. Basically, you tell MySQL Sudoku rules and MySQL does all work for you.
I’ve published sample query and positions table data online here: positions, query. Example will solve puzzle given in original Lamneth post (here) and it shouldn’t take too long – in my laptop it takes about 0.7 s. I haven’t tried any optimizations, but I strongly believe that solving process can be optimized dramatically (especially for hard puzzles).
This method works pretty good – almost all puzzles are solved around 1 s., and only hard ones takes a while. Compared to real solvers it’s very slow, but since it’s only a simple query – results look very good.
MySQL is not made for games, but for fun you can make some nice applications (solving Sudoku with MySQL will not help you to get a better job). How much faster you can make this query run?
tzach
emendez
