| Copyright | Copyright (C) 2021 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Problems.P98
Description
Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P98.
Documentation
Arguments
| :: [[Int]] | Lengths of occupied cells in each row |
| -> [[Int]] | Lengths of occupied cells in each column |
| -> Maybe [[Bool]] | Solution to the puzzle, if it exists |
Nonograms are picture logic puzzles invented in 1987, spreading from Japan to across the world. They look like this:
□ □ □ □ □ □ □ □ 3 □ □ □ □ □ □ □ □ 2 1 □ □ □ □ □ □ □ □ 3 2 □ □ □ □ □ □ □ □ 2 2 □ □ □ □ □ □ □ □ 6 □ □ □ □ □ □ □ □ 1 5 □ □ □ □ □ □ □ □ 6 □ □ □ □ □ □ □ □ 1 □ □ □ □ □ □ □ □ 2 1 3 1 7 5 3 4 3 2 1 5 1
Essentially, each row and column of a rectangular bitmap is annotated with the respective lengths of its distinct strings of occupied cells. The person who solves the puzzle must complete the bitmap given only these lengths. Published puzzles are larger than this example, e.g., \(25 \times 20\), and apparently always have unique solutions.
Try to solve the \(25 \times 25\) puzzle in nonogramPuzzle.
Examples
>>>:{printNonogramSolution $ nonogram [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] :} ■ ■ ■ 3 ■ ■ ■ 2 1 ■ ■ ■ ■ ■ 3 2 ■ ■ ■ ■ 2 2 ■ ■ ■ ■ ■ ■ 6 ■ ■ ■ ■ ■ ■ 1 5 ■ ■ ■ ■ ■ ■ 6 ■ 1 ■ ■ 2 1 3 1 7 5 3 4 3 2 1 5 1
Hint
If there is a string of occupied cells with length 9 in a row of 10 cells, can we infer which cells in the row must be occupied?
printNonogramPuzzle :: [[Int]] -> [[Int]] -> IO () Source #
Print out a nonogram puzzle.
>>>:{printNonogramPuzzle [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] :} □ □ □ □ □ □ □ □ 3 □ □ □ □ □ □ □ □ 2 1 □ □ □ □ □ □ □ □ 3 2 □ □ □ □ □ □ □ □ 2 2 □ □ □ □ □ □ □ □ 6 □ □ □ □ □ □ □ □ 1 5 □ □ □ □ □ □ □ □ 6 □ □ □ □ □ □ □ □ 1 □ □ □ □ □ □ □ □ 2 1 3 1 7 5 3 4 3 2 1 5 1
printNonogramSolution :: Maybe [[Bool]] -> IO () Source #
Print out a nonogram solution.
>>>:{printNonogramSolution $ nonogram [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] :} ■ ■ ■ 3 ■ ■ ■ 2 1 ■ ■ ■ ■ ■ 3 2 ■ ■ ■ ■ 2 2 ■ ■ ■ ■ ■ ■ 6 ■ ■ ■ ■ ■ ■ 1 5 ■ ■ ■ ■ ■ ■ 6 ■ 1 ■ ■ 2 1 3 1 7 5 3 4 3 2 1 5 1
nonogramPuzzle :: ([[Int]], [[Int]]) Source #
A nonogram puzzle of size \(25 \times 25\).
>>>printNonogramSolution $ let (rs, cs) = nonogramPuzzle in nonogram rs cs...