Nonogram (Paint by Numbers)

  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}"