Solve a Hidato puzzle: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|C}}: new favorite torture example)
(Updated Python entry on the base of the simpler D entry)
Line 781: Line 781:


=={{header|Python}}==
=={{header|Python}}==
<lang python>class Hidato:
<lang python>board = []
given = []
EMPTY_CELL = -2
start = None
UNKNOWN_CELL = -1


def __init__(self, input):
def setup(s):
global board, given, start
path_seen = set()
self.board = []
lines = s.splitlines()
ncols = len(lines[0].split())
self.known = {}
nrows = len(lines)
self.board_max = -1
board = [[-1] * (ncols + 2) for _ in xrange(nrows + 2)]


lines = input.splitlines()
for r, row in enumerate(lines):
n_cols = len(lines[0].split())
for c, cell in enumerate(row.split()):
for r, row in enumerate(lines):
if cell == "__" :
assert len(row.split()) == n_cols
board[r + 1][c + 1] = 0
board_row = [Hidato.UNKNOWN_CELL] * n_cols
continue
for c, item in enumerate(row.split()):
elif cell == ".":
if item == ".":
continue # -1
board_row[c] = Hidato.EMPTY_CELL
else:
continue
val = int(cell)
elif item == "__":
board[r + 1][c + 1] = val
board_row[c] = Hidato.UNKNOWN_CELL
given.append(val)
continue
if val == 1:
else:
start = (r + 1, c + 1)
given.sort()
n = int(item)
assert n > 0, "Path numbers must be > 0."
assert n not in path_seen, "Duplicated path number"
path_seen.add(n)
board_row[c] = n
self.known[n] = (r, c)
self.board_max = max(self.board_max, n)


def solve(r, c, n, next=0):
self.board.append(board_row)
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


n_rows = len(self.board)
back = 0
if board[r][c] == n:
assert 0 < self.board_max <= n_rows * n_cols
assert 2 <= len(self.known) <= n_rows * n_cols
next += 1
back = n
assert 1 in self.known and self.board_max in self.known


board[r][c] = n
for row in self.board:
for it in row:
for i in xrange(-1, 2):
assert (it == Hidato.EMPTY_CELL or
for j in xrange(-1, 2):
it == Hidato.UNKNOWN_CELL or
if solve(r + i, c + j, n + 1, next):
1 <= it <= n_rows * n_cols)

for n, (r,c) in self.known.iteritems():
assert 0 < n <= self.board_max
assert 0 <= r < n_rows
assert 0 <= c < n_cols

def solve(self):
def fill(r, c, n):
if n > self.board_max:
return True
return True
board[r][c] = back
return False


def print_board():
if (c < 0 or c >= len(self.board[0]) or
r < 0 or r >= len(self.board)):
for row in board[1:-1]:
return False
for c in row[1:-1]:
if c == -1:
print " ",
elif c == 0:
print "__",
else:
print "%2d" % c,
print


hi = """\
if ((self.board[r][c] != Hidato.UNKNOWN_CELL and
self.board[r][c] != n) or
(n in self.known and self.known[n] != (r, c))):
return False

self.board[r][c] = n
for i in xrange(-1, 2):
for j in xrange(-1, 2):
if fill(r + i, c + j, n + 1):
return True

self.board[r][c] = Hidato.UNKNOWN_CELL
return False

assert 1 in self.known
return fill(self.known[1][0], self.known[1][1], 1)

def __repr__(self):
form = "%" + str(len(str(self.board_max)) + 1) + "s"
rows = []
for row in self.board:
row_str = ""
for c in row:
if c == Hidato.UNKNOWN_CELL:
row_str += form % "__"; continue
elif c == Hidato.EMPTY_CELL:
row_str += form % " "; continue
else:
row_str += form % c
rows.append(row_str)
return "\n".join(rows)

def main():
hi = Hidato("""\
__ 33 35 __ __ . . .
__ 33 35 __ __ . . .
__ __ 24 22 __ . . .
__ __ 24 22 __ . . .
Line 878: Line 845:
__ 26 __ 13 40 11 . .
__ 26 __ 13 40 11 . .
27 __ __ __ 9 __ 1 .
27 __ __ __ 9 __ 1 .
. . __ __ 18 __ __ .
. . __ __ 18 __ __ .
. . . . __ 7 __ __
. . . . __ 7 __ __
. . . . . . 5 __""")
. . . . . . 5 __"""


setup(hi)
print "Problem:\n", hi
print_board()
hi.solve()
solve(start[0], start[1], 1)
print "Solution:\n", hi
print
print_board()</lang>
{{out}}
<pre>__ 33 35 __ __
__ __ 24 22 __
__ __ __ 21 __ __
__ 26 __ 13 40 11
27 __ __ __ 9 __ 1
__ __ 18 __ __
__ 7 __ __
5 __


