Solve a Hidato puzzle: Difference between revisions
→{{header|Phix}}
Alpha bravo (talk | contribs) (Added AutoHotkey) |
|||
Line 2,163:
say "$tries tries";
}</lang>
=={{header|Phix}}==
<lang Phix>sequence board, warnsdorffs, knownx, knowny
integer width, height, limit, nchars, tries
string fmt, blank
constant ROW = 1, COL = 2
constant moves = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}
function onboard(integer row, integer col)
return row>=1 and row<=height and col>=nchars and col<=nchars*width
end function
procedure init_warnsdorffs()
integer nrow,ncol
for row=1 to height do
for col=nchars to nchars*width by nchars do
for move=1 to length(moves) do
nrow = row+moves[move][ROW]
ncol = col+moves[move][COL]*nchars
if onboard(nrow,ncol)
and board[nrow][ncol]='_' then
warnsdorffs[nrow][ncol] += 1
end if
end for
end for
end for
end procedure
function solve(integer row, integer col, integer n)
integer nrow, ncol
tries+= 1
if n>limit then return 1 end if
if knownx[n] then
for move=1 to length(moves) do
nrow = row+moves[move][ROW]
ncol = col+moves[move][COL]*nchars
if nrow = knownx[n]
and ncol = knowny[n] then
if solve(nrow,ncol,n+1) then return 1 end if
exit
end if
end for
return 0
end if
sequence wmoves = {}
for move=1 to length(moves) do
nrow = row+moves[move][ROW]
ncol = col+moves[move][COL]*nchars
if onboard(nrow,ncol)
and board[nrow][ncol]='_' then
wmoves = append(wmoves,{warnsdorffs[nrow][ncol],nrow,ncol})
end if
end for
wmoves = sort(wmoves)
-- avoid creating orphans
if length(wmoves)<2 or wmoves[2][1]>1 then
for m=1 to length(wmoves) do
{?,nrow,ncol} = wmoves[m]
warnsdorffs[nrow][ncol] -= 1
end for
for m=1 to length(wmoves) do
{?,nrow,ncol} = wmoves[m]
board[nrow][ncol-nchars+1..ncol] = sprintf(fmt,n)
if solve(nrow,ncol,n+1) then return 1 end if
board[nrow][ncol-nchars+1..ncol] = blank
end for
for m=1 to length(wmoves) do
{?,nrow,ncol} = wmoves[m]
warnsdorffs[nrow][ncol] += 1
end for
end if
return 0
end function
procedure Hidato(sequence s, integer w, integer h, integer lim)
integer y, ch, ch2, k
atom t0 = time()
s = split(s,'\n')
width = w
height = h
nchars = length(sprintf(" %d",lim))
fmt = sprintf(" %%%dd",nchars-1)
blank = repeat('_',nchars)
board = repeat(repeat(' ',width*nchars),height)
knownx = repeat(0,lim)
knowny = repeat(0,lim)
limit = 0
for x=1 to height do
for y=nchars to width*nchars by nchars do
if y>length(s[x]) then
ch = '.'
else
ch = s[x][y]
end if
if ch='_' then
limit += 1
elsif ch!='.' then
k = ch-'0'
ch2 = s[x][y-1]
if ch2!=' ' then
k += (ch2-'0')*10
board[x][y-1] = ch2
end if
knownx[k] = x
knowny[k] = y
limit += 1
end if
board[x][y] = ch
end for
end for
warnsdorffs = repeat(repeat(0,width*nchars),height)
init_warnsdorffs()
tries = 0
if solve(knownx[1],knowny[1],2) then
puts(1,join(board,"\n"))
printf(1,"\nsolution found in %d tries (%3.2fs)\n",{tries,time()-t0})
else
puts(1,"no solutions found\n")
end if
end procedure
constant board1 = """
__ 33 35 __ __ .. .. ..
__ __ 24 22 __ .. .. ..
__ __ __ 21 __ __ .. ..
__ 26 __ 13 40 11 .. ..
27 __ __ __ 9 __ 1 ..
.. .. __ __ 18 __ __ ..
.. .. .. .. __ 7 __ __
.. .. .. .. .. .. 5 __"""
Hidato(board1,8,8,40)
constant board2 = """
. 4 .
_ 7 _
1 _ _"""
Hidato(board2,3,3,7)
constant board3 = """
1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74
. . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ .
. . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."""
Hidato(board3,50,3,74)
constant board4 = """
54 __ 60 59 __ 67 __ 69 __
__ 55 __ __ 63 65 __ 72 71
51 50 56 62 __ .. .. .. ..
__ __ __ 14 .. .. 17 __ ..
48 10 11 .. 15 __ 18 __ 22
__ 46 __ .. 3 __ 19 23 __
__ 44 __ 5 __ 1 33 32 __
__ 43 7 __ 36 __ 27 __ 31
42 __ __ 38 __ 35 28 __ 30"""
Hidato(board4,9,9,72)
constant board5 = """
__ 58 __ 60 __ __ 63 66 __
57 55 59 53 49 __ 65 __ 68
__ 8 __ __ 50 __ 46 45 __
10 6 __ .. .. .. __ 43 70
__ 11 12 .. .. .. 72 71 __
__ 14 __ .. .. .. 30 39 __
15 3 17 __ 28 29 __ __ 40
__ __ 19 22 __ __ 37 36 __
1 20 __ 24 __ 26 __ 34 33"""
Hidato(board5,9,9,72)
constant board6 = """
1 __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. 82
.. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ ..
.. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. ..
__ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. .."""
Hidato(board6,46,4,82)</lang>
{{out}}
<pre style="font-size: 8px">
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
solution found in 760 tries (0.00s)
. 4 .
3 7 5
1 2 6
solution found in 10 tries (0.00s)
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 .
solution found in 74 tries (0.00s)
54 53 60 59 58 67 66 69 70
52 55 61 57 63 65 68 72 71
51 50 56 62 64 . . . .
49 12 13 14 . . 17 21 .
48 10 11 . 15 16 18 20 22
47 46 9 . 3 2 19 23 24
45 44 8 5 4 1 33 32 25
41 43 7 6 36 34 27 26 31
42 40 39 38 37 35 28 29 30
solution found in 106 tries (0.00s)
56 58 54 60 61 62 63 66 67
57 55 59 53 49 47 65 64 68
9 8 52 51 50 48 46 45 69
10 6 7 . . . 44 43 70
5 11 12 . . . 72 71 42
4 14 13 . . . 30 39 41
15 3 17 18 28 29 38 31 40
2 16 19 22 25 27 37 36 32
1 20 21 24 23 26 35 34 33
solution found in 495 tries (0.00s)
1 2 . . . 10 11 . . . 19 20 . . . 28 29 . . . 37 38 . . . 46 47 . . . 55 56 . . . 64 65 . . . 73 74 . . . 82
. . 3 . 9 . . 12 . 18 . . 21 . 27 . . 30 . 36 . . 39 . 45 . . 48 . 54 . . 57 . 63 . . 66 . 72 . . 75 . 81 .
. 4 . 8 . . 13 . 17 . . 22 . 26 . . 31 . 35 . . 40 . 44 . . 49 . 53 . . 58 . 62 . . 67 . 71 . . 76 . 80 . .
5 6 7 . . 14 15 16 . . 23 24 25 . . 32 33 34 . . 41 42 43 . . 50 51 52 . . 59 60 61 . . 68 69 70 . . 77 78 79 . . .
solution found in 82 tries (0.02s)
</pre>
=={{header|PicoLisp}}==
| |||