62 lines
2.7 KiB
Plaintext
62 lines
2.7 KiB
Plaintext
A [[wp:Nonogram|nonogram]] is a puzzle that provides
|
|
numeric clues used to fill in a grid of cells,
|
|
establishing for each cell whether it is filled or not.
|
|
The puzzle solution is typically a picture of some kind.
|
|
|
|
Each row and column of a rectangular grid is annotated with the lengths
|
|
of its distinct runs of occupied cells.
|
|
Using only these lengths you should find one valid configuration
|
|
of empty and occupied cells, or show a failure message.
|
|
|
|
;Example
|
|
<pre>Problem: Solution:
|
|
|
|
. . . . . . . . 3 . # # # . . . . 3
|
|
. . . . . . . . 2 1 # # . # . . . . 2 1
|
|
. . . . . . . . 3 2 . # # # . . # # 3 2
|
|
. . . . . . . . 2 2 . . # # . . # # 2 2
|
|
. . . . . . . . 6 . . # # # # # # 6
|
|
. . . . . . . . 1 5 # . # # # # # . 1 5
|
|
. . . . . . . . 6 # # # # # # . . 6
|
|
. . . . . . . . 1 . . . . # . . . 1
|
|
. . . . . . . . 2 . . . # # . . . 2
|
|
1 3 1 7 5 3 4 3 1 3 1 7 5 3 4 3
|
|
2 1 5 1 2 1 5 1</pre>
|
|
The problem above could be represented by two lists of lists:
|
|
<pre>x = [[3], [2,1], [3,2], [2,2], [6], [1,5], [6], [1], [2]]
|
|
y = [[1,2], [3,1], [1,5], [7,1], [5], [3], [4], [3]]</pre>
|
|
A more compact representation of the same problem uses strings,
|
|
where the letters represent the numbers, A=1, B=2, etc:
|
|
<pre>x = "C BA CB BB F AE F A B"
|
|
y = "AB CA AE GA E C D C"</pre>
|
|
|
|
;Task
|
|
For this task, try to solve the 4 problems below, read from a “<tt>nonogram_problems.txt</tt>” file that has this content
|
|
(the blank lines are separators):
|
|
<pre>C BA CB BB F AE F A B
|
|
AB CA AE GA E C D C
|
|
|
|
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
|
|
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
|
|
|
|
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
|
|
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
|
|
|
|
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
|
|
E CB BAB AAA AAA AC BB ACC ACCA AGB AIA AJ AJ ACE AH BAF CAG DAG FAH FJ GJ ADK ABK BL CM</pre>
|
|
|
|
'''Extra credit''': generate nonograms with unique solutions, of desired height and width.
|
|
<br><br>
|
|
This task is the problem n.98 of the "[https://sites.google.com/site/prologsite/prolog-problems 99 Prolog Problems]" [https://web.archive.org/web/20230406102539/https://sites.google.com/site/prologsite/prolog-problems (archived)] by Werner Hett (also thanks to Paul Singleton for the idea and the examples).
|
|
<br><br>
|
|
; Related tasks
|
|
* [[Nonoblock]].
|
|
<br>
|
|
;See also
|
|
* [[wp:AC-3_algorithm|Arc Consistency Algorithm]]
|
|
* http://www.haskell.org/haskellwiki/99_questions/Solutions/98 (Haskell)
|
|
* http://twanvl.nl/blog/haskell/Nonograms (Haskell)
|
|
* http://picolisp.com/5000/!wiki?99p98 (PicoLisp)
|
|
<br><br>
|
|
|