Solutions.P97

Description

Some solutions to Problems.P97 of Ninety-Nine Haskell Problems.

Synopsis

# Documentation

sudoku :: [[Int]] -> Maybe [[Int]] Source #

Returns a solution for a given Sudoku puzzle.

Both will be expressed as a list of 9 rows. Each row will be a list of 9 numbers from 0 to 9, where 0 signifies a blank spot.

randomSudoku :: RandomGen g => [[Int]] -> g -> (Maybe [[Int]], g) Source #

Solves Sudoku puzzles.

Uses the given source of randomness when choosing among multiple possibilities. This underlies the sudoku function, which uses a fixed source of randomness.

The overall approach is thus:

1. Prune possible values for blank spots so that values which are not possible are pruned. This is determined by what numbers have been definitely determined for other positions in the same row, column, and square.

• Some blank spots may end up with a single possible value. In this case, it has become a position with a definite value.
2. Repeat pruning until there are no more possibilities to be pruned. If all positions have definite values, we have found a solution.
3. If we can't prune enough possibilities to get a solution, pick a random position. For each of its possible values, pretend it is definite, i.e., part of the solution, and repeat the pruning from step 1.