Solve a Hidato puzzle
You are encouraged to solve this task according to the task description, using any language you may know.
The task is to write a program which solves Hidato puzzles.
The rules are:
- You are given a grid with some numbers placed in it. The other squares in the grid will be blank.
- The grid is not necessarily rectangular.
- The grid may have holes in it.
- The grid is always connected.
- The number “1” is always present, as is another number that is equal to the number of squares in the grid. Other numbers are present so as to force the solution to be unique.
- It may be assumed that the difference between numbers present on the grid is not greater than lucky 13.
- The aim is to place a natural number in each blank square so that in the sequence of numbered squares from “1” upwards, each square is in the wp:Moore neighborhood of the squares immediately before and after it in the sequence (except for the first and last squares, of course, which only have one-sided constraints).
- Thus, if the grid was overlaid on a chessboard, a king would be able to make legal moves along the path from first to last square in numerical order.
- A square may only contain one number.
- In a proper Hidato puzzle, the solution is unique.
For example the following problem
has the following solution, with path marked on it:
C
Depth-first graph, with simple connectivity check to reject some impossible situations early. The checks slow down simpler puzzles significantly, but can make some deep recursions backtrack much earilier. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <ctype.h>
int *board, *flood, *known, top = 0, w, h;
inline int idx(int y, int x) { return y * w + x; }
int neighbors(int c, int *p) { int i, j, n = 0; int y = c / w, x = c % w;
for (i = y - 1; i <= y + 1; i++) { if (i < 0 || i >= h) continue; for (j = x - 1; j <= x + 1; j++) if (!(j < 0 || j >= w || (j == x && i == y) || board[ p[n] = idx(i,j) ] == -1)) n++; }
return n; }
void flood_fill(int c) { int i, n[8], nei;
nei = neighbors(c, n); for (i = 0; i < nei; i++) { if (board[n[i]] || flood[n[i]]) continue;
flood[n[i]] = 1; flood_fill(n[i]); } }
/* Check all empty cells are reachable from higher known cells.
Should really do more checks to make sure cell_x and cell_x+1 share enough reachable empty cells; I'm lazy. Will implement if a good counter example is presented. */
int check_connectity(int lowerbound) { int c; memset(flood, 0, sizeof(flood[0]) * w * h); for (c = lowerbound + 1; c <= top; c++) if (known[c]) flood_fill(known[c]);
for (c = 0; c < w * h; c++) if (!board[c] && !flood[c]) return 0;
return 1; }
void make_board(int x, int y, char *s) { int i;
w = x, h = y; x = w * h;
known = calloc(sizeof(int*), x + 1); board = calloc(sizeof(int), x); flood = calloc(sizeof(int), x);
while (x--) board[x] = -1;
for (y = 0; y < h; y++) for (x = 0; x < w; x++) { i = idx(y, x);
while (isspace(*s)) s++;
switch (*s) { case '_': board[i] = 0; case '.': break; default: known[ board[i] = strtol(s, 0, 10) ] = i; if (board[i] > top) top = board[i]; }
while (*s && !isspace(*s)) s++; } }
void show_board(char *s) { int i, j, c;
printf("\n%s:\n", s);
for (i = 0; i < h; i++, putchar('\n')) for (j = 0; j < w; j++) { c = board[ idx(i, j) ]; printf(!c ? " __" : c == -1 ? " " : " %2d", c); } }
int fill(int c, int n) { int i, nei, p[8], ko, bo;
if ((board[c] && board[c] != n) || (known[n] && known[n] != c)) return 0;
if (n == top) return 1;
ko = known[n]; bo = board[c]; board[c] = n;
if (check_connectity(n)) { nei = neighbors(c, p); for (i = 0; i < nei; i++) if (fill(p[i], n + 1)) return 1; }
board[c] = bo; known[n] = ko; return 0; }
int main() { make_board(
- define USE_E 0
- if (USE_E == 0)
8,8, " __ 33 35 __ __ .. .. .." " __ __ 24 22 __ .. .. .." " __ __ __ 21 __ __ .. .." " __ 26 __ 13 40 11 .. .." " 27 __ __ __ 9 __ 1 .." " . . __ __ 18 __ __ .." " . .. . . __ 7 __ __" " . .. .. .. . . 5 __"
- elif (USE_E == 1)
3, 3, " . 4 ." " _ 7 _" " 1 _ _"
- else
50, 3, " 1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74" " . . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ ." " . . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."
- endif
);
show_board("Before"); fill(known[1], 1); show_board("After"); /* "40 lbs in two weeks!" */
return 0; }</lang>
- Output:
Before: __ 33 35 __ __ __ __ 24 22 __ __ __ __ 21 __ __ __ 26 __ 13 40 11 27 __ __ __ 9 __ 1 __ __ 18 __ __ __ 7 __ __ 5 __ After: 32 33 35 36 37 31 34 24 22 38 30 25 23 21 12 39 29 26 20 13 40 11 27 28 14 19 9 10 1 15 16 18 8 2 17 7 6 3 5 4
D
More C-Style Version
This version retains some of the characteristics of the original C version. It uses global variables, it doesn't enforce immutability and purity. This style is faster to write for prototypes, short programs or less important code, but in larger programs you usually want more strictness to avoid some bugs and increase long-term maintainability.
<lang d>import std.stdio, std.array, std.conv, std.algorithm;
int[][] board; int[] given, start;
void setup(string s) {
auto lines = s.split("\n"); auto cols = lines[0].split().length; auto rows = lines.length; given.length = 0;
board = new int[][](rows + 2, cols + 2); foreach (i; 0 .. rows + 2) board[i][] = -1;
foreach (r, row; lines) { foreach (c, cell; row.split()) { switch (cell) { case "__" : board[r + 1][c + 1] = 0; break; case "." : break; default : int val = to!int(cell); board[r + 1][c + 1] = val; given ~= val; if (val == 1) start = [r + 1, c + 1]; } } } given.sort();
}
bool solve(int r, int c, int n, int next = 0) {
if (n > given[$-1]) return true;
if (board[r][c] && board[r][c] != n) return false;
if (board[r][c] == 0 && given[next] == n) return false;
int back = board[r][c];
board[r][c] = n; foreach (i; -1 .. 2) foreach (j; -1 .. 2) if (solve(r + i, c + j, n + 1, next + (back == n))) return true;
board[r][c] = back; return false;
}
void printBoard() {
foreach (r; 0 .. board.length) { foreach (c; board[r]) writef(c == -1 ? " " : !c ? "__ " : "%2d ", c); write('\n'); }
}
void main() {
auto hi = "__ 33 35 __ __ . . . __ __ 24 22 __ . . . __ __ __ 21 __ __ . . __ 26 __ 13 40 11 . . 27 __ __ __ 9 __ 1 . . . __ __ 18 __ __ . . . . . __ 7 __ __ . . . . . . 5 __";
setup(hi); printBoard(); solve(start[0], start[1], 1); printBoard();
}</lang>
- Output:
__ 33 35 __ __ __ __ 24 22 __ __ __ __ 21 __ __ __ 26 __ 13 40 11 27 __ __ __ 9 __ 1 __ __ 18 __ __ __ 7 __ __ 5 __ 32 33 35 36 37 31 34 24 22 38 30 25 23 21 12 39 29 26 20 13 40 11 27 28 14 19 9 10 1 15 16 18 8 2 17 7 6 3 5 4
Stronger Version
This version uses a little stronger typing, performs tests a run-time with contracts, it doesn't use global variables, it enforces immutability and purity where possible, and produces a correct text output for both larger ad small boards. This style is more fit for larger programs, or when you want the code to be less bug-prone or a little more efficient. <lang d>import std.stdio, std.string, std.conv, std.array, std.algorithm,
std.exception;
struct Hidato {
alias int Cell; enum : Cell { emptyCell = -2, unknownCell = -1 }
alias int[2][Cell] KnownT; immutable KnownT known; immutable Cell boardMax; Cell[][] board;
this(in string input) /*pure*/ nothrow in { assert(!input.empty); } out { immutable nRows = board.length; immutable nCols = board[0].length; assert(boardMax > 0 && boardMax <= nRows * nCols); assert(known.length >= 2 && known.length <= nRows * nCols); assert(1 in known && boardMax in known);
foreach (row; board) foreach (cell; row) assert(cell == Hidato.emptyCell || cell == Hidato.unknownCell || (cell >= 1 && cell <= nRows * nCols));
foreach (n, rc; known) { assert(n > 0 && n <= boardMax); assert(rc[0] >= 0 && rc[0] < nRows); assert(rc[1] >= 0 && rc[1] < nCols); } } body { bool[Cell] pathSeen; // a set KnownT knownMutable; const lines = input.splitLines(); immutable nCols = lines[0].split().length; foreach (int r, row; lines) { assert(row.split().length == nCols, text("Wrong cols n.: ", row.split().length)); auto boardRow = new typeof(board[0])(nCols); foreach (int c, cell; row.split()) { switch (cell) { case ".": boardRow[c] = Hidato.emptyCell; break; case "_": boardRow[c] = Hidato.unknownCell; break; default: // known immutable val = to!Cell(cell); enforce(val > 0, "Path numbers must be > 0."); enforce(val !in pathSeen, text("Duplicated path number: ", val)); pathSeen[val] = true; boardRow[c] = val; knownMutable[val] = [r, c]; boardMax = max(boardMax, val); } } board ~= boardRow; }
known = assumeUnique(knownMutable); // Not verified }
bool solve() pure nothrow in { assert(1 in known); } body { /*static*/ bool fill(in int r, in int c, in Cell n) pure nothrow { if (n > boardMax) return true;
if (c < 0 || c >= board[0].length || r < 0 || r >= board.length) return false;
if ((board[r][c] != Hidato.unknownCell && board[r][c] != n) || (n in known && known[n] != [r, c])) return false;
board[r][c] = n; foreach (i; -1 .. 2) foreach (j; -1 .. 2) if (fill(r + i, c + j, n + 1)) return true;
board[r][c] = Hidato.unknownCell; return false; }
return fill(known[1][0], known[1][1], 1); }
string toString() const { immutable d = [Hidato.emptyCell: ".", Hidato.unknownCell: "_"]; immutable form = "%" ~ text(text(boardMax).length + 1) ~ "s";
string result; foreach (row; board) { foreach (c; row) result ~= xformat(form, d.get(c, text(c))); result ~= "\n"; } return result; }
}
void solveHidato(in string problem) {
auto hi = Hidato(problem); writeln("Problem:\n", hi); hi.solve(); writeln("Solution:\n", hi); writeln();
}
void main() {
solveHidato(" _ 33 35 _ _ . . . _ _ 24 22 _ . . . _ _ _ 21 _ _ . . _ 26 _ 13 40 11 . . 27 _ _ _ 9 _ 1 . . . _ _ 18 _ _ . . . . . _ 7 _ _ . . . . . . 5 _");
solveHidato(". 4 . _ 7 _ 1 _ _");
solveHidato(
"1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74
. . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . . . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."
); }</lang>
- Output:
Problem: _ 33 35 _ _ . . . _ _ 24 22 _ . . . _ _ _ 21 _ _ . . _ 26 _ 13 40 11 . . 27 _ _ _ 9 _ 1 . . . _ _ 18 _ _ . . . . . _ 7 _ _ . . . . . . 5 _ Solution: 32 33 35 36 37 . . . 31 34 24 22 38 . . . 30 25 23 21 12 39 . . 29 26 20 13 40 11 . . 27 28 14 19 9 10 1 . . . 15 16 18 8 2 . . . . . 17 7 6 3 . . . . . . 5 4 Problem: . 4 . _ 7 _ 1 _ _ Solution: . 4 . 3 7 5 1 2 6 Problem: 1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74 . . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . . . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . Solution: 1 2 3 . . 8 9 . . 14 15 . . 20 21 . . 26 27 . . 32 33 . . 38 39 . . 44 45 . . 50 51 . . 56 57 . . 62 63 . . 68 69 . . 74 . . 4 . 7 . 10 . 13 . 16 . 19 . 22 . 25 . 28 . 31 . 34 . 37 . 40 . 43 . 46 . 49 . 52 . 55 . 58 . 61 . 64 . 67 . 70 . 73 . . . . 5 6 . . 11 12 . . 17 18 . . 23 24 . . 29 30 . . 35 36 . . 41 42 . . 47 48 . . 53 54 . . 59 60 . . 65 66 . . 71 72 .
Mathprog
<lang mathprog>/*Hidato.mathprog, part of KuKu by Nigel Galloway
Find a solution to a Hidato problem
Nigel_Galloway@operamail.com 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 := 8; param COLS := 8; param ZBLS := 40; param Iz: 1 2 3 4 5 6 7 8 :=
1 . 33 35 . . -1 -1 -1 2 . . 24 22 . -1 -1 -1 3 . . . 21 . . -1 -1 4 . 26 . 13 40 11 -1 -1 5 27 . . . 9 . 1 -1 6 -1 -1 . . 18 . . -1 7 -1 -1 -1 -1 . 7 . . 8 -1 -1 -1 -1 -1 -1 5 . ; end;</lang>
Using the data in the model produces the following:
- Output:
>glpsol --minisat --math Hidato.mathprog GLPSOL: GLPK LP/MIP Solver, v4.47 Parameter(s) specified in the command line: --minisat --math Hidato.mathprog Reading model section from Hidato.mathprog... Reading data section from Hidato.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 Will search for ANY feasible solution Translating to CNF-SAT... Original problem has 5279 rows, 4100 columns, and 33359 non-zeros 2520 covering inequalities 2719 partitioning equalities Solving CNF-SAT problem... Instance has 7076 variables, 24047 clauses, and 77735 literals ==================================[MINISAT]=================================== | Conflicts | ORIGINAL | LEARNT | Progress | | | Clauses Literals | Limit Clauses Literals Lit/Cl | | ============================================================================== | 0 | 21432 75120 | 7144 0 0 0.0 | 0.000 % | ============================================================================== SATISFIABLE Objective value = 0.000000000e+000 Time used: 0.0 secs Memory used: 14.5 Mb (15192264 bytes) 32 33 35 36 37 0 0 0 31 34 24 22 38 0 0 0 30 25 23 21 12 39 0 0 29 26 20 13 40 11 0 0 27 28 14 19 9 10 1 0 0 0 15 16 18 8 2 0 0 0 0 0 17 7 6 3 0 0 0 0 0 0 5 4 Model has been successfully processed
Modelling Evil Case 1:
data; param ROWS := 3; param COLS := 3; param ZBLS := 7; param Iz: 1 2 3 := 1 -1 4 -1 2 . 7 . 3 1 . . ; end;
Produces:
>glpsol --minisat --math Hidato.mathprog --data Evil1.data GLPSOL: GLPK LP/MIP Solver, v4.47 Parameter(s) specified in the command line: --minisat --math Hidato.mathprog --data Evil1.data Reading model section from Hidato.mathprog... Hidato.mathprog:47: warning: data section ignored 47 lines were read Reading data section from Evil1.data... 11 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 Will search for ANY feasible solution Translating to CNF-SAT... Original problem has 256 rows, 200 columns, and 935 non-zeros 56 covering inequalities 193 partitioning equalities Solving CNF-SAT problem... Instance has 337 variables, 1237 clauses, and 4094 literals ==================================[MINISAT]=================================== | Conflicts | ORIGINAL | LEARNT | Progress | | | Clauses Literals | Limit Clauses Literals Lit/Cl | | ============================================================================== | 0 | 1060 3917 | 353 0 0 0.0 | 0.000 % | ============================================================================== SATISFIABLE Objective value = 0.000000000e+000 Time used: 0.0 secs Memory used: 0.8 Mb (861188 bytes) 0 4 0 3 7 5 1 2 6 Model has been successfully processed
Modelling Evil Case 2 - The Snake in the Grass:
data; param ROWS := 3; param COLS := 50; param ZBLS := 74; param Iz: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 := 1 1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 74 2 -1 -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 . -1 3 -1 -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 -1 . . -1 ; end;
Produces:
G:\IAJAAR4.47>glpsol --minisat --math Hidato.mathprog --data Evil2.data GLPSOL: GLPK LP/MIP Solver, v4.47 Parameter(s) specified in the command line: --minisat --math Hidato.mathprog --data Evil2.data Reading model section from Hidato.mathprog... Hidato.mathprog:47: warning: data section ignored 47 lines were read Reading data section from Evil2.data... Evil2.data:11: warning: final NL missing before end of file 11 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 Will search for ANY feasible solution Translating to CNF-SAT... Original problem has 25500 rows, 19500 columns, and 147452 non-zeros 11026 covering inequalities 14400 partitioning equalities Solving CNF-SAT problem... Instance has 31338 variables, 98310 clauses, and 305726 literals ==================================[MINISAT]=================================== | Conflicts | ORIGINAL | LEARNT | Progress | | | Clauses Literals | Limit Clauses Literals Lit/Cl | | ============================================================================== | 0 | 84134 291550 | 28044 0 0 0.0 | 0.000 % | | 101 | 31135 126809 | 30848 98 5496 56.1 | 65.521 % | | 251 | 31135 126809 | 33933 244 12470 51.1 | 66.552 % | | 476 | 27353 115512 | 37327 446 23819 53.4 | 68.160 % | | 814 | 26574 113330 | 41059 770 42161 54.8 | 69.586 % | | 1321 | 25432 110534 | 45165 1262 83658 66.3 | 70.056 % | ============================================================================== SATISFIABLE Objective value = 0.000000000e+000 Time used: 1.0 secs Memory used: 60.9 Mb (63862624 bytes) 1 2 3 0 0 8 9 0 0 14 15 0 0 20 21 0 0 26 27 0 0 32 33 0 0 38 39 0 0 44 45 0 0 50 51 0 0 56 57 0 0 62 63 0 0 68 69 0 0 74 0 0 4 0 7 0 10 0 13 0 16 0 19 0 22 0 25 0 28 0 31 0 34 0 37 0 40 0 43 0 46 0 49 0 52 0 55 0 58 0 61 0 64 0 67 0 70 0 73 0 0 0 0 5 6 0 0 11 12 0 0 17 18 0 0 23 24 0 0 29 30 0 0 35 36 0 0 41 42 0 0 47 48 0 0 53 54 0 0 59 60 0 0 65 66 0 0 71 72 0 Model has been successfully processed
Modelling Evil Case 3 - A fatter snake in the Grass:
data; param ROWS := 4; param COLS := 46; param ZBLS := 82; param Iz: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 := 1 1 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 82 2 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 3 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 4 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 -1 ; end;
Produces:
>glpsol --minisat --math Hidato.mathprog --data Evil3.data GLPSOL: GLPK LP/MIP Solver, v4.47 Parameter(s) specified in the command line: --minisat --math Hidato.mathprog --data Evil3.data Reading model section from Hidato.mathprog... Hidato.mathprog:47: warning: data section ignored 47 lines were read Reading data section from Evil3.data... 12 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 Will search for ANY feasible solution Translating to CNF-SAT... Original problem has 32684 rows, 23904 columns, and 198488 non-zeros 15006 covering inequalities 17596 partitioning equalities Solving CNF-SAT problem... Instance has 39792 variables, 130040 clauses, and 407222 literals ==================================[MINISAT]=================================== | Conflicts | ORIGINAL | LEARNT | Progress | | | Clauses Literals | Limit Clauses Literals Lit/Cl | | ============================================================================== | 0 | 112710 389892 | 37570 0 0 0.0 | 0.000 % | ============================================================================== SATISFIABLE Objective value = 0.000000000e+000 Time used: 0.0 secs Memory used: 80.2 Mb (84067912 bytes) 1 2 0 0 0 10 11 0 0 0 19 20 0 0 0 28 29 0 0 0 37 38 0 0 0 46 47 0 0 0 55 56 0 0 0 64 65 0 0 0 73 74 0 0 0 82 0 0 3 0 9 0 0 12 0 18 0 0 21 0 27 0 0 30 0 36 0 0 39 0 45 0 0 48 0 54 0 0 57 0 63 0 0 66 0 72 0 0 75 0 81 0 0 4 0 8 0 0 13 0 17 0 0 22 0 26 0 0 31 0 35 0 0 40 0 44 0 0 49 0 53 0 0 58 0 62 0 0 67 0 71 0 0 76 0 80 0 0 5 6 7 0 0 14 15 16 0 0 23 24 25 0 0 32 33 34 0 0 41 42 43 0 0 50 51 52 0 0 59 60 61 0 0 68 69 70 0 0 77 78 79 0 0 0 Model has been successfully processed
Perl
<lang perl>use strict; use List::Util 'max';
our (@grid, @known, $n);
sub show_board { for my $r (@grid) { print map(!defined($_) ? ' ' : $_ ? sprintf("%3d", $_) : ' __' , @$r), "\n" } }
sub parse_board { @grid = map{[map(/^_/ ? 0 : /^\./ ? undef: $_, split ' ')]} split "\n", shift(); for my $y (0 .. $#grid) { for my $x (0 .. $#{$grid[$y]}) { $grid[$y][$x] > 0 and $known[$grid[$y][$x]] = "$y,$x"; } } $n = max(map { max @$_ } @grid); }
sub neighbors { my ($y, $x) = @_; my @out; for ( [-1, -1], [-1, 0], [-1, 1], [ 0, -1], [ 0, 1], [ 1, -1], [ 1, 0], [ 1, 1]) { my $y1 = $y + $_->[0]; my $x1 = $x + $_->[1]; next if $x1 < 0 || $y1 < 0; next unless defined $grid[$y1][$x1]; push @out, "$y1,$x1"; } @out }
sub try_fill { my ($v, $coord) = @_; return 1 if $v > $n;
my ($y, $x) = split ',', $coord; my $old = $grid[$y][$x];
return if $old && $old != $v; return if exists $known[$v] and $known[$v] ne $coord;
$grid[$y][$x] = $v; print "\033[0H"; show_board();
try_fill($v + 1, $_) && return 1 for neighbors($y, $x);
$grid[$y][$x] = $old; return }
parse_board
- ". 4 .
- _ 7 _
- 1 _ _";
- " 1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74
- . . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _
- . . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _
- ";
"__ 33 35 __ __ .. .. .. . __ __ 24 22 __ .. .. .. . __ __ __ 21 __ __ .. .. . __ 26 __ 13 40 11 .. .. . 27 __ __ __ 9 __ 1 .. . . . __ __ 18 __ __ .. . . .. . . __ 7 __ __ . . .. .. .. . . 5 __ .";
print "\033[2J";
try_fill(1, $known[1]);</lang>
- Output:
32 33 35 36 37 31 34 24 22 38 30 25 23 21 12 39 29 26 20 13 40 11 27 28 14 19 9 10 1 15 16 18 8 2 17 7 6 3 5 4
Prolog
Works with SWI-Prolog and library(clpfd) written by Markus Triska.
Puzzle solved is from the Wilkipedia page : http://en.wikipedia.org/wiki/Hidato
<lang Prolog>:- use_module(library(clpfd)).
hidato :- init1(Li), % skip first blank line init2(1, 1, 10, Li), my_write(Li).
init1(Li) :-
Li = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, A, 33, 35, B, C, 0, 0, 0, 0,
0, D, E, 24, 22, F, 0, 0, 0, 0,
0, G, H, I, 21, J, K, 0, 0, 0,
0, L, 26, M, 13, 40, 11, 0, 0, 0,
0, 27, N, O, P, 9, Q, 1, 0, 0,
0, 0, 0, R, S, 18, T, U, 0, 0,
0, 0, 0, 0, 0, V, 7, W, X, 0,
0, 0, 0, 0, 0, 0, 0, 5, Y, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
LV = [ A, 33, 35, B, C, D, E, 24, 22, F, G, H, I, 21, J, K, L, 26, M, 13, 40, 11, 27, N, O, P, 9, Q, 1, R, S, 18, T, U, V, 7, W, X, 5, Y],
LV ins 1..40,
all_distinct(LV).
% give the constraints % Stop before the last line init2(_N, Col, Max_Col, _L) :- Col is Max_Col - 1.
% skip zeros init2(N, Lig, Col, L) :- I is N + Lig * Col, element(I, L, 0), !, V is N+1, ( V > Col -> N1 = 1, Lig1 is Lig + 1; N1 = V, Lig1 = Lig), init2(N1, Lig1, Col, L).
% skip first column
init2(1, Lig, Col, L) :-
!,
init2(2, Lig, Col, L) .
% skip last column init2(Col, Lig, Col, L) :- !, Lig1 is Lig+1, init2(1, Lig1, Col, L).
% V5 V3 V6 % V1 V V2 % V7 V4 V8 % general case init2(N, Lig, Col, L) :- I is N + Lig * Col, element(I, L, V),
I1 is I - 1, I2 is I + 1, I3 is I - Col, I4 is I + Col, I5 is I3 - 1, I6 is I3 + 1, I7 is I4 - 1, I8 is I4 + 1,
maplist(compute_BI(L, V), [I1,I2,I3,I4,I5,I6,I7,I8], VI, BI),
sum(BI, #=, SBI),
( ((V #= 1 #\/ V #= 40) #/\ SBI #= 1) #\/ (V #\= 1 #/\ V #\= 40 #/\ SBI #= 2)) #<==> 1,
labeling([ffc, enum], [V | VI]),
N1 is N+1, init2(N1, Lig, Col, L).
compute_BI(L, V, I, VI, BI) :- element(I, L, VI), VI #= 0 #==> BI #= 0, ( VI #\= 0 #/\ (V - VI #= 1 #\/ VI - V #= 1)) #<==> BI.
% display the result my_write([0, A, B, C, D, E, F, G, H, 0 | T]) :- maplist(my_write_1, [A, B, C, D, E, F, G, H]), nl, my_write(T).
my_write([]).
my_write_1(0) :- write(' ').
my_write_1(X) :- writef('%3r', [X]).</lang>
- Output:
?- hidato. 32 33 35 36 37 31 34 24 22 38 30 25 23 21 12 39 29 26 20 13 40 11 27 28 14 19 9 10 1 15 16 18 8 2 17 7 6 3 5 4 true
Python
<lang python>board = [] given = [] start = None
def setup(s):
global board, given, start lines = s.splitlines() ncols = len(lines[0].split()) nrows = len(lines) board = [[-1] * (ncols + 2) for _ in xrange(nrows + 2)]
for r, row in enumerate(lines): for c, cell in enumerate(row.split()): if cell == "__" : board[r + 1][c + 1] = 0 continue elif cell == ".": continue # -1 else: val = int(cell) board[r + 1][c + 1] = val given.append(val) if val == 1: start = (r + 1, c + 1) given.sort()
def solve(r, c, n, next=0):
if n > given[-1]: return True if board[r][c] and board[r][c] != n: return False if board[r][c] == 0 and given[next] == n: return False
back = 0 if board[r][c] == n: next += 1 back = n
board[r][c] = n for i in xrange(-1, 2): for j in xrange(-1, 2): if solve(r + i, c + j, n + 1, next): return True board[r][c] = back return False
def print_board():
d = {-1: " ", 0: "__"} bmax = max(max(r) for r in board) form = "%" + str(len(str(bmax)) + 1) + "s" for r in board[1:-1]: print "".join(form % d.get(c, str(c)) for c in r[1:-1])
hi = """\ __ 33 35 __ __ . . . __ __ 24 22 __ . . . __ __ __ 21 __ __ . . __ 26 __ 13 40 11 . . 27 __ __ __ 9 __ 1 .
. . __ __ 18 __ __ . . . . . __ 7 __ __ . . . . . . 5 __"""
setup(hi) print_board() solve(start[0], start[1], 1) print print_board()</lang>
- Output:
__ 33 35 __ __ __ __ 24 22 __ __ __ __ 21 __ __ __ 26 __ 13 40 11 27 __ __ __ 9 __ 1 __ __ 18 __ __ __ 7 __ __ 5 __ 32 33 35 36 37 31 34 24 22 38 30 25 23 21 12 39 29 26 20 13 40 11 27 28 14 19 9 10 1 15 16 18 8 2 17 7 6 3 5 4
Ruby
Without Warnsdorff
The followin class provides functionallity for solving a hidato problem: <lang ruby>
- Solve a Hidato Puzzle
- Nigel_Galloway
- May 5th., 2012.
class Cell
def initialize(row=0, col=0, value=nil) @adj = [[row-1,col-1],[row,col-1],[row+1,col-1],[row-1,col],[row+1,col],[row-1,col+1],[row,col+1],[row+1,col+1]] @t = false $zbl[value] = false unless value == nil @value = value end def try(value) return false if @value == nil return true if value > E return false if @t return false if @value > 0 and @value != value return false if @value == 0 and not $zbl[value] @t = true @adj.each{|x| if (Board[x[0]][x[1]].try(value+1)) then @value = value return true end } @t = false return false end def value return @value end
end </lang> Which may be used as follows to solve Evil Case 1: <lang ruby> Rows = 3 Cols = 3 E = 7 $zbl = Array.new(E+1,true) Board = [[Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()],
[Cell.new(),Cell.new() ,Cell.new(1,2,4) ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new(2,1,0) ,Cell.new(2,2,7) ,Cell.new(2,3,0) ,Cell.new()], [Cell.new(),Cell.new(3,1,1) ,Cell.new(3,2,0) ,Cell.new(3,3,0) ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()]]
require 'benchmark' puts Benchmark.measure {Board[3][1].try(1)} (1..Rows).each{|r|
(1..Cols).each{|c| printf("%2s",Board[r][c].value)} puts ""}
</lang> Which produces:
>ruby Program.rb 0.000000 0.000000 0.000000 ( 0.000000) 4 3 7 5 1 2 6
Which may be used as follows to solve this tasks example: <lang ruby> Rows = 8 Cols = 8 E = 40 $zbl = Array.new(E+1,true) Board = [[Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()],
[Cell.new(),Cell.new(1,1,0) ,Cell.new(1,2,33) ,Cell.new(1,3,35) ,Cell.new(1,4,0) ,Cell.new(1,5,0) ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new(2,1,0) ,Cell.new(2,2,0) ,Cell.new(2,3,24) ,Cell.new(2,4,22) ,Cell.new(2,5,0) ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new(3,1,0) ,Cell.new(3,2,0) ,Cell.new(3,3,0) ,Cell.new(3,4,21) ,Cell.new(3,5,0) ,Cell.new(3,6,0) ,Cell.new() ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new(4,1,0) ,Cell.new(4,2,26) ,Cell.new(4,3,0) ,Cell.new(4,4,13) ,Cell.new(4,5,40) ,Cell.new(4,6,11) ,Cell.new() ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new(5,1,27) ,Cell.new(5,2,0) ,Cell.new(5,3,0) ,Cell.new(5,4,0) ,Cell.new(5,5,9) ,Cell.new(5,6,0) ,Cell.new(5,7,1) ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new(6,3,0) ,Cell.new(6,4,0) ,Cell.new(6,5,18) ,Cell.new(6,6,0) ,Cell.new(6,7,0) ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(7,5,0) ,Cell.new(7,6,7) ,Cell.new(7,7,0) ,Cell.new(7,8,0) ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(8,7,5) ,Cell.new(8,8,0) ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()]]
require 'benchmark' puts Benchmark.measure {Board[5][7].try(1)} (1..Rows).each{|r|
(1..Cols).each{|c| printf("%3s",Board[r][c].value)} puts ""}
</lang>
>ruby Program.rb 0.000000 0.000000 0.000000 ( 0.000000) 32 33 35 36 37 31 34 24 22 38 30 25 23 21 12 39 29 26 20 13 40 11 27 28 14 19 9 10 1 15 16 18 8 2 17 7 6 3 5 4
Which may be used as follows to solve The Snake in the Grass: <lang ruby> Rows = 3 Cols = 50 E = 74 $zbl = Array.new(E+1,true) Board = [[Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()],
[Cell.new(),Cell.new(1,1,1) ,Cell.new(1,2,0) ,Cell.new(1,3,0) ,Cell.new() ,Cell.new() ,Cell.new(1,6,0) ,Cell.new(1,7,0) ,Cell.new() ,Cell.new() ,Cell.new(1,10,0) ,Cell.new(1,11,0) ,Cell.new() ,Cell.new() ,Cell.new(1,14,0) ,Cell.new(1,15,0) ,Cell.new() ,Cell.new() ,Cell.new(1,18,0) ,Cell.new(1,19,0) ,Cell.new() ,Cell.new() ,Cell.new(1,22,0) ,Cell.new(1,23,0) ,Cell.new() ,Cell.new() ,Cell.new(1,26,0) ,Cell.new(1,27,0) ,Cell.new() ,Cell.new() ,Cell.new(1,30,0) ,Cell.new(1,31,0) ,Cell.new() ,Cell.new() ,Cell.new(1,34,0) ,Cell.new(1,35,0) ,Cell.new() ,Cell.new() ,Cell.new(1,38,0) ,Cell.new(1,39,0) ,Cell.new() ,Cell.new() ,Cell.new(1,42,0) ,Cell.new(1,43,0) ,Cell.new() ,Cell.new() ,Cell.new(1,46,0) ,Cell.new(1,47,0) ,Cell.new() ,Cell.new() ,Cell.new(1,50,74),Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new(2,3,0) ,Cell.new() ,Cell.new(2,5,0) ,Cell.new() ,Cell.new(2,7,0) ,Cell.new() ,Cell.new(2,9,0) ,Cell.new() ,Cell.new(2,11,0) ,Cell.new() ,Cell.new(2,13,0) ,Cell.new() ,Cell.new(2,15,0) ,Cell.new() ,Cell.new(2,17,0) ,Cell.new() ,Cell.new(2,19,0) ,Cell.new() ,Cell.new(2,21,0) ,Cell.new() ,Cell.new(2,23,0) ,Cell.new() ,Cell.new(2,25,0) ,Cell.new() ,Cell.new(2,27,0) ,Cell.new() ,Cell.new(2,29,0) ,Cell.new() ,Cell.new(2,31,0) ,Cell.new() ,Cell.new(2,33,0) ,Cell.new() ,Cell.new(2,35,0) ,Cell.new() ,Cell.new(2,37,0) ,Cell.new() ,Cell.new(2,39,0) ,Cell.new() ,Cell.new(2,41,0) ,Cell.new() ,Cell.new(2,43,0) ,Cell.new() ,Cell.new(2,45,0) ,Cell.new() ,Cell.new(2,47,0) ,Cell.new() ,Cell.new(2,49,0) ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(3,4,0) ,Cell.new(3,5,0) ,Cell.new() ,Cell.new() ,Cell.new(3,8,0) ,Cell.new(3,9,0) ,Cell.new() ,Cell.new() ,Cell.new(3,12,0) ,Cell.new(3,13,0) ,Cell.new() ,Cell.new() ,Cell.new(3,16,0) ,Cell.new(3,17,0) ,Cell.new() ,Cell.new() ,Cell.new(3,20,0) ,Cell.new(3,21,0) ,Cell.new() ,Cell.new() ,Cell.new(3,24,0) ,Cell.new(3,25,0) ,Cell.new() ,Cell.new() ,Cell.new(3,28,0) ,Cell.new(3,29,0) ,Cell.new() ,Cell.new() ,Cell.new(3,32,0) ,Cell.new(3,33,0) ,Cell.new() ,Cell.new() ,Cell.new(3,36,0) ,Cell.new(3,37,0) ,Cell.new() ,Cell.new() ,Cell.new(3,40,0) ,Cell.new(3,41,0) ,Cell.new() ,Cell.new() ,Cell.new(3,44,0) ,Cell.new(3,45,0) ,Cell.new() ,Cell.new() ,Cell.new(3,48,0) ,Cell.new(3,49,0) ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()]]
require 'benchmark' puts Benchmark.measure {Board[1][1].try(1)} (1..Rows).each{|r|
(1..Cols).each{|c| printf("%3s",Board[r][c].value)} puts ""}
</lang> Which produces:
>ruby Program.rb 87.626000 0.000000 87.626000 ( 87.640800) 1 2 3 8 9 14 15 20 21 26 27 32 33 38 39 44 45 50 51 56 57 62 63 68 69 74 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 5 6 11 12 17 18 23 24 29 30 35 36 41 42 47 48 53 54 59 60 65 66 71 72
Note that if The Snake in the Grass is modified to look more like a genuine Hidato by shortening the path between hints: <lang ruby> Rows = 3 Cols = 50 E = 74 $zbl = Array.new(E+1,true) Board = [[Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()],
[Cell.new(),Cell.new(1,1,1) ,Cell.new(1,2,0) ,Cell.new(1,3,0) ,Cell.new() ,Cell.new() ,Cell.new(1,6,0) ,Cell.new(1,7,0) ,Cell.new() ,Cell.new() ,Cell.new(1,10,0) ,Cell.new(1,11,0) ,Cell.new() ,Cell.new() ,Cell.new(1,14,0) ,Cell.new(1,15,0) ,Cell.new() ,Cell.new() ,Cell.new(1,18,0) ,Cell.new(1,19,0) ,Cell.new() ,Cell.new() ,Cell.new(1,22,0) ,Cell.new(1,23,0) ,Cell.new() ,Cell.new() ,Cell.new(1,26,0) ,Cell.new(1,27,0) ,Cell.new() ,Cell.new() ,Cell.new(1,30,0) ,Cell.new(1,31,0) ,Cell.new() ,Cell.new() ,Cell.new(1,34,0) ,Cell.new(1,35,0) ,Cell.new() ,Cell.new() ,Cell.new(1,38,0) ,Cell.new(1,39,0) ,Cell.new() ,Cell.new() ,Cell.new(1,42,0) ,Cell.new(1,43,0) ,Cell.new() ,Cell.new() ,Cell.new(1,46,0) ,Cell.new(1,47,0) ,Cell.new() ,Cell.new() ,Cell.new(1,50,74),Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new(2,3,0) ,Cell.new() ,Cell.new(2,5,0) ,Cell.new() ,Cell.new(2,7,0) ,Cell.new() ,Cell.new(2,9,0) ,Cell.new() ,Cell.new(2,11,0) ,Cell.new() ,Cell.new(2,13,0) ,Cell.new() ,Cell.new(2,15,0) ,Cell.new() ,Cell.new(2,17,0) ,Cell.new() ,Cell.new(2,19,0) ,Cell.new() ,Cell.new(2,21,0) ,Cell.new() ,Cell.new(2,23,0) ,Cell.new() ,Cell.new(2,25,0) ,Cell.new() ,Cell.new(2,27,0) ,Cell.new() ,Cell.new(2,29,0) ,Cell.new() ,Cell.new(2,31,0) ,Cell.new() ,Cell.new(2,33,0) ,Cell.new() ,Cell.new(2,35,0) ,Cell.new() ,Cell.new(2,37,0) ,Cell.new() ,Cell.new(2,39,0) ,Cell.new() ,Cell.new(2,41,0) ,Cell.new() ,Cell.new(2,43,0) ,Cell.new() ,Cell.new(2,45,0) ,Cell.new() ,Cell.new(2,47,0) ,Cell.new() ,Cell.new(2,49,0) ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(3,4,0) ,Cell.new(3,5,0) ,Cell.new() ,Cell.new() ,Cell.new(3,8,11) ,Cell.new(3,9,0) ,Cell.new() ,Cell.new() ,Cell.new(3,12,0) ,Cell.new(3,13,0) ,Cell.new() ,Cell.new() ,Cell.new(3,16,23) ,Cell.new(3,17,0) ,Cell.new() ,Cell.new() ,Cell.new(3,20,0) ,Cell.new(3,21,0) ,Cell.new() ,Cell.new() ,Cell.new(3,24,35) ,Cell.new(3,25,0) ,Cell.new() ,Cell.new() ,Cell.new(3,28,0) ,Cell.new(3,29,0) ,Cell.new() ,Cell.new() ,Cell.new(3,32,47) ,Cell.new(3,33,0) ,Cell.new() ,Cell.new() ,Cell.new(3,36,0) ,Cell.new(3,37,0) ,Cell.new() ,Cell.new() ,Cell.new(3,40,0) ,Cell.new(3,41,0) ,Cell.new() ,Cell.new() ,Cell.new(3,44,65) ,Cell.new(3,45,0) ,Cell.new() ,Cell.new() ,Cell.new(3,48,0) ,Cell.new(3,49,0) ,Cell.new() ,Cell.new()], [Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new()]]
</lang> Produces the following in 0 secs instead of 87.62
>ruby Program.rb 0.000000 0.000000 0.000000 ( 0.000000) 1 2 3 8 9 14 15 20 21 26 27 32 33 38 39 44 45 50 51 56 57 62 63 68 69 74 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 5 6 11 12 17 18 23 24 29 30 35 36 41 42 47 48 53 54 59 60 65 66 71 72
header|With Warnsdorff
I modify Cell as follows to implement Warnsdorff <lang ruby>
- Solve a Hidato Puzzle with Warnsdorff like logic applied
- Nigel_Galloway
- May 6th., 2012.
class Cell
def initialize(row=0, col=0, value=nil) @adj = [[row-1,col-1],[row,col-1],[row+1,col-1],[row-1,col],[row+1,col],[row-1,col+1],[row,col+1],[row+1,col+1]] @t = false $zbl[value] = false unless value == nil @value = value end def try(value) return false if @value == nil return true if value > E return false if @t return false if @value > 0 and @value != value return false if @value == 0 and not $zbl[value] @t = true h = Hash.new n = 0 @adj.each{|x| h[Board[x[0]][x[1]].wdof*10+n] = Board[x[0]][x[1]] n += 1 } h.sort.each{|key,cell| if (cell.try(value+1)) then @value = value return true end } @t = false return false end def wdon return 0 if @value == nil return 0 if @value > 0 return 0 if @t return 1 end def wdof res = 0 @adj.each{|x| res += Board[x[0]][x[1]].wdon} return res end def value return @value end
end </lang> The usage remains unchanged from above and produces:
>ruby Program.rb 0.000000 0.000000 0.000000 ( 0.000000) 4 3 7 5 1 2 6 >ruby Program.rb 0.046000 0.000000 0.046000 ( 0.046800) 32 33 35 36 37 31 34 24 22 38 30 25 23 21 12 39 29 26 20 13 40 11 27 28 14 19 9 10 1 15 16 18 8 2 17 7 6 3 5 4 >ruby Program.rb 0.016000 0.000000 0.016000 ( 0.015600) 1 2 3 8 9 14 15 20 21 26 27 32 33 38 39 44 45 50 51 56 57 62 63 68 69 74 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 5 6 11 12 17 18 23 24 29 30 35 36 41 42 47 48 53 54 59 60 65 66 71 72
This cell may be used to solve Knight's Tour: <lang ruby> class Cell
def initialize(row=0, col=0, value=nil) @adj = [[row-1,col-2],[row-2,col-1],[row-2,col+1],[row-1,col+2],[row+1,col+2],[row+2,col+1],[row+2,col-1],[row+1,col-2]] @t = false $zbl[value] = false unless value == nil @value = value end def try(value) return false if @value == nil return true if value > E return false if @t return false if @value > 0 and @value != value return false if @value == 0 and not $zbl[value] @t = true h = Hash.new n = 0 @adj.each{|x| h[Board[x[0]][x[1]].wdof*10+n] = Board[x[0]][x[1]] n += 1 } h.sort.each{|key,cell| if (cell.try(value+1)) then @value = value return true end } @t = false return false end def wdon return 0 if @value == nil return 0 if @value > 0 return 0 if @t return 1 end def wdof res = 0 @adj.each{|x| res += Board[x[0]][x[1]].wdon} return res end def value return @value end
end </lang> Where only line 3 @adj= <the list> is changed. A possible test for this is: <lang ruby> Rows = 9 Cols = 9 E = 64 $zbl = Array.new(E+1,true) Board = [[Cell.new(),Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(),Cell.new()],
[Cell.new(),Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new(2,2,0),Cell.new(2,3,0),Cell.new(2,4,0),Cell.new(2,5,0),Cell.new(2,6,0),Cell.new(2,7,0),Cell.new(2,8,0),Cell.new(2,9,0) ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new(3,2,0),Cell.new(3,3,0),Cell.new(3,4,0),Cell.new(3,5,0),Cell.new(3,6,0),Cell.new(3,7,0),Cell.new(3,8,0),Cell.new(3,9,0) ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new(4,2,0),Cell.new(4,3,0),Cell.new(4,4,0),Cell.new(4,5,0),Cell.new(4,6,0),Cell.new(4,7,0),Cell.new(4,8,0),Cell.new(4,9,0) ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new(5,2,0),Cell.new(5,3,1),Cell.new(5,4,0),Cell.new(5,5,0),Cell.new(5,6,0),Cell.new(5,7,0),Cell.new(5,8,0),Cell.new(5,9,0) ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new(6,2,0),Cell.new(6,3,0),Cell.new(6,4,0),Cell.new(6,5,0),Cell.new(6,6,0),Cell.new(6,7,0),Cell.new(6,8,0),Cell.new(6,9,0) ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new(7,2,0),Cell.new(7,3,0),Cell.new(7,4,0),Cell.new(7,5,0),Cell.new(7,6,0),Cell.new(7,7,0),Cell.new(7,8,0),Cell.new(7,9,0) ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new(8,2,0),Cell.new(8,3,0),Cell.new(8,4,0),Cell.new(8,5,0),Cell.new(8,6,0),Cell.new(8,7,0),Cell.new(8,8,0),Cell.new(8,9,0) ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new(9,2,0),Cell.new(9,3,0),Cell.new(9,4,0),Cell.new(9,5,0),Cell.new(9,6,0),Cell.new(9,7,0),Cell.new(9,8,0),Cell.new(9,9,0),Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(),Cell.new()], [Cell.new(),Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(),Cell.new()]]
require 'benchmark' puts Benchmark.measure {Board[5][3].try(1)} (1..Rows).each{|r|
(1..Cols).each{|c| printf("%3s",Board[r][c].value)} puts ""}
</lang> Which produces:
>ruby Program.rb 0.000000 0.000000 0.000000 ( 0.000000) 23 20 3 32 25 10 5 8 2 35 24 21 4 7 26 11 19 22 33 36 31 28 9 6 34 1 50 29 48 37 12 27 51 18 53 44 61 30 47 38 54 43 56 49 58 45 62 13 17 52 41 60 15 64 39 46 42 55 16 57 40 59 14 63
Tcl
<lang tcl>proc init {initialConfiguration} {
global grid max filled set max 1 set y 0 foreach row [split [string trim $initialConfiguration "\n"] "\n"] {
set x 0 set rowcontents {} foreach cell $row { if {![string is integer -strict $cell]} {set cell -1} lappend rowcontents $cell set max [expr {max($max, $cell)}] if {$cell > 0} { dict set filled $cell [list $y $x] } incr x } lappend grid $rowcontents incr y
}
}
proc findseps {} {
global max filled set result {} for {set i 1} {$i < $max-1} {incr i} {
if {[dict exists $filled $i]} { for {set j [expr {$i+1}]} {$j <= $max} {incr j} { if {[dict exists $filled $j]} { if {$j-$i > 1} { lappend result [list $i $j [expr {$j-$i}]] } break } } }
} return [lsort -integer -index 2 $result]
}
proc makepaths {sep} {
global grid filled lassign $sep from to len lassign [dict get $filled $from] y x set result {} foreach {dx dy} {-1 -1 -1 0 -1 1 0 -1 0 1 1 -1 1 0 1 1} {
discover [expr {$x+$dx}] [expr {$y+$dy}] [expr {$from+1}] $to \ [list [list $from $x $y]] $grid
} return $result
} proc discover {x y n limit path model} {
global filled # Check for illegal if {[lindex $model $y $x] != 0} return upvar 1 result result lassign [dict get $filled $limit] ly lx # Special case if {$n == $limit-1} {
if {abs($x-$lx)<=1 && abs($y-$ly)<=1 && !($lx==$x && $ly==$y)} { lappend result [lappend path [list $n $x $y] [list $limit $lx $ly]] } return
} # Check for impossible if {abs($x-$lx) > $limit-$n || abs($y-$ly) > $limit-$n} return # Recursive search lappend path [list $n $x $y] lset model $y $x $n incr n foreach {dx dy} {-1 -1 -1 0 -1 1 0 -1 0 1 1 -1 1 0 1 1} {
discover [expr {$x+$dx}] [expr {$y+$dy}] $n $limit $path $model
}
}
proc applypath {path} {
global grid filled puts "Found unique path for [lindex $path 0 0] -> [lindex $path end 0]" foreach cell [lrange $path 1 end-1] {
lassign $cell n x y lset grid $y $x $n dict set filled $n [list $y $x]
}
}
proc printgrid {} {
global grid max foreach row $grid {
foreach cell $row { puts -nonewline [format " %*s" [string length $max] [expr { $cell==-1 ? "." : $cell }]] } puts ""
}
}
proc solveHidato {initialConfiguration} {
init $initialConfiguration set limit [llength [findseps]] while {[llength [set seps [findseps]]] && [incr limit -1]>=0} {
foreach sep $seps { if {[llength [set paths [makepaths $sep]]] == 1} { applypath [lindex $paths 0] break } }
} puts "" printgrid
}</lang> Demonstrating (dots are “outside” the grid, and zeroes are the cells to be filled in): <lang tcl>solveHidato "
0 33 35 0 0 . . . 0 0 24 22 0 . . . 0 0 0 21 0 0 . . 0 26 0 13 40 11 . . 27 0 0 0 9 0 1 . . . 0 0 18 0 0 . . . . . 0 7 0 0 . . . . . . 5 0
"</lang>
- Output:
Found unique path for 5 -> 7 Found unique path for 7 -> 9 Found unique path for 9 -> 11 Found unique path for 11 -> 13 Found unique path for 33 -> 35 Found unique path for 18 -> 21 Found unique path for 1 -> 5 Found unique path for 35 -> 40 Found unique path for 22 -> 24 Found unique path for 24 -> 26 Found unique path for 27 -> 33 Found unique path for 13 -> 18 32 33 35 36 37 . . . 31 34 24 22 38 . . . 30 25 23 21 12 39 . . 29 26 20 13 40 11 . . 27 28 14 19 9 10 1 . . . 15 16 18 8 2 . . . . . 17 7 6 3 . . . . . . 5 4
More complex cases are solvable with an extended version of this code, though that has more onerous version requirements.