Solve a Hidato puzzle: Difference between revisions
m
no edit summary
m (→{{header|REXX}}: corrected the spelling for the puzzle name. -- ~~~~) |
mNo edit summary |
||
(86 intermediate revisions by 31 users not shown) | |||
Line 1:
{{task}}
The task is to write a program which solves [[wp:Hidato|Hidato (aka Hidoku) puzzles]].
The rules are:
Line 14:
* In a proper Hidato puzzle, the solution is unique.
<br>For example the following problem
[[File:Hidato_Start.png|center|Sample Hidato problem, from Wikipedia]]
Line 20:
[[File:HEnd.png|center|Solution to sample Hidato problem]]
;Related tasks:
* [[A* search algorithm]]
* [[N-queens problem]]
* [[Solve a Holy Knight's tour]]
* [[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}}==
<syntaxhighlight lang="autohotkey">SolveHidato(Grid, Locked, Max, row, col, num:=1, R:="", C:=""){
if (R&&C) ; if neighbors (not first iteration)
{
Grid[R, C] := ">" num ; place num in current neighbor and mark it visited ">"
row:=R, col:=C ; move to current neighbor
}
num++ ; increment num
if (num=max) ; if reached end
return map(Grid) ; return solution
if locked[num] ; if current num is a locked value
{
row := StrSplit((StrSplit(locked[num], ",").1) , ":").1 ; find row of num
col := StrSplit((StrSplit(locked[num], ",").1) , ":").2 ; find col of num
if SolveHidato(Grid, Locked, Max, row, col, num) ; solve for current location and value
return map(Grid) ; if solved, return solution
}
else
{
for each, value in StrSplit(Neighbor(row,col), ",")
{
R := StrSplit(value, ":").1
C := StrSplit(value, ":").2
if (Grid[R,C] = "") ; a hole or out of bounds
|| InStr(Grid[R, C], ">") ; visited
|| Locked[num+1] && !(Locked[num+1]~= "\b" R ":" C "\b") ; not neighbor of locked[num+1]
|| Locked[num-1] && !(Locked[num-1]~= "\b" R ":" C "\b") ; not neighbor of locked[num-1]
|| Locked[num] ; locked value
|| Locked[Grid[R, C]] ; locked cell
continue
if SolveHidato(Grid, Locked, Max, row, col, num, R, C) ; solve for current location, neighbor and value
return map(Grid) ; if solved, return solution
}
}
num-- ; step back
for i, line in Grid
for j, element in line
if InStr(element, ">") && (StrReplace(element, ">") >= num)
Grid[i, j] := "Y"
}
;--------------------------------
;--------------------------------
;--------------------------------
Neighbor(row,col){
R := row-1
loop, 9
{
DeltaC := Mod(A_Index, 3) ? Mod(A_Index, 3)-2 : 1
res .= (R=row && !DeltaC) ? "" : R ":" col+DeltaC ","
R := Mod(A_Index, 3) ? R : R+1
}
return Trim(res, ",")
}
;--------------------------------
map(Grid){
for i, row in Grid
{
for j, element in row
line .= (A_Index > 1 ? "`t" : "") . element
map .= (map<>""?"`n":"") line
line := ""
}
return StrReplace(map, ">")
}</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">;--------------------------------
Grid := [[ "Y" , 33 , 35 , "Y" , "Y"]
,[ "Y" , "Y" , 24 , 22 , "Y"]
,[ "Y" , "Y" , "Y" , 21 , "Y" , "Y"]
,[ "Y" , 26 , "Y" , 13 , 40 , 11 ]
,[ 27 , "Y" , "Y" , "Y" , 9 , "Y" , 1 ]
,[ "" , "" , "Y" , "Y" , 18 , "Y" , "Y"]
,[ "" , "" , "" , "" , "Y" , 7 , "Y" , "Y"]
,[ "" , "" , "" , "" , "" , "" , 5 , "Y"]]
;--------------------------------
; find locked cells, find row and col of first value "1" and max value
Locked := []
for i, line in Grid
for j, element in line
{
if element = 1
row :=i , col := j
if element is integer
Locked[element] := i ":" j "," Neighbor(i, j) ; save locked elements position and neighbors
, max := element > max ? element : max ; find max value
}
;--------------------------------
MsgBox, 262144, ,% SolveHidato(Grid, Locked, Max, row, col)
return</syntaxhighlight>
Outputs:<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|Bracmat}}==
<
( hidato
= Line solve lowest Ncells row column rpad
Line 134 ⟶ 340:
: ?board
& out$(hidato$!board)
);</
Output:
<pre>
Line 158 ⟶ 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 324 ⟶ 530:
return 0;
}</
{{out}}
<pre> Before:
Line 345 ⟶ 551:
17 7 6 3
5 4</pre>
=={{header|C sharp}}==
The same solver can solve Hidato, Holy Knight's Tour, Hopido and Numbrix puzzles.<br/>
The input can be an array of strings if each cell is one character. The length of the first row must be the number of columns in the puzzle.<br/>
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/>
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.
<syntaxhighlight lang="csharp">using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
using static System.Linq.Enumerable;
public class Solver
{
private static readonly (int dx, int dy)[]
//other puzzle types elided
hidatoMoves = {(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)};
private (int dx, int dy)[] moves;
public static void Main()
{
Print(new Solver(hidatoMoves).Solve(false, new [,] {
{ 0, 33, 35, 0, 0, -1, -1, -1 },
{ 0, 0, 24, 22, 0, -1, -1, -1 },
{ 0, 0, 0, 21, 0, 0, -1, -1 },
{ 0, 26, 0, 13, 40, 11, -1, -1 },
{ 27, 0, 0, 0, 9, 0, 1, -1 },
{ -1, -1, 0, 0, 18, 0, 0, -1 },
{ -1, -1, -1, -1, 0, 7, 0, 0 },
{ -1, -1, -1, -1, -1, -1, 5, 0 }
}));
}
public Solver(params (int dx, int dy)[] moves) => this.moves = moves;
public int[,] Solve(bool circular, params string[] puzzle)
{
var (board, given, count) = Parse(puzzle);
return Solve(board, given, count, circular);
}
public int[,] Solve(bool circular, int[,] puzzle)
{
var (board, given, count) = Parse(puzzle);
return Solve(board, given, count, circular);
}
private int[,] Solve(int[,] board, BitArray given, int count, bool circular)
{
var (height, width) = (board.GetLength(0), board.GetLength(1));
bool solved = false;
for (int x = 0; x < height && !solved; x++) {
solved = Range(0, width).Any(y => Solve(board, given, circular, (height, width), (x, y), count, (x, y), 1));
if (solved) return board;
}
return null;
}
private bool Solve(int[,] board, BitArray given, bool circular,
(int h, int w) size, (int x, int y) start, int last, (int x, int y) current, int n)
{
var (x, y) = current;
if (x < 0 || x >= size.h || y < 0 || y >= size.w) return false;
if (board[x, y] < 0) return false;
if (given[n - 1]) {
if (board[x, y] != n) return false;
} else if (board[x, y] > 0) return false;
board[x, y] = n;
if (n == last) {
if (!circular || AreNeighbors(start, current)) return true;
}
for (int i = 0; i < moves.Length; i++) {
var move = moves[i];
if (Solve(board, given, circular, size, start, last, (x + move.dx, y + move.dy), n + 1)) return true;
}
if (!given[n - 1]) board[x, y] = 0;
return false;
bool AreNeighbors((int x, int y) p1, (int x, int y) p2) => moves.Any(m => (p2.x + m.dx, p2.y + m.dy).Equals(p1));
}
private static (int[,] board, BitArray given, int count) Parse(string[] input)
{
(int height, int width) = (input.Length, input[0].Length);
int[,] board = new int[height, width];
int count = 0;
for (int x = 0; x < height; x++) {
string line = input[x];
for (int y = 0; y < width; y++) {
board[x, y] = y < line.Length && char.IsDigit(line[y]) ? line[y] - '0' : -1;
if (board[x, y] >= 0) count++;
}
}
BitArray given = Scan(board, count, height, width);
return (board, given, count);
}
private static (int[,] board, BitArray given, int count) Parse(int[,] input)
{
(int height, int width) = (input.GetLength(0), input.GetLength(1));
int[,] board = new int[height, width];
int count = 0;
for (int x = 0; x < height; x++)
for (int y = 0; y < width; y++)
if ((board[x, y] = input[x, y]) >= 0) count++;
BitArray given = Scan(board, count, height, width);
return (board, given, count);
}
private static BitArray Scan(int[,] board, int count, int height, int width)
{
var given = new BitArray(count + 1);
for (int x = 0; x < height; x++)
for (int y = 0; y < width; y++)
if (board[x, y] > 0) given[board[x, y] - 1] = true;
return given;
}
private static void Print(int[,] board)
{
if (board == null) {
WriteLine("No solution");
} else {
int w = board.Cast<int>().Where(i => i > 0).Max(i => (int?)Ceiling(Log10(i+1))) ?? 1;
string e = new string('-', w);
foreach (int x in Range(0, board.GetLength(0)))
WriteLine(string.Join(" ", Range(0, board.GetLength(1))
.Select(y => board[x, y] < 0 ? e : board[x, y].ToString().PadLeft(w, ' '))));
}
WriteLine();
}
}</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|C++}}==
<
#include <iostream>
#include <sstream>
Line 500 ⟶ 852:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
Output:
<pre>
Line 522 ⟶ 874:
01 20 21 24 25 26 35 34 33
</pre>
=={{header|Curry}}==
{{Works with|PAKCS}}
Probably not efficient.
<syntaxhighlight lang="curry">import CLPFD
import Constraint (andC, anyC)
import Findall (unpack)
import Integer (abs)
hidato :: [[Int]] -> Success
hidato path =
test path inner
& domain inner 1 40
& allDifferent inner
& andFD [x `near` y | x <- cells, y <- cells]
& labeling [] (concat path)
where
andFD = solve . foldr1 (#/\#)
cells = enumerate path
inner free
near :: (Int,Int,Int) -> (Int,Int,Int) -> Constraint
(x,rx,cx) `near` (y,ry,cy) = x #<=# y #/\# dist (y -# x)
#\/# x #># y #/\# dist (x -# y)
#\/# x #=# 0
#\/# y #=# 0
where
dist d = abs (rx - ry) #<=# d
#/\# abs (cx - cy) #<=# d
enumerate :: [[Int]] -> [(Int,Int,Int)]
enumerate xss = [(x,row,col) | (xs,row) <- xss `zip` [1..]
, (x ,col) <- xs `zip` [1..]
]
test [[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
,[ 0, A, 33, 35, B, C, 0, 0, 0, 0]
,[ 0, D, E, 24, 22, F, 0, 0, 0, 0]
,[ 0, G, H, I, 21, J, K, 0, 0, 0]
,[ 0, L, 26, M, 13, 40, 11, 0, 0, 0]
,[ 0, 27, N, O, P, 9, Q, 1, 0, 0]
,[ 0, 0, 0, R, S, 18, T, U, 0, 0]
,[ 0, 0, 0, 0, 0, V, 7, W, X, 0]
,[ 0, 0, 0, 0, 0, 0, 0, 5, Y, 0]
,[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
[ A, 33, 35, B, C
, D, E, 24, 22, F
, G, H, I, 21, J, K
, L, 26, M, 13, 40, 11
, 27, N, O, P, 9, Q, 1
, R, S, 18, T, U
, V, 7, W, X
, 5, Y
] = success
main = unpack hidato</syntaxhighlight>
{{Output}}
<pre>Execution time: 1440 msec. / elapsed: 2270 msec.
[[0,0,0,0,0,0,0,0,0,0],[0,32,33,35,36,37,0,0,0,0],[0,31,34,24,22,38,0,0,0,0],[0,30,25,23,21,12,39,0,0,0],[0,29,26,20,13,40,11,0,0,0],[0,27,28,14,19,9,10,1,0,0],[0,0,0,15,16,18,8,2,0,0],[0,0,0,0,0,17,7,6,3,0],[0,0,0,0,0,0,0,5,4,0],[0,0,0,0,0,0,0,0,0,0]]
More values? [y(es)/N(o)/a(ll)]</pre>
=={{header|D}}==
Line 527 ⟶ 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 607 ⟶ 1,021:
solve(start[0], start[1], 1);
printBoard;
}</
{{out}}
<pre> . . . . . . . . . .
Line 637 ⟶ 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 652 ⟶ 1,066:
bool[] flood;
this(in string input) pure @safe
in {
assert(!input.strip.empty);
Line 672 ⟶ 1,086:
(cell >= 1 && cell <= size));
if (cell > 0)
assert(i == known[
}
} body {
bool[Cell] pathSeen; // A set.
this.nRows = lines.length;
this.nCols = lines[0].split.length;
immutable size = nCols * nRows;
this.board.length =
this.board[] = emptyCell;
this.known.length =
this.flood.length =
auto boardMaxMutable = Cell.min;
Line 719 ⟶ 1,133:
private Pos idx(in size_t r, in size_t c) const pure nothrow @safe @nogc {
return r * nCols + c;
}
private uint nNeighbors(in Pos pos, ref Pos[8] neighbours)
const pure nothrow @safe @nogc {
immutable r = pos / nCols;
immutable c = pos % nCols;
Line 749 ⟶ 1,163:
/// Fill all free cells around 'cell' with true and write
/// output to variable "flood".
private void floodFill(in Pos pos) pure nothrow @safe @nogc {
Pos[8] n = void;
Line 763 ⟶ 1,177:
/// Check all empty cells are reachable from higher known cells.
private bool checkConnectity(in uint lowerBound) pure nothrow @safe @nogc {
flood[] = false;
Line 778 ⟶ 1,192:
}
private bool fill(in Pos pos, in uint n) pure nothrow @safe @nogc {
if ((board[pos] && board[pos] != n) ||
(known[n] && known[n] != pos))
Line 801 ⟶ 1,215:
}
void solve() pure nothrow @safe @nogc
in {
assert(!known.empty);
Line 851 ⟶ 1,265:
. . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."
);
}</
{{out}}
<pre>Problem:
Line 892 ⟶ 1,306:
. . 4 . 7 . 10 . 13 . 16 . 19 . 22 . 25 . 28 . 31 . 34 . 37 . 40 . 43 . 46 . 49 . 52 . 55 . 58 . 61 . 64 . 67 . 70 . 73 .
. . . 5 6 . . 11 12 . . 17 18 . . 23 24 . . 29 30 . . 35 36 . . 41 42 . . 47 48 . . 53 54 . . 59 60 . . 65 66 . . 71 72 .</pre>
=={{header|Elixir}}==
{{trans|Ruby}}
<syntaxhighlight lang="elixir"># Solve a Hidato Like Puzzle with Warnsdorff like logic applied
#
defmodule HLPsolver do
defmodule Cell do
defstruct value: -1, used: false, adj: []
end
def solve(str, adjacent, print_out\\true) do
board = setup(str)
if print_out, do: print(board, "Problem:")
{start, _} = Enum.find(board, fn {_,cell} -> cell.value==1 end)
board = set_adj(board, adjacent)
zbl = for %Cell{value: n} <- Map.values(board), into: %{}, do: {n, true}
try do
solve(board, start, 1, zbl, map_size(board))
IO.puts "No solution"
catch
{:ok, result} -> if print_out, do: print(result, "Solution:"),
else: result
end
end
defp solve(board, position, seq_num, zbl, goal) do
value = board[position].value
cond do
value > 0 and value != seq_num -> nil
value == 0 and zbl[seq_num] -> nil
true ->
cell = %Cell{board[position] | value: seq_num, used: true}
board = %{board | position => cell}
if seq_num == goal, do: throw({:ok, board})
Enum.each(wdof(board, cell.adj), fn pos ->
solve(board, pos, seq_num+1, zbl, goal)
end)
end
end
defp setup(str) do
lines = String.strip(str) |> String.split(~r/(\n|\r\n|\r)/) |> Enum.with_index
for {line,i} <- lines, {char,j} <- Enum.with_index(String.split(line)),
:error != Integer.parse(char), into: %{} do
{n,_} = Integer.parse(char)
{{i,j}, %Cell{value: n}}
end
end
defp set_adj(board, adjacent) do
Enum.reduce(Map.keys(board), board, fn {x,y},map ->
adj = Enum.map(adjacent, fn {i,j} -> {x+i, y+j} end)
|> Enum.reduce([], fn pos,acc -> if board[pos], do: [pos | acc], else: acc end)
Map.update!(map, {x,y}, fn cell -> %Cell{cell | adj: adj} end)
end)
end
defp wdof(board, adj) do # Warnsdorf's rule
Enum.reject(adj, fn pos -> board[pos].used end)
|> Enum.sort_by(fn pos ->
Enum.count(board[pos].adj, fn p -> not board[p].used end)
end)
end
def print(board, title) do
IO.puts "\n#{title}"
{xmin, xmax} = Map.keys(board) |> Enum.map(fn {x,_} -> x end) |> Enum.min_max
{ymin, ymax} = Map.keys(board) |> Enum.map(fn {_,y} -> y end) |> Enum.min_max
len = map_size(board) |> to_char_list |> length
space = String.duplicate(" ", len)
Enum.each(xmin..xmax, fn x ->
Enum.map_join(ymin..ymax, " ", fn y ->
case Map.get(board, {x,y}) do
nil -> space
cell -> to_string(cell.value) |> String.rjust(len)
end
end)
|> IO.puts
end)
end
end</syntaxhighlight>
'''Test:'''
<syntaxhighlight lang="elixir">adjacent = [{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}]
"""
. 4
0 7 0
1 0 0
"""
|> HLPsolver.solve(adjacent)
"""
0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
. . 0 0 18 0 0
. . . . 0 7 0 0
. . . . . . 5 0
"""
|> HLPsolver.solve(adjacent)
"""
1 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0
. . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0
. . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0
"""
|> HLPsolver.solve(adjacent)</syntaxhighlight>
{{out}}
<pre>
Problem:
4
0 7 0
1 0 0
Solution:
4
3 7 5
1 2 6
Problem:
0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
0 0 18 0 0
0 7 0 0
5 0
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
Problem:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Solution:
1 2 3 9 10 11 17 18 19 25 26 27 33 34 35 41 42 43 49 50 51
4 8 12 16 20 24 28 32 36 40 44 48 52
5 6 7 13 14 15 21 22 23 29 30 31 37 38 39 45 46 47 53
</pre>
=={{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,000 ⟶ 1,567:
store( {Key, Value}, Dict ) -> dict:store( Key, Value, Dict ).
</syntaxhighlight>
{{out}}
<pre>
Line 1,024 ⟶ 1,591:
17 7 6 3
5 4
</pre>
=={{header|Go}}==
{{trans|Java}}
<syntaxhighlight lang="go">package main
import (
"fmt"
"sort"
"strconv"
"strings"
)
var board [][]int
var start, given []int
func setup(input []string) {
/* This task is not about input validation, so
we're going to trust the input to be valid */
puzzle := make([][]string, len(input))
for i := 0; i < len(input); i++ {
puzzle[i] = strings.Fields(input[i])
}
nCols := len(puzzle[0])
nRows := len(puzzle)
list := make([]int, nRows*nCols)
board = make([][]int, nRows+2)
for i := 0; i < nRows+2; i++ {
board[i] = make([]int, nCols+2)
for j := 0; j < nCols+2; j++ {
board[i][j] = -1
}
}
for r := 0; r < nRows; r++ {
row := puzzle[r]
for c := 0; c < nCols; c++ {
switch cell := row[c]; cell {
case "_":
board[r+1][c+1] = 0
case ".":
break
default:
val, _ := strconv.Atoi(cell)
board[r+1][c+1] = val
list = append(list, val)
if val == 1 {
start = append(start, r+1, c+1)
}
}
}
}
sort.Ints(list)
given = make([]int, len(list))
for i := 0; i < len(given); i++ {
given[i] = list[i]
}
}
func solve(r, c, n, next int) bool {
if n > given[len(given)-1] {
return true
}
back := board[r][c]
if back != 0 && back != n {
return false
}
if back == 0 && given[next] == n {
return false
}
if back == n {
next++
}
board[r][c] = n
for i := -1; i < 2; i++ {
for j := -1; j < 2; j++ {
if solve(r+i, c+j, n+1, next) {
return true
}
}
}
board[r][c] = back
return false
}
func printBoard() {
for _, row := range board {
for _, c := range row {
switch {
case c == -1:
fmt.Print(" . ")
case c > 0:
fmt.Printf("%2d ", c)
default:
fmt.Print("__ ")
}
}
fmt.Println()
}
}
func main() {
input := []string{
"_ 33 35 _ _ . . .",
"_ _ 24 22 _ . . .",
"_ _ _ 21 _ _ . .",
"_ 26 _ 13 40 11 . .",
"27 _ _ _ 9 _ 1 .",
". . _ _ 18 _ _ .",
". . . . _ 7 _ _",
". . . . . . 5 _",
}
setup(input)
printBoard()
fmt.Println("\nFound:")
solve(start[0], start[1], 1, 0)
printBoard()
}</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|Haskell}}==
<syntaxhighlight lang="haskell">{-# LANGUAGE TupleSections #-}
{-# LANGUAGE Rank2Types #-}
import qualified Data.IntMap as I
import Data.IntMap (IntMap)
import Data.List
import Data.Maybe
import Data.Time.Clock
data BoardProblem = Board
{ cells :: IntMap (IntMap Int)
, endVal :: Int
, onePos :: (Int, Int)
, givens :: [Int]
} deriving (Show, Eq)
tupIns x y v m = I.insert x (I.insert y v (I.findWithDefault I.empty x m)) m
tupLookup x y m = I.lookup x m >>= I.lookup y
makeBoard =
(\x ->
x
{ givens = dropWhile (<= 1) $ sort $ givens x
}) .
foldl' --'
f
(Board I.empty 0 (0, 0) []) .
concatMap (zip [0 ..]) . zipWith (\y w -> map (y, ) $ words w) [0 ..]
where
f bd (x, (y, v)) =
if v == "."
then bd
else Board
(tupIns x y (read v) (cells bd))
(if read v > endVal bd
then read v
else endVal bd)
(if v == "1"
then (x, y)
else onePos bd)
(read v : givens bd)
hidato brd = listToMaybe $ h 2 (cells brd) (onePos brd) (givens brd)
where
h nval pmap (x, y) gs
| nval == endVal brd = [pmap]
| nval == head gs =
if null nvalAdj
then []
else h (nval + 1) pmap (fst $ head nvalAdj) (tail gs)
| not $ null nvalAdj = h (nval + 1) pmap (fst $ head nvalAdj) gs
| otherwise = hEmptyAdj
where
around =
[ (x - 1, y - 1)
, (x, y - 1)
, (x + 1, y - 1)
, (x - 1, y)
, (x + 1, y)
, (x - 1, y + 1)
, (x, y + 1)
, (x + 1, y + 1)
]
lkdUp = map (\(x, y) -> ((x, y), tupLookup x y pmap)) around
nvalAdj = filter ((== Just nval) . snd) lkdUp
hEmptyAdj =
concatMap
(\((nx, ny), _) -> h (nval + 1) (tupIns nx ny nval pmap) (nx, ny) gs) $
filter ((== Just 0) . snd) lkdUp
printCellMap cellmap = putStrLn $ concat strings
where
maxPos = xyBy I.findMax maximum
minPos = xyBy I.findMin minimum
xyBy :: (forall a. IntMap a -> (Int, a)) -> ([Int] -> Int) -> (Int, Int)
xyBy a b = (fst (a cellmap), b $ map (fst . a . snd) $ I.toList cellmap)
strings =
map
f
[ (x, y)
| y <- [snd minPos .. snd maxPos]
, x <- [fst minPos .. fst maxPos] ]
f (x, y) =
let z =
if x == fst maxPos
then "\n"
else " "
in case tupLookup x y cellmap of
Nothing -> " " ++ z
Just n ->
(if n < 10
then ' ' : show n
else show n) ++
z
main = do
let sampleBoard = makeBoard sample
printCellMap $ cells sampleBoard
printCellMap $ fromJust $ hidato sampleBoard
sample =
[ " 0 33 35 0 0"
, " 0 0 24 22 0"
, " 0 0 0 21 0 0"
, " 0 26 0 13 40 11"
, "27 0 0 0 9 0 1"
, ". . 0 0 18 0 0"
, ". . . . 0 7 0 0"
, ". . . . . . 5 0"
]</syntaxhighlight>
{{Out}}
<pre> 0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
0 0 18 0 0
0 7 0 0
5 0
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>
Line 1,029 ⟶ 1,875:
This is an Unicon-specific solution but could easily be adjusted to work in Icon.
<
record Pos(r,c)
Line 1,133 ⟶ 1,979:
QMouse(puzzle, goWest(), self, val)
QMouse(puzzle, goNW(), self, val)
end</
Sample run:
Line 1,162 ⟶ 2,008:
->
</pre>
=={{header|Java}}==
{{trans|D}}
{{works with|Java|7}}
<syntaxhighlight lang="java">import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Hidato {
private static int[][] board;
private static int[] given, start;
public static void main(String[] args) {
String[] input = {"_ 33 35 _ _ . . .",
"_ _ 24 22 _ . . .",
"_ _ _ 21 _ _ . .",
"_ 26 _ 13 40 11 . .",
"27 _ _ _ 9 _ 1 .",
". . _ _ 18 _ _ .",
". . . . _ 7 _ _",
". . . . . . 5 _"};
setup(input);
printBoard();
System.out.println("\nFound:");
solve(start[0], start[1], 1, 0);
printBoard();
}
private static void setup(String[] input) {
/* This task is not about input validation, so
we're going to trust the input to be valid */
String[][] puzzle = new String[input.length][];
for (int i = 0; i < input.length; i++)
puzzle[i] = input[i].split(" ");
int nCols = puzzle[0].length;
int nRows = puzzle.length;
List<Integer> list = new ArrayList<>(nRows * nCols);
board = new int[nRows + 2][nCols + 2];
for (int[] row : board)
for (int c = 0; c < nCols + 2; c++)
row[c] = -1;
for (int r = 0; r < nRows; r++) {
String[] row = puzzle[r];
for (int c = 0; c < nCols; c++) {
String cell = row[c];
switch (cell) {
case "_":
board[r + 1][c + 1] = 0;
break;
case ".":
break;
default:
int val = Integer.parseInt(cell);
board[r + 1][c + 1] = val;
list.add(val);
if (val == 1)
start = new int[]{r + 1, c + 1};
}
}
}
Collections.sort(list);
given = new int[list.size()];
for (int i = 0; i < given.length; i++)
given[i] = list.get(i);
}
private static boolean solve(int r, int c, int n, int next) {
if (n > given[given.length - 1])
return true;
if (board[r][c] != 0 && board[r][c] != n)
return false;
if (board[r][c] == 0 && given[next] == n)
return false;
int back = board[r][c];
if (back == n)
next++;
board[r][c] = n;
for (int i = -1; i < 2; i++)
for (int j = -1; j < 2; j++)
if (solve(r + i, c + j, n + 1, next))
return true;
board[r][c] = back;
return false;
}
private static void printBoard() {
for (int[] row : board) {
for (int c : row) {
if (c == -1)
System.out.print(" . ");
else
System.out.printf(c > 0 ? "%2d " : "__ ", c);
}
System.out.println();
}
}
}</syntaxhighlight>
Output:
<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|Julia}}==
This solution utilizes a Hidato puzzle solver module which is also used for the Hopido and knight move tasks.
<syntaxhighlight lang="julia">module Hidato
export hidatosolve, printboard, hidatoconfigure
function hidatoconfigure(str)
lines = split(str, "\n")
nrows, ncols = length(lines), length(split(lines[1], r"\s+"))
board = fill(-1, (nrows, ncols))
presets = Vector{Int}()
starts = Vector{CartesianIndex{2}}()
maxmoves = 0
for (i, line) in enumerate(lines), (j, s) in enumerate(split(strip(line), r"\s+"))
c = s[1]
if c == '_' || (c == '0' && length(s) == 1)
board[i, j] = 0
maxmoves += 1
elseif c == '.'
continue
else # numeral, get 2 digits
board[i, j] = parse(Int, s)
push!(presets, board[i, j])
if board[i, j] == 1
push!(starts, CartesianIndex(i, j))
end
maxmoves += 1
end
end
board, maxmoves, sort!(presets), length(starts) == 1 ? starts : findall(x -> x == 0, board)
end
function hidatosolve(board, maxmoves, movematrix, fixed, row, col, sought)
if sought > maxmoves
return true
elseif (0 != board[row, col] != sought) || (board[row, col] == 0 && sought in fixed)
return false
end
backnum = board[row, col] == sought ? sought : 0
board[row, col] = sought # try board with this cell set to next number
for move in movematrix
i, j = row + move[1], col + move[2]
if (0 < i <= size(board)[1]) && (0 < j <= size(board)[2]) &&
hidatosolve(board, maxmoves, movematrix, fixed, i, j, sought + 1)
return true
end
end
board[row, col] = backnum # return board to original state
false
end
function printboard(board, emptysquare= "__ ", blocked = " ")
d = Dict(-1 => blocked, 0 => emptysquare, -2 => "\n")
map(x -> d[x] = rpad(lpad(string(x), 2), 3), 1:maximum(board))
println(join([d[i] for i in hcat(board, fill(-2, size(board)[1]))'], ""))
end
end # module
</syntaxhighlight><syntaxhighlight lang="julia">using .Hidato
hidat = """
__ 33 35 __ __ . . .
__ __ 24 22 __ . . .
__ __ __ 21 __ __ . .
__ 26 __ 13 40 11 . .
27 __ __ __ 9 __ 1 .
. . __ __ 18 __ __ .
. . . . __ 7 __ __
. . . . . . 5 __"""
const kingmoves = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
board, maxmoves, fixed, starts = hidatoconfigure(hidat)
printboard(board)
hidatosolve(board, maxmoves, kingmoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
</syntaxhighlight>{{output}}<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|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">// version 1.2.0
lateinit var board: List<IntArray>
lateinit var given: IntArray
lateinit var start: IntArray
fun setUp(input: List<String>) {
val nRows = input.size
val puzzle = List(nRows) { input[it].split(" ") }
val nCols = puzzle[0].size
val list = mutableListOf<Int>()
board = List(nRows + 2) { IntArray(nCols + 2) { -1 } }
for (r in 0 until nRows) {
val row = puzzle[r]
for (c in 0 until nCols) {
val cell = row[c]
if (cell == "_") {
board[r + 1][c + 1] = 0
}
else if (cell != ".") {
val value = cell.toInt()
board[r + 1][c + 1] = value
list.add(value)
if (value == 1) start = intArrayOf(r + 1, c + 1)
}
}
}
list.sort()
given = list.toIntArray()
}
fun solve(r: Int, c: Int, n: Int, next: Int): Boolean {
if (n > given[given.lastIndex]) return true
val 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++
board[r][c] = n
for (i in -1..1)
for (j in -1..1)
if (solve(r + i, c + j, n + 1, next2)) return true
board[r][c] = back
return false
}
fun printBoard() {
for (row in board) {
for (c in row) {
if (c == -1)
print(" . ")
else
print(if (c > 0) "%2d ".format(c) else "__ ")
}
println()
}
}
fun main(args: Array<String>) {
var input = listOf(
"_ 33 35 _ _ . . .",
"_ _ 24 22 _ . . .",
"_ _ _ 21 _ _ . .",
"_ 26 _ 13 40 11 . .",
"27 _ _ _ 9 _ 1 .",
". . _ _ 18 _ _ .",
". . . . _ 7 _ _",
". . . . . . 5 _"
)
setUp(input)
printBoard()
println("\nFound:")
solve(start[0], start[1], 1, 0)
printBoard()
}</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|Mathprog}}==
<
Find a solution to a Hidato problem
Line 1,228 ⟶ 2,408:
;
end;</
Using the data in the model produces the following:
{{out}}
Line 1,472 ⟶ 2,652:
</pre>
=={{header|
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]], #] &];
,
{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 *)
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},
{{5, 5}, {40}},
{{6, 5}, {11}},
{{4,
{{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}}==
<syntaxhighlight lang="nim">import strutils, algorithm, sequtils, strformat
type Hidato = object
board: seq[seq[int]]
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 in 0 .. result.board.high:
for j in 0 .. result.board[0].high:
result.board[i][j] = -1
for r, row in lines:
for c, cell in row.splitWhitespace().pairs():
case cell
of "__" :
result.board[r + 1][c + 1] = 0
continue
of "." :
continue
else :
let val = parseInt(cell)
result.board[r + 1][c + 1] = val
result.given.add(val)
if val == 1:
result.start = (r + 1, c + 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 1,578 ⟶ 3,240:
=={{header|Perl}}==
<
use List::Util 'max';
Line 1,661 ⟶ 3,323:
print "\033[2J";
try_fill(1, $known[1]);</
32 33 35 36 37
31 34 24 22 38
Line 1,670 ⟶ 3,332:
17 7 6 3
5 4
=={{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: #008080;">else</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'_'</span> <span style="color: #008080;">then</span>
<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;">"""
__ 33 35 __ __ .. .. ..
__ __ 24 22 __ .. .. ..
__ __ __ 21 __ __ .. ..
__ 26 __ 13 40 11 .. ..
27 __ __ __ 9 __ 1 ..
.. .. __ __ 18 __ __ ..
.. .. .. .. __ 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;">"""
1 _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . 74
. . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ . _ .
. . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."""</span>
<span style="color: #000000;">Hidato</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">74</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board4</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
54 __ 60 59 __ 67 __ 69 __
__ 55 __ __ 63 65 __ 72 71
51 50 56 62 __ .. .. .. ..
__ __ __ 14 .. .. 17 __ ..
48 10 11 .. 15 __ 18 __ 22
__ 46 __ .. 3 __ 19 23 __
__ 44 __ 5 __ 1 33 32 __
__ 43 7 __ 36 __ 27 __ 31
42 __ __ 38 __ 35 28 __ 30"""</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;">"""
__ 58 __ 60 __ __ 63 66 __
57 55 59 53 49 __ 65 __ 68
__ 8 __ __ 50 __ 46 45 __
10 6 __ .. .. .. __ 43 70
__ 11 12 .. .. .. 72 71 __
__ 14 __ .. .. .. 30 39 __
15 3 17 __ 28 29 __ __ 40
__ __ 19 22 __ __ 37 36 __
1 20 __ 24 __ 26 __ 34 33"""</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;">"""
1 __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. __ __ .. .. .. 82
.. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ ..
.. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. .. __ .. __ .. ..
__ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. __ __ __ .. .. .."""</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">
32 33 35 36 37 . . .
31 34 24 22 38 . . .
30 25 23 21 12 39 . .
29 26 20 13 40 11 . .
27 28 14 19 9 10 1 .
. . 15 16 18 8 2 .
. . . . 17 7 6 3
. . . . . . 5 4
solution found in 760 tries (0.00s)
. 4 .
3 7 5
1 2 6
solution found in 10 tries (0.00s)
1 2 3 . . 8 9 . . 14 15 . . 20 21 . . 26 27 . . 32 33 . . 38 39 . . 44 45 . . 50 51 . . 56 57 . . 62 63 . . 68 69 . . 74
. . 4 . 7 . 10 . 13 . 16 . 19 . 22 . 25 . 28 . 31 . 34 . 37 . 40 . 43 . 46 . 49 . 52 . 55 . 58 . 61 . 64 . 67 . 70 . 73 .
. . . 5 6 . . 11 12 . . 17 18 . . 23 24 . . 29 30 . . 35 36 . . 41 42 . . 47 48 . . 53 54 . . 59 60 . . 65 66 . . 71 72 .
solution found in 74 tries (0.00s)
54 53 60 59 58 67 66 69 70
52 55 61 57 63 65 68 72 71
51 50 56 62 64 . . . .
49 12 13 14 . . 17 21 .
48 10 11 . 15 16 18 20 22
47 46 9 . 3 2 19 23 24
45 44 8 5 4 1 33 32 25
41 43 7 6 36 34 27 26 31
42 40 39 38 37 35 28 29 30
solution found in 106 tries (0.00s)
56 58 54 60 61 62 63 66 67
57 55 59 53 49 47 65 64 68
9 8 52 51 50 48 46 45 69
10 6 7 . . . 44 43 70
5 11 12 . . . 72 71 42
4 14 13 . . . 30 39 41
15 3 17 18 28 29 38 31 40
2 16 19 22 25 27 37 36 32
1 20 21 24 23 26 35 34 33
solution found in 495 tries (0.00s)
1 2 . . . 10 11 . . . 19 20 . . . 28 29 . . . 37 38 . . . 46 47 . . . 55 56 . . . 64 65 . . . 73 74 . . . 82
. . 3 . 9 . . 12 . 18 . . 21 . 27 . . 30 . 36 . . 39 . 45 . . 48 . 54 . . 57 . 63 . . 66 . 72 . . 75 . 81 .
. 4 . 8 . . 13 . 17 . . 22 . 26 . . 31 . 35 . . 40 . 44 . . 49 . 53 . . 58 . 62 . . 67 . 71 . . 76 . 80 . .
5 6 7 . . 14 15 16 . . 23 24 25 . . 32 33 34 . . 41 42 43 . . 50 51 52 . . 59 60 61 . . 68 69 70 . . 77 78 79 . . .
solution found in 82 tries (0.02s)
</pre>
=={{header|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 1,791 ⟶ 3,661:
(disp Grid 0
'((This)
(if (: val) (align 3 @) " ") ) ) ) )</
Test:
<
(quote
(T 33 35 T T)
Line 1,802 ⟶ 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 1,826 ⟶ 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 1,925 ⟶ 3,795:
my_write_1(X) :-
writef('%3r', [X]).</
{{out}}
<pre>?- hidato.
Line 1,939 ⟶ 3,809:
=={{header|Python}}==
<
given = []
start = None
Line 2,007 ⟶ 3,877:
solve(start[0], start[1], 1)
print
print_board()</
{{out}}
<pre> __ 33 35 __ __
Line 2,028 ⟶ 3,898:
=={{header|Racket}}==
===Standalone===
Algorithm is depth first search for each number, repeating for all numbers in ascending order.
It currently runs slowish due to temporary shortcomings in untyped Racket's array indexing, but finished
immediately when tested with custom 2d vector library.
<syntaxhighlight lang="racket">
#lang racket
(require math/array)
Line 2,102 ⟶ 3,973:
;main function
(define (hidato board) (put-path board (hidato-path board)))
</syntaxhighlight>
{{out}}
<pre>
Line 2,116 ⟶ 3,987:
#[#f #f #f #f #f #f 5 4]])
</pre>
===Using Hidato Family Solver from [[Solve a Numbrix puzzle#Racket|Numbrix]]===
This solution uses the module "hidato-family-solver.rkt" from
[[Solve a Numbrix puzzle#Racket]]. The difference between the two is
essentially the neighbourhood function.
<syntaxhighlight lang="racket">#lang racket
(require "hidato-family-solver.rkt")
(define moore-neighbour-offsets
'((+1 0) (-1 0) (0 +1) (0 -1) (+1 +1) (-1 -1) (-1 +1) (+1 -1)))
(define solve-hidato (solve-hidato-family moore-neighbour-offsets))
(displayln
(puzzle->string
(solve-hidato
#(#( 0 33 35 0 0)
#( 0 0 24 22 0)
#( 0 0 0 21 0 0)
#( 0 26 0 13 40 11)
#(27 0 0 0 9 0 1)
#( _ _ 0 0 18 0 0)
#( _ _ _ _ 0 7 0 0)
#( _ _ _ _ _ _ 5 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|Raku}}==
(formerly Perl 6)
This uses a Warnsdorff solver, which cuts down the number of tries by more than a factor of six over the brute force approach. This same solver is used in:
* [[Solve a Hidato puzzle#Raku|Solve a Hidato puzzle]]
* [[Solve a Hopido puzzle#Raku|Solve a Hopido puzzle]]
* [[Solve a Holy Knight's tour#Raku|Solve a Holy Knight's tour]]
* [[Solve a Numbrix puzzle#Raku|Solve a Numbrix puzzle]]
* [[Solve the no connection puzzle#Raku|Solve the no connection puzzle]]
<syntaxhighlight lang="raku" line>my @adjacent = [-1, -1], [-1, 0], [-1, 1],
[ 0, -1], [ 0, 1],
[ 1, -1], [ 1, 0], [ 1, 1];
solveboard q:to/END/;
__ 33 35 __ __ .. .. ..
__ __ 24 22 __ .. .. ..
__ __ __ 21 __ __ .. ..
__ 26 __ 13 40 11 .. ..
27 __ __ __ 9 __ 1 ..
.. .. __ __ 18 __ __ ..
.. .. .. .. __ 7 __ __
.. .. .. .. .. .. 5 __
END
sub solveboard($board) {
my $max = +$board.comb(/\w+/);
my $width = $max.chars;
my @grid;
my @known;
my @neigh;
my @degree;
@grid = $board.lines.map: -> $line {
[ $line.words.map: { /^_/ ?? 0 !! /^\./ ?? Rat !! $_ } ]
}
sub neighbors($y,$x --> List) {
eager gather for @adjacent {
my $y1 = $y + .[0];
my $x1 = $x + .[1];
take [$y1,$x1] if defined @grid[$y1][$x1];
}
}
for ^@grid -> $y {
for ^@grid[$y] -> $x {
if @grid[$y][$x] -> $v {
@known[$v] = [$y,$x];
}
if @grid[$y][$x].defined {
@neigh[$y][$x] = neighbors($y,$x);
@degree[$y][$x] = +@neigh[$y][$x];
}
}
}
print "\e[0H\e[0J";
my $tries = 0;
try_fill 1, @known[1];
sub try_fill($v, $coord [$y,$x] --> Bool) {
return True if $v > $max;
$tries++;
my $old = @grid[$y][$x];
return False if +$old and $old != $v;
return False if @known[$v] and @known[$v] !eqv $coord;
@grid[$y][$x] = $v; # conjecture grid value
print "\e[0H"; # show conjectured board
for @grid -> $r {
say do for @$r {
when Rat { ' ' x $width }
when 0 { '_' x $width }
default { .fmt("%{$width}d") }
}
}
my @neighbors = @neigh[$y][$x][];
my @degrees;
for @neighbors -> \n [$yy,$xx] {
my $d = --@degree[$yy][$xx]; # conjecture new degrees
push @degrees[$d], n; # and categorize by degree
}
for @degrees.grep(*.defined) -> @ties {
for @ties.reverse { # reverse works better for this hidato anyway
return True if try_fill $v + 1, $_;
}
}
for @neighbors -> [$yy,$xx] {
++@degree[$yy][$xx]; # undo degree conjectures
}
@grid[$y][$x] = $old; # undo grid value conjecture
return False;
}
say "$tries tries";
}</syntaxhighlight>
=={{header|REXX}}==
Programming note: the coördinates for the cells used are the same as an X Y grid, that is,
<br>the bottom left-most cell is 1 1 and the tenth cell on row 2
<br>If ''any'' marker is negative, then it's assumed to be a Numbrix puzzle (and the absolute value is used).
<br>Over half of the REXX program deals with validating the input and displaying the puzzle.
''Hidato'' and ''Numbrix'' are registered trademarks.
<syntaxhighlight lang="rexx">/*REXX program solves a Numbrix (R) puzzle, it also displays the puzzle and solution. */
maxR=0; maxC=0; maxX=0; minR=9e9;
parse arg xxx; PZ='Hidato puzzle'
xxx=translate(xxx, , "/\;:_", ',') /*also allow other characters as comma.*/
do while
x=abs(x) /*use │x│ */
end
minR=min(minR,r); maxR=max(maxR,r); minC=min(minC,c); maxC=max(maxC,c)
if x==1 then do; !r=r; !c=c; end /*the START cell. */
if _\=='' then call err "cell at" r c 'is already occupied with:' _
@.r.c=x; c=c+1; cells=cells+1 /*assign a mark. */
if x==. then iterate /*is a hole? Skip*/
if \datatype(x,'W') then call err 'illegal marker specified:' x
end /*while
end /*while
call
Nr = '0 1
Nc = '1 0 -1 0
pMoves=words(Nr) -4*(left(PZ,1)=='N') /*is this to be a Numbrix puzzle ? */
do i=1 for pMoves; Nr.i=word(Nr,i); Nc.i=word(Nc,i); end /*for fast moves. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
err: say; say '***error*** (from' PZ"): " arg(1); say; exit 13
/*──────────────────────────────────────────────────────────────────────────────────────*/
next: procedure expose @. Nr. Nc. cells pMoves; parse arg #,r,c; ##=#+1
do t=1 for pMoves /* [↓] try some moves. */
parse value r+Nr.t c+Nc.t with nr nc /*next move coördinates.*/
if @.nr.nc==. then do;
if #==cells
if next(##,nr,nc)
@.nr.nc=. /*undo the above move. */
iterate /*go & try another move.*/
end
if @.nr.nc==# then do /*
if #==cells
if next(##,nr,nc)
end
end /*t*/
return 0 /*
/*──────────────────────────────────────────────────────────────────────────────────────*/
if
w=max(2,length(cells)); do r=maxR to minR by -1; _=
do c=minC to maxC; _=_ right(@.r.c,w); end /*c*/
say;
'''output''' when using the following as input:
<pre>
. 33 35 . .
Line 2,183 ⟶ 4,209:
5 .
A solution for the Hidato puzzle exists.
32 33 35 36 37
Line 2,198 ⟶ 4,225:
===Without Warnsdorff===
The following class provides functionality for solving a hidato problem:
<syntaxhighlight lang="ruby"># Solve a Hidato Puzzle
#
class Hidato
Cell = Struct.new(:value, :used, :adj)
ADJUST = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
def initialize(board, pout=true)
@
board.each_line do |line|
@board << line.split.map{|n| Cell[Integer(n), false] rescue nil} + [nil]
end
@board << [] # frame (Sentinel value : nil)
@board.each_with_index do |row, x|
row.each_with_index do |cell, y|
if cell
@sx, @sy = x, y if cell.value==1 # start position
cell.adj = ADJUST.map{|dx,dy| [x+dx,y+dy]}.select{|xx,yy| @board[xx][yy]}
end
end
end
@xmax = @board.size - 1
@ymax = @board.map(&:size).max - 1
@end = @board.flatten.compact.size
puts to_s('Problem:') if pout
end
def solve
@zbl = Array.new(@end+1, false)
@board.flatten.compact.each{|cell| @zbl[cell.value] = true}
puts (try(@board[@sx][@sy], 1) ? to_s('Solution:') : "No solution")
end
def try(cell, seq_num)
return true if seq_num > @end
return false if cell.used
value = cell.value
return false if value > 0 and value != seq_num
return false if value == 0 and @zbl[seq_num]
cell.used = true
cell.adj.each do |x, y|
if try(@board[x][y], seq_num+1)
cell.value = seq_num
return true
end
end
cell.used = false
end
def to_s(msg=nil)
str = (0...@xmax).map do |x|
(0...@ymax).map{|y| "%3s" % ((c=@board[x][y]) ? c.value : c)}.join
end
(msg ? [msg] : []) + str + [""]
end</syntaxhighlight>
'''Test:'''
<syntaxhighlight lang="ruby"># Which may be used as follows to solve Evil Case 1:
board1 = <<EOS
. 4
1 0 0
EOS
Hidato.new(board1).solve
# Which may be used as follows to solve this tasks example:
board2 = <<EOS
0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
. . 0 0 18 0 0
. . . . 0 7 0 0
. . . . . . 5 0
EOS
Hidato.new(board2).solve
# Which may be used as follows to solve The Snake in the Grass:
board3 = <<EOS
1 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 74
. . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 .
. . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 .
EOS
t0 = Time.now
Hidato.new(board3).solve
puts " #{Time.now - t0} sec"</syntaxhighlight>
{{out}}
<pre>
Problem:
4
0
1 0 0
Solution:
4
3 7 5
1 2 6
Problem:
0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
0 0 18 0 0
0 7 0 0
5 0
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
Problem:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 74
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Solution:
1 2 3 8 9 14 15 20 21 26 27 32 33 38 39 44 45 50 51 56 57 62 63 68 69 74
4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73
5 6 11 12 17 18 23 24 29 30 35 36 41 42 47 48 53 54 59 60 65 66 71 72
40.198299 sec
</pre>
===
I modify
<syntaxhighlight lang="ruby"># Solve a Hidato Like Puzzle with Warnsdorff like logic applied
#
class HLPsolver
attr_reader :board
Cell = Struct.new(:value, :used, :adj)
def initialize(board, pout=true)
@
frame = ADJACENT.flatten.map(&:abs).max
@board << line.split.map{|n| Cell[Integer(n), false] rescue nil} + [nil]*frame
end
frame.times {@board << []} # frame (Sentinel value : nil)
@board.each_with_index do |row, x|
row.each_with_index do |cell, y|
if cell
@sx, @sy = x, y if cell.value==1 # start position
cell.adj = ADJACENT.map{|dx,dy| [x+dx,y+dy]}.select{|xx,yy| @board[xx][yy]}
end
end
end
@xmax = @board.size - frame
@ymax = @board.map(&:size).max - frame
@end = @board.flatten.compact.size
@format = " %#{@end.to_s.size}s"
puts to_s('Problem:') if pout
end
def solve
@zbl = Array.new(@end+1, false)
@board.flatten.compact.each{|cell| @zbl[cell.value] = true}
puts (try(@board[@sx][@sy], 1) ? to_s('Solution:') : "No solution")
end
def try(cell, seq_num)
return false if value > 0 and value != seq_num
return false if value == 0 and @zbl[seq_num]
cell.used
if seq_num == @end
cell.value = seq_num
return true
end
a = []
cell.adj.each_with_index do |(x, y), n|
cl = @board[x][y]
a << [wdof(cl.adj)*10+n, x, y] unless cl.used
end
a.sort.each do |key, x, y|
if try(@board[x][y], seq_num+1)
cell.value = seq_num
return true
end
end
def wdof(adj)
adj.count {|x,y| not @board[x][y].used}
end
def
str = (0...@xmax).map do |x|
(0...@ymax).map{|y| @format % ((c=@board[x][y]) ? c.value : c)}.join
end
(msg ? [msg] : []) + str + [""]
end
end</syntaxhighlight>
Which may be used as follows to solve Hidato Puzzles:
<syntaxhighlight lang="ruby">require 'HLPsolver'
ADJACENT = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
# solve Evil Case 1:
board1 = <<EOS
. 4
0 7 0
1 0 0
EOS
HLPsolver.new(board1).solve
boardx = <<EOS
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
EOS
HLPsolver.new(boardx).solve
# solve this tasks example:
board2 = <<EOS
0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
. . 0 0 18 0 0
. . . . 0 7 0 0
. . . . . . 5 0
EOS
HLPsolver.new(board2).solve
#solve The Snake in the Grass:
board3 = <<EOS
1 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 74
. . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 .
. . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 .
EOS
t0 = Time.now
HLPsolver.new(board3).solve
puts " #{Time.now - t0} sec"</syntaxhighlight>
Which produces:
<pre>
Problem:
4
0 7
1 0 0
Solution:
4
3 7 5
1 2 6
Problem:
0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Solution:
33 34 36 37 41 42 43 44
32 35 38 40 56 55 46 45
2 31 39 57 59 60 54 47
3 1 30 58 61 62 53 48
4 6 18 29 63 64 52 49
5 7 17 19 28 51 50 25
8 11 13 16 20 27 26 24
9 10 12 14 15 21 22 23
Problem:
0 33 35 0 0
0 0 24 22 0
0 0 0 21 0 0
0 26 0 13 40 11
27 0 0 0 9 0 1
0 0 18 0 0
0 7 0 0
5 0
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
Problem:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 74
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Solution:
1 2 3 8 9 14 15 20 21 26 27 32 33 38 39 44 45 50 51 56 57 62 63 68 69 74
4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73
5 6 11 12 17 18 23 24 29 30 35 36 41 42 47 48 53 54 59 60 65 66 71 72
0.003001 sec
</pre>
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 {
r.iter()
.map(|c| if *c == u32::MAX { None } else { Some(*c) })
.collect()
})
.collect();
Board { cells: b }
}
fn
}
fn width(&self) -> usize {
self.cells[0].len()
}
impl ops::Index<(usize, usize)> for Board {
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
31 34 24 22 38
30 25 23
29 26 20 13 40 11
27 28 14 19
5 4
</pre>
=={{header|Seed7}}==
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
var set of integer: given is {};
var array array integer: board is 0 times 0 times 0;
var integer: startRow is 0;
var integer: startColumn is 0;
const proc: setup (in array string: input) is func
local
var integer: r is 0;
var integer: c is 0;
var array string: row is 0 times "";
var string: cell is "";
var integer: value is 0;
begin
board := (length(input) + 2) times 0 times 0;
for key r range input do
row := split(input[r], " ");
board[r + 1] := (length(row) + 2) times - 1;
for key c range row do
cell := row[c];
if cell = "_" then
board[r + 1][c + 1] := 0;
elsif cell[1] in {'0' .. '9'} then
value := integer parse cell;
board[r + 1][c + 1] := value;
incl(given, value);
if value = 1 then
startRow := r + 1;
startColumn := c + 1;
end if;
end if;
end for;
end for;
board[1] := (length(row) + 2) times - 1;
board[length(input) + 2] := (length(row) + 2) times - 1;
end func;
const func boolean: solve (in integer: r, in integer: c, in integer: n) is func
result
var boolean: solved is FALSE;
local
var integer: back is 0;
var integer: i is 0;
var integer: j is 0;
begin
if n > max(given) then
solved := TRUE;
elsif board[r][c] = 0 and n not in given or board[r][c] = n then
back := board[r][c];
board[r][c] := n;
for i range -1 to 1 until solved do
for j range -1 to 1 until solved do
solved := solve(r + i, c + j, n + 1);
end for;
end for;
if not solved then
board[r][c] := back;
end if;
end if;
end func;
const proc: printBoard is func
local
var integer: r is 0;
var integer: c is 0;
begin
for key r range board do
for c range board[r] do
if c = -1 then
write(" . ");
elsif c > 0 then
write(c lpad 2 <& " ");
else
write("__ ");
end if;
end for;
writeln;
end for;
end func;
const proc: main is func
local
const array string: input is [] ("_ 33 35 _ _ . . .",
"_ _ 24 22 _ . . .",
"_ _ _ 21 _ _ . .",
"_ 26 _ 13 40 11 . .",
"27 _ _ _ 9 _ 1 .",
". . _ _ 18 _ _ .",
". . . . _ 7 _ _",
". . . . . . 5 _");
begin
setup(input);
printBoard;
writeln;
if solve(startRow, startColumn, 1) then
writeln("Found:");
printBoard;
end if;
end func;</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|Tailspin}}==
{{trans|Java}}
<syntaxhighlight lang="tailspin">
def input:
'__ 33 35 __ __ . . .
__ __ 24 22 __ . . .
__ __ __ 21 __ __ . .
__ 26 __ 13 40 11 . .
27 __ __ __ 9 __ 1 .
. . __ __ 18 __ __ .
. . . . __ 7 __ __
. . . . . . 5 __';
templates hidato
composer setup
data givenInput <n´1:[<´{}´ ={}|{row: <row>, col: <col>}>*]> local
@: {row: 1, col: 1, givenInput:n´1:[]};
{ board: row´1:[ <line>+ ], given: $@.givenInput -> \[i](<~´{}´ ={}> { n: $i, $...} !\) }
rule line: col´1:[ <cell>+ ] (<'\n '>?) (..|@: {row: $@.row::raw + 1, col: 1};)
rule cell: <open|blocked|given> (<' '>?) (@.col: $@.col::raw + 1;)
rule open: <'__'> -> n´0
rule blocked: <' \.'> -> n´-1
rule given: (<' '>?) (def given: <n´INT>;)
($given -> ..|@.givenInput: $@.givenInput::length+1..$::raw -> {};)
($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(first)... } -> solve !
end hidato
$input -> hidato -> '$... -> '$... -> ' $ -> \(when <=n´-1> do ' .' ! when <n´10..> do '$;' ! otherwise ' $;' !\);';
';
' ->!OUT::write
</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|Tcl}}==
<
global grid max filled
set max 1
Line 2,610 ⟶ 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 2,621 ⟶ 5,072:
. . . . 0 7 0 0
. . . . . . 5 0
"</
{{out}}
<pre>
Line 2,648 ⟶ 5,099:
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}}
<syntaxhighlight lang="zkl">hi:= // 0==empty cell, X==not a cell
#<<<
"0 33 35 0 0 X X X
0 0 24 22 0 X X X
0 0 0 21 0 0 X X
0 26 0 13 40 11 X X
27 0 0 0 9 0 1 X
X X 0 0 18 0 0 X
X X X X 0 7 0 0
X X X X X X 5 0";
#<<<
board,given,start:=setup(hi);
print_board(board);
solve(board,given, start.xplode(), 1);
println();
print_board(board);</syntaxhighlight>
<syntaxhighlight lang="zkl">fcn print_board(board){
d:=D(-1," ", 0,"__");
foreach r in (board[1,-1]){
r[1,-1].pump(String,'wrap(c){ "%2s ".fmt(d.find(c,c)) }).println();
}
}
fcn setup(s){
lines:=s.split("\n");
ncols,nrows:=lines[0].split().len(),lines.len();
board:=(nrows+2).pump(List(), (ncols+2).pump(List(),-1).copy);
given,start:=List(),Void;
foreach r,row in (lines.enumerate()){
foreach c,cell in (row.split().enumerate()){
if(cell=="X") continue; // X == not in play, leave at -1
val:=cell.toInt();
board[r+1][c+1]=val;
given.append(val);
if(val==1) start=T(r+1,c+1);
}
}
return(board,given.filter().sort(),start);
}
fcn solve(board,given, r,c,n, next=0){
if(n>given[-1]) return(True);
if(board[r][c] and board[r][c]!=n) return(False);
if(board[r][c]==0 and given[next]==n) return(False);
back:=0;
if(board[r][c]==n){ next+=1; back=n; }
board[r][c]=n;
foreach i,j in ([-1..1],[-1..1]){
if(solve(board,given, r+i,c+j,n+1, next)) return(True);
}
board[r][c]=back;
False
}</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>
[[Category:Puzzles]]
|