Solve a Hidato puzzle: Difference between revisions

Content added Content deleted

Inline

Revision as of 12:29, 12 January 2012

The task is to write a program which solves the puzzles found daily here:

   http://www.smithsonianmag.com/games/hidato.html

An extra point will be awarded for showing that the code can be reused to solve the Knight Tour, see http://rosettacode.org/wiki/Knight%27s_tour

Mathprog

<lang> /*Hidato.mathprog, part of KuKu by Nigel Galloway

 Find a solution to a Hidato problem

 Nigel_Galloway
 April 1st., 2011

/

param ZBLS; param ROWS; param COLS; param D := 1; set ROWSR := 1..ROWS; set COLSR := 1..COLS; set ROWSV := (1-D)..(ROWS+D); set COLSV := (1-D)..(COLS+D); param Iz{ROWSR,COLSR}, integer, default 0; set ZBLSV := 1..(ZBLS+1); set ZBLSR := 1..ZBLS;

var BR{ROWSV,COLSV,ZBLSV}, binary;

void0{r in ROWSV, z in ZBLSR,c in (1-D)..0}: BR[r,c,z] = 0; void1{r in ROWSV, z in ZBLSR,c in (COLS+1)..(COLS+D)}: BR[r,c,z] = 0; void2{c in COLSV, z in ZBLSR,r in (1-D)..0}: BR[r,c,z] = 0; void3{c in COLSV, z in ZBLSR,r in (ROWS+1)..(ROWS+D)}: BR[r,c,z] = 0; void4{r in ROWSV,c in (1-D)..0}: BR[r,c,ZBLS+1] = 1; void5{r in ROWSV,c in (COLS+1)..(COLS+D)}: BR[r,c,ZBLS+1] = 1; void6{c in COLSV,r in (1-D)..0}: BR[r,c,ZBLS+1] = 1; void7{c in COLSV,r in (ROWS+1)..(ROWS+D)}: BR[r,c,ZBLS+1] = 1;

Izfree{r in ROWSR, c in COLSR, z in ZBLSR : Iz[r,c] = -1}: BR[r,c,z] = 0; Iz1{Izr in ROWSR, Izc in COLSR, r in ROWSR, c in COLSR, z in ZBLSR : Izr=r and Izc=c and Iz[Izr,Izc]=z}: BR[r,c,z] = 1;

rule1{z in ZBLSR}: sum{r in ROWSR, c in COLSR} BR[r,c,z] = 1; rule2{r in ROWSR, c in COLSR}: sum{z in ZBLSV} BR[r,c,z] = 1; rule3{r in ROWSR, c in COLSR, z in ZBLSR}: BR[0,0,z+1] + BR[r-1,c-1,z+1] + BR[r-1,c,z+1] + BR[r-1,c+1,z+1] + BR[r,c-1,z+1] + BR[r,c+1,z+1] + BR[r+1,c-1,z+1] + BR[r+1,c,z+1] + BR[r+1,c+1,z+1] - BR[r,c,z] >= 0;

solve;

for {r in ROWSR} {

   for {c in COLSR} {
       printf " %2d", sum{z in ZBLSR} BR[r,c,z]*z;
   }
   printf "\n";

} data;

param ROWS := 7; param COLS := 7; param ZBLS := 49; param Iz: 1 2 3 4 5 6 7 :=

1  .   .   6   .  23   .   . 
2  .  40   .   .   9   .   . 
3  .  39   .   .   .   .  21 
4  1  38   .   .  12   .  19 
5 36   .  30   .   .  18   . 
6  .  32   .   .  14   .  16 
7  .  33   .   .   .  48  49 
;

end;

</lang>

Produces:

<lang> GLPSOL: GLPK LP/MIP Solver, v4.47 Parameter(s) specified in the command line:

--math H20110503.mprog

Reading model section from H20110503.mathprog... Reading data section from H20110503.mathprog... 64 lines were read Generating void0... Generating void1... Generating void2... Generating void3... Generating void4... Generating void5... Generating void6... Generating void7... Generating Izfree... Generating Iz1... Generating rule1... Generating rule2... Generating rule3... Model has been successfully generated GLPK Integer Optimizer, v4.47 4318 rows, 4050 columns, 30631 non-zeros 4050 integer variables, all of which are binary Preprocessing... 38 hidden packing inequaliti(es) were detected 220 rows, 223 columns, 1099 non-zeros 223 integer variables, all of which are binary Scaling...

A: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000

Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 220 Solving LP relaxation... GLPK Simplex Optimizer, v4.47 220 rows, 223 columns, 1099 non-zeros

     0: obj =  0.000000000e+000  infeas = 3.100e+001 (0)

167: obj = 0.000000000e+000 infeas = 9.430e-015 (0)

OPTIMAL SOLUTION FOUND Integer optimization begins... + 167: mip = not found yet >= -inf (1; 0) + 181: >>>>> 0.000000000e+000 >= 0.000000000e+000 0.0% (1; 0) + 181: mip = 0.000000000e+000 >= tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 5.9 Mb (6168823 bytes)

 4  5  6  8 23 24 25
 3 40  7 10  9 22 26
 2 39 41 11 28 27 21
 1 38 42 29 12 20 19
36 37 30 43 13 18 17
35 32 31 44 14 15 16
34 33 45 46 47 48 49

Model has been successfully processed

</lang>