Solve a Hidato puzzle: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Tailspin}}: update to stricter typing) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 35:
{{trans|Python}}
<
[Int] given
V start = (-1, -1)
Line 102:
solve(start[0], start[1], 1)
print()
print_board()</
{{out}}
Line 126:
=={{header|AutoHotkey}}==
<
if (R&&C) ; if neighbors (not first iteration)
{
Line 192:
}
return StrReplace(map, ">")
}</
Examples:<
Grid := [[ "Y" , 33 , 35 , "Y" , "Y"]
,[ "Y" , "Y" , 24 , 22 , "Y"]
Line 216:
;--------------------------------
MsgBox, 262144, ,% SolveHidato(Grid, Locked, Max, row, col)
return</
Outputs:<pre>32 33 35 36 37
31 34 24 22 38
Line 228:
=={{header|Bracmat}}==
<
( hidato
= Line solve lowest Ncells row column rpad
Line 340:
: ?board
& out$(hidato$!board)
);</
Output:
<pre>
Line 364:
=={{header|C}}==
Depth-first graph, with simple connectivity check to reject some impossible situations early. The checks slow down simpler puzzles significantly, but can make some deep recursions backtrack much earilier.
<
#include <stdlib.h>
#include <string.h>
Line 530:
return 0;
}</
{{out}}
<pre> Before:
Line 558:
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/>
The puzzle can be made circular (the end cell must connect to the start cell). In that case, no start cell needs to be given.
<
using System.Collections.Generic;
using static System.Console;
Line 685:
}
}</
{{out}}
<pre>
Line 699:
=={{header|C++}}==
<
#include <iostream>
#include <sstream>
Line 852:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
Output:
<pre>
Line 878:
{{Works with|PAKCS}}
Probably not efficient.
<
import Constraint (andC, anyC)
import Findall (unpack)
Line 931:
] = success
main = unpack hidato</
{{Output}}
<pre>Execution time: 1440 msec. / elapsed: 2270 msec.
Line 941:
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.
{{trans|C}}
<
int[][] board;
Line 1,021:
solve(start[0], start[1], 1);
printBoard;
}</
{{out}}
<pre> . . . . . . . . . .
Line 1,051:
With this coding style the changes in the code become less bug-prone, but also more laborious. This version is also faster, its total runtime is about 0.02 seconds or less.
<
std.algorithm, std.exception, std.range, std.typetuple;
Line 1,265:
. . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."
);
}</
{{out}}
<pre>Problem:
Line 1,309:
=={{header|Elixir}}==
{{trans|Ruby}}
<
#
defmodule HLPsolver do
Line 1,386:
end)
end
end</
'''Test:'''
<
"""
Line 1,415:
. . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0
"""
|> HLPsolver.solve(adjacent)</
{{out}}
Line 1,462:
=={{header|Erlang}}==
To simplify the code I start a new process for searching each potential path through the grid. This means that the default maximum number of processes had to be raised ("erl +P 50000" works for me). The task takes about 1-2 seconds on a low level Mac mini. If faster times are needed, or even less performing hardware is used, some optimisation should be done.
<syntaxhighlight lang="erlang">
-module( solve_hidato_puzzle ).
Line 1,567:
store( {Key, Value}, Dict ) -> dict:store( Key, Value, Dict ).
</syntaxhighlight>
{{out}}
<pre>
Line 1,595:
=={{header|Go}}==
{{trans|Java}}
<
import (
Line 1,712:
solve(start[0], start[1], 1, 0)
printBoard()
}</
{{out}}
Line 1,741:
=={{header|Haskell}}==
<
{-# LANGUAGE Rank2Types #-}
Line 1,851:
, ". . . . 0 7 0 0"
, ". . . . . . 5 0"
]</
{{Out}}
<pre> 0 33 35 0 0
Line 1,875:
This is an Unicon-specific solution but could easily be adjusted to work in Icon.
<
record Pos(r,c)
Line 1,979:
QMouse(puzzle, goWest(), self, val)
QMouse(puzzle, goNW(), self, val)
end</
Sample run:
Line 2,013:
{{trans|D}}
{{works with|Java|7}}
<
import java.util.Collections;
import java.util.List;
Line 2,117:
}
}
}</
Output:
Line 2,146:
=={{header|Julia}}==
This solution utilizes a Hidato puzzle solver module which is also used for the Hopido and knight move tasks.
<
export hidatosolve, printboard, hidatoconfigure
Line 2,202:
end # module
</
hidat = """
Line 2,220:
hidatosolve(board, maxmoves, kingmoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
</
__ 33 35 __ __
__ __ 24 22 __
Line 2,242:
=={{header|Kotlin}}==
{{trans|Java}}
<
lateinit var board: List<IntArray>
Line 2,316:
solve(start[0], start[1], 1, 0)
printBoard()
}</
{{out}}
Line 2,345:
=={{header|Mathprog}}==
<
Find a solution to a Hidato problem
Line 2,408:
;
end;</
Using the data in the model produces the following:
{{out}}
Line 2,654:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
This implements a solver that works based on various techniques, i.e. not brute-forcing:
<
NakedN, HiddenN, ChainSearch, HidatoSolve, Cornering, ValidPuzzle, \
GapSearch, ReachDelete, GrowNeighbours]
Line 3,000:
VisualizeHidato[cells, candidates]
out = HidatoSolve[cells, candidates];
VisualizeHidato[cells, out]</
{{out}}
Outputs a graphical version of the solved hidato.
=={{header|Nim}}==
<
type Hidato = object
Line 3,083:
echo("Found:")
discard hidato.solve(hidato.start[0], hidato.start[1], 1)
hidato.print()</
{{out}}
<pre> . . . . . . . . . .
Line 3,109:
=={{header|Perl}}==
<
use List::Util 'max';
Line 3,192:
print "\033[2J";
try_fill(1, $known[1]);</
32 33 35 36 37
31 34 24 22 38
Line 3,203:
=={{header|Phix}}==
<!--<
<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>
Line 3,379:
__ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. .."""</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>
<!--</
{{out}}
<pre style="font-size: 8px">
Line 3,427:
=={{header|Picat}}==
<
main =>
Line 3,472:
R1 >= 1, R1 =< MaxR, C1 >= 1, C1 =< MaxC,
(R1,C1) != (R,C), M[R1,C1] !== 0].
</syntaxhighlight>
{{out}}
<pre>
Line 3,486:
=={{header|PicoLisp}}==
<
(de hidato (Lst)
Line 3,530:
(disp Grid 0
'((This)
(if (: val) (align 3 @) " ") ) ) ) )</
Test:
<
(quote
(T 33 35 T T)
Line 3,541:
(NIL NIL T T 18 T T)
(NIL NIL NIL NIL T 7 T T)
(NIL NIL NIL NIL NIL NIL 5 T) ) )</
Output:
<pre> +---+---+---+---+---+---+---+---+
Line 3,565:
Works with SWI-Prolog and library(clpfd) written by '''Markus Triska'''.<br>
Puzzle solved is from the Wilkipedia page : http://en.wikipedia.org/wiki/Hidato
<
hidato :-
Line 3,664:
my_write_1(X) :-
writef('%3r', [X]).</
{{out}}
<pre>?- hidato.
Line 3,678:
=={{header|Python}}==
<
given = []
start = None
Line 3,746:
solve(start[0], start[1], 1)
print
print_board()</
{{out}}
<pre> __ 33 35 __ __
Line 3,772:
immediately when tested with custom 2d vector library.
<syntaxhighlight lang="racket">
#lang racket
(require math/array)
Line 3,842:
;main function
(define (hidato board) (put-path board (hidato-path board)))
</syntaxhighlight>
{{out}}
<pre>
Line 3,863:
essentially the neighbourhood function.
<
(require "hidato-family-solver.rkt")
Line 3,882:
#( _ _ _ _ 0 7 0 0)
#( _ _ _ _ _ _ 5 0)))))
</syntaxhighlight>
{{out}}
Line 3,905:
* [[Solve the no connection puzzle#Raku|Solve the no connection puzzle]]
<syntaxhighlight lang="raku"
[ 0, -1], [ 0, 1],
[ 1, -1], [ 1, 0], [ 1, 1];
Line 4,002:
say "$tries tries";
}</
=={{header|REXX}}==
Line 4,011:
''Hidato'' and ''Numbrix'' are registered trademarks.
<
maxR=0; maxC=0; maxX=0; minR=9e9; minC=9e9; minX=9e9; cells=0; @.=
parse arg xxx; PZ='Hidato puzzle' /*get the cell definitions from the CL.*/
Line 4,065:
say _
end /*r*/
say; return</
'''output''' when using the following as input:
<br> <tt> 1 7 5 .\2 5 . 7 . .\3 3 . . 18 . .\4 1 27 . . . 9 . 1\5 1 . 26 . 13 40 11\6 1 . . . 21 . .\7 1 . . 24 22 .\8 1 . 33 35 . .</tt>
Line 4,094:
===Without Warnsdorff===
The following class provides functionality for solving a hidato problem:
<
#
class Hidato
Line 4,148:
(msg ? [msg] : []) + str + [""]
end
end</
'''Test:'''
<
board1 = <<EOS
. 4
Line 4,180:
t0 = Time.now
Hidato.new(board3).solve
puts " #{Time.now - t0} sec"</
{{out}}
Line 4,229:
===With Warnsdorff===
I modify method as follows to implement [[wp:Knight's_tour#Warnsdorff|Warnsdorff]] like
<
#
class HLPsolver
Line 4,296:
(msg ? [msg] : []) + str + [""]
end
end</
Which may be used as follows to solve Hidato Puzzles:
<
ADJACENT = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
Line 4,343:
t0 = Time.now
HLPsolver.new(board3).solve
puts " #{Time.now - t0} sec"</
Which produces:
Line 4,413:
=={{header|Rust}}==
<
use std::cmp::{max, min};
use std::fmt;
Line 4,608:
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,631:
</pre>
=={{header|Seed7}}==
<
var set of integer: given is {};
Line 4,730:
printBoard;
end if;
end func;</
{{out}}
Line 4,760:
=={{header|Tailspin}}==
{{trans|Java}}
<
def input:
'__ 33 35 __ __ . . .
Line 4,807:
';
' ->!OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 4,821:
=={{header|Tcl}}==
<
global grid max filled
set max 1
Line 4,930:
puts ""
printgrid
}</
Demonstrating (dots are “outside” the grid, and zeroes are the cells to be filled in):
<
0 33 35 0 0 . . .
0 0 24 22 0 . . .
Line 4,941:
. . . . 0 7 0 0
. . . . . . 5 0
"</
{{out}}
<pre>
Line 4,972:
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<
import "/fmt" for Fmt
Line 5,050:
System.print("\nFound:")
solve.call(start[0], start[1], 1, 0)
printBoard.call()</
{{out}}
Line 5,080:
=={{header|zkl}}==
{{trans|Python}}
<
#<<<
"0 33 35 0 0 X X X
Line 5,096:
solve(board,given, start.xplode(), 1);
println();
print_board(board);</
<
d:=D(-1," ", 0,"__");
foreach r in (board[1,-1]){
Line 5,133:
board[r][c]=back;
False
}</
{{out}}
<pre>
|