Solve a Hopido puzzle: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(5 intermediate revisions by 3 users not shown) | |||
Line 32:
{{trans|Python}}
<
V cnt = 0
V pWid = 0
Line 86:
print()
E
print(‘No solution!’, end' ‘’)</
{{out}}
Line 99:
=={{header|AutoHotkey}}==
<
if (R&&C) ; if neighbors (not first iteration)
{
Line 168:
}
return StrReplace(map, ">")
}</
Examples:<
Grid := [["",0 ,0 ,"",0 ,0 ,""]
,[0 ,0 ,0 ,0 ,0 ,0 ,0]
Line 197:
;--------------------------------
MsgBox, 262144, ,% SolveHopido(Grid, Locked, Max, row, col)
return</
Outputs:<pre> 17 24 16 25
22 8 11 21 7 10 20
Line 210:
Any non-numeric value indicates a no-go.<br/>
If there are cells that require more characters, then a 2-dimensional array of ints must be used. Any number < 0 indicates a no-go.<br/>
<
using System.Collections.Generic;
using static System.Console;
Line 335:
}
}</
{{out}}
<pre style="height:30ex;overflow:scroll">
Line 347:
=={{header|C++}}==
<
#include <vector>
#include <sstream>
Line 481:
return system( "pause" );
}
</syntaxhighlight>
{{out}}
<pre>
Line 495:
{{trans|C++}}
From the refactored C++ version with more precise typing. This tries all possible start positions. The HopidoPuzzle struct is created at compile-time, so its pre-conditions can catch most malformed puzzles at compile-time.
<
Line 608:
else
writefln("One solution:\n%(%-(%2s %)\n%)", solution);
}</
{{out}}
<pre>One solution:
Line 621:
{{trans|Ruby}}
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]]
<
adjacent = [{-3, 0}, {0, -3}, {0, 3}, {3, 0}, {-2, -2}, {-2, 2}, {2, -2}, {2, 2}]
Line 633:
. . . 1 . . .
"""
HLPsolver.solve(board, adjacent)</
{{out}}
Line 656:
=={{header|Go}}==
{{trans|Java}}
<
import (
Line 778:
}
printResult()
}</
{{out}}
Line 794:
Minor variant of [[Solve_a_Holy_Knight's_tour]]. Works in Unicon only.
<
record Pos(r,c)
Line 891:
QMouse(puzzle, visit(loc.r, loc.c+3), self, val)
QMouse(puzzle, visit(loc.r-2,loc.c+2), self, val)
end</
Sample run:
Line 923:
=={{header|Java}}==
{{works with|Java|8}}
<
public class Hopido {
Line 1,031:
}
}
}</
<pre>
Line 1,043:
=={{header|Julia}}==
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task.
<
const hopid = """
Line 1,059:
hidatosolve(board, maxmoves, hopidomoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
</
0 0 0 0
0 0 0 0 0 0 0
Line 1,077:
=={{header|Kotlin}}==
{{trans|Java}}
<
val board = listOf(
Line 1,172:
printResult()
}</
{{out}}
Line 1,186:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Uses shortest tours on graphs to solve it:
<
puzz //= StringSplit[#, "\n"] & /* Map[Characters];
puzz //= Transpose /* Map[Reverse];
Line 1,193:
g = Graph[UndirectedEdge @@@ moves];
ord = Most[FindShortestTour[g][[2]]];
Graphics[MapThread[Text, {Range[Length[ord]], VertexList[g][[ord]]}]]</
{{out}}
Shows a graphical solution.
Line 1,200:
{{trans|Go}}
<
const Moves = [(-3, 0), (0, 3), ( 3, 0), ( 0, -3),
Line 1,294:
var hopido = initHopido(Board)
hopido.findSolution()
hopido.print()</
{{out}}
Line 1,310:
=={{header|Perl}}==
<
use strict; # http://www.rosettacode.org/wiki/Solve_a_Hopido_puzzle
Line 1,347:
. 0 0 0 0 0 .
. . 0 0 0 . .
. . . 0 . . .</
{{out}}
<pre>
Line 1,362:
=={{header|Phix}}==
Simple brute force approach.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #004080;">integer</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tries</span>
<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;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">}}</span>
<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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ncol</span>
<span style="color: #000000;">tries</span><span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<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>
<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>
<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>
<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;">3</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nrow</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nrow</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">ncol</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ncol</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">row</span><span style="color: #0000FF;">])</span>
<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>
<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;">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: #008000;">"%2d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<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>
<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;">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: #008000;">" "</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Hopido</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;">rx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ry</span>
<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>
<span style="color: #000000;">board</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>
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<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;">h</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">*</span><span style="color: #000000;">3</span> <span style="color: #008080;">by</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <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: #008000;">'0'</span> <span style="color: #008080;">then</span>
<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: #008000;">' '</span>
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">rx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ry</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">3</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'1'</span>
<span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<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>
<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>
<span style="color: #008080;">else</span>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board1</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
.
. . 0 0 0 . .
. . . 0 . . ."""</span>
<span style="color: #000000;">Hopido</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
The best and worse cases observed were:
<pre>
Line 1,440 ⟶ 1,443:
solution found in 67702 tries (0.09s)
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">
import sat.
main =>
Grid = {{0,1,1,0,1,1,0},
{1,1,1,1,1,1,1},
{1,1,1,1,1,1,1},
{0,1,1,1,1,1,0},
{0,0,1,1,1,0,0},
{0,0,0,1,0,0,0}},
NR = len(Grid), NC = len(Grid[1]),
Es = [{(R,C), (R1,C1), _} : R in 1..NR, C in 1..NC, R1 in 1..NR, C1 in 1..NC, % Edges
((R1 = R, abs(C1 - C) = 3); (C1 = C, abs(R1 - R) = 3); % horizontal hop
(abs(R1 - R) = 2, abs(C1 - C) = 2)), % diagonal hop
Grid[R,C] = 1, Grid[R1,C1] = 1],
hcp_grid(Grid, Es), % find a Hamiltion cylce on the vertices in Grid through the edges in Es
solve(vars(Es)),
% Write the solution as a matrix, starting at the base tile 6|4:
M = {{0: _ in 1..NC} : _ in 1..NR},
R1 = 6, C1 = 4, I = 0,
do
I := I + 1, M[R1,C1] := I, Stop = 0,
foreach({(R1,C1), (R2,C2), 1} in Es, break(Stop == 1))
R1 := R2, C1 := C2, Stop := 1
end
while ((R1,C1) != (6,4)),
foreach(R in 1..NR, C in 1..NC)
if M[R,C] = 0 then print(" ") else printf("%2d ", M[R,C]) end,
if C = NC then nl end
end.
</syntaxhighlight>
Output:
<pre> 24 15 23 26
6 9 12 5 8 11 4
14 17 20 25 16 19 22
2 7 10 3 27
13 18 21
1
CPU time 0.019 seconds</pre>
=={{header|Prolog}}==
This is a pure prolog implementation (no cuts,etc..), the only libary predicate used is select/3 witch is pure.
<
select(C,Grid,RGrid),
solve(RGrid,C,Solved,Xs,Ys).
Line 1,467 ⟶ 1,509:
j3(O,N,[O,_,_,N|_]).
j3(O,N,[_|T]) :- j3(O,N,T).</
To test send in a list of p/2 terms that represent points that can be hopped to (order is not important).
The grid coords can be anything so need to specify the valid coordinates as a list (in this case numbers between 0 and 6).
<
p(1,0),p(2,0) ,p(4,0),p(5,0),
p(0,1),p(1,1),p(2,1),p(3,1),p(4,1),p(5,1),p(6,1),
Line 1,484 ⟶ 1,526:
XYs = [0,1,2,3,4,5,6],
hopido(P,S,XYs,XYs),
maplist(writeln,S).</
{{out}}
<pre>
Line 1,520 ⟶ 1,562:
=={{header|Python}}==
<
from sys import stdout
Line 1,584 ⟶ 1,626:
else:
stdout.write("No solution!")
</
01 25 17 03
27 13 10 07 14 11 08
Line 1,599 ⟶ 1,641:
essentially the neighbourhood function.
<
(require "hidato-family-solver.rkt")
Line 1,616 ⟶ 1,658:
#(_ _ 0 0 0 _ _)
#(_ _ _ 0 _ _ _)))))
</syntaxhighlight>
{{out}}
Line 1,637 ⟶ 1,679:
* [[Solve the no connection puzzle#Raku|Solve the no connection puzzle]]
<syntaxhighlight lang="raku"
[2, -2], [2, 2],
[0, -3], [0, 3],
Line 1,734 ⟶ 1,776:
say "$tries tries";
}</
{{out}}
Line 1,749 ⟶ 1,791:
No particular effort was made to reduce the elapsed time in solving the puzzle.
<
call time 'Reset' /*reset the REXX elapsed timer to zero.*/
maxR=0; maxC=0; maxX=0; minR=9e9; minC=9e9; minX=9e9; cells=0; @.=
Line 1,804 ⟶ 1,846:
say _
end /*r*/
say; return</
'''output''' when the input is: <br>
<tt> 1 4 1 \2 3 . . . \3 2 . . . . . \4 1 . . . . . . . \5 1 . . . . . . . \6 2 . . \6 5 . . </tt>
Line 1,829 ⟶ 1,871:
=={{header|Ruby}}==
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#With_Warnsdorff | here]]
<
ADJACENT = [[-3, 0], [0, -3], [0, 3], [3, 0], [-2, -2], [-2, 2], [2, -2], [2, 2]]
Line 1,843 ⟶ 1,885:
t0 = Time.now
HLPsolver.new(board1).solve
puts " #{Time.now - t0} sec"</
Which produces:
<pre>
Line 1,867 ⟶ 1,909:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
oo::class create HopidoSolver {
Line 1,962 ⟶ 2,004:
HopidoSolver create hop $puzzle
hop solve
showPuzzle [hop solution] "Output"</
{{out}}
<pre>
Line 1,985 ⟶ 2,027:
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var board = [
Line 2,083 ⟶ 2,125:
if (pos >= nRows * nCols) break
}
printResult.call()</
{{out}}
Line 2,097 ⟶ 2,139:
=={{header|zkl}}==
This solution uses the code from [[Solve_a_Numbrix_puzzle#zkl]]
<
#<<<
" X 0 0 X 0 0 X
Line 2,117 ⟶ 2,159:
println();
puzzle.print_board();
println();</
{{out}}
<pre>
|