Solve a Numbrix puzzle: Difference between revisions

</pre>

=={{header|zkl}}==

This code solves Hidato, Hopido and Numbrix puzzles.

<lang zkl> // Solve Hidato/Hopido/Numbrix puzzles

class Puzzle{ // hold info concerning this puzzle

var board, nrows,ncols, cells,

start, // (r,c) where 1 is located, Void if no 1

terminated, // if board holds highest numbered cell

given, // all the pre-loaded cells

adj, // a list of (r,c) that are valid next cells

;

fcn print_board{

d:=D(-1," ", 0,"__");

foreach r in (board){

r.pump(String,'wrap(c){ "%2s ".fmt(d.find(c,c)) }).println();

}

}

fcn init(s,adjacent){

adj=adjacent;

lines:=s.split("\n");

ncols,nrows=lines[0].split().len(),lines.len();

board=nrows.pump(List(), ncols.pump(List(),-1).copy);

given,start=List(),Void;

cells,terminated=0,True;

foreach r,row in (lines.enumerate()){

foreach c,cell in (row.split().enumerate()){

if(cell=="X") continue; // X == not in play, leave at -1

cells+=1;

val:=cell.toInt();

board[r][c]=val;

given.append(val);

if(val==1) start=T(r,c);

}

}

println("Number of cells = ",cells);

if(not given.holds(cells)){ given.append(cells); terminated=False; }

given=given.filter().sort();

self

}

fcn solve{ //-->Bool

if(start) return(_solve(start.xplode()));

foreach r,c in (nrows,ncols){

if(board[r][c]==0 and _solve(r,c)) return(True);

}

False

}

fcn [private] _solve(r,c,n=1, next=0){

if(n>given[-1]) return(True);

if(not ( (0<=r<nrows) and (0<=c<ncols) )) return(False);

if(board[r][c] and board[r][c]!=n) return(False);

if(terminated and 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;

foreach i,j in (adj){ if(self.fcn(r+i,c+j,n+1, next)) return(True) }

board[r][c]=back;

False

}

} // Puzzle</lang>

<lang zkl>hi1:= // 0==empty cell, X==not a cell

#<<<

"0 0 0 0 0 0 0 0 0

0 0 46 45 0 55 74 0 0

0 38 0 0 43 0 0 78 0

0 35 0 0 0 0 0 71 0

0 0 33 0 0 0 59 0 0

0 17 0 0 0 0 0 67 0

0 18 0 0 11 0 0 64 0

0 0 24 21 0 1 2 0 0

0 0 0 0 0 0 0 0 0";

#<<<

hi2:= // 0==empty cell, X==not a cell

#<<<

"0 0 0 0 0 0 0 0 0

0 11 12 15 18 21 62 61 0

0 6 0 0 0 0 0 60 0

0 33 0 0 0 0 0 57 0

0 32 0 0 0 0 0 56 0

0 37 0 1 0 0 0 73 0

0 38 0 0 0 0 0 72 0

0 43 44 47 48 51 76 77 0

0 0 0 0 0 0 0 0 0";

#<<<

adjacent:=T( T(-1,0),

T( 0,-1), T( 0,1),

T( 1,0) );

foreach hi in (T(hi1,hi2)){

puzzle:=Puzzle(hi); puzzle.adjacent=adjacent;

puzzle.print_board();

puzzle.solve();

println();

puzzle.print_board();

println();

}</lang>

{{out}}

<pre>

Number of cells = 81

__ __ __ __ __ __ __ __ __

__ __ 46 45 __ 55 74 __ __

__ 38 __ __ 43 __ __ 78 __

__ 35 __ __ __ __ __ 71 __

__ __ 33 __ __ __ 59 __ __

__ 17 __ __ __ __ __ 67 __

__ 18 __ __ 11 __ __ 64 __

__ __ 24 21 __ 1 2 __ __

__ __ __ __ __ __ __ __ __

49 50 51 52 53 54 75 76 81

48 47 46 45 44 55 74 77 80

37 38 39 40 43 56 73 78 79

36 35 34 41 42 57 72 71 70

31 32 33 14 13 58 59 68 69

30 17 16 15 12 61 60 67 66

29 18 19 20 11 62 63 64 65

28 25 24 21 10 1 2 3 4

27 26 23 22 9 8 7 6 5

Number of cells = 81

__ __ __ __ __ __ __ __ __

__ 11 12 15 18 21 62 61 __

__ 6 __ __ __ __ __ 60 __

__ 33 __ __ __ __ __ 57 __

__ 32 __ __ __ __ __ 56 __

__ 37 __ 1 __ __ __ 73 __

__ 38 __ __ __ __ __ 72 __

__ 43 44 47 48 51 76 77 __

__ __ __ __ __ __ __ __ __

9 10 13 14 19 20 63 64 65

8 11 12 15 18 21 62 61 66

7 6 5 16 17 22 59 60 67

34 33 4 3 24 23 58 57 68

35 32 31 2 25 54 55 56 69

36 37 30 1 26 53 74 73 70

39 38 29 28 27 52 75 72 71

40 43 44 47 48 51 76 77 78

41 42 45 46 49 50 81 80 79