Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
m (→{{header|Tailspin}}: Extract raw values from tagged identifiers) |
m (→{{header|Phix}}: syntax coloured) |
||
Line 3,203: | Line 3,203: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<lang Phix>(phixonline)--> |
|||
<lang Phix>sequence board, warnsdorffs, knownx, knowny |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">knownx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">knowny</span> |
|||
integer width, height, limit, nchars, tries |
|||
string fmt, blank |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">width</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">height</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nchars</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tries</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">fmt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">blank</span> |
|||
constant ROW = 1, COL = 2 |
|||
constant moves = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}} |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">ROW</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">COL</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span> |
|||
function onboard(integer row, integer col) |
|||
return row>=1 and row<=height and col>=nchars and col<=nchars*width |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">)</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">row</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">height</span> <span style="color: #008080;">and</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">nchars</span> <span style="color: #008080;">and</span> <span style="color: #000000;">col</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">*</span><span style="color: #000000;">width</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
procedure init_warnsdorffs() |
|||
integer nrow,ncol |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</span> |
|||
for row=1 to height do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span> |
|||
for col=nchars to nchars*width by nchars do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">height</span> <span style="color: #008080;">do</span> |
|||
for move=1 to length(moves) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nchars</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nchars</span><span style="color: #0000FF;">*</span><span style="color: #000000;">width</span> <span style="color: #008080;">by</span> <span style="color: #000000;">nchars</span> <span style="color: #008080;">do</span> |
|||
nrow = row+moves[move][ROW] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
ncol = col+moves[move][COL]*nchars |
|||
<span style="color: #000000;">nrow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ROW</span><span style="color: #0000FF;">]</span> |
|||
if onboard(nrow,ncol) |
|||
<span style="color: #000000;">ncol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">COL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">nchars</span> |
|||
and board[nrow][ncol]='_' then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">)</span> |
|||
warnsdorffs[nrow][ncol] += 1 |
|||
<span style="color: #008080;">and</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'_'</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
function solve(integer row, integer col, integer n) |
|||
integer nrow, ncol |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
tries+= 1 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ncol</span> |
|||
if n>limit then return 1 end if |
|||
<span style="color: #000000;">tries</span><span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
if knownx[n] then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">limit</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
for move=1 to length(moves) do |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">knownx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
nrow = row+moves[move][ROW] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
ncol = col+moves[move][COL]*nchars |
|||
<span style="color: #000000;">nrow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ROW</span><span style="color: #0000FF;">]</span> |
|||
if nrow = knownx[n] |
|||
<span style="color: #000000;">ncol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">COL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">nchars</span> |
|||
and ncol = knowny[n] then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">nrow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">knownx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> |
|||
if solve(nrow,ncol,n+1) then return 1 end if |
|||
<span style="color: #008080;">and</span> <span style="color: #000000;">ncol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">knowny</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
exit |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">exit</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return 0 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end if |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span> |
|||
sequence wmoves = {} |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
for move=1 to length(moves) do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
nrow = row+moves[move][ROW] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
ncol = col+moves[move][COL]*nchars |
|||
<span style="color: #000000;">nrow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ROW</span><span style="color: #0000FF;">]</span> |
|||
if onboard(nrow,ncol) |
|||
<span style="color: #000000;">ncol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">COL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">nchars</span> |
|||
and board[nrow][ncol]='_' then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">)</span> |
|||
wmoves = append(wmoves,{warnsdorffs[nrow][ncol],nrow,ncol}) |
|||
<span style="color: #008080;">and</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'_'</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">],</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">})</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
wmoves = sort(wmoves) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
-- avoid creating orphans |
|||
<span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> |
|||
if length(wmoves)<2 or wmoves[2][1]>1 then |
|||
<span style="color: #000080;font-style:italic;">-- avoid creating orphans</span> |
|||
for m=1 to length(wmoves) do |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">2</span> <span style="color: #008080;">or</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
{?,nrow,ncol} = wmoves[m] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
warnsdorffs[nrow][ncol] -= 1 |
|||
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
for m=1 to length(wmoves) do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
{?,nrow,ncol} = wmoves[m] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
board[nrow][ncol-nchars+1..ncol] = sprintf(fmt,n) |
|||
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span> |
|||
if solve(nrow,ncol,n+1) then return 1 end if |
|||
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">-</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
board[nrow][ncol-nchars+1..ncol] = blank |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">-</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">blank</span> |
|||
for m=1 to length(wmoves) do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
{?,nrow,ncol} = wmoves[m] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
warnsdorffs[nrow][ncol] += 1 |
|||
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return 0 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
procedure Hidato(sequence s, integer w, integer h, integer lim) |
|||
integer y, ch, ch2, k |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Hidato</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span> |
|||
atom t0 = time() |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span> |
|||
s = split(s,'\n') |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
width = w |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span> |
|||
height = h |
|||
<span style="color: #000000;">width</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">w</span> |
|||
nchars = length(sprintf(" %d",lim)) |
|||
<span style="color: #000000;">height</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h</span> |
|||
fmt = sprintf(" %%%dd",nchars-1) |
|||
<span style="color: #000000;">nchars</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" %d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">))</span> |
|||
blank = repeat('_',nchars) |
|||
<span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" %%%dd"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
board = repeat(repeat(' ',width*nchars),height) |
|||
<span style="color: #000000;">blank</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'_'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">)</span> |
|||
knownx = repeat(0,lim) |
|||
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">width</span><span style="color: #0000FF;">*</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">),</span><span style="color: #000000;">height</span><span style="color: #0000FF;">)</span> |
|||
knowny = repeat(0,lim) |
|||
<span style="color: #000000;">knownx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span> |
|||
limit = 0 |
|||
<span style="color: #000000;">knowny</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span> |
|||
for x=1 to height do |
|||
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
for y=nchars to width*nchars by nchars do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">height</span> <span style="color: #008080;">do</span> |
|||
if y>length(s[x]) then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nchars</span> <span style="color: #008080;">to</span> <span style="color: #000000;">width</span><span style="color: #0000FF;">*</span><span style="color: #000000;">nchars</span> <span style="color: #008080;">by</span> <span style="color: #000000;">nchars</span> <span style="color: #008080;">do</span> |
|||
ch = '.' |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span> |
|||
else |
|||
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</span> |
|||
ch = s[x][y] |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> |
|||
if ch='_' then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'_'</span> <span style="color: #008080;">then</span> |
|||
elsif ch!='.' then |
|||
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
k = ch-'0' |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">'.'</span> <span style="color: #008080;">then</span> |
|||
ch2 = s[x][y-1] |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">-</span><span style="color: #008000;">'0'</span> |
|||
if ch2!=' ' then |
|||
<span style="color: #000000;">ch2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
k += (ch2-'0')*10 |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ch2</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span> |
|||
board[x][y-1] = ch2 |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">ch2</span><span style="color: #0000FF;">-</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">10</span> |
|||
end if |
|||
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch2</span> |
|||
knownx[k] = x |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
knowny[k] = y |
|||
<span style="color: #000000;">knownx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span> |
|||
limit += 1 |
|||
<span style="color: #000000;">knowny</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span> |
|||
end if |
|||
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
board[x][y] = ch |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
warnsdorffs = repeat(repeat(0,width*nchars),height) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
init_warnsdorffs() |
|||
<span style="color: #000000;">warnsdorffs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">width</span><span style="color: #0000FF;">*</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">),</span><span style="color: #000000;">height</span><span style="color: #0000FF;">)</span> |
|||
tries = 0 |
|||
<span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</span> |
|||
if solve(knownx[1],knowny[1],2) then |
|||
<span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
puts(1,join(board,"\n")) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">knownx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">knowny</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
printf(1,"\nsolution found in %d tries (%3.2fs)\n",{tries,time()-t0}) |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span> |
|||
else |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nsolution found in %d tries (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span> |
|||
puts(1,"no solutions found\n") |
|||
<span style="color: #008080;">else</span> |
|||
end if |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"no solutions found\n"</span><span style="color: #0000FF;">)</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
constant board1 = """ |
|||
__ 33 35 __ __ .. .. .. |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">board1</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" |
|||
__ __ 24 22 __ .. .. .. |
|||
__ 33 35 __ __ .. .. .. |
|||
__ __ 24 22 __ .. .. .. |
|||
__ __ __ 21 __ __ .. .. |
|||
__ 26 __ 13 40 11 .. .. |
|||
27 __ __ __ 9 __ 1 .. |
|||
.. .. __ __ 18 __ __ .. |
|||
.. .. .. .. __ 7 __ __ |
|||
Hidato(board1,8,8,40) |
|||
.. .. .. .. .. .. 5 __"""</span> |
|||
<span style="color: #000000;">Hidato</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">)</span> |
|||
constant board2 = """ |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">board2</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" |
|||
_ 7 _ |
|||
. 4 . |
|||
1 _ _""" |
|||
_ 7 _ |
|||
Hidato(board2,3,3,7) |
|||
1 _ _"""</span> |
|||
<span style="color: #000000;">Hidato</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)</span> |
|||
constant board3 = """ |
|||
1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74 |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">board3</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" |
|||
. . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . |
|||
1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74 |
|||
. . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . |
|||
Hidato(board3,50,3,74) |
|||
. . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."""</span> |
|||
<span style="color: #000000;">Hidato</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">74</span><span style="color: #0000FF;">)</span> |
|||
constant board4 = """ |
|||
54 __ 60 59 __ 67 __ 69 __ |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">board4</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" |
|||
__ 55 __ __ 63 65 __ 72 71 |
|||
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 |
|||
Hidato(board4,9,9,72) |
|||
42 __ __ 38 __ 35 28 __ 30"""</span> |
|||
<span style="color: #000000;">Hidato</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">72</span><span style="color: #0000FF;">)</span> |
|||
constant board5 = """ |
|||
__ 58 __ 60 __ __ 63 66 __ |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">board5</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" |
|||
57 55 59 53 49 __ 65 __ 68 |
|||
__ 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 __ |
|||
Hidato(board5,9,9,72) |
|||
1 20 __ 24 __ 26 __ 34 33"""</span> |
|||
<span style="color: #000000;">Hidato</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">72</span><span style="color: #0000FF;">)</span> |
|||
constant board6 = """ |
|||
1 __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. 82 |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">board6</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""" |
|||
.. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. |
|||
1 __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. 82 |
|||
.. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. |
|||
.. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. |
|||
Hidato(board6,46,4,82)</lang> |
|||
__ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. .."""</span> |
|||
<span style="color: #000000;">Hidato</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">46</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">82</span><span style="color: #0000FF;">)</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre style="font-size: 8px"> |
<pre style="font-size: 8px"> |