GitHub: https://github.com/PatrickBuhagiar/Sudoku-Solver

Given an initial Sudoku puzzle S0, we explore the state-space until we reach an end state Sn representing the solved puzzle. With the singleton technique, transitions between states will occur by looking up cells which only have one single candidate value.

The class *Sudoku* will represent the puzzle as a list of rows each containing a list of integers. Unknown cells are represented by the number 0.

class Sudoku(val grid: List[List[Int]]) {
def row (row: Int): Set[Int] = ...
def column(column: Int): Set[Int] = ...
def block(block: Int): Set[Int] = ...
}

The row, column and block functions take an index as a parameter and return the content of the row, column or block respectively.

Next, the *Solver *works in the following way:

- Determine all possible candidates for each empty element in the grid to form a hypothesis set.
- Analyse all hypothesis sets and assign values to the empty cells whose hypothesis set cardinality is 1.
- Check if complete.

Additional notes:

- The
*hypothesis()* function returns all possible candidates for a given element in the grid.
- The
*allHypothesis()* function returns a list of tuples, were each tuple contain the row, column and hypothesis set relevant to that particular row and column.
- The
*step()* function analyses all hypothesis sets and filter those with cardinality 1.
- The
*complete()* function determines whether the puzzle has been solved.

### Like this:

Like Loading...

*Related*

## Published by Patrick Buhagiar

Software Engineer
View all posts by Patrick Buhagiar