sudoku

Project image

CLI that solves a Sudoku puzzle

About the project:

Given a Sudoku board, sudoku can produce the solved output, if it exists.

This project only exists as a CLI, but I hope to eventually rewrite it in Swift and use ARKit to allow the program to use pictures of Sudoku boards as input. This way, all you have to do is take a picture of the board, rather than entering in all of those pesky numbers! Future plans also include returning specific cells of the solved board, so if you only want a hint on how to solve a Sudoku board it won't give you the whole solution 😉


Technology used:

Java

View on GitHub

Demo

sudoku solves a standard Sudoku puzzle.

Given the following input:

* * * | 5 * 6 | * * *  
* * 4 | * * * | 8 * *
* 9 * | 1 * 2 | * * *
---------------------
9 * 8 | * * * | 3 * 2
* * * | * 9 * | * * *
1 * 2 | * * * | 4 * 7
---------------------
* 2 * | 3 * 4 | * 8 *
* * 7 | * * * | 9 * *
* * * | 9 * 5 | * * *

sudoku produces the following output:

2 8 1 | 5 4 6 | 7 3 9 
6 5 4 | 7 3 9 | 8 2 1
7 9 3 | 1 8 2 | 5 6 4
---------------------
9 7 8 | 4 6 1 | 3 5 2
4 3 5 | 2 9 7 | 6 1 8
1 6 2 | 8 5 3 | 4 9 7
---------------------
5 2 9 | 3 7 4 | 1 8 6
3 1 7 | 6 2 8 | 9 4 5
8 4 6 | 9 1 5 | 2 7 3

Usage is very simple:

$ java Solver.java input.txt output.txt

A lesson in Dynamic Programming

sudoku uses dynamic programming to solve each puzzle. The basic algorithm is quite simple. We construct a tree via recursive calls:

  1. Place a number [1,9] in a random open cell.

  2. If the move creates a valid board, continue doing so (create a node and move to its child). If it does not, take a note (memo), undo the move from step 1 (move up to the node's parent), and try another random move.

  3. Continue until the board is solved, or until no more moves are available, in which case the game is unsolvable.

The key here is the memoization, which keeps us from trying every single impossible board. Effectively, we are building a tree of possible boards, and only traversing branches that produce possible winning states. In theory, each tree node could have 72 children, but clever prunning keeps us from having to produce such an expensive tree.