This weeks news
This is mostly a consolidation (with some additional information) of the tweets on twitter.com/hakankj since last time.
The parameters to the program are now:
Where the {tr:from:to:} means translate digit
This is now probably better written with
Also, see below for some more examples.
The fixed versions is here:
* MiniZinc: nonogram_create_automaton2.mzn
* Comet: nonogram_regular.co
It was quite tricky to debug the generated automata, but I found a fix for it surprisingly soon. I won't publish the fixes here, but it suffice to say that the MiniZinc model is - shall we say - not more beautiful than before.
A test instance for this: T2 (source unknown)
* Comet: nonogram_t2.co. * MiniZinc: nonogram_t2.dzn
T2 has the following two solutions:
* Comet: nonogram_gondola.co
* MiniZinc: nonogram_gondola.dzn.
For the curious, here is the solution, using the following command (see above for the mzn_show.pl part):
I have updated the model with his suggestion that uses
This problem is from the swedish book Paul Vaderlind: Vaderlinds nya hjärngympa ('Vaderlind's new brain gymnastics'), page 63ff. Unfortunately, I don't know the origin of this problem.
The objective is to create a matrix where all values on each row/column is different, except for the blanks.
A set of hints is given: the (or some) first seen non blank of each
- upper row
- lower row
- left column
- right column
seen from that view.
Example:
Here is yet another opportunity to use mzn_show.pl (0 is here translated to blank, etc):
With the following output:
mzn_show.pl
The Perl program mzn_show.pl is used for making little better output from the FlatZinc solvers.The parameters to the program are now:
-
{tr:from:to:}: translate digit to another digit/character
-
{trvar:var:from:to:}: translate digit to another digit/character for a specific variablevar
-
{trtr:from_string:replacement_string:}: translates all digits infrom_stringto the corresponding digit/character inreplacement_string(inspired from the Unix tr command)
-
{trtrvar:var:from_string:replacement_string:}: astrtrbut for a specific variablevar -
{nospaces}: don't show space after character
-
{noprintf}: don't try to be clever with printf stuff
flatzinc nonogram_create_automaton2.fzn | mzn_show.pl "{tr:1: :} {tr:2:#:} {nospace}"
Where the {tr:from:to:} means translate digit
from to character to, and {nospace} means that no spaces are shown after each digit/character.
This is now probably better written with
trtr:
flatzinc nonogram_create_automaton2.fzn | mzn_show.pl "{trtr:12: #:} {nospace}"
Also, see below for some more examples.
MiniZinc/Comet: Nonogram model fixed for "zero length" clues
I discovered that my MiniZinc and Comet models had a little bug in the generation of the automaton for "zero length" clues (i.e. the row/column is completely empty, just 0's).The fixed versions is here:
* MiniZinc: nonogram_create_automaton2.mzn
* Comet: nonogram_regular.co
It was quite tricky to debug the generated automata, but I found a fix for it surprisingly soon. I won't publish the fixes here, but it suffice to say that the MiniZinc model is - shall we say - not more beautiful than before.
A test instance for this: T2 (source unknown)
* Comet: nonogram_t2.co. * MiniZinc: nonogram_t2.dzn
T2 has the following two solutions:
## ## ### # # # # # # # # # # # # ### # # # # # ## ## # ---------- ## ## ### # # # # # # # # # # # # ### # # # # # ## ## #
One more Nonogram example
Besides the T2 problem instance mentioned above, there is a new Nonogram example: Gondola for both Comet and MiniZinc:* Comet: nonogram_gondola.co
* MiniZinc: nonogram_gondola.dzn.
For the curious, here is the solution, using the following command (see above for the mzn_show.pl part):
$ mzn2fzn -G jacop --data nonogram_gondola.dzn nonogram_create_automaton2.mzn
$ java JaCoP.fz.Fz2jacop -a -s nonogram_create_automaton2.fzn | mzn_show.pl "{trtr:12: #:} {nospaces}"
##### ######
###### # # #
### ########### ###
###### # # # # #
####### # # # ## # ###
#### # # ## # ####
####### # # # ## ### #
####### # # ### # #
#### # # # # #########
#### ######## # #
#### # #### # ###
#### # ####### # #####
#### # # ## # #### # #
#### ######### ## # ##
#### # ### # ## #
#### # ###### # # #
#### ######## ### #
########## ### ##### ###
#### # ## ### ##### ##
### ##### ## ########
## ###### ### # #
# ############ #
#################### # #
## #########################
## ### ####################
## ##### ### ## ## ## ## #
# ## ######################
####################
### ##################
# ##
Updated Comet's SONET model
In About 20 more constraint programming models in Comet Pierre Schaus (on of Comet's developers) commented that my use oftryall outside the using block in the SONET problem (sonet_problem.co) was not to recommend.
I have updated the model with his suggestion that uses
or instead:
m.post(or(ring in 1..r) (rings[ring,client1] + rings[ring, client2] >= 2));Thanks for the correction (suggestion), Pierre.
New MiniZinc model: Letter Square problem
letter_square.mzn is (yet another) grid problem. From my comment in the model file:This problem is from the swedish book Paul Vaderlind: Vaderlinds nya hjärngympa ('Vaderlind's new brain gymnastics'), page 63ff. Unfortunately, I don't know the origin of this problem.
The objective is to create a matrix where all values on each row/column is different, except for the blanks.
A set of hints is given: the (or some) first seen non blank of each
- upper row
- lower row
- left column
- right column
seen from that view.
Example:
B B
-------
|A B C|
B| B C A|
B|B C A |
|C A B|
--------
C
This model codes the hints as follows:
blank -> 0 A -> 1 B -> 2 C -> 3 row_upper = [0,2,2,0]; row_lower = [3,0,0,0]; col_left = [0,2,0,0]; col_right = [0,0,0,0];Note: there are no hints for the right column.
Here is yet another opportunity to use mzn_show.pl (0 is here translated to blank, etc):
solver model.fzn | mzn_show.pl "{trtr:0123456: ABCDEF:}"
With the following output:
A B C
A B C
B C A
A C B
C B A
The following problem instances from the book has been created:
- letter_square1.dzn: from the introduction
- letter_square59.dzn: #59, 5x5
- letter_square60.dzn: #60, 5x5
- letter_square89.dzn: #89, 8x8, the last problem (except for a Sudoku combo variant that I have not implemented)