Solve a Hidato puzzle: Difference between revisions
m
no edit summary
m (→{{header|Tailspin}}: syntax update) |
mNo edit summary |
||
(20 intermediate revisions by 11 users not shown) | |||
Line 26:
* [[N-queens problem]]
* [[Solve a Holy Knight's tour]]
* [[
* [[Solve a Hopido puzzle]]
* [[Solve a Numbrix puzzle]]
* [[Solve the no connection puzzle]];
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">[[Int]] board
[Int] given
V start = (-1, -1)
F setup(s)
V lines = s.split("\n")
V ncols = lines[0].split(‘ ’, group_delimiters' 1B).len
V nrows = lines.len
:board = (0 .< nrows + 2).map(_ -> [-1] * (@ncols + 2))
L(row) lines
V r = L.index
L(cell) row.split(‘ ’, group_delimiters' 1B)
V c = L.index
I cell == ‘__’
:board[r + 1][c + 1] = 0
L.continue
E I cell == ‘.’
L.continue
E
V val = Int(cell)
:board[r + 1][c + 1] = val
:given.append(val)
I val == 1
:start = (r + 1, c + 1)
:given.sort()
F solve(r, c, n, =next = 0)
I n > :given.last
R 1B
I :board[r][c] & :board[r][c] != n
R 0B
I :board[r][c] == 0 & :given[next] == n
R 0B
V back = 0
I :board[r][c] == n
next++
back = n
:board[r][c] = n
L(i) -1 .< 2
L(j) -1 .< 2
I solve(r + i, c + j, n + 1, next)
R 1B
:board[r][c] = back
R 0B
F print_board()
V d = [-1 = ‘ ’, 0 = ‘__’]
V bmax = max(:board.map(r -> max(r)))
V lbmax = String(bmax).len + 1
L(r) :board[1 .< (len)-1]
print(r[1 .< (len)-1].map(c -> @d.get(c, String(c)).rjust(@lbmax)).join(‘’))
V hi =
|‘__ 33 35 __ __ . . .
__ __ 24 22 __ . . .
__ __ __ 21 __ __ . .
__ 26 __ 13 40 11 . .
27 __ __ __ 9 __ 1 .
. . __ __ 18 __ __ .
. . . . __ 7 __ __
. . . . . . 5 __’
setup(hi)
print_board()
solve(start[0], start[1], 1)
print()
print_board()</syntaxhighlight>
{{out}}
<pre>
__ 33 35 __ __
__ __ 24 22 __
__ __ __ 21 __ __
__ 26 __ 13 40 11
27 __ __ __ 9 __ 1
__ __ 18 __ __
__ 7 __ __
5 __
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
</pre>
=={{header|AutoHotkey}}==
<
if (R&&C) ; if neighbors (not first iteration)
{
Line 99 ⟶ 192:
}
return StrReplace(map, ">")
}</
Examples:<
Grid := [[ "Y" , 33 , 35 , "Y" , "Y"]
,[ "Y" , "Y" , 24 , 22 , "Y"]
Line 123 ⟶ 216:
;--------------------------------
MsgBox, 262144, ,% SolveHidato(Grid, Locked, Max, row, col)
return</
Outputs:<pre>32 33 35 36 37
31 34 24 22 38
Line 135 ⟶ 228:
=={{header|Bracmat}}==
<
( hidato
= Line solve lowest Ncells row column rpad
Line 247 ⟶ 340:
: ?board
& out$(hidato$!board)
);</
Output:
<pre>
Line 271 ⟶ 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 437 ⟶ 530:
return 0;
}</
{{out}}
<pre> Before:
Line 465 ⟶ 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 592 ⟶ 685:
}
}</
{{out}}
<pre>
Line 606 ⟶ 699:
=={{header|C++}}==
<
#include <iostream>
#include <sstream>
Line 759 ⟶ 852:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
Output:
<pre>
Line 785 ⟶ 878:
{{Works with|PAKCS}}
Probably not efficient.
<
import Constraint (andC, anyC)
import Findall (unpack)
Line 838 ⟶ 931:
] = success
main = unpack hidato</
{{Output}}
<pre>Execution time: 1440 msec. / elapsed: 2270 msec.
Line 848 ⟶ 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 928 ⟶ 1,021:
solve(start[0], start[1], 1);
printBoard;
}</
{{out}}
<pre> . . . . . . . . . .
Line 958 ⟶ 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,172 ⟶ 1,265:
. . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."
);
}</
{{out}}
<pre>Problem:
Line 1,216 ⟶ 1,309:
=={{header|Elixir}}==
{{trans|Ruby}}
<
#
defmodule HLPsolver do
Line 1,293 ⟶ 1,386:
end)
end
end</
'''Test:'''
<
"""
Line 1,322 ⟶ 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,369 ⟶ 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,474 ⟶ 1,567:
store( {Key, Value}, Dict ) -> dict:store( Key, Value, Dict ).
</syntaxhighlight>
{{out}}
<pre>
Line 1,502 ⟶ 1,595:
=={{header|Go}}==
{{trans|Java}}
<
import (
Line 1,619 ⟶ 1,712:
solve(start[0], start[1], 1, 0)
printBoard()
}</
{{out}}
Line 1,648 ⟶ 1,741:
=={{header|Haskell}}==
<
{-# LANGUAGE Rank2Types #-}
Line 1,758 ⟶ 1,851:
, ". . . . 0 7 0 0"
, ". . . . . . 5 0"
]</
{{Out}}
<pre> 0 33 35 0 0
Line 1,782 ⟶ 1,875:
This is an Unicon-specific solution but could easily be adjusted to work in Icon.
<
record Pos(r,c)
Line 1,886 ⟶ 1,979:
QMouse(puzzle, goWest(), self, val)
QMouse(puzzle, goNW(), self, val)
end</
Sample run:
Line 1,920 ⟶ 2,013:
{{trans|D}}
{{works with|Java|7}}
<
import java.util.Collections;
import java.util.List;
Line 2,024 ⟶ 2,117:
}
}
}</
Output:
Line 2,053 ⟶ 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,109 ⟶ 2,202:
end # module
</
hidat = """
Line 2,127 ⟶ 2,220:
hidatosolve(board, maxmoves, kingmoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
</
__ 33 35 __ __
__ __ 24 22 __
Line 2,149 ⟶ 2,242:
=={{header|Kotlin}}==
{{trans|Java}}
<
lateinit var board: List<IntArray>
Line 2,223 ⟶ 2,316:
solve(start[0], start[1], 1, 0)
printBoard()
}</
{{out}}
Line 2,252 ⟶ 2,345:
=={{header|Mathprog}}==
<
Find a solution to a Hidato problem
Line 2,315 ⟶ 2,408:
;
end;</
Using the data in the model produces the following:
{{out}}
Line 2,558 ⟶ 2,651:
Model has been successfully processed
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
This implements a solver that works based on various techniques, i.e. not brute-forcing:
<syntaxhighlight lang="mathematica">ClearAll[NeighbourQ, CellDistance, VisualizeHidato, HiddenSingle, \
NakedN, HiddenN, ChainSearch, HidatoSolve, Cornering, ValidPuzzle, \
GapSearch, ReachDelete, GrowNeighbours]
NeighbourQ[cell1_, cell2_] := (CellDistance[cell1, cell2] === 1)
ValidPuzzle[cells_List, cands_List] :=
MemberQ[cands, {1}] \[And] MemberQ[cands, {Length[cells]}] \[And]
Length[cells] == Length[candidates] \[And]
MinMax[Flatten[cands]] === {1,
Length[cells]} \[And] (Union @@ cands === Range[Length[cells]])
CellDistance[cell1_, cell2_] := ChessboardDistance[cell1, cell2]
VisualizeHidato[cells_List, cands_List] := Module[{grid, nums, cb, hx},
grid = {EdgeForm[Thick],
MapThread[
If[Length[#2] > 1, {FaceForm[],
Rectangle[#1]}, {FaceForm[LightGray],
Rectangle[#1]}] &, {cells, cands}]};
nums =
MapThread[
If[Length[#1] == 1, Text[Style[First[#1], 16], #2 + 0.5 {1, 1}],
Text[
Tooltip[Style[Length[#1], Red, 10], #1], #2 +
0.5 {1, 1}]] &, {cands, cells}];
cb = CoordinateBounds[cells];
Graphics[{grid, nums}, PlotRange -> cb + {{-0.5, 1.5}, {-0.5, 1.5}},
ImageSize -> 60 (1 + cb[[1, 2]] - cb[[1, 1]])]
]
HiddenSingle[cands_List] := Module[{singles, newcands = cands},
singles = Cases[Tally[Flatten[cands]], {_, 1}];
If[Length[singles] > 0,
singles = Sort[singles[[All, 1]]];
newcands =
If[ContainsAny[#, singles], Intersection[#, singles], #] & /@
newcands;
newcands
,
cands
]
]
HiddenN[cands_List, n_Integer?(# > 1 &)] := Module[{tmp, out},
tmp = cands;
tmp = Join @@ MapIndexed[{#1, First[#2]} &, tmp, {2}];
tmp = Transpose /@ GatherBy[tmp, First];
tmp[[All, 1]] = tmp[[All, 1, 1]];
tmp = Select[tmp, 2 <= Length[Last[#]] <= n &];
If[Length[tmp] > 0,
tmp = Transpose /@ Subsets[tmp, {n}];
tmp[[All, 2]] = Union @@@ tmp[[All, 2]];
tmp = Select[tmp, Length[Last[#]] == n &];
If[Length[tmp] > 0,
(* for each tmp {cands,
cells} in each of the cells delete everything except the cands *)
out = cands;
Do[
Do[
out[[c]] = Select[out[[c]], MemberQ[t[[1]], #] &];
,
{c, t[[2]]}
]
,
{t, tmp}
];
out
,
cands
]
,
cands
]
]
NakedN[cands_List, n_Integer?(# > 1 &)] := Module[{tmp, newcands, ids},
tmp = {Range[Length[cands]], cands}\[Transpose];
tmp = Select[tmp, 2 <= Length[Last[#]] <= n &];
If[Length[tmp] > 0,
tmp = Transpose /@ Subsets[tmp, {n}];
tmp[[All, 2]] = Union @@@ tmp[[All, 2]];
tmp = Select[tmp, Length[Last[#]] == n &];
If[Length[tmp] > 0,
newcands = cands;
Do[
ids = Complement[Range[Length[newcands]], t[[1]]];
newcands[[ids]] =
DeleteCases[newcands[[ids]],
Alternatives @@ t[[2]], \[Infinity]];
,
{t, tmp}
];
newcands
,
cands
]
,
cands
]
]
Cornering[cells_List, cands_List] :=
Module[{newcands, neighbours, filled, neighboursfiltered, cellid,
filledneighours, begin, end, beginend},
filled = Flatten[MapIndexed[If[Length[#1] == 1, #2, {}] &, cands]];
begin = If[MemberQ[cands, {1}], {}, {1}];
end = If[MemberQ[cands, {Length[cells]}], {}, {Length[cells]}];
beginend = Join[begin, end];
neighbours = Outer[NeighbourQ, cells, cells, 1];
neighbours =
Association[
MapIndexed[
First[#2] -> {Complement[Flatten[Position[#1, True]], filled],
Intersection[Flatten[Position[#1, True]], filled]} &,
neighbours]];
KeyDropFrom[neighbours, filled];
neighbours = Select[neighbours, Length[First[#]] == 1 &];
If[Length[neighbours] > 0,
newcands = cands;
neighbours = KeyValueMap[List, neighbours];
Do[
cellid = n[[1]];
filledneighours = n[[2, 2]];
filledneighours = Join @@ cands[[filledneighours]];
filledneighours =
Union[filledneighours - 1, filledneighours + 1];
filledneighours = Union[filledneighours, beginend];
newcands[[cellid]] =
Intersection[newcands[[cellid]], filledneighours];
,
{n, neighbours}
];
newcands
,
cands
]
]
ChainSearch[cells_, cands_] := Module[{neighbours, sols, out},
neighbours = Outer[NeighbourQ, cells, cells, 1];
neighbours =
Association[
MapIndexed[First[#2] -> Flatten[Position[#1, True]] &,
neighbours]];
sols = Reap[ChainSearch[neighbours, cands, {}];][[2]];
If[Length[sols] > 0,
sols = sols[[1]];
If[Length[sols] > 1,
Print["multiple solutions found, showing first"];
];
sols = First[sols];
out = cands;
out[[sols]] = List /@ Range[Length[out]];
out
,
cands
]
]
ChainSearch[neighbours_, cands_List, solcellids_List] :=
Module[{largest, largestid, next, poss},
largest = Length[solcellids];
largestid = Last[solcellids, 0];
If[largest < Length[cands],
next = largest + 1;
poss =
Flatten[MapIndexed[If[MemberQ[#1, next], First[#2], {}] &, cands]];
If[Length[poss] > 0,
If[largest > 0,
poss = Intersection[poss, neighbours[largestid]];
];
poss = Complement[poss, solcellids]; (* can't be in previous path*)
If[Length[poss] > 0, (* there are 'next' ones iterate over,
calling this function *)
Do[
ChainSearch[neighbours, cands, Append[solcellids, p]]
,
{p, poss}
]
]
,
Print["There should be a next!"];
Abort[];
]
,
Sow[solcellids] (*
we found a solution with this ordering of cells *)
]
]
GrowNeighbours[neighbours_, set_List] :=
Module[{lastdone, ids, newneighbours, old},
old = Join @@ set[[All, All, 1]];
lastdone = Last[set];
ids = lastdone[[All, 1]];
newneighbours = Union @@ (neighbours /@ ids);
newneighbours = Complement[newneighbours, old]; (*only new ones*)
If[Length[newneighbours] > 0,
Append[set, Thread[{newneighbours, lastdone[[1, 2]] + 1}]]
,
set
]
]
ReachDelete[cells_List, cands_List, neighbours_, startid_] :=
Module[{seed, distances, val, newcands},
If[MatchQ[cands[[startid]], {_}],
val = cands[[startid, 1]];
seed = {{{startid, 0}}};
distances =
Join @@ FixedPoint[GrowNeighbours[neighbours, #] &, seed];
If[Length[distances] > 0,
distances = Select[distances, Last[#] > 0 &];
If[Length[distances] > 0,
newcands = cands;
distances[[All, 2]] =
Transpose[
val + Outer[Times, {-1, 1}, distances[[All, 2]] - 1]];
Do[newcands[[\[CurlyPhi][[1]]]] =
Complement[newcands[[\[CurlyPhi][[1]]]],
Range @@ \[CurlyPhi][[2]]];
, {\[CurlyPhi], distances}
];
newcands
,
cands
]
,
cands
]
,
Print["invalid starting point for neighbour search"];
Abort[];
]
]
GapSearch[cells_List, cands_List] :=
Module[{givensid, givens, neighbours},
givensid = Flatten[Position[cands, {_}]];
givens = {cells[[givensid]], givensid,
Flatten[cands[[givensid]]]}\[Transpose];
If[Length[givens] > 0,
givens = SortBy[givens, Last];
givens = Split[givens, Last[#2] == Last[#1] + 1 &];
givens = If[Length[#] <= 2, #, #[[{1, -1}]]] & /@ givens;
If[Length[givens] > 0,
givens = Join @@ givens;
If[Length[givens] > 0,
neighbours = Outer[NeighbourQ, cells, cells, 1];
neighbours =
Association[
MapIndexed[First[#2] -> Flatten[Position[#1, True]] &,
neighbours]];
givens = givens[[All, 2]];
Fold[ReachDelete[cells, #1, neighbours, #2] &, cands, givens]
,
cands
]
,
cands
]
,
cands
]
]
HidatoSolve[cells_List, cands_List] :=
Module[{newcands = cands, old},
If[ValidPuzzle[cells, cands] \[Or] 1 == 1,
old = -1;
newcands = GapSearch[cells, newcands];
While[old =!= newcands,
old = newcands;
newcands = GapSearch[cells, newcands];
If[old === newcands,
newcands = HiddenSingle[newcands];
If[old === newcands,
newcands = NakedN[newcands, 2];
newcands = HiddenN[newcands, 2];
If[old === newcands,
newcands = NakedN[newcands, 3];
newcands = HiddenN[newcands, 3];
If[old === newcands,
newcands = Cornering[cells, newcands];
If[old === newcands,
newcands = NakedN[newcands, 4];
newcands = HiddenN[newcands, 4];
If[old === newcands,
newcands = NakedN[newcands, 5];
newcands = HiddenN[newcands, 5];
If[old === newcands,
newcands = NakedN[newcands, 6];
newcands = HiddenN[newcands, 6];
If[old === newcands,
newcands = NakedN[newcands, 7];
newcands = HiddenN[newcands, 7];
If[old === newcands,
newcands = NakedN[newcands, 8];
newcands = HiddenN[newcands, 8];
]
]
]
]
]
]
]
]
]
];
If[Length[Flatten[newcands]] > Length[newcands], (*
if not solved do a depth-first brute force search*)
newcands = ChainSearch[cells, newcands];
];
(*Print@VisualizeHidato[cells,newcands];*)
newcands
,
Print[
"There seems to be something wrong with your Hidato puzzle. Check \
if the begin and endpoints are given, the cells and candidates have \
the same length, all the numbers are among the \
candidates\[Ellipsis]"]
]
]
cells = {{1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {2, 4}, {2, 5}, {2,
6}, {2, 7}, {2, 8}, {3, 3}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3,
8}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {5, 2}, {5,
3}, {5, 4}, {5, 5}, {5, 6}, {5, 7}, {5, 8}, {6, 2}, {6, 3}, {6,
4}, {6, 5}, {6, 6}, {7, 1}, {7, 2}, {7, 3}, {7, 4}, {8, 1}, {8,
2}}; (* cartesian coordinates of the cells *)
candidates =
ConstantArray[Range@Length[cells],
Length[
cells]]; (* all the cells start with candidates 1 through 40 *)
hints = {
{{1, 4}, {27}},
{{2, 5}, {26}},
{{7, 1}, {5}},
{{6, 2}, {7}},
{{5, 3}, {18}},
{{5, 4}, {9}},
{{5, 5}, {40}},
{{6, 5}, {11}},
{{4, 5}, {13}},
{{4, 6}, {21}},
{{4, 7}, {22}},
{{3, 7}, {24}},
{{3, 8}, {35}},
{{2, 8}, {33}},
{{7, 4}, {1}}
};
indices = Flatten[Position[cells, #] & /@ hints[[All, 1]]];
candidates[[indices]] = hints[[All, 2]];
VisualizeHidato[cells, candidates]
out = HidatoSolve[cells, candidates];
VisualizeHidato[cells, out]</syntaxhighlight>
{{out}}
Outputs a graphical version of the solved hidato.
=={{header|MiniScript}}==
<syntaxhighlight lang="miniscript">
string.splitBySpaces = function
s = self.split
while s.indexOf("") != null
s.remove(s.indexOf(""))
end while
return s
end function
Hidato = {"board": [], "given": [], "start": [], "maxNum": 0}
Hidato.__emptyBoard = function(nRows, nCols)
self.board = []
emptyRow = []
for c in range(1,nCols + 2)
emptyRow.push(-1)
end for
for r in range(1,nRows + 2)
self.board.push(emptyRow[:])
end for
end function
Hidato.setup = function(s)
lines = s.split(char(13))
cols = lines[0].splitBySpaces.len
rows = lines.len
// create empty board with room
// for the wall at the edge
self.__emptyBoard(rows,cols)
board = self.board
// fill board with start puzzle
for r in range(0, rows - 1)
for c in range(0, cols - 1)
cell = (lines[r].splitBySpaces)[c]
if cell == "__" then
board[r+1][c+1] = 0 // unknown
else if cell == "." then
continue // -1 for blocked
else
num = cell.val
board[r+1][c+1] = num
self.given.push(num)
if num == 1 then
self.start = [r+1,c+1]
end if
if num > self.maxNum then self.maxNum = num
end if
end for
end for
self.given.sort
end function
Hidato.solve = function(n, pos = null, next = 0)
if n > self.given[-1] then return true
if pos == null then pos = self.start
r = pos[0]
c = pos[1]
board = self.board
if board[r][c] and board[r][c] != n then return false
if board[r][c] == 0 and self.given[next] == n then return false
back = 0
if board[r][c] == n then
next += 1
back = n
end if
board[r][c] = n
for i in range(-1, 1)
for j in range(-1,1)
if self.solve(n + 1, [r + i, c + j], next) then return true
end for
end for
board[r][c] = back
return false
end function
Hidato.print = function
board = self.board
maxLen = str(self.maxNum).len + 1
padding = " " * maxLen
for row in board[1:-1]
s = ""
for cell in row[1:-1]
c = padding + "__" * (cell == 0) + str(cell) * (cell > 0)
s += c[-maxLen:]
end for
print s
end for
end function
puzzle = "__ 33 35 __ __ . . ." + char(13)
puzzle += "__ __ 24 22 __ . . ." + char(13)
puzzle += "__ __ __ 21 __ __ . ." + char(13)
puzzle += "__ 26 __ 13 40 11 . ." + char(13)
puzzle += "27 __ __ __ 9 __ 1 ." + char(13)
puzzle += " . . __ __ 18 __ __ ." + char(13)
puzzle += " . . . . __ 7 __ __" + char(13)
puzzle += " . . . . . . 5 __"
Hidato.setup(puzzle)
print "The initial puzzle board:"
Hidato.print
print
Hidato.solve(1)
print "The puzzle solved:"
Hidato.print</syntaxhighlight>
{{out}}
<pre>
The initial puzzle board:
__ 33 35 __ __
__ __ 24 22 __
__ __ __ 21 __ __
__ 26 __ 13 40 11
27 __ __ __ 9 __ 1
__ __ 18 __ __
__ 7 __ __
5 __
The puzzle solved:
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</pre>
=={{header|Nim}}==
<
type Hidato = object
given: seq[int]
start: (int, int)
proc initHidato(s: string): Hidato =
var lines = s.splitLines()
let cols = lines[0].splitWhitespace().len()
let rows = lines.len()
result.board = newSeqWith(rows + 2, newSeq[int](cols + 2)) # Make room for borders.
for i
for j in 0 .. result.board[
for r, row in lines:
for c, cell in row.splitWhitespace().pairs():
of "__" :
result.board[r +
else :
let val =
result.board[r + 1][c + 1] = val
if val == 1:
result.given.sort()
proc solve(hidato: var Hidato; r, c, n: int; next = 0): bool =
if n > hidato.given[^1]:
return true
if hidato.board[r][c] < 0:
return false
if hidato.board[r][c] > 0 and hidato.board[r][c] != n:
return false
if hidato.board[r][c] == 0 and hidato.given[next] == n:
return false
let back = hidato.board[r][c]
hidato.board[r][c] = n
for i in -1 .. 1:
for j in -1 .. 1:
if back == n:
if hidato.solve(r + i, c + j, n + 1, next + 1): return true
else:
if hidato.solve(r + i, c + j, n + 1, next): return true
hidato.board[r][c] = back
result = false
proc print(hidato: Hidato) =
for row in hidato.board:
for val in row:
stdout.write if val == -1: " . " elif val == 0: "__ " else: &"{val:2} "
writeLine(stdout, "")
const Hi = """
__ 33 35 __ __ . . .
__ __ 24 22 __ . . .
__ __ __ 21 __ __ . .
__ 26 __ 13 40 11 . .
27 __ __ __ 9 __ 1 .
. . __ __ 18 __ __ .
. . . . __ 7 __ __
. . . . . . 5 __"""
var hidato = initHidato(Hi)
hidato.print()
echo("")
echo("Found:")
discard hidato.solve(hidato.start[0], hidato.start[1], 1)
hidato.print()</syntaxhighlight>
{{out}}
<pre> . . . . . . . . . .
Line 2,665 ⟶ 3,240:
=={{header|Perl}}==
<
use List::Util 'max';
Line 2,748 ⟶ 3,323:
print "\033[2J";
try_fill(1, $known[1]);</
32 33 35 36 37
31 34 24 22 38
Line 2,759 ⟶ 3,334:
=={{header|Phix}}==
<!--<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: #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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">init_warnsdorffs</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: #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>
<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>
<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;">nchars</span>
<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>
<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;">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>
<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;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</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;">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>
<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;">nchars</span>
<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>
<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>
<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: #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;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</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;">nchars</span>
<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>
<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;">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>
<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: #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>
<span style="color: #000080;font-style:italic;">-- avoid creating orphans</span>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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>
<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>
<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;">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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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;">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>
<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>
<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;">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>
<span style="color: #000000;">width</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">w</span>
<span style="color: #000000;">height</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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;">height</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;">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>
<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>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</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>
<span style="color: #008080;">end</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>
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<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>
<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>
<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: #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>
<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: #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>
<span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</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;">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>
<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;">"""
.. .. .. .. __ 7 __ __
.. .. .. .. .. .. 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>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board2</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
. 4 .
_ 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>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board3</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
. . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ .
. . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."""</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>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board4</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
__ 43 7 __ 36 __ 27 __ 31
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>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board5</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
__ __ 19 22 __ __ 37 36 __
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>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board6</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
.. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. ..
__ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. .."""</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>
<!--</syntaxhighlight>-->
{{out}}
<pre style="font-size: 8px">
Line 2,977 ⟶ 3,555:
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|Picat}}==
<syntaxhighlight lang="picat">import sat.
main =>
M = {{ _,33,35, _, _, 0, 0, 0},
{ _, _,24,22, _, 0, 0, 0},
{ _, _, _,21, _, _, 0, 0},
{ _,26, _,13,40,11, 0, 0},
{27, _, _, _, 9, _, 1, 0},
{ 0, 0, _, _,18, _, _, 0},
{ 0, 0, 0, 0, _, 7, _, _},
{ 0, 0, 0, 0, 0, 0, 5, _}},
MaxR = len(M),
MaxC = len(M[1]),
NZeros = len([1 : R in 1..MaxR, C in 1..MaxC, M[R,C] == 0]),
M :: 0..MaxR*MaxC-NZeros,
Vs = [{(R,C),1} : R in 1..MaxR, C in 1..MaxC, M[R,C] !== 0],
find_start(M,MaxR,MaxC,StartR,StartC),
Es = [{(R,C),(R1,C1),_} : R in 1..MaxR, C in 1..MaxC, M[R,C] !== 0,
neibs(M,MaxR,MaxC,R,C,Neibs),
(R1,C1) in [(StartR,StartC)|Neibs], M[R1,C1] !== 0],
hcp(Vs,Es),
foreach ({(R,C),(R1,C1),B} in Es)
B #/\ M[R1,C1] #!= 1 #=> M[R1,C1] #= M[R,C]+1
end,
solve(M),
foreach (R in 1..MaxR)
foreach (C in 1..MaxC)
if M[R,C] == 0 then
printf("%4c", '.')
else
printf("%4d", M[R,C])
end
end,
nl
end.
find_start(M,MaxR,MaxC,StartR,StartC) =>
between(1,MaxR,StartR),
between(1,MaxC,StartC),
M[StartR,StartC] == 1,!.
neibs(M,MaxR,MaxC,R,C,Neibs) =>
Neibs = [(R1,C1) : Dr in -1..1, Dc in -1..1, R1 = R+Dr, C1 = C+Dc,
R1 >= 1, R1 =< MaxR, C1 >= 1, C1 =< MaxC,
(R1,C1) != (R,C), M[R1,C1] !== 0].
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|PicoLisp}}==
<
(de hidato (Lst)
Line 3,024 ⟶ 3,661:
(disp Grid 0
'((This)
(if (: val) (align 3 @) " ") ) ) ) )</
Test:
<
(quote
(T 33 35 T T)
Line 3,035 ⟶ 3,672:
(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,059 ⟶ 3,696:
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,158 ⟶ 3,795:
my_write_1(X) :-
writef('%3r', [X]).</
{{out}}
<pre>?- hidato.
Line 3,172 ⟶ 3,809:
=={{header|Python}}==
<
given = []
start = None
Line 3,240 ⟶ 3,877:
solve(start[0], start[1], 1)
print
print_board()</
{{out}}
<pre> __ 33 35 __ __
Line 3,266 ⟶ 3,903:
immediately when tested with custom 2d vector library.
<syntaxhighlight lang="racket">
#lang racket
(require math/array)
Line 3,336 ⟶ 3,973:
;main function
(define (hidato board) (put-path board (hidato-path board)))
</syntaxhighlight>
{{out}}
<pre>
Line 3,357 ⟶ 3,994:
essentially the neighbourhood function.
<
(require "hidato-family-solver.rkt")
Line 3,376 ⟶ 4,013:
#( _ _ _ _ 0 7 0 0)
#( _ _ _ _ _ _ 5 0)))))
</syntaxhighlight>
{{out}}
Line 3,399 ⟶ 4,036:
* [[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 3,496 ⟶ 4,133:
say "$tries tries";
}</
=={{header|REXX}}==
Line 3,505 ⟶ 4,142:
''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 3,559 ⟶ 4,196:
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 3,588 ⟶ 4,225:
===Without Warnsdorff===
The following class provides functionality for solving a hidato problem:
<
#
class Hidato
Line 3,642 ⟶ 4,279:
(msg ? [msg] : []) + str + [""]
end
end</
'''Test:'''
<
board1 = <<EOS
. 4
Line 3,674 ⟶ 4,311:
t0 = Time.now
Hidato.new(board3).solve
puts " #{Time.now - t0} sec"</
{{out}}
Line 3,723 ⟶ 4,360:
===With Warnsdorff===
I modify method as follows to implement [[wp:Knight's_tour#Warnsdorff|Warnsdorff]] like
<
#
class HLPsolver
Line 3,790 ⟶ 4,427:
(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 3,837 ⟶ 4,474:
t0 = Time.now
HLPsolver.new(board3).solve
puts " #{Time.now - t0} sec"</
Which produces:
Line 3,906 ⟶ 4,543:
HLPsolver may be used to solve [[Knight's tour#Ruby|Knight's tour]]:
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use std::cmp::{max, min};
use std::fmt;
use std::ops;
#[derive(Debug, Clone, PartialEq)]
struct Board {
cells: Vec<Vec<Option<u32>>>,
}
impl Board {
fn new(initial_board: Vec<Vec<u32>>) -> Self {
let b = initial_board
.iter()
.map(|r| {
r.iter()
.map(|c| if *c == u32::MAX { None } else { Some(*c) })
.collect()
})
.collect();
Board { cells: b }
}
fn height(&self) -> usize {
self.cells.len()
}
fn width(&self) -> usize {
self.cells[0].len()
}
}
impl ops::Index<(usize, usize)> for Board {
type Output = Option<u32>;
fn index(&self, (y, x): (usize, usize)) -> &Self::Output {
&self.cells[y][x]
}
}
impl ops::IndexMut<(usize, usize)> for Board {
/// Returns a mutable reference to an cell for a given 'x' 'y' coordinates
fn index_mut(&mut self, (y, x): (usize, usize)) -> &mut Option<u32> {
&mut self.cells[y][x]
}
}
impl fmt::Display for Board {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let output: Vec<String> = self
.cells
.iter()
.map(|r| {
let mut row = String::default();
r.iter().for_each(|c| match c {
None => row.push_str(format!("{:>2} ", " ").as_ref()),
Some(c) if c == &0 => row.push_str(format!("{:>2} ", ".").as_ref()),
Some(c) => row.push_str(format!("{:>2} ", c).as_ref()),
});
row
})
.collect();
write!(f, "{}", output.join("\n"))
}
}
/// Structure for holding puzzle related information.
#[derive(Clone, Debug)]
struct Puzzle {
/// The state of the board.
board: Board,
/// All the numbers which were given at puzzle setup:
/// the numbers which cannot be changed during solving the puzzle.
fixed: Vec<u32>,
/// Position of the first number (1).
start: (usize, usize),
}
impl Puzzle {
/// Creates a new puzzle
/// * `initial_board` contains the layout and the startin position.
///
/// - Simple numbers in the `initial_board` are considered as "fixed",
/// aka the solving does not change them
///
/// - As the board can be non-rectangular, all cells which are invalid or cannot be used
/// are marked with u32::MAX in the `initial_board`
fn new(initial_board: Vec<Vec<u32>>) -> Self {
let mut s: (usize, usize) = (0, 0);
let mut f = initial_board
.iter()
.enumerate()
.flat_map(|(y, r)| r.iter().enumerate().map(move |(x, c)| (y, x, *c)))
.filter(|(_, _, c)| (1..u32::MAX).contains(c))
.fold(Vec::new(), |mut fixed, (y, x, c)| {
fixed.push(c);
if c == 1 {
// store the position of the start
s = (y, x)
};
fixed
});
f.sort_unstable();
Puzzle {
board: Board::new(initial_board),
fixed: f,
start: s,
}
}
pub fn print_board(&self) {
println!("{}", self.board);
}
fn solver(&mut self, current: (usize, usize), n: &u32, mut next: usize) -> bool {
// reached the last number, solving successful
if n > self.fixed.last().unwrap() {
return true;
}
// check for exit conditions
match self.board[current] {
// cell outside of the board
None => return false,
//cell is already has a number in it
Some(c) if c != 0 && c != *n => return false,
//cell is empty, but the to be placed number is already matching the next fixed number
Some(c) if c == 0 && self.fixed[next] == *n => return false,
// continue
_ => (),
}
let mut backup: u32 = 0;
if self.board[current] == Some(*n) {
backup = *n;
next += 1;
}
self.board[current] = Some(*n);
for y in (max(current.0, 1) - 1)..=min(current.0 + 1, self.board.height() - 1) {
for x in (max(current.1, 1) - 1)..=min(current.1 + 1, self.board.width() - 1) {
if self.solver((y, x), &(n + 1), next) {
return true;
}
}
}
// unsuccessful branch, restore original value
self.board[current] = Some(backup);
false
}
pub fn solve(&mut self) {
let start = self.start;
self.solver(start, &1, 0);
}
}
fn main() {
let input = vec![
vec![0, 33, 35, 0, 0, u32::MAX, u32::MAX, u32::MAX],
vec![0, 0, 24, 22, 0, u32::MAX, u32::MAX, u32::MAX],
vec![0, 0, 0, 21, 0, 0, u32::MAX, u32::MAX],
vec![0, 26, 0, 13, 40, 11, u32::MAX, u32::MAX],
vec![27, 0, 0, 0, 9, 0, 1, u32::MAX],
vec![u32::MAX, u32::MAX, 0, 0, 18, 0, 0, u32::MAX],
vec![u32::MAX, u32::MAX, u32::MAX, u32::MAX, 0, 7, 0, 0],
vec![
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
5,
0,
],
];
let mut p = Puzzle::new(input);
p.print_board();
p.solve();
println!("\nSolution:");
p.print_board();
}
</syntaxhighlight>
{{out}}
<pre>
. 33 35 . .
. . 24 22 .
. . . 21 . .
. 26 . 13 40 11
27 . . . 9 . 1
. . 18 . .
. 7 . .
5 .
Solution:
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
</pre>
=={{header|Seed7}}==
<
var set of integer: given is {};
Line 4,006 ⟶ 4,861:
printBoard;
end if;
end func;</
{{out}}
Line 4,036 ⟶ 4,891:
=={{header|Tailspin}}==
{{trans|Java}}
<
def input:
'__ 33 35 __ __ . . .
Line 4,049 ⟶ 4,904:
templates hidato
composer setup
@: {row: 1, col: 1, givenInput:n´1:[]};
rule
rule
rule
rule
rule given: (
($given -> ..|@.
($given -> @.givenInput($): { row: $@.row, col: $@.col };)
$given
end setup
templates solve
when <~{row: <1..$@hidato.board::length>, col: <1..$@hidato.board(row´1)::length>}> do !VOID
when <{ n: <=$@hidato.given(last).n>, row: <=$@hidato.given(last).row>, col: <=$@hidato.given(last).col> }> do $@hidato.board !
when <?($@hidato.board($.row; $.col) <~=n´0|=$.n>)> do !VOID
when <?($@hidato.board($.row; $.col) <=n´0>)?($@hidato.given($.next) <{n: <=$.n>}>)> do !VOID
otherwise
def guess: $;
def back: $@hidato.board($.row; $.col);
def next: $ -> \(when <{n: <=$back>}> do n´($.next::raw + 1)! otherwise $.next!\);
@hidato.board($.row; $.col): $.n;
0..8 -> { next: $next, n: $guess.n::raw + 1, row: $guess.row::raw + $ ~/ 3 - 1, col: $guess.col::raw + $ mod 3 - 1 } -> #
@hidato.board($.row; $.col): $back;
end solve
@: $ -> setup;
{ next: n´1, $@.given(
end hidato
$input -> hidato -> '$... -> '$... -> ' $ -> \(when <=n´-1> do ' .' ! when <n´10..> do '$;' ! otherwise ' $;' !\);';
';
' ->!OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 4,096 ⟶ 4,952:
=={{header|Tcl}}==
<
global grid max filled
set max 1
Line 4,205 ⟶ 5,061:
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,216 ⟶ 5,072:
. . . . 0 7 0 0
. . . . . . 5 0
"</
{{out}}
<pre>
Line 4,242 ⟶ 5,098:
</pre>
More complex cases are solvable with an [[/Extended Tcl solution|extended version of this code]], though that has more onerous version requirements.
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./sort" for Sort
import "./fmt" for Fmt
var board = []
var given = []
var start = []
var setUp = Fn.new { |input|
var nRows = input.count
var puzzle = List.filled(nRows, null)
for (i in 0...nRows) puzzle[i] = input[i].split(" ")
var nCols = puzzle[0].count
var list = []
board = List.filled(nRows+2, null)
for (i in 0...board.count) board[i] = List.filled(nCols+2, -1)
for (r in 0...nRows) {
var row = puzzle[r]
for (c in 0...nCols) {
var cell = row[c]
if (cell == "_") {
board[r + 1][c + 1] = 0
} else if (cell != ".") {
var value = Num.fromString(cell)
board[r + 1][c + 1] = value
list.add(value)
if (value == 1) start = [r + 1, c + 1]
}
}
}
Sort.quick(list)
given = list
}
var solve // recursive
solve = Fn.new { |r, c, n, next|
if (n > given[-1]) return true
var back = board[r][c]
if (back != 0 && back != n) return false
if (back == 0 && given[next] == n) return false
var next2 = next
if (back == n) next2 = next2 + 1
board[r][c] = n
for (i in -1..1) {
for (j in -1..1) if (solve.call(r + i, c + j, n + 1, next2)) return true
}
board[r][c] = back
return false
}
var printBoard = Fn.new {
for (row in board) {
for (c in row) {
if (c == -1) {
System.write(" . ")
} else if (c > 0) {
Fmt.write("$2d ", c)
} else {
System.write("__ ")
}
}
System.print()
}
}
var input = [
"_ 33 35 _ _ . . .",
"_ _ 24 22 _ . . .",
"_ _ _ 21 _ _ . .",
"_ 26 _ 13 40 11 . .",
"27 _ _ _ 9 _ 1 .",
". . _ _ 18 _ _ .",
". . . . _ 7 _ _",
". . . . . . 5 _"
]
setUp.call(input)
printBoard.call()
System.print("\nFound:")
solve.call(start[0], start[1], 1, 0)
printBoard.call()</syntaxhighlight>
{{out}}
<pre>
. . . . . . . . . .
. __ 33 35 __ __ . . . .
. __ __ 24 22 __ . . . .
. __ __ __ 21 __ __ . . .
. __ 26 __ 13 40 11 . . .
. 27 __ __ __ 9 __ 1 . .
. . . __ __ 18 __ __ . .
. . . . . __ 7 __ __ .
. . . . . . . 5 __ .
. . . . . . . . . .
Found:
. . . . . . . . . .
. 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 .
. . . . . . . . . .
</pre>
=={{header|zkl}}==
{{trans|Python}}
<
#<<<
"0 33 35 0 0 X X X
Line 4,261 ⟶ 5,227:
solve(board,given, start.xplode(), 1);
println();
print_board(board);</
<
d:=D(-1," ", 0,"__");
foreach r in (board[1,-1]){
Line 4,298 ⟶ 5,264:
board[r][c]=back;
False
}</
{{out}}
<pre>
|