Sudoku

 I solve a lot of sudoku puzzles. Typically when I'm at work and I need to clear my head. They're semi-enjoyable busy work, sufficiently engaging to consume my entire attention but sufficiently formulaic to not require any innovative thinking. But my interest goes in cycles. After a few weeks or months it will become routine. Instead of going to the NYTimes Sudoku page when I need a distraction, I'll start going there out of habit and I'll very quickly grow bored and frustrated with the process. So this time around I decided a better way to clear my head might be to write a sudoku solver.

I've never read any guides for how to solve sudokus faster or better. I only have a few rules I've learned on my own. The first and most straight-forward of which is the very definition of a sudoku, that each row, column, and block of nine squares contains the numbers one through nine exactly one time each. So using that, I wrote a little program that can solve most easy puzzles using some very basic rules.

Rule 1: If the value of a cell is known, then that value is not a possibility for any neighbor.

"Neighbor" is any other cell in one of the same groups. "Group" is a row, column, or block containing nine cells.

Rule 2: If only one possibility exists for a cell, then the cell must be that value.

Rule 3: If only one cell in a group has a possibility for the a particular value, then that cell must be that value.

Rule 4: If all of the cells in Group_A that potentially have Value_x exist in the region of Group_A where Group_A overlaps with Group_B, then Value_x can be cleared as a possibility from the region of Group_B that does not overlap with Group_A.

Those are all the rules I've figured out and I've never found a puzzle that I couldn't solve with those. Rules 1, 2, and 3 are very easy to implement and those are more than sufficient to solve most easy puzzles. So I start out with a blank board of 81 cells, each cell containing a numeral value (initially blank) and a list of possibilities (initially full). If a cell is empty, the user types in a 0 for that cell. If the value is known, the user types in the known value, the known value is stored, and Rule 1 is applied. After the starting board is fully entered, I cycle through the entire board, applying Rule 2. Three rounds of this is usually enough to solve an easy puzzle.

This won't solve harder puzzles, so eventually I'll add in Rules 2 and 3. 99% of the time involved in solving a puzzle is manually transposing 81 numerals in and then out of the solver. Maybe after I complete the solver I'll start working on something fancy like an interface to copy and paste conditions and results into a webpage.

https://gitlab.com/tllado/sudoku_solver

Comments