| Copyright | Copyright (C) 2023 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Solutions.P97
Description
Some solutions to Problems.P97 of Ninety-Nine Haskell Problems.
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:
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.
- Repeat pruning until there are no more possibilities to be pruned. If all positions have definite values, we have found a solution.
- 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.