Nonogram in Gecode/R
I have now implemented a model for solving Nonograms in Gecode/R: nonogram.rb. See My Gecode/R page for more about Gecode/R).
Wikipedia explains Nonogram in this way (Nonogram
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.
A problem file may looks like this (see the file nonogram_heart.txt). First are the rules for the rows, then the rules for the columns.
row_rules
2,2
4,4
1,3,1
2,1,2
1,1
2,2
2,2
3
1
col_rules
3
2,3
2,2
2,2
2,2
2,2
2,2
2,3
3
The solution is a heart:
## ##
#### ####
# ### #
## # ##
# #
## ##
## ##
###
#
The program parses a nonogram problem file (or uses a default problem sans a problem file) and translates the rules to "regular expressions", e.g. the rule 3,2 is translated to the "regular expression" [repeat(0), repeat(1,3,3), at_least_once(0),repeat(1,2,2),repeat(0)] (i.e. the regexp /^0*1{3}0+1{3}0*$/), which means:
* start with 0 or more 0's
* then exactly 3 1's
* then 1 or more 0's
* then exactly 2 1's
* and last 0 or more 0's
For more about regular expressions in Gecode/R, see Integer Enum operands
The code
The translation is done via this method (debug printouts has been omitted):
def parse_regex(a, debug = false)
r = [repeat(0)]
a.each_with_index{|e,i|
r << repeat(1,e,e)
if i < a.length-1 then
r << at_least_once(0)
end
}
r << repeat(0)
return r
end
The constraint part is
def initialize(row_rules, col_rules)
rows = row_rules.length
cols = col_rules.length
x_is_an int_var_matrix(rows, cols, 0..1) # decision matrix
rows.times{|i| # rows
x.row(i).must.match(parse_regex(row_rules[i], debug))
}
cols.times{|j| # columns
x.column(j).must.match parse_regex(col_rules[j], debug)
}
branch_on x, :variable => :none, :value => :max
end
Files
Except for the P200 problem, all problem listed below was solved in about a second or two. For the P200 problem the solution is printed in about 3 seconds, then it takes nearly a minute to very that there are no other solution.
Most problems are from Gecode examples:
* nonogram.rb: The model
* nonogram_simple.txt: Very simple problem
* nonogram_bear.txt: Bear
* nonogram_crocodile.txt: Crocodile
* nonogram_difficult.txt: Difficult
* nonogram_dragonfly.txt: Dragonfly
* nonogram_heart.txt: Heart
* nonogram_house.txt: House
* nonogram_nonunique.txt: Non unique problem (43 solutions)
* nonogram_p200.txt: P200
* nonogram_pinwheel.txt: Pinwheel
* nonogram_soccer_player.txt: Soccer player
* nonogram_unknown.txt: "Unkwnown"
Also see my MiniZinc model nonogram.mzn, which is way more complicated and often much slower.