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:

  1. Determine all possible candidates for each empty element in the grid to form a hypothesis set.
  2. Analyse all hypothesis sets and assign values to the empty cells whose hypothesis set cardinality is 1.
  3. 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s