32 33 35 36 37
main()</lang>
31 34 24 22 38
{{out}}
30 25 23 21 12 39
<pre>Problem:
__ 33 35 __ __
29 26 20 13 40 11
__ __ 24 22 __
27 28 14 19 9 10 1
__ __ __ 21 __ __
15 16 18 8 2
__ 26 __ 13 40 11
17 7 6 3
27 __ __ __ 9 __ 1
5 4</pre>
__ __ 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</pre>


=={{header|Tcl}}==
=={{header|Tcl}}==

Revision as of 00:01, 3 May 2012

Task
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.
  • 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

Sample Hidato problem, from Wikipedia
Sample Hidato problem, from Wikipedia

has the following solution, with path marked on it:

Solution to sample Hidato problem
Solution to sample Hidato problem

C

Depth-first graph search: <lang c>#include <stdio.h>

  1. include <stdlib.h>
  2. include <ctype.h>

int *board, **fixed, top = 0, w, h;

  1. define cell(x, y) (board + (((y) + 1) * (w + 2) + (x) + 1))

void make_board(int x, int y, char *s) { int *b;

w = x, h = y; x = (2 + w) * (2 + h);

fixed = calloc(sizeof(int*), x); board = malloc(sizeof(int) * x);

while (x--) board[x] = -1;

for (y = 0; y < h; y++) for (x = 0; x < w; x++) { b = cell(x, y);

while (isspace(*s)) s++;

switch (*s) { case '_': *b = 0; case '.': break; default: fixed[*b = strtol(s, 0, 10)] = b; if (*b > top) top = *b; }

while (!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 = *(cell(j, i)); printf(!c ? " __" : c == -1 ? " " : " %2d", c); } }

int fill(int *b, int n) { int i, j;

if (n > top) return 1;

if((*b && *b != n) || (fixed[n] && fixed[n] != b)) return 0;

for (*b = n++, i = -1; i <= 1; i++) for (j = -1; j <= 1; j ++) if (fill(b + i * (w + 2) + j, n)) return 1;

return *b = 0; }

int main() { make_board( 8,8, " __ 33 35 __ __ .. .. .." " __ __ 24 22 __ .. .. .." " __ __ __ 21 __ __ .. .." " __ 26 __ 13 40 11 .. .." " 27 __ __ __ 9 __ 1 .." " . . __ __ 18 __ __ .." " . .. . . __ 7 __ __" " . .. .. .. . . 5 __" /* 3, 3, " . 4 ." " _ 7 _" " 1 _ _" */ /* 50, 3, " 1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74" " . . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ ." " . . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ." */ );

show_board("Before"); fill(fixed[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.

Translation of: C

<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;

   board = new int[][](cols + 2, rows + 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;
   if (board[r][c] == n) {
       next++;
       back = n;
   }

   board[r][c] = n;
   foreach (i; -1 .. 2)
       foreach (j; -1 .. 2)
           if (solve(r + i, c + j, n + 1, next))
               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 (it; row)
               assert(it == Hidato.emptyCell ||
                      it == Hidato.unknownCell ||
                      (it >= 1 && it <= 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, item; row.split()) {
               switch (item) {
                   case ".":
                       boardRow[c] = Hidato.emptyCell;
                       break;
                   case "__":
                       boardRow[c] = Hidato.unknownCell;
                       break;
                   default: // known
                       immutable n = to!Cell(item);
                       enforce(n > 0, "Path numbers must be > 0.");
                       enforce(n !in pathSeen,
                               text("Duplicated path number: ", n));
                       pathSeen[n] = true;
                       boardRow[c] = n;
                       knownMutable[n] = [r, c];
                       boardMax = max(boardMax, n);
               }
           }
           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 form = "%" ~ text(text(boardMax).length + 1) ~ "s";

       string result;
       foreach (row; board) {
           foreach (c; row) {
               switch (c) {
                   case Hidato.unknownCell:
                       result ~= xformat(form, "__"); break;
                   case Hidato.emptyCell:
                       result ~= xformat(form, "  "); break;
                   default:
                       result ~= xformat(form, c);
               }
           }
           result ~= "\n";
       }
       return result;
   }

}

void main() { 

   auto hi = Hidato("__ 33 35 __ __  .  .  .
                     __ __ 24 22 __  .  .  .
                     __ __ __ 21 __ __  .  .
                     __ 26 __ 13 40 11  .  .
                     27 __ __ __  9 __  1  .
                      .  . __ __ 18 __ __  .
                      .  .  .  . __  7 __ __
                      .  .  .  .  .  .  5 __");

   writeln("Problem:\n", hi);
   hi.solve();
   writeln("Solution:\n", hi);

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

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>

Produces: 

GLPSOL: GLPK LP/MIP Solver, v4.47
Parameter(s) specified in the command line:
 --math Hidato.mathprog

...

INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 6.4 Mb (6712828 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

Perl

Trying to combine logical elimination and brute force search. The code is entirely too complicated, and can solve without the eliminate part at all. <lang perl>#!/usr/bin/perl

use strict; use List::Util 'max';

our (@grid, @known, $n, $rows, $cols);

sub show_board { my $ss = shift; for my $r (@grid) { print +(map { ! defined($_) ? ' ' : $_ ? sprintf("%3d", $_) : ' __' } @$r), "\n" if $ss } }

sub parse_board { @grid = map{[map(/^_/ ? 0 : /^\./ ? undef: $_, split ' ')]} split "\n", shift(); }

sub mark_known { my ($y, $x, $v) = @_; my @new_mark;

delete $_->{"$y,$x"} for @known;

%{ $known[$v] } = ("$y,$x" => 1); $grid[$y][$x] = $v; return @new_mark; }

sub init_assign { $rows = scalar @grid; $cols = max(map(scalar @$_, @grid)); $n = max(map(max(@$_), @grid));

my %vs; for my $i (0 .. $#grid) { for my $j (0 .. $#{$grid[$i]}) { my $v = $grid[$i][$j]; next unless defined $v;

$known[$_]{"$i,$j"} = 1 for 1 .. $n; $vs{$v} = [$i, $j] if $v; } } mark_known(@{$vs{$_}}, $_) for keys %vs; }

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 $i = $y + $_->[1]; my $j = $x + $_->[0]; next if $i < 0 || $i >= $rows || $j < 0 || $j >= $cols; next if !defined $grid[$i][$j]; push @out, [$i, $j]; } @out }

sub eliminate { again: my @seqs = sort { keys %{$known[$a]} <=> keys %{$known[$b]} } 1 .. $n; my @sizes = map { scalar keys %$_ } @known;

for my $v (@seqs) { my @neighbors; for (keys %{$known[$v]}) { push @neighbors, neighbors(split ',') } goto again if merge_set($v - 1, \@neighbors) || merge_set($v + 1, \@neighbors); }

for (1 .. $n) { goto again if ($sizes[$_] != scalar keys %{$known[$_]}); if (keys %{$known[$_]} == 1) { my ($k) = keys %{$known[$_]}; mark_known(split(',', $k), $_); } } }

sub merge_set { my ($seq, $keys) = @_; return if $seq <= 0 || $seq > $n;

my $old_size = keys %{$known[$seq]}; my %incoming; $incoming{"$_->[0],$_->[1]"} = 1 for @$keys;

for (keys %{$known[$seq]}) { delete $known[$seq]{$_} unless $incoming{$_} }

if (!keys %{$known[$seq]}) { die "Can't to place $seq; dead" }

if ($old_size > 1 and 1 == keys %{$known[$seq]}) { my ($key) = keys %{$known[$seq]}; mark_known(split(',', $key), $seq); return 1 } }

sub do_brute_stuff { my $needs_brute; my ($y, $x) = split(',', (keys %{$known[1]})[0]); for (1 .. @known - 1) { if (keys %{$known[$_]} > 1) { $known[$_] = 0; $needs_brute ++; } else { $known[$_] = (keys %{$known[$_]})[0]; } }

if ($needs_brute) { print "\nBruteforcing remaining $needs_brute cells\n"; brute_fill(1, $y, $x); return 1 } print "\nSolved\n"; return 0; }

sub brute_fill { my ($s, $y, $x) = @_;

return 1 if $s >= $n; my $old = $grid[$y][$x];

return 0 if $old and $old != $s; return 0 if $known[$s] && ($known[$s] ne "$y,$x");

$grid[$y][$x] = $s;

for (neighbors($y, $x)) { return 1 if brute_fill($s + 1, @$_); } $grid[$y][$x] = $old; show_board(); }

parse_board

  1. ". 4 .
  2. _ 7 _
  3. 1 _ _";

"__ 33 35 __ __ .. .. .. . __ __ 24 22 __ .. .. .. . __ __ __ 21 __ __ .. .. . __ 26 __ 13 40 11 .. .. . 27 __ __ __ 9 __ 1 .. . . . __ __ 18 __ __ .. . . .. . . __ 7 __ __ . . .. .. .. . . 5 __ .";

init_assign; print "Initial puzzle:\n"; show_board(1);

if (1) { eliminate; print "\nAfter elimination pass:\n"; show_board(1); } show_board(1) if do_brute_stuff;</lang>

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(): 

   for row in board[1:-1]:
       for c in row[1:-1]:
           if c == -1:
               print "  ",
           elif c == 0:
               print "__",
           else:
               print "%2d" % c,
       print

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

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.

Retrieved from "https://rosettacode.org/wiki/Solve_a_Hidato_puzzle?oldid=211234"