Implementing a Sudoku solver (open-ended)

Motivation

This is an example of an exercise with some more complex behavior, lots of external data sources for example games, some simple visualizations and actions, potential for a GUI, with immutable puzzle states and history.

Our goal is to have an explainable Sudoku solver that can load sudokus from standard formats, allow us to solve a puzzle ourselves, or use set strategies to solve the game, and explain to the user how strategies are applied to solve it. It should be possible to go back and forth in the history, just as is done in the Ludo Game.

Caveat The tasks below will just get you started. The next steps to start solving puzzles and exploring the history are up to you!

Sudoku Resources

Sudopedia

Sudoku diagrams and notations

Sudoku file formats

Solving techniques

Andrew Stuart's Sudoku Solver

Sudoku puzzle collections (SDM)

Sudoku Master collection in SDM format

Tasks

Wrap the data

Here's an easy sudoku expressed as SDM.

Wrap the raw data as a Sudoku instance.

Decide on a suitable data structure for accessing the rows, columns and blocks.

Create some initial views

Create a columnedList view showing the sudoku state as a grid.

Create a SudokuExamples class with some simple examples and tests for accessing the puzzle state.

Export simple sudoku format

Write code to “pretty-print” a puzzle state as a user-friendly Simple Sudoku string.

Turn it into a view.

Tracking candidates

Most strategies require you to compute the candidates for each cell, by eliminating those that are excluded by the other values in the same row, column or block as that cell.

Decide on a data structure for tracking candidates (keep itsimple — you can change it later), and prototype an algorithm to compute the candidates using the Contextual Playground of a Sudoku instance.

Produce a simple textual view of the candidate grid.

Check invariants

Now that you have the candidates, investigate how to check invariants, for example, each cell is either solved, or has more than one candidate. A cell cannot have zero candidates.

Next steps

Now you have a simple representation of a sudoku, so next you should explore how to apply the simplest strategies to solve the puzzle.