Solving Sudoku, the Geek way
You probably know Sudoku - the nifty little number puzzle that has taken over most of the world. What I don't like, is having paper versions without knowing if I'm right or wrong. Hence, I made a bot to solve Sudoku grids.
The code is available on GitHub , under the Apache License. It is pretty simple - you basically have a static HTML file that defines a 9x9 grid, with 3x3 boxes. The code aims to be flexible to other square dimensions, but I really haven't tried it yet.
The basic workflow : you load the page, and either fill in clues by hand, or click Generate for a grid to be generated for you (currently it serves a static grid, will be expanded at some point). After you have your clues in, click "Solve" to have the grid crunched for you. This actually works suprisingly well! Both buttons trigger an AJAX request, with JSON response ( AJAJ? )
How it works
The code iterates over each blank cell. For each cell, it maintains an array of possible solutions ( initialized to 1..SIZE ( 1-9 in the 9x9 grid case )), It then Applies 3 basic rules, to eliminate values from that array :
- Values that appear on the same row
- Values that appear on the same column
- Values that appear on the same box
Additionally, it has one "smart" rule - checking adjoined boxes. That is, assuming that we are considering a cell in the top center box: check if the possible value appears on the other two boxes of the same row. If so, we know the row of the value. Then check if the number appears on the other two boxes of the same column. If the value again appears on both, we know the column of the value!
Each time there is only one possible value, it is placed onto the grid. The whole process is repeated until one of two outcomes:
- No blank cells left ( ie we successfully solved the grid, huzza! )
- The blank count has not decreased over two runs ( ie we're stuck and cannot find any more cells )
Once completed, the results are returned to the browser, and populated on the grid.
Obviously more work is required, but it's a pretty good start!
Future expansions :
- Properly generate random grids, and optionally cache them
- Allow "hinting", ie solve the grid, and only send back the solution for the selected cell
- Better theming
- Make a proper game out of it