# Nonogram (Paint by Numbers)

## Problem

Nonograms or Paint by Numbers are picture logic puzzles in which cells in a grid have to be colored or left blank according to numbers given at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers measure how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of “4 8 3” would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups. - Wikipedia

## Code

1 require 'rubygems'
2 require 'gecoder'
3 require 'enumerator'
4
5 #
6 # Nonogram (a.k.a. Painting by Numbers) in Gecode/R
7 #
8 # http://en.wikipedia.org/wiki/Nonogram
9 # """
10 # Nonograms or Paint by Numbers are picture logic puzzles in which cells
11 # in a grid have to be colored or left blank according to numbers given
12 # at the side of the grid to reveal a hidden picture. In this puzzle
13 # type, the numbers measure how many unbroken lines of filled-in squares
14 # there are in any given row or column. For example, a clue of "4 8 3"
15 # would mean there are sets of four, eight, and three filled squares, in
16 # that order, with at least one blank square between successive groups.
17 # """
18 #
19 # Also see
20 #   * Brunetti, Sara & Daurat, Alain (2003)
21 #     "An algorithm reconstructing convex lattice sets"
22 #     http://geodisi.u-strasbg.fr/~daurat/papiers/tomoqconv.pdf
23 #
24 #   * CSPLib problem 12 at http://www.csplib.org/
25 #
26 #   * http://www.puzzlemuseum.com/nonogram.htm
27 #
28 #   * Haskell solution:
29 #     http://twan.home.fmf.nl/blog/haskell/Nonograms.details
30 #
31 #   * My MiniZinc model http://www.hakank.org/minizinc/nonogram.mzn
32 #
33 #
34 # Model created by Hakan Kjellerstrand, hakank@bonetmail.com
35 # See also my Gecode/R page: http://www.hakank.org/gecode_r
36 #
37 # Slight modifications made by Andreas Launila to keep the example in
38 # line with the other example models.
39 class Nonogram
40   include Gecode::Mixin
41
42   def initialize(row_rules, col_rules)
43     # A matrix of variables where each variable represents whether the
44     # square has been filled in or not.
45     filled_is_an bool_var_matrix(row_rules.size, col_rules.size)
46
47     # Place the constraints on the rows.
48     row_rules.each_with_index do |row_rule, i|
49       filled.row(i).must.match parse_regex(row_rule)
50     end
51     # Place the constraints on the columns.
52     col_rules.each_with_index do |col_rule, i|
53       filled.column(i).must.match parse_regex(col_rule)
54     end
55
56     branch_on filled, :variable => :none, :value => :max
57   end
58
59   # Parses a nonogram segment and converts it to a "regexp"
60   # e.g. [3,2] -> [repeat(false), repeat(true,3,3), at_least_once(false),
61   #                repeat(true,2,2),repeat(false)]
62   def parse_regex(a)
63     r = [repeat(false)]
64     a.each_with_index do |e,i|
65       r << repeat(true,e,e)
66       if i < a.length-1 then
67         r << at_least_once(false)
68       end
69     end
70     r << repeat(false)
71     return r
72   end
73 end
74
75 # A nonogram problem taken from Wikipedia
76 # http://en.wikipedia.org/wiki/Nonogram
77 # Animation:
78 # http://en.wikipedia.org/wiki/File:Paint_by_numbers_Animation.gif
79 #
80 row_rules =
81 [
82   [3],
83   [5],
84   [3,1],
85   [2,1],
86   [3,3,4],
87   [2,2,7],
88   [6,1,1],
89   [4,2,2],
90   [1,1],
91   [3,1],
92   [6],
93   [2,7],
94   [6,3,1],
95   [1,2,2,1,1],
96   [4,1,1,3],
97   [4,2,2],
98   [3,3,1],
99   [3,3],
100   [3],
101   [2,1]
102 ]
103
104 col_rules =
105  [
106   [2],
107   [1,2],
108   [2,3],
109   [2,3],
110   [3,1,1],
111   [2,1,1],
112   [1,1,1,2,2],
113   [1,1,3,1,3],
114   [2,6,4],
115   [3,3,9,1],
116   [5,3,2],
117   [3,1,2,2],
118   [2,1,7],
119   [3,3,2],
120   [2,4],
121   [2,1,2],
122   [2,2,1],
123   [2,2],
124   [1],
125   [1]
126 ]
127
128 nonogram = Nonogram.new(row_rules, col_rules)
129 # Find all of the solutions.
130 num_solutions = 0
131 nonogram.each_solution do |s|
132   num_solutions += 1
133   puts "\nSolution ##{num_solutions}\n"
134   # Output the solution.
135   s.filled.values.enum_slice(s.filled.column_size).each do |row|
136     puts row.map{ |filled| filled ? "#" : " " }.join
137   end
138 end
139
140 puts "\nNumber of solutions: #{num_solutions}"

## Output

Solution #1
###
#####
### #
##  #
### ### ####
##  ##   #######
###### #   #
####   ##  ##
#   #
###  #
######
##   #######
######  ### #
# ##  ## #  #
####  # #  ###
#### ## ##
###  ### #
###    ###
###
## #

Number of solutions: 1