Rosetta Code

Solve a Holy Knight's tour: Difference between revisions

Page Discussion

Solve a Holy Knight's tour (view source)

Revision as of 20:15, 16 June 2024

84,064 bytes added ,  12 days ago
→‎{{header|jq}}
m (→‎{{header|REXX}}: changed/added some comments and whitespace.)
 
(39 intermediate revisions by 13 users not shown)
Line 8:
The present task is to produce a solution to such problems. At least demonstrate your program by solving the following:
 
 
;Example 1
;Example:
<pre>
0 0 0
Line 24 ⟶ 25:
Extra credit is available for other interesting examples.
 
 
;Related tasks:
* [[A* search algorithm]]
* [[Knight's tour]]
* [[N-queens problem]]
* [[Solve a Hidato puzzle]]
* [[Solve a Hopido puzzle]]
* [[Solve a Numbrix puzzle]]
* [[Solve the no connection puzzle]]
<br><br>
* [[Knight's tour]]
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">V moves = [
[-1, -2], [1, -2], [-1, 2], [1, 2],
[-2, -1], [-2, 1], [2, -1], [2, 1]
]
 
F solve(&pz, sz, sx, sy, idx, cnt)
I idx > cnt
R 1
 
L(i) 0 .< :moves.len
V x = sx + :moves[i][0]
V y = sy + :moves[i][1]
I sz > x & x > -1 & sz > y & y > -1 & pz[x][y] == 0
pz[x][y] = idx
I 1 == solve(&pz, sz, x, y, idx + 1, cnt)
R 1
pz[x][y] = 0
R 0
 
F find_solution(pz, sz)
V p = [[-1] * sz] * sz
V idx = 0
V x = 0
V y = 0
V cnt = 0
L(j) 0 .< sz
L(i) 0 .< sz
I pz[idx] == ‘x’
p[i][j] = 0
cnt++
E I pz[idx] == ‘s’
p[i][j] = 1
cnt++
x = i
y = j
idx++
 
I 1 == solve(&p, sz, x, y, 2, cnt)
L(j) 0 .< sz
L(i) 0 .< sz
I p[i][j] != -1
print(‘ #02’.format(p[i][j]), end' ‘’)
E
print(‘ ’, end' ‘’)
print()
E
print(‘Cannot solve this puzzle!’)
 
find_solution(‘.xxx.....x.xx....xxxxxxxxxx..x.xx.x..xxxsxxxxxx...xx.x.....xxx..’, 8)
print()
find_solution(‘.....s.x..........x.x.........xxxxx.........xxx.......x..x.x..x..xxxxx...xxxxx..xx.....xx..xxxxx...xxxxx..x..x.x..x.......xxx.........xxxxx.........x.x..........x.x.....’, 13)</syntaxhighlight>
 
{{out}}
<pre>
17 14 29
28 18 15
13 16 27 30 19 32 07
25 02 11 06 20
12 26 31 08 33
01 24 03 10 05 34 21
36 23 09
04 35 22
 
01 05
10 12
02 13 04 09 06
08 11 14
36 03 07 16
35 42 33 44 37 15 20 27 22 25
38 41 17 24
39 34 43 32 45 19 28 21 26 23
40 31 29 18
46 51 56
52 55 30 47 50
48 54
53 49
</pre>
 
=={{header|Ada}}==
Line 35 ⟶ 121:
This solution uses the package Knights_Tour from [[Knight's Tour#Ada]]. The board is quadratic, the size of the board is read from the command line and the board itself is read from the standard input. For the board itself, Space and Minus indicate a no-go (i.e., a coin on the board), all other characters represent places the knight must visit. A '1' represents the start point. Ill-formatted input will crash the program.
 
<langsyntaxhighlight Adalang="ada">with Knights_Tour, Ada.Text_IO, Ada.Command_Line;
procedure Holy_Knight is
Line 70 ⟶ 156:
Ada.Text_IO.Put_Line("Tour:");
KT.Tour_IO(KT.Warnsdorff_Get_Tour(Start_X, Start_Y, Board));
end Holy_Knight;</langsyntaxhighlight>
 
{{out}}
Line 133 ⟶ 219:
=={{header|ALGOL 68}}==
Uses a modified version of the [[Knight's Tour#ALGOL 68]] solution.
<langsyntaxhighlight lang="algol68"># directions for moves #
INT nne = 1, ne = 2, se = 3, sse = 4;
INT ssw = 5, sw = 6, nw = 7, nnw = 8;
Line 309 ⟶ 395:
FI;
print( ( iterations, " iterations, ", backtracks, " backtracks", newline ) )
)</langsyntaxhighlight>
{{out}}
<pre>
Line 328 ⟶ 414:
This solution can handle different input formats: the widths of the first and the other columns are computed. The cell were to start from should have a unique value, but this value is not prescribed. Non-empty cells (such as the start cell) should contain a character that is different from '-', '.' or white space.
The puzzle solver itself is only a few lines long.
<langsyntaxhighlight lang="bracmat">( ( Holy-Knight
= begin colWidth crumbs non-empty pairs path parseLine
, display isolateStartCell minDistance numberElementsAndSort
Line 540 ⟶ 626:
& whl'(!boards:%?board ?boards&Holy-Knight$!board)
& done
);</langsyntaxhighlight>
Output:
<pre>
Line 588 ⟶ 674:
16 12
13 15</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
knightMoves = {(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2)};
 
private (int dx, int dy)[] moves;
public static void Main()
{
var knightSolver = new Solver(knightMoves);
Print(knightSolver.Solve(true,
".000....",
".0.00...",
".0000000",
"000..0.0",
"0.0..000",
"1000000.",
"..00.0..",
"...000.."));
 
Print(knightSolver.Solve(true,
".....0.0.....",
".....0.0.....",
"....00000....",
".....000.....",
"..0..0.0..0..",
"00000...00000",
"..00.....00..",
"00000...00000",
"..0..0.0..0..",
".....000.....",
"....00000....",
".....0.0.....",
".....0.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>
-- 23 32 21 -- -- -- --
-- 16 -- 24 31 -- -- --
-- 33 22 15 20 25 30 27
17 36 19 -- -- 28 -- 8
34 -- 14 -- -- 9 26 29
1 18 35 10 13 4 7 --
-- -- 2 5 -- 11 -- --
-- -- -- 12 3 6 -- --
 
-- -- -- -- -- 1 -- 37 -- -- -- -- --
-- -- -- -- -- 34 -- 56 -- -- -- -- --
-- -- -- -- 2 55 38 33 36 -- -- -- --
-- -- -- -- -- 32 35 54 -- -- -- -- --
-- -- 28 -- -- 3 -- 39 -- -- 48 -- --
29 6 25 4 31 -- -- -- 53 40 51 42 47
-- -- 30 27 -- -- -- -- -- 49 46 -- --
7 26 5 24 9 -- -- -- 45 52 41 50 43
-- -- 8 -- -- 23 -- 15 -- -- 44 -- --
-- -- -- -- -- 10 19 22 -- -- -- -- --
-- -- -- -- 18 21 16 11 14 -- -- -- --
-- -- -- -- -- 12 -- 20 -- -- -- -- --
-- -- -- -- -- 17 -- 13 -- -- -- -- --
</pre>
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">
#include <vector>
#include <sstream>
Line 726 ⟶ 988:
return system( "pause" );
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 757 ⟶ 1,019:
{{trans|C++}}
From the refactored C++ version with more precise typing, and some optimizations. The HolyKnightPuzzle struct is created at compile-time, so its pre-conditions can catch most malformed puzzles at compile-time.
<langsyntaxhighlight lang="d">import std.stdio, std.conv, std.string, std.range, std.algorithm,
std.typecons, std.typetuple;
 
Line 889 ⟶ 1,151:
writefln("One solution:\n%(%-(%2s %)\n%)\n", solution);
}
}</langsyntaxhighlight>
{{out}}
<pre>One solution:
Line 921 ⟶ 1,183:
{{trans|Ruby}}
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]]
<langsyntaxhighlight lang="elixir"># require HLPsolver
adjacent = [{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}]
Line 952 ⟶ 1,214:
_ _ _ _ _ 0 _ 0
"""
|> HLPsolver.solve(adjacent)</langsyntaxhighlight>
 
{{out}}
Line 1,005 ⟶ 1,267:
12 20
17 13
</pre>
 
=={{header|Go}}==
{{trans|Python}}
<syntaxhighlight lang="go">package main
 
import "fmt"
 
var moves = [][2]int{
{-1, -2}, {1, -2}, {-1, 2}, {1, 2}, {-2, -1}, {-2, 1}, {2, -1}, {2, 1},
}
 
var board1 = " xxx " +
" x xx " +
" xxxxxxx" +
"xxx x x" +
"x x xxx" +
"sxxxxxx " +
" xx x " +
" xxx "
 
var board2 = ".....s.x....." +
".....x.x....." +
"....xxxxx...." +
".....xxx....." +
"..x..x.x..x.." +
"xxxxx...xxxxx" +
"..xx.....xx.." +
"xxxxx...xxxxx" +
"..x..x.x..x.." +
".....xxx....." +
"....xxxxx...." +
".....x.x....." +
".....x.x....."
 
func solve(pz [][]int, sz, sx, sy, idx, cnt int) bool {
if idx > cnt {
return true
}
for i := 0; i < len(moves); i++ {
x := sx + moves[i][0]
y := sy + moves[i][1]
if (x >= 0 && x < sz) && (y >= 0 && y < sz) && pz[x][y] == 0 {
pz[x][y] = idx
if solve(pz, sz, x, y, idx+1, cnt) {
return true
}
pz[x][y] = 0
}
}
return false
}
 
func findSolution(b string, sz int) {
pz := make([][]int, sz)
for i := 0; i < sz; i++ {
pz[i] = make([]int, sz)
for j := 0; j < sz; j++ {
pz[i][j] = -1
}
}
var x, y, idx, cnt int
for j := 0; j < sz; j++ {
for i := 0; i < sz; i++ {
switch b[idx] {
case 'x':
pz[i][j] = 0
cnt++
case 's':
pz[i][j] = 1
cnt++
x, y = i, j
}
idx++
}
}
 
if solve(pz, sz, x, y, 2, cnt) {
for j := 0; j < sz; j++ {
for i := 0; i < sz; i++ {
if pz[i][j] != -1 {
fmt.Printf("%02d ", pz[i][j])
} else {
fmt.Print("-- ")
}
}
fmt.Println()
}
} else {
fmt.Println("Cannot solve this puzzle!")
}
}
 
func main() {
findSolution(board1, 8)
fmt.Println()
findSolution(board2, 13)
}</syntaxhighlight>
 
{{out}}
<pre>
-- 17 14 29 -- -- -- --
-- 28 -- 18 15 -- -- --
-- 13 16 27 30 19 32 07
25 02 11 -- -- 06 -- 20
12 -- 26 -- -- 31 08 33
01 24 03 10 05 34 21 --
-- -- 36 23 -- 09 -- --
-- -- -- 04 35 22 -- --
 
-- -- -- -- -- 01 -- 05 -- -- -- -- --
-- -- -- -- -- 10 -- 12 -- -- -- -- --
-- -- -- -- 02 13 04 09 06 -- -- -- --
-- -- -- -- -- 08 11 14 -- -- -- -- --
-- -- 36 -- -- 03 -- 07 -- -- 16 -- --
35 42 33 44 37 -- -- -- 15 20 27 22 25
-- -- 38 41 -- -- -- -- -- 17 24 -- --
39 34 43 32 45 -- -- -- 19 28 21 26 23
-- -- 40 -- -- 31 -- 29 -- -- 18 -- --
-- -- -- -- -- 46 51 56 -- -- -- -- --
-- -- -- -- 52 55 30 47 50 -- -- -- --
-- -- -- -- -- 48 -- 54 -- -- -- -- --
-- -- -- -- -- 53 -- 49 -- -- -- -- --
</pre>
 
=={{header|Haskell}}==
<syntaxhighlight lang Haskell="haskell">import qualified Data.Array as Arr
(Array, (//), (!), assocs, elems, bounds, listArray)
import qualified Data.Foldable as Fold
import qualified Data.List asFoldable List(forM_)
import Data.List (intercalate, transpose)
import Data.Maybe
 
type Position = (Int, Int)
 
type KnightBoard = Arr.Array Position (Maybe Int)
type KnightBoard = Array Position (Maybe Int)
 
toSlot :: Char -> Maybe Int
toSlot '0' = Just 0
toSlot '1' = Just 1
toSlot _ = Nothing
 
toString :: Maybe Int -> String
toString Nothing = replicate 3 ' '
toString (Just n) = replicate (3 - length nn) ' ' ++ nn
where
Line 1,029 ⟶ 1,416:
chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs = take n xs : (chunksOf n $ drop n xs)
let (chunk, rest) = splitAt n xs
in chunk : chunksOf n rest
 
showBoard :: KnightBoard -> String
showBoard board =
List.intercalate "\n" . map concat . List.transpose . chunksOf (height + 1) . map toString $
. chunksOf (height + 1) . map toString $ Arr.elems board
where
(_, (_, height)) = Arr.bounds board
 
toBoard :: [String] -> KnightBoard
Line 1,042 ⟶ 1,431:
where
height = length strs
width = minimum (length <$ map length> strs)
board =
board = Arr.listArray ((0, 0), (width - 1, height - 1))
listArray ((0, 0), (width - 1, height - 1)) . map toSlot . concat . List.transpose $ map (take width) strs
take width <$> strs
 
add
 
add :: Num a => (a, a) -> (a, a) -> (a, a)
=> (a, a) -> (a, a) -> (a, a)
add (a, b) (x, y) = (a + x, b + y)
 
within
within :: Ord a => ((a, a), (a, a)) -> (a, a) -> Bool
:: Ord a
within ((a, b), (c, d)) (x, y) =
=> ((a, <=a), x(a, &&a)) x-> <=(a, a) c-> &&Bool
within ((a, b), (c, d)) (x, y) = a <= x && x <= c && b <= y && y <= d
 
-- Enumerate valid moves given a board and a knight's position.
Line 1,059 ⟶ 1,450:
validMoves board position = filter isValid plausible
where
bound = Arr.bounds board
plausible = map (add position) [(1, 2), (2, 1), (2, -1), (-1, 2),
add position <$>
(-2, 1), (1, -2), (-1, -2), (-2, -1)]
isValid pos =[(1, within2), bound(2, pos1), &&(2, maybe-1), False(-1, 2), (==-2, 01), (board1, Arr.!-2), (-1, -2), (-2, pos-1)]
isValid pos = within bound pos && maybe False (== 0) (board ! pos)
 
isSolved :: KnightBoard -> Bool
isSolved = Fold.all (maybe True (0 /= 0))
 
-- Solve the knight's tour with a simple Depth First Search.
Line 1,071 ⟶ 1,463:
solveKnightTour board = solve board 1 initPosition
where
initPosition = fst $ head $ filter ((== (Just 1)) . snd) $ Arr.assocs board
solve boardA depth position =
let boardB = boardA Arr.// [(position, Just depth)]
in if isSolved boardB
then Just boardB
else listToMaybe $ mapMaybeelse (solve boardBlistToMaybe $ depth + 1)
mapMaybe (solve boardB $ depth + 1) $ validMoves boardB position
 
tourExA :: [String]
tourExA =
[ " 000 "
, " 0 00 "
, " 0000000"
, "000 0 0"
, "0 0 000"
, "1000000 "
, " 00 0 "
, " 000 "]
]
 
tourExB :: [String]
tourExB =
[ "-----1-0-----"
, "-----0-0-----"
, "----00000----"
, "-----000-----"
, "--0--0-0--0--"
, "00000---00000"
, "--00-----00--"
, "00000---00000"
, "--0--0-0--0--"
, "-----000-----"
, "----00000----"
, "-----0-0-----"
, "-----0-0-----"]
]
 
main :: IO ()
main =
forM_
flip mapM_ [tourExA, tourExB]
[tourExA, tourExB]
(\board ->
case solveKnightTour $ toBoard (\board of->
case solveKnightTour $ toBoard board of
Nothing -> putStrLn "No solution.\n"
Nothing -> putStrLn "No solution.\n"
Just solution -> putStrLn $ showBoard solution ++ "\n")</lang>
Just solution -> putStrLn $ showBoard solution ++ "\n")</syntaxhighlight>
{{out}}
<pre> 19 26 17
Line 1,137 ⟶ 1,532:
17 15 </pre>
As requested, in an attempt to make this solution faster, the following is a version that replaces the Array with an STUArray (unboxed and mutable), and yields a speedup of 4.2. No speedups were gained until move validation was inlined with the logic in `solve'. This seems to point to the list consing as the overhead for time and allocation, although profiling did show that about 25% of the time in the immutable version was spent creating arrays. Perhaps a more experienced Haskeller could provide insight on how to further optimize this or what optimizations were frivolous (barring a different algorithm or search heuristic, and jumping into C, unless those are the only way).
<syntaxhighlight lang="haskell">{-# LANGUAGE FlexibleContexts #-}
<lang Haskell>import Control.Monad.ST
 
import qualified Data.Array.Base as AB
import qualified DataControl.Array.ST asMonad AST(forM_)
 
import qualified Data.Array.Unboxed as AU
 
import qualified Data.List as List
import Control.Monad.ST (ST, runST)
 
import Data.Array.Base (unsafeFreeze)
 
import Data.List (intercalate, transpose)
 
import Data.Array.ST
(STUArray, readArray, writeArray, newListArray)
 
type Position = (Int, Int)
 
type KnightBoard = AU.UArray Position Int
 
Line 1,149 ⟶ 1,554:
toSlot '0' = 0
toSlot '1' = 1
toSlot _ = -1
 
toString :: Int -> String
toString (-1) = replicate 3 ' '
toString n = replicate (3 - length nn) ' ' ++ nn
where
nn = show n
Line 1,159 ⟶ 1,564:
chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs = take n xs :uncurry ((. chunksOf n) $. drop(:)) (splitAt n xs)
 
showBoard :: KnightBoard -> String
showBoard board =
List.intercalate "\n" . map concat . List.transpose . chunksOf (height + 1) . map toString $
. chunksOf (height + 1) . map toString $ AU.elems board
where
(_, (_, height)) = AU.bounds board
Line 1,172 ⟶ 1,577:
where
height = length strs
width = minimum (length <$ map length> strs)
board =
board = AU.listArray ((0, 0), (width - 1, height - 1))
AU.listArray ((0, 0), (width - 1, height - 1)) . map toSlot . concat . List.transpose $ map (take width) strs
take width <$> strs
 
add
add :: Num a => (a, a) -> (a, a) -> (a, a)
:: Num a
=> (a, a) -> (a, a) -> (a, a)
add (a, b) (x, y) = (a + x, b + y)
 
within
within :: Ord a => ((a, a), (a, a)) -> (a, a) -> Bool
:: Ord a
within ((a, b), (c, d)) (x, y) =
=> ((a, <=a), x(a, &&a)) x-> <=(a, a) c-> &&Bool
within ((a, b), (c, d)) (x, y) = a <= x && x <= c && b <= y && y <= d
 
-- Solve the knight's tour with a simple Depth First Search.
solveKnightTour :: KnightBoard -> Maybe KnightBoard
solveKnightTour board =
runST $ do
do let assocs = AU.assocs board
let
assocs bounds = AU.assocsbounds board
array <-
bounds = AU.bounds board
newListArray bounds (AU.elems board) :: ST s (STUArray s Position Int)
let initPosition = fst $ head $ filter ((== 1) . snd) assocs
maxDepth = fromIntegral $ 1 + length (filter ((== 0) . snd) assocs)
offsets =
[ (1, 2)
, (2, 1)
, (2, -1)
, (-1, 2)
, (-2, 1)
, (1, -2)
, (-1, -2)
, (-2, -1)
]
solve depth position =
if within bounds position
then do
oldValue <- readArray array position
if oldValue == 0
then do
writeArray array position depth
if depth == maxDepth
then return True
-- This mapM-any combo can be reduced to a string of ||'s
-- with the goal of removing the allocation overhead due to consing
-- which the compiler may not be able to optimize out.
else do
results <- mapM (solve (depth + 1) . add position) offsets
if or results
then return True
else do
writeArray array position oldValue
return False
else return False
else return False
writeArray array initPosition 0
result <- solve 1 initPosition
farray <- unsafeFreeze array
return $
if result
then Just farray
else Nothing
 
tourExA :: [String]
array <- (AST.newListArray bounds (AU.elems board))
tourExA =
:: ST s (AST.STUArray s Position Int)
[ " 000 "
, " 0 00 "
, " 0000000"
, "000 0 0"
, "0 0 000"
, "1000000 "
, " 00 0 "
, " 000 "
]
 
tourExB :: [String]
let
tourExB =
initPosition = fst $ head $ filter ((== 1) . snd) assocs
[ "-----1-0-----"
maxDepth = fromIntegral $ 1 + (length $ filter ((== 0) . snd) assocs)
, "-----0-0-----"
offsets =
, "----00000----"
[(1, 2), (2, 1), (2, -1), (-1, 2),
, "-----000-----"
(-2, 1), (1, -2), (-1, -2), (-2, -1)]
, "--0--0-0--0--"
, "00000---00000"
, "--00-----00--"
, "00000---00000"
, "--0--0-0--0--"
, "-----000-----"
, "----00000----"
, "-----0-0-----"
, "-----0-0-----"
]
 
main :: IO ()
solve depth position = do
main =
if within bounds position
forM_
then do
[tourExA, tourExB]
oldValue <- AST.readArray array position
(\board ->
if oldValue == 0
case solveKnightTour then$ dotoBoard board of
Nothing -> AST.writeArrayputStrLn array"No position depthsolution.\n"
Just solution -> putStrLn $ showBoard solution ++ "\n")</syntaxhighlight>
if depth == maxDepth
 
then return True
This version is similar to the previous one but:
else do
* the working code is cleaned up slightly with minor optimisations here and there
-- This mapM-any combo can be reduced to a string of ||'s
* only valid board fields are taken into consideration: previously a huge amount of time was wasted on constantly verifying if moves were valid rather than building only valid moves to start with
-- with the goal of removing the allocation overhead due to consing
* vector is used instead of array to take advantage of any fusion
-- which the compiler may not be able to optimize out.
 
results <- mapM ((solve $ depth + 1) . add position) offsets
This results in 117x speedup over the very first version. This speed up comes from a smarter traversal rather than from minor code optimisations.
if any (== True) results
 
then return True
<syntaxhighlight lang="haskell">
else do
{-# LANGUAGE FlexibleContexts #-}
AST.writeArray array position oldValue
{-# LANGUAGE LambdaCase #-}
return False
{-# LANGUAGE BangPatterns #-}
else return False
{-# OPTIONS_GHC -ddump-simpl -ddump-to-file -ddump-stg -O2 -fforce-recomp #-}
else return False
module Main (main) where
 
import Control.Monad.ST (runST)
import Data.List (intercalate, transpose)
import qualified Data.Ix as Ix
import qualified Data.Vector as V
import Data.Vector.Unboxed (Vector)
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as MU
import Data.Foldable (for_)
 
type Position = ( Int, Int )
 
type Bounds = (Position, Position)
 
type KnightBoard = (Bounds, Vector Int)
 
toSlot :: Char -> Int
toSlot '0' = 0
toSlot '1' = 1
toSlot _ = -1
 
toString :: Int -> String
toString (-1) = replicate 3 ' '
toString n = replicate (3 - length nn) ' ' ++ nn
where
nn = show n
 
chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs = uncurry ((. chunksOf n) . (:)) (splitAt n xs)
 
showBoard :: KnightBoard -> String
showBoard (bounds, board) =
intercalate "\n" . map concat . transpose . chunksOf (height + 1) . map toString $
U.toList board
where
(_, (_, height)) = bounds
 
toBoard :: [String] -> KnightBoard
toBoard strs = (((0,0),(width-1,height-1)), board)
where
height = length strs
width = minimum (length <$> strs)
board =
U.fromListN (width*height) . map toSlot . concat . transpose $
take width <$> strs
 
-- Solve the knight's tour with a simple Depth First Search.
solveKnightTour :: KnightBoard -> Maybe KnightBoard
solveKnightTour (bounds@(_,(_,yb)), board) = runST $ do
array <- U.thaw board
let maxDepth = U.length $ U.filter (/= (-1)) board
Just iniIdx = U.findIndex (==1) board
initPosition = mkPos iniIdx
!hops = V.generate (U.length board) $ \i ->
if board `U.unsafeIndex` i == -1
then U.empty
else mkHops (mkPos i)
 
solve !depth !position = MU.unsafeRead array position >>= \case
0 -> do
MU.unsafeWrite array position depth
case depth == maxDepth of
True -> return True
False -> do
results <- U.mapM (solve (depth + 1)) (hops `V.unsafeIndex` position)
if U.or results
then return True
else do
MU.unsafeWrite array position 0
return False
_ -> pure False
 
MU.unsafeWrite array (Ix.index bounds initPosition) 0
result <- solve 1 (Ix.index bounds initPosition)
farray <- U.unsafeFreeze array
return $ if result then Just (bounds, farray) else Nothing
where
offsets = U.fromListN 8 [ (1, 2), (2, 1), (2, -1), (-1, 2), (-2, 1), (1, -2), (-1, -2), (-2, -1) ]
mkHops pos = U.filter (\i -> board `U.unsafeIndex` i == 0)
$ U.map (Ix.index bounds)
$ U.filter (Ix.inRange bounds)
$ U.map (add pos) offsets
add (x, y) (x', y') = (x + x', y + y')
mkPos idx = idx `quotRem` (yb+1)
 
AST.writeArray array initPosition 0
result <- solve 1 initPosition
farray <- AB.unsafeFreeze array
return $ if result
then Just farray
else Nothing
 
tourExA :: [String]
tourExA =
[ [" 000 "
, ," 0 00 "
, ," 0000000"
, ,"000 0 0"
, ,"0 0 000"
, ,"1000000 "
, ," 00 0 "
, ," 000 "]
]
 
tourExB :: [String]
tourExB =
[ ["-----1-0-----"
, ,"-----0-0-----"
, ,"----00000----"
, ,"-----000-----"
, ,"--0--0-0--0--"
, ,"00000---00000"
, ,"--00-----00--"
, ,"00000---00000"
, ,"--0--0-0--0--"
, ,"-----000-----"
, ,"----00000----"
, ,"-----0-0-----"
, ,"-----0-0-----"]
]
 
main :: IO ()
main =
for_
flip mapM_ [tourExA, tourExB]
[tourExA, tourExB]
(\board ->
(\board -> do
case solveKnightTour $ toBoard board of
case solveKnightTour $ toBoard board of
Nothing -> putStrLn "No solution.\n"
Just solution Nothing -> putStrLn $ showBoard"No solution ++ ".\n")</lang>
Just solution -> putStrLn $ showBoard solution ++ "\n")
 
</syntaxhighlight>
 
==Icon and {{header|Unicon}}==
This is a Unicon-specific solution:
<langsyntaxhighlight lang="unicon">global nCells, cMap, best
record Pos(r,c)
 
Line 1,365 ⟶ 1,918:
QMouse(puzzle, visit(loc.r+1,loc.c-2), self, val)
QMouse(puzzle, visit(loc.r-1,loc.c-2), self, val)
end</langsyntaxhighlight>
 
Sample run:
Line 1,397 ⟶ 1,950:
->
</pre>
 
=={{header|J}}==
 
The simplest J implementation here uses a breadth first search - but that can be memory inefficient so it's worth representing the boards as characters (several orders of magnitude space improvement) and it's worth capping how much memory we allow J to use (2^34 is 16GB):
 
<syntaxhighlight lang="j">9!:21]2^34
 
unpack=:verb define
mask=. +./' '~:y
board=. (255 0 1{a.) {~ {.@:>:@:"."0 mask#"1 y
)
 
ex1=:unpack ];._2]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
)
 
solve=:verb define
board=.,:y
for_move.1+i.+/({.a.)=,y do.
board=. ;move <@knight"2 board
end.
)
 
kmoves=: ,/(2 1,:1 2)*"1/_1^#:i.4
 
knight=:dyad define
pos=. ($y)#:(,y)i.x{a.
moves=. <"1(#~ 0&<: */"1@:* ($y)&>"1)pos+"1 kmoves
moves=. (#~ (0{a.)={&y) moves
moves y adverb def (':';'y x} m')"0 (x+1){a.
)</syntaxhighlight>
 
Letting that cook:
 
<syntaxhighlight lang="j"> $~.sol
48422 8 8</syntaxhighlight>
 
That's 48422 solutions. Here's one of them:
 
<syntaxhighlight lang="j"> (a.i.{.sol){(i.255),__
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
__ 27 12 21 14 9 16 31
23 2 25 __ __ 30 __ 8
26 __ 20 __ __ 15 32 17
1 24 3 34 5 18 7 __
__ __ 36 19 __ 33 __ __
__ __ __ 4 35 6 __ __</syntaxhighlight>
 
and here's a couple more:
 
<syntaxhighlight lang="j"> (a.i.{:sol){(i.255),__
__ 5 8 31 __ __ __ __
__ 32 __ 6 9 __ __ __
__ 7 4 33 30 23 10 21
3 34 29 __ __ 20 __ 24
36 __ 2 __ __ 11 22 19
1 28 35 12 15 18 25 __
__ __ 16 27 __ 13 __ __
__ __ __ 14 17 26 __ __
(a.i.24211{sol){(i.255),__
__ 11 14 33 __ __ __ __
__ 34 __ 10 13 __ __ __
__ 19 12 15 32 9 6 25
35 16 31 __ __ 24 __ 8
18 __ 20 __ __ 7 26 5
1 36 17 30 27 4 23 __
__ __ 2 21 __ 29 __ __
__ __ __ 28 3 22 __ __</syntaxhighlight>
 
This is something of a problem, however, because finding all those solutions is slow. And even having to be concerned about a 16GB memory limit for this small of a problem is troubling (and using 64 bit integers, instead of 8 bit characters, to represent board squares, would exceed that limit). Also, you'd get bored, inspecting 48422 boards.
 
So, let's just find one solution:
 
<syntaxhighlight lang="j">unpack=:verb define
mask=. +./' '~:y
board=. __ 0 1 {~ {.@:>:@:"."0 mask#"1 y
)
 
ex1=:unpack ];._2]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
)
 
solve1=:verb define
(1,+/0=,y) solve1 ,:y
:
for_block._10 <\ y do.
board=. ;({.x) <@knight"2 ;block
if. #board do.
if. =/x do.
{.board return.
else.
board=. (1 0+x) solve1 board
if. #board do.
board return.
end.
end.
end.
end.
i.0 0
)
 
kmoves=: ,/(2 1,:1 2)*"1/_1^#:i.4
 
knight=:dyad define
pos=. ($y)#:(,y)i.x
moves=. <"1(#~ 0&<: */"1@:* ($y)&>"1)pos+"1 kmoves
moves=. (#~ 0={&y) moves
moves y adverb def (':';'y x} m')"0 x+1
)</syntaxhighlight>
 
Here, we break our problem space up into blocks of no more than 10 boards each, and use recursion to investigate each batch of boards. When we find a solution, we stop there (for each iteration at each level of recursion):
 
<syntaxhighlight lang="j"> solve1 ex1
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
__ 27 12 21 14 9 16 31
23 2 25 __ __ 30 __ 8
26 __ 20 __ __ 15 32 17
1 24 3 34 5 18 7 __
__ __ 36 19 __ 33 __ __
__ __ __ 4 35 6 __ __</syntaxhighlight>
 
[Why ten boards and not just one board? Because 10 is a nice compromise between amortizing the overhead of each attempt and not trying too much at one time. Most individual attempts will fail, but by splitting up the workload after exceeding 10 possibilities, instead of investigating each possibility individually, we increase the chances that we are investigating something useful. Also, J implementations penalize the performance of algorithms which are overly serial in structure.]
 
With this tool in hand, we can now attempt bigger problems:
 
<syntaxhighlight lang="j">ex2=:unpack ];._2]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 0
0 0 0 0
0 0 0
0 0 0 0 0
0 0
0 0
)</syntaxhighlight>
 
Finding a solution for this looks like:
 
<syntaxhighlight lang="j"> solve1 ex2
__ __ __ __ __ 1 __ 5 __ __ __ __ __
__ __ __ __ __ 6 __ 46 __ __ __ __ __
__ __ __ __ 48 45 2 7 4 __ __ __ __
__ __ __ __ __ 8 47 44 __ __ __ __ __
__ __ 56 __ __ 49 __ 3 __ __ 42 __ __
13 52 11 50 9 __ __ __ 43 38 31 36 33
__ __ 14 55 __ __ __ __ __ 41 34 __ __
53 12 51 10 15 __ __ __ 39 30 37 32 35
__ __ 54 __ __ 23 __ 29 __ __ 40 __ __
__ __ __ __ __ 16 19 22 __ __ __ __ __
__ __ __ __ 24 21 26 17 28 __ __ __ __
__ __ __ __ __ 18 __ 20 __ __ __ __ __
__ __ __ __ __ 25 __ 27 __ __ __ __ __</syntaxhighlight>
 
=={{header|Java}}==
{{works with|Java|8}}
<syntaxhighlight lang="java">import java.util.*;
 
public class HolyKnightsTour {
 
final static String[] board = {
" xxx ",
" x xx ",
" xxxxxxx",
"xxx x x",
"x x xxx",
"1xxxxxx ",
" xx x ",
" xxx "};
 
private final static int base = 12;
private final static int[][] moves = {{1, -2}, {2, -1}, {2, 1}, {1, 2},
{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}};
private static int[][] grid;
private static int total = 2;
 
public static void main(String[] args) {
int row = 0, col = 0;
 
grid = new int[base][base];
 
for (int r = 0; r < base; r++) {
Arrays.fill(grid[r], -1);
for (int c = 2; c < base - 2; c++) {
if (r >= 2 && r < base - 2) {
if (board[r - 2].charAt(c - 2) == 'x') {
grid[r][c] = 0;
total++;
}
if (board[r - 2].charAt(c - 2) == '1') {
row = r;
col = c;
}
}
}
}
 
grid[row][col] = 1;
 
if (solve(row, col, 2))
printResult();
}
 
private static boolean solve(int r, int c, int count) {
if (count == total)
return true;
 
List<int[]> nbrs = neighbors(r, c);
 
if (nbrs.isEmpty() && count != total)
return false;
 
Collections.sort(nbrs, (a, b) -> a[2] - b[2]);
 
for (int[] nb : nbrs) {
r = nb[0];
c = nb[1];
grid[r][c] = count;
if (solve(r, c, count + 1))
return true;
grid[r][c] = 0;
}
 
return false;
}
 
private static List<int[]> neighbors(int r, int c) {
List<int[]> nbrs = new ArrayList<>();
 
for (int[] m : moves) {
int x = m[0];
int y = m[1];
if (grid[r + y][c + x] == 0) {
int num = countNeighbors(r + y, c + x) - 1;
nbrs.add(new int[]{r + y, c + x, num});
}
}
return nbrs;
}
 
private static int countNeighbors(int r, int c) {
int num = 0;
for (int[] m : moves)
if (grid[r + m[1]][c + m[0]] == 0)
num++;
return num;
}
 
private static void printResult() {
for (int[] row : grid) {
for (int i : row) {
if (i == -1)
System.out.printf("%2s ", ' ');
else
System.out.printf("%2d ", i);
}
System.out.println();
}
}
}</syntaxhighlight>
<pre> 19 26 21
28 18 25
33 20 27 22 17 24 7
29 2 35 8 16
34 32 23 6 9
1 30 3 36 13 10 15
12 31 5
4 11 14 </pre>
 
=={{header|JavaScript}}==
===ES6===
By composition of generic functions, cacheing degree-sorted moves for each node.
<syntaxhighlight lang="javascript">(() => {
'use strict';
 
// problems :: [[String]]
const problems = [
[
" 000 " //
, " 0 00 " //
, " 0000000" //
, "000 0 0" //
, "0 0 000" //
, "1000000 " //
, " 00 0 " //
, " 000 " //
],
[
"-----1-0-----" //
, "-----0-0-----" //
, "----00000----" //
, "-----000-----" //
, "--0--0-0--0--" //
, "00000---00000" //
, "--00-----00--" //
, "00000---00000" //
, "--0--0-0--0--" //
, "-----000-----" //
, "----00000----" //
, "-----0-0-----" //
, "-----0-0-----" //
]
];
 
// GENERIC FUNCTIONS ------------------------------------------------------
 
// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
(x, y) => {
const
a = f(x),
b = f(y);
return a < b ? -1 : a > b ? 1 : 0
};
 
// concat :: [[a]] -> [a] | [String] -> String
const concat = xs =>
xs.length > 0 ? (() => {
const unit = typeof xs[0] === 'string' ? '' : [];
return unit.concat.apply(unit, xs);
})() : [];
 
// charColRow :: Char -> [String] -> Maybe (Int, Int)
const charColRow = (c, rows) =>
foldr((a, xs, iRow) =>
a.nothing ? (() => {
const mbiCol = elemIndex(c, xs);
return mbiCol.nothing ? mbiCol : {
just: [mbiCol.just, iRow],
nothing: false
};
})() : a, {
nothing: true
}, rows);
 
// 2 or more arguments
// curry :: Function -> Function
const curry = (f, ...args) => {
const go = xs => xs.length >= f.length ? (f.apply(null, xs)) :
function () {
return go(xs.concat(Array.from(arguments)));
};
return go([].slice.call(args, 1));
};
 
// elem :: Eq a => a -> [a] -> Bool
const elem = (x, xs) => xs.indexOf(x) !== -1;
 
// elemIndex :: Eq a => a -> [a] -> Maybe Int
const elemIndex = (x, xs) => {
const i = xs.indexOf(x);
return {
nothing: i === -1,
just: i
};
};
 
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
 
// filter :: (a -> Bool) -> [a] -> [a]
const filter = (f, xs) => xs.filter(f);
 
// findIndex :: (a -> Bool) -> [a] -> Maybe Int
const findIndex = (f, xs) => {
for (var i = 0, lng = xs.length; i < lng; i++) {
if (f(xs[i])) return {
nothing: false,
just: i
};
}
return {
nothing: true
};
};
 
// foldl :: (b -> a -> b) -> b -> [a] -> b
const foldl = (f, a, xs) => xs.reduce(f, a);
 
// foldr (a -> b -> b) -> b -> [a] -> b
const foldr = (f, a, xs) => xs.reduceRight(f, a);
 
// groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
const groupBy = (f, xs) => {
const dct = xs.slice(1)
.reduce((a, x) => {
const
h = a.active.length > 0 ? a.active[0] : undefined,
blnGroup = h !== undefined && f(h, x);
return {
active: blnGroup ? a.active.concat([x]) : [x],
sofar: blnGroup ? a.sofar : a.sofar.concat([a.active])
};
}, {
active: xs.length > 0 ? [xs[0]] : [],
sofar: []
});
return dct.sofar.concat(dct.active.length > 0 ? [dct.active] : []);
};
 
// intercalate :: String -> [a] -> String
const intercalate = (s, xs) => xs.join(s);
 
// intersectBy::(a - > a - > Bool) - > [a] - > [a] - > [a]
const intersectBy = (eq, xs, ys) =>
(xs.length > 0 && ys.length > 0) ?
xs.filter(x => ys.some(curry(eq)(x))) : [];
 
// justifyRight :: Int -> Char -> Text -> Text
const justifyRight = (n, cFiller, strText) =>
n > strText.length ? (
(cFiller.repeat(n) + strText)
.slice(-n)
) : strText;
 
// length :: [a] -> Int
const length = xs => xs.length;
 
// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) => xs.map(f);
 
// mappendComparing :: [(a -> b)] -> (a -> a -> Ordering)
const mappendComparing = fs => (x, y) =>
fs.reduce((ord, f) => {
if (ord !== 0) return ord;
const
a = f(x),
b = f(y);
return a < b ? -1 : a > b ? 1 : 0
}, 0);
 
// maximumBy :: (a -> a -> Ordering) -> [a] -> a
const maximumBy = (f, xs) =>
xs.reduce((a, x) => a === undefined ? x : (
f(x, a) > 0 ? x : a
), undefined);
 
// min :: Ord a => a -> a -> a
const min = (a, b) => b < a ? b : a;
 
// replicate :: Int -> a -> [a]
const replicate = (n, a) => {
let v = [a],
o = [];
if (n < 1) return o;
while (n > 1) {
if (n & 1) o = o.concat(v);
n >>= 1;
v = v.concat(v);
}
return o.concat(v);
};
 
// sortBy :: (a -> a -> Ordering) -> [a] -> [a]
const sortBy = (f, xs) => xs.slice()
.sort(f);
 
// splitOn :: String -> String -> [String]
const splitOn = (s, xs) => xs.split(s);
 
// take :: Int -> [a] -> [a]
const take = (n, xs) => xs.slice(0, n);
 
// unlines :: [String] -> String
const unlines = xs => xs.join('\n');
 
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = (p, f, x) => {
let v = x;
while (!p(v)) v = f(v);
return v;
};
 
// zip :: [a] -> [b] -> [(a,b)]
const zip = (xs, ys) =>
xs.slice(0, Math.min(xs.length, ys.length))
.map((x, i) => [x, ys[i]]);
 
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = (f, xs, ys) =>
Array.from({
length: min(xs.length, ys.length)
}, (_, i) => f(xs[i], ys[i]));
 
// HOLY KNIGHT's TOUR FUNCTIONS -------------------------------------------
 
// kmoves :: (Int, Int) -> [(Int, Int)]
const kmoves = ([x, y]) => map(
([a, b]) => [a + x, b + y], [
[1, 2],
[1, -2],
[-1, 2],
[-1, -2],
[2, 1],
[2, -1],
[-2, 1],
[-2, -1]
]);
 
// rowPosns :: Int -> String -> [(Int, Int)]
const rowPosns = (iRow, s) => {
return foldl((a, x, i) => (elem(x, ['0', '1']) ? (
a.concat([
[i, iRow]
])
) : a), [], splitOn('', s));
};
 
// hash :: (Int, Int) -> String
const hash = ([col, row]) => col.toString() + '.' + row.toString();
 
// Start node, and degree-sorted cache of moves from each node
// All node references are hash strings (for this cache)
 
// problemModel :: [[String]] -> {cache: {nodeKey: [nodeKey], start:String}}
const problemModel = boardLines => {
const
steps = foldl((a, xs, i) =>
a.concat(rowPosns(i, xs)), [], boardLines),
courseMoves = (xs, [x, y]) => intersectBy(
([a, b], [c, d]) => a === c && b === d, kmoves([x, y]), xs
),
maybeStart = charColRow('1', boardLines);
return {
start: maybeStart.nothing ? '' : hash(maybeStart.just),
boardWidth: boardLines.length > 0 ? boardLines[0].length : 0,
stepCount: steps.length,
cache: (() => {
const moveCache = foldl((a, xy) => (
a[hash(xy)] = map(hash, courseMoves(steps, xy)),
a
), {}, steps),
lstMoves = Object.keys(moveCache),
dctDegree = foldl((a, k) =>
(a[k] = moveCache[k].length,
a), {}, lstMoves);
 
return foldl((a, k) => (
a[k] = sortBy(comparing(x => dctDegree[x]), moveCache[k]),
a
), {}, lstMoves);
})()
};
};
 
// firstSolution :: {nodeKey: [nodeKey]} -> Int ->
// nodeKey -> nodeKey -> [nodeKey] ->
// -> {path::[nodeKey], pathLen::Int, found::Bool}
const firstSolution = (dctMoves, intTarget, strStart, strNodeKey, path) => {
const
intPath = path.length,
moves = dctMoves[strNodeKey];
 
if ((intTarget - intPath) < 2 && elem(strStart, moves)) {
return {
nothing: false,
just: [strStart, strNodeKey].concat(path),
pathLen: intTarget
};
}
 
const
nexts = filter(k => !elem(k, path), moves),
intNexts = nexts.length,
lstFullPath = [strNodeKey].concat(path);
 
// Until we find a full path back to start
return until(
x => (x.nothing === false || x.i >= intNexts),
x => {
const
idx = x.i,
dctSoln = firstSolution(
dctMoves, intTarget, strStart, nexts[idx], lstFullPath
);
return {
i: idx + 1,
nothing: dctSoln.nothing,
just: dctSoln.just,
pathLen: dctSoln.pathLen
};
}, {
nothing: true,
just: [],
i: 0
}
);
};
 
// maybeTour :: [String] -> {
// nothing::Bool, Just::[nodeHash], i::Int: pathLen::Int }
const maybeTour = trackLines => {
const
dctModel = problemModel(trackLines),
strStart = dctModel.start;
return strStart !== '' ? firstSolution(
dctModel.cache, dctModel.stepCount, strStart, strStart, []
) : {
nothing: true
};
};
 
// showLine :: Int -> Int -> String -> Maybe (Int, Int) ->
// [(Int, Int, String)] -> String
const showLine = curry((intCell, strFiller, maybeStart, xs) => {
const
blnSoln = maybeStart.nothing,
[startCol, startRow] = blnSoln ? [0, 0] : maybeStart.just;
return foldl((a, [iCol, iRow, sVal], i, xs) => ({
col: iCol + 1,
txt: a.txt +
concat(replicate((iCol - a.col) * intCell, strFiller)) +
justifyRight(
intCell, strFiller,
(blnSoln ? sVal : (
iRow === startRow &&
iCol === startCol ? '1' : '0')
)
)
}), {
col: 0,
txt: ''
},
xs
)
.txt
});
 
// solutionString :: [String] -> Int -> String
const solutionString = (boardLines, iProblem) => {
const
dtePre = Date.now(),
intCols = boardLines.length > 0 ? boardLines[0].length : 0,
soln = maybeTour(boardLines),
intMSeconds = Date.now() - dtePre;
 
if (soln.nothing) return 'No solution found …';
 
const
kCol = 0,
kRow = 1,
kSeq = 2,
steps = soln.just,
lstTriples = zipWith((h, n) => {
const [col, row] = map(
x => parseInt(x, 10), splitOn('.', h)
);
return [col, row, n.toString()];
},
steps,
enumFromTo(1, soln.pathLen)),
cellWidth = length(maximumBy(
comparing(x => length(x[kSeq])), lstTriples
)[kSeq]) + 1,
lstGroups = groupBy(
(a, b) => a[kRow] === b[kRow],
sortBy(
mappendComparing([x => x[kRow], x => x[kCol]]),
lstTriples
)),
startXY = take(2, lstTriples[0]),
strMap = 'PROBLEM ' + (parseInt(iProblem, 10) + 1) + '.\n\n' +
unlines(map(showLine(cellWidth, ' ', {
nothing: false,
just: startXY
}), lstGroups)),
strSoln = 'First solution found in c. ' +
intMSeconds + ' milliseconds:\n\n' +
unlines(map(showLine(cellWidth, ' ', {
nothing: true,
just: startXY
}), lstGroups)) + '\n\n';
 
console.log(strSoln);
return strMap + '\n\n' + strSoln;
};
 
// TEST -------------------------------------------------------------------
return unlines(map(solutionString, problems));
})();</syntaxhighlight>
{{Out}}
(Executed in Atom editor, using 'Script' package).
<pre>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
1 0 0 0 0 0 0
0 0 0
0 0 0
 
First solution found in c. 21 milliseconds:
 
25 14 23
8 26 15
13 24 7 22 27 16 31
9 36 11 30 28
12 6 21 32 17
1 10 35 20 3 18 29
2 5 33
34 19 4
 
 
PROBLEM 2.
 
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 0
0 0
 
First solution found in c. 7084 milliseconds:
 
1 3
50 52
56 53 2 49 4
48 51 54
46 55 5 10
45 42 35 40 47 11 6 13 8 15
44 37 9 16
43 36 41 34 39 19 12 7 14 17
38 33 27 18
26 23 20
32 21 30 25 28
24 22
31 29
 
 
[Finished in 7.2s]</pre>
 
=={{header|jq}}==
'''Works with jq, the C implementation of jq'''
 
'''Works with jaq, the Rust implementation of jq'''
 
'''Works with gojq, the Go implementation of jq''' (*)
 
(*) The current implementations of jq are not well-suited
to solving this kind of problem efficiently, but the
C and Rust implementations were able to run the following program
to completion, producing the results shown below,
without requiring excessive amounts of memory.
 
The Go implementation was able to produce
the first solution but required about 3GB of RAM.
<syntaxhighlight lang="jq">
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
 
def moves: [ [-1, -2], [1, -2], [-1, 2], [1, 2], [-2, -1], [-2, 1], [2, -1], [2, 1] ];
 
def board1:
" xxx " +
" x xx " +
" xxxxxxx" +
"xxx x x" +
"x x xxx" +
"sxxxxxx " +
" xx x " +
" xxx "
;
def board2:
".....s.x....." +
".....x.x....." +
"....xxxxx...." +
".....xxx....." +
"..x..x.x..x.." +
"xxxxx...xxxxx" +
"..xx.....xx.." +
"xxxxx...xxxxx" +
"..x..x.x..x.." +
".....xxx....." +
"....xxxxx...." +
".....x.x....." +
".....x.x....."
;
 
# Input: {pz}
def solve($sz; $sx; $sy; $idx; $cnt):
# debug( "solve(\($sz); \($sx); \($sy); \($idx); \($cnt))" ) |
if $idx > $cnt then .
else first(
range(0;moves|length) as $i
| ($sx + moves[$i][0]) as $x
| ($sy + moves[$i][1]) as $y
| if $x >= 0 and $x < $sz and $y >= 0 and $y < $sz and .pz[$x][$y] == 0
then .pz[$x][$y] = $idx
| solve($sz; $x; $y; $idx + 1; $cnt)
else empty
end )
end;
 
def printSolution($sz):
range(0; $sz) as $j
| .emit = ""
| reduce range(0; $sz) as $i (.;
if .pz[$i][$j] != -1
then .emit += (.pz[$i][$j] | lpad(3))
else .emit += " --"
end )
| .emit;
 
# $b should be a board of size $sz
def findSolution($b; $sz):
[range(0; $sz) | -1] as $minus
| { pz: [range(0;$sz) | $minus],
x: 0,
y: 0,
idx: 0,
cnt: 0
}
| reduce range(0; $sz) as $j (.;
reduce range(0; $sz) as $i (.;
if $b[.idx: .idx+1] == "x"
then .pz[$i][$j] = 0
| .cnt += 1
elif $b[.idx: .idx+1] == "s"
then
.pz[$i][$j] = 1
| .cnt += 1
| .x = $i
| .y = $j
end
| .idx += 1 ))
| (solve($sz; .x; .y; 2; .cnt) | printSolution($sz))
// "Whoops!" ;
 
findSolution(board1; 8),
"",
findSolution(board2; 13)
</syntaxhighlight>
{{output}}
<pre>
-- 17 14 29 -- -- -- --
-- 28 -- 18 15 -- -- --
-- 13 16 27 30 19 32 7
25 2 11 -- -- 6 -- 20
12 -- 26 -- -- 31 8 33
1 24 3 10 5 34 21 --
-- -- 36 23 -- 9 -- --
-- -- -- 4 35 22 -- --
 
-- -- -- -- -- 1 -- 5 -- -- -- -- --
-- -- -- -- -- 10 -- 12 -- -- -- -- --
-- -- -- -- 2 13 4 9 6 -- -- -- --
-- -- -- -- -- 8 11 14 -- -- -- -- --
-- -- 36 -- -- 3 -- 7 -- -- 16 -- --
35 42 33 44 37 -- -- -- 15 20 27 22 25
-- -- 38 41 -- -- -- -- -- 17 24 -- --
39 34 43 32 45 -- -- -- 19 28 21 26 23
-- -- 40 -- -- 31 -- 29 -- -- 18 -- --
-- -- -- -- -- 46 51 56 -- -- -- -- --
-- -- -- -- 52 55 30 47 50 -- -- -- --
-- -- -- -- -- 48 -- 54 -- -- -- -- --
-- -- -- -- -- 53 -- 49 -- -- -- -- --
</pre>
 
=={{header|Julia}}==
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task.
<syntaxhighlight lang="julia">using .Hidato # Note that the . here means to look locally for the module rather than in the libraries
 
const holyknight = """
. 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 . . """
 
const knightmoves = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]
 
board, maxmoves, fixed, starts = hidatoconfigure(holyknight)
printboard(board, " 0", " ")
hidatosolve(board, maxmoves, knightmoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
</syntaxhighlight>{{output}}<pre>
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
 
7 4 17
16 8 5
9 6 3 18 25 20 23
31 2 15 22 26
10 30 19 24 21
1 32 11 14 29 34 27
36 33 13
12 35 28
</pre>
 
=={{header|Kotlin}}==
{{trans|Python}}
<syntaxhighlight lang="scala">// version 1.1.3
 
val moves = arrayOf(
intArrayOf(-1, -2), intArrayOf( 1, -2), intArrayOf(-1, 2), intArrayOf(1, 2),
intArrayOf(-2, -1), intArrayOf(-2, 1), intArrayOf( 2, -1), intArrayOf(2, 1)
)
 
val board1 =
" xxx " +
" x xx " +
" xxxxxxx" +
"xxx x x" +
"x x xxx" +
"sxxxxxx " +
" xx x " +
" xxx "
 
val board2 =
".....s.x....." +
".....x.x....." +
"....xxxxx...." +
".....xxx....." +
"..x..x.x..x.." +
"xxxxx...xxxxx" +
"..xx.....xx.." +
"xxxxx...xxxxx" +
"..x..x.x..x.." +
".....xxx....." +
"....xxxxx...." +
".....x.x....." +
".....x.x....."
 
fun solve(pz: Array<IntArray>, sz: Int, sx: Int, sy: Int, idx: Int, cnt: Int): Boolean {
if (idx > cnt) return true
for (i in 0 until moves.size) {
val x = sx + moves[i][0]
val y = sy + moves[i][1]
if ((x in 0 until sz) && (y in 0 until sz) && pz[x][y] == 0) {
pz[x][y] = idx
if (solve(pz, sz, x, y, idx + 1, cnt)) return true
pz[x][y] = 0
}
}
return false
}
 
fun findSolution(b: String, sz: Int) {
val pz = Array(sz) { IntArray(sz) { -1 } }
var x = 0
var y = 0
var idx = 0
var cnt = 0
for (j in 0 until sz) {
for (i in 0 until sz) {
if (b[idx] == 'x') {
pz[i][j] = 0
cnt++
}
else if (b[idx] == 's') {
pz[i][j] = 1
cnt++
x = i
y = j
}
idx++
}
}
 
if (solve(pz, sz, x, y, 2, cnt)) {
for (j in 0 until sz) {
for (i in 0 until sz) {
if (pz[i][j] != -1)
print("%02d ".format(pz[i][j]))
else
print("-- ")
}
println()
}
}
else println("Cannot solve this puzzle!")
}
 
fun main(args: Array<String>) {
findSolution(board1, 8)
println()
findSolution(board2, 13)
}</syntaxhighlight>
 
{{out}}
<pre>
-- 17 14 29 -- -- -- --
-- 28 -- 18 15 -- -- --
-- 13 16 27 30 19 32 07
25 02 11 -- -- 06 -- 20
12 -- 26 -- -- 31 08 33
01 24 03 10 05 34 21 --
-- -- 36 23 -- 09 -- --
-- -- -- 04 35 22 -- --
 
-- -- -- -- -- 01 -- 05 -- -- -- -- --
-- -- -- -- -- 10 -- 12 -- -- -- -- --
-- -- -- -- 02 13 04 09 06 -- -- -- --
-- -- -- -- -- 08 11 14 -- -- -- -- --
-- -- 36 -- -- 03 -- 07 -- -- 16 -- --
35 42 33 44 37 -- -- -- 15 20 27 22 25
-- -- 38 41 -- -- -- -- -- 17 24 -- --
39 34 43 32 45 -- -- -- 19 28 21 26 23
-- -- 40 -- -- 31 -- 29 -- -- 18 -- --
-- -- -- -- -- 46 51 56 -- -- -- -- --
-- -- -- -- 52 55 30 47 50 -- -- -- --
-- -- -- -- -- 48 -- 54 -- -- -- -- --
-- -- -- -- -- 53 -- 49 -- -- -- -- --
</pre>
 
=={{header|Lua}}==
<syntaxhighlight lang="lua">
local p1, p1W = ".xxx.....x.xx....xxxxxxxxxx..x.xx.x..xxxsxxxxxx...xx.x.....xxx..", 8
local p2, p2W = ".....s.x..........x.x.........xxxxx.........xxx.......x..x.x..x..xxxxx...xxxxx..xx.....xx..xxxxx...xxxxx..x..x.x..x.......xxx.........xxxxx.........x.x..........x.x.....", 13
local puzzle, movesCnt, wid = {}, 0, 0
local moves = { { -1, -2 }, { 1, -2 }, { -1, 2 }, { 1, 2 },
{ -2, -1 }, { -2, 1 }, { 2, -1 }, { 2, 1 } }
 
function isValid( x, y )
return( x > 0 and x <= wid and y > 0 and y <= wid and puzzle[x + y * wid - wid] == 0 )
end
function solve( x, y, s )
if s > movesCnt then return true end
local test, a, b
for i = 1, #moves do
test = false
a = x + moves[i][1]; b = y + moves[i][2]
if isValid( a, b ) then
puzzle[a + b * wid - wid] = s
if solve( a, b, s + 1 ) then return true end
puzzle[a + b * wid - wid] = 0
end
end
return false
end
function printSolution()
local lp
for j = 1, wid do
for i = 1, wid do
lp = puzzle[i + j * wid - wid]
if lp == -1 then io.write( " " )
else io.write( string.format( " %.2d", lp ) )
end
end
print()
end
print( "\n" )
end
local sx, sy
function fill( pz, w )
puzzle = {}; wid = w; movesCnt = #pz
local lp
for i = 1, #pz do
lp = pz:sub( i, i )
if lp == "x" then
table.insert( puzzle, 0 )
elseif lp == "." then
table.insert( puzzle, -1 ); movesCnt = movesCnt - 1
else
table.insert( puzzle, 1 )
sx = 1 + ( i - 1 ) % wid; sy = math.floor( ( i + wid - 1 ) / wid )
end
end
end
-- [[ entry point ]] --
print( "\n\n" ); fill( p1, p1W );
if solve( sx, sy, 2 ) then printSolution() end
print( "\n\n" ); fill( p2, p2W );
if solve( sx, sy, 2 ) then printSolution() end
</syntaxhighlight>
{{out}}
<pre>
 
17 14 29
28 18 15
13 16 27 30 19 32 07
25 02 11 06 20
12 26 31 08 33
01 24 03 10 05 34 21
36 23 09
04 35 22
 
01 05
10 12
02 13 04 09 06
08 11 14
36 03 07 16
35 42 33 44 37 15 20 27 22 25
38 41 17 24
39 34 43 32 45 19 28 21 26 23
40 31 29 18
46 51 56
52 55 30 47 50
48 54
53 49
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Outputs coordinates and a visualization of the tour:
<syntaxhighlight lang="mathematica">puzzle = " 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";
puzzle = StringSplit[puzzle, "\n"];
puzzle = StringTake[#, {1, -1, 2}] & /@ puzzle;
pos0 = Join @@ Table[{i, #} & /@ StringPosition[puzzle[[i]], "0"][[All, 1]], {i, Length@puzzle}];
pos1 = Join @@ Table[{i, #} & /@ StringPosition[puzzle[[i]], "1"][[All, 1]], {i, Length@puzzle}];
 
allpoints = Join[pos1, pos0];
validmoves = Select[Subsets[allpoints, {2}], Differences /* Norm /* EqualTo[Sqrt[5]]];
g = Graph[UndirectedEdge @@@ validmoves];
e = VertexList[g];
order = FindShortestTour[g][[2]]
Graphics[{Red, Disk[#, 0.2] & /@ e, Black, BlockMap[Arrow, e[[order]], 2, 1]}]</syntaxhighlight>
{{out}}
<pre>{{6,1},{4,2},{6,3},{8,4},{7,6},{6,4},{5,6},{3,5},{1,4},{2,2},{4,3},{5,1},{3,2},{2,4},{1,2},{3,3},{4,1},{6,2},{7,4},{8,6},{6,7},{4,8},{3,6},{5,7},{3,8},{4,6},{6,5},{5,3},{3,4},{1,3},{2,5},{3,7},{5,8},{6,6},{8,5},{7,3},{6,1}}
[Visualization of the tour]</pre>
 
=={{header|Nim}}==
{{trans|Go}}
In this version, the board is described as an array of strings rather than a string in the Go version (so, we don’t have to specify the size). The way to initialize is also different and even if the Moves where in the same order, the solution would be different. Changing the order of the Moves may have a great impact on performance, but there is no best order. The order we have chosen provides excellent performance with the two examples: less than 20 ms on our laptop. But with another order, it took more than 2 seconds!
 
<syntaxhighlight lang="nim">import sequtils, strformat
 
const Moves = [[-1, -2], [1, -2], [-2, -1], [2, -1], [-2, 1], [2, 1], [-1, 2], [1, 2]]
 
proc solve(pz: var seq[seq[int]]; sx, sy, idx, count: Natural): bool =
 
if idx > count: return true
 
var x, y: int
for move in Moves:
x = sx + move[0]
y = sy + move[1]
if x in 0..pz.high and y in 0..pz.high and pz[x][y] == 0:
pz[x][y] = idx
if pz.solve(x, y, idx + 1, count): return true
pz[x][y] = 0
 
 
proc findSolution(board: openArray[string]) =
let sz = board.len
var pz = newSeqWith(sz, repeat(-1, sz))
 
var count = 0
var x, y: int
for i in 0..<sz:
for j in 0..<sz:
case board[i][j]
of 'x':
pz[i][j] = 0
inc count
of 's':
pz[i][j] = 1
inc count
(x, y) = (i, j)
else:
discard
 
if pz.solve(x, y, 2, count):
for i in 0..<sz:
for j in 0..<sz:
if pz[i][j] != -1:
stdout.write &"{pz[i][j]:02} "
else:
stdout.write "-- "
stdout.write '\n'
 
when isMainModule:
 
const
 
Board1 = [" xxx ",
" x xx ",
" xxxxxxx",
"xxx x x",
"x x xxx",
"sxxxxxx ",
" xx x ",
" xxx "]
 
Board2 = [".....s.x.....",
".....x.x.....",
"....xxxxx....",
".....xxx.....",
"..x..x.x..x..",
"xxxxx...xxxxx",
"..xx.....xx..",
"xxxxx...xxxxx",
"..x..x.x..x..",
".....xxx.....",
"....xxxxx....",
".....x.x.....",
".....x.x....."]
 
Board1.findSolution()
echo()
Board2.findSolution()</syntaxhighlight>
 
{{out}}
<pre>-- 13 06 15 -- -- -- --
-- 08 -- 12 31 -- -- --
-- 05 14 07 16 27 32 29
09 02 11 -- -- 30 -- 26
04 -- 22 -- -- 17 28 33
01 10 03 18 21 34 25 --
-- -- 36 23 -- 19 -- --
-- -- -- 20 35 24 -- --
 
-- -- -- -- -- 01 -- 55 -- -- -- -- --
-- -- -- -- -- 50 -- 48 -- -- -- -- --
-- -- -- -- 02 47 54 51 56 -- -- -- --
-- -- -- -- -- 52 49 46 -- -- -- -- --
-- -- 14 -- -- 03 -- 53 -- -- 44 -- --
09 06 11 04 13 -- -- -- 45 38 33 40 43
-- -- 08 15 -- -- -- -- -- 35 42 -- --
07 10 05 12 17 -- -- -- 37 32 39 34 41
-- -- 16 -- -- 23 -- 31 -- -- 36 -- --
-- -- -- -- -- 18 21 24 -- -- -- -- --
-- -- -- -- 22 25 28 19 30 -- -- -- --
-- -- -- -- -- 20 -- 26 -- -- -- -- --
-- -- -- -- -- 27 -- 29 -- -- -- -- -- </pre>
 
=={{header|Perl}}==
We perform a brute-force search. As an enhancement, we unroll the search by one level and use Parallel::ForkManager to search the top-level sub-trees concurrently, subject to the number of cores of course. We implement the search with explicit recursion, which impacts performance but improves readability and provides a use case for the "local" keyword.
<langsyntaxhighlight lang="perl">package KT_Locations;
# A sequence of locations on a 2-D board whose order might or might not
# matter. Suitable for representing a partial tour, a complete tour, or the
Line 1,653 ⟶ 3,467:
$kt->find_tour();
return;
}</langsyntaxhighlight>
{{out}}
The timings shown below were obtained on a Dell Optiplex 9020 with 4 cores.
Line 1,733 ⟶ 3,547:
- - - - - 48 - 50 - - - - -
- - - - - 41 - 43 - - - - - </pre>
 
=={{header|Perl 6}}==
Using the Warnsdorff algorithm from [[Solve_a_Hidato_puzzle]].
<lang perl6>my @adjacent =
[ -2, -1], [ -2, 1],
[-1,-2], [-1,+2],
[+1,-2], [+1,+2],
[ +2, -1], [ +2, 1];
 
solveboard q:to/END/;
. 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
END</lang>
{{out}}
<pre> 25 14 27
36 24 15
31 26 13 28 23 6 17
35 12 29 16 22
30 32 7 18 5
1 34 11 8 19 4 21
2 33 9
10 3 20
84 tries</pre>
 
=={{header|J}}==
 
The simplest J implementation here uses a breadth first search - but that can be memory inefficient so it's worth representing the boards as characters (several orders of magnitude space improvement) and it's worth capping how much memory we allow J to use (2^34 is 16GB):
 
<lang J>9!:21]2^34
 
unpack=:verb define
mask=. +./' '~:y
board=. (255 0 1{a.) {~ {.@:>:@:"."0 mask#"1 y
)
 
ex1=:unpack ];._2]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
)
 
solve=:verb define
board=.,:y
for_move.1+i.+/({.a.)=,y do.
board=. ;move <@knight"2 board
end.
)
 
kmoves=: ,/(2 1,:1 2)*"1/_1^#:i.4
 
knight=:dyad define
pos=. ($y)#:(,y)i.x{a.
moves=. <"1(#~ 0&<: */"1@:* ($y)&>"1)pos+"1 kmoves
moves=. (#~ (0{a.)={&y) moves
moves y adverb def (':';'y x} m')"0 (x+1){a.
)</lang>
 
Letting that cook:
 
<lang J> $~.sol
48422 8 8</lang>
 
That's 48422 solutions. Here's one of them:
 
<lang J> (a.i.{.sol){(i.255),__
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
__ 27 12 21 14 9 16 31
23 2 25 __ __ 30 __ 8
26 __ 20 __ __ 15 32 17
1 24 3 34 5 18 7 __
__ __ 36 19 __ 33 __ __
__ __ __ 4 35 6 __ __</lang>
 
and here's a couple more:
 
<lang J> (a.i.{:sol){(i.255),__
__ 5 8 31 __ __ __ __
__ 32 __ 6 9 __ __ __
__ 7 4 33 30 23 10 21
3 34 29 __ __ 20 __ 24
36 __ 2 __ __ 11 22 19
1 28 35 12 15 18 25 __
__ __ 16 27 __ 13 __ __
__ __ __ 14 17 26 __ __
(a.i.24211{sol){(i.255),__
__ 11 14 33 __ __ __ __
__ 34 __ 10 13 __ __ __
__ 19 12 15 32 9 6 25
35 16 31 __ __ 24 __ 8
18 __ 20 __ __ 7 26 5
1 36 17 30 27 4 23 __
__ __ 2 21 __ 29 __ __
__ __ __ 28 3 22 __ __</lang>
 
This is something of a problem, however, because finding all those solutions is slow. And even having to be concerned about a 16GB memory limit for this small of a problem is troubling (and using 64 bit integers, instead of 8 bit characters, to represent board squares, would exceed that limit). Also, you'd get bored, inspecting 48422 boards.
 
So, let's just find one solution:
 
<lang J>unpack=:verb define
mask=. +./' '~:y
board=. __ 0 1 {~ {.@:>:@:"."0 mask#"1 y
)
 
ex1=:unpack ];._2]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
)
 
solve1=:verb define
(1,+/0=,y) solve1 ,:y
:
for_block._10 <\ y do.
board=. ;({.x) <@knight"2 ;block
if. #board do.
if. =/x do.
{.board return.
else.
board=. (1 0+x) solve1 board
if. #board do.
board return.
end.
end.
end.
end.
i.0 0
)
 
kmoves=: ,/(2 1,:1 2)*"1/_1^#:i.4
 
knight=:dyad define
pos=. ($y)#:(,y)i.x
moves=. <"1(#~ 0&<: */"1@:* ($y)&>"1)pos+"1 kmoves
moves=. (#~ 0={&y) moves
moves y adverb def (':';'y x} m')"0 x+1
)</lang>
 
Here, we break our problem space up into blocks of no more than 10 boards each, and use recursion to investigate each batch of boards. When we find a solution, we stop there (for each iteration at each level of recursion):
 
<lang J> solve1 ex1
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
__ 27 12 21 14 9 16 31
23 2 25 __ __ 30 __ 8
26 __ 20 __ __ 15 32 17
1 24 3 34 5 18 7 __
__ __ 36 19 __ 33 __ __
__ __ __ 4 35 6 __ __</lang>
 
[Why ten boards and not just one board? Because 10 is a nice compromise between amortizing the overhead of each attempt and not trying too much at one time. Most individual attempts will fail, but by splitting up the workload after exceeding 10 possibilities, instead of investigating each possibility individually, we increase the chances that we are investigating something useful. Also, J implementations penalize the performance of algorithms which are overly serial in structure.]
 
With this tool in hand, we can now attempt bigger problems:
 
<lang J>ex2=:unpack ];._2]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 0
0 0 0 0
0 0 0
0 0 0 0 0
0 0
0 0
)</lang>
 
Finding a solution for this looks like:
 
<lang J> solve1 ex2
__ __ __ __ __ 1 __ 5 __ __ __ __ __
__ __ __ __ __ 6 __ 46 __ __ __ __ __
__ __ __ __ 48 45 2 7 4 __ __ __ __
__ __ __ __ __ 8 47 44 __ __ __ __ __
__ __ 56 __ __ 49 __ 3 __ __ 42 __ __
13 52 11 50 9 __ __ __ 43 38 31 36 33
__ __ 14 55 __ __ __ __ __ 41 34 __ __
53 12 51 10 15 __ __ __ 39 30 37 32 35
__ __ 54 __ __ 23 __ 29 __ __ 40 __ __
__ __ __ __ __ 16 19 22 __ __ __ __ __
__ __ __ __ 24 21 26 17 28 __ __ __ __
__ __ __ __ __ 18 __ 20 __ __ __ __ __
__ __ __ __ __ 25 __ 27 __ __ __ __ __</lang>
 
=={{header|Java}}==
{{works with|Java|8}}
<lang java>import java.util.*;
 
public class HolyKnightsTour {
 
final static String[] board = {
" xxx ",
" x xx ",
" xxxxxxx",
"xxx x x",
"x x xxx",
"1xxxxxx ",
" xx x ",
" xxx "};
 
private final static int base = 12;
private final static int[][] moves = {{1, -2}, {2, -1}, {2, 1}, {1, 2},
{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}};
private static int[][] grid;
private static int total = 2;
 
public static void main(String[] args) {
int row = 0, col = 0;
 
grid = new int[base][base];
 
for (int r = 0; r < base; r++) {
Arrays.fill(grid[r], -1);
for (int c = 2; c < base - 2; c++) {
if (r >= 2 && r < base - 2) {
if (board[r - 2].charAt(c - 2) == 'x') {
grid[r][c] = 0;
total++;
}
if (board[r - 2].charAt(c - 2) == '1') {
row = r;
col = c;
}
}
}
}
 
grid[row][col] = 1;
 
if (solve(row, col, 2))
printResult();
}
 
private static boolean solve(int r, int c, int count) {
if (count == total)
return true;
 
List<int[]> nbrs = neighbors(r, c);
 
if (nbrs.isEmpty() && count != total)
return false;
 
Collections.sort(nbrs, (a, b) -> a[2] - b[2]);
 
for (int[] nb : nbrs) {
r = nb[0];
c = nb[1];
grid[r][c] = count;
if (solve(r, c, count + 1))
return true;
grid[r][c] = 0;
}
 
return false;
}
 
private static List<int[]> neighbors(int r, int c) {
List<int[]> nbrs = new ArrayList<>();
 
for (int[] m : moves) {
int x = m[0];
int y = m[1];
if (grid[r + y][c + x] == 0) {
int num = countNeighbors(r + y, c + x) - 1;
nbrs.add(new int[]{r + y, c + x, num});
}
}
return nbrs;
}
 
private static int countNeighbors(int r, int c) {
int num = 0;
for (int[] m : moves)
if (grid[r + m[1]][c + m[0]] == 0)
num++;
return num;
}
 
private static void printResult() {
for (int[] row : grid) {
for (int i : row) {
if (i == -1)
System.out.printf("%2s ", ' ');
else
System.out.printf("%2d ", i);
}
System.out.println();
}
}
}</lang>
<pre> 19 26 21
28 18 25
33 20 27 22 17 24 7
29 2 35 8 16
34 32 23 6 9
1 30 3 36 13 10 15
12 31 5
4 11 14 </pre>
 
=={{header|Phix}}==
Tweaked the knights tour algorithm (to use a limit variable rather than size*size). Bit slow on the second one... (hence omitted under pwa/p2js)
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>sequence board, warnsdorffs
<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>
integer size, limit, nchars
string fmt, blank
<span style="color: #004080;">integer</span> <span style="color: #000000;">size</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: #004080;">string</span> <span style="color: #000000;">fmt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">blank</span>
constant ROW = 1, COL = 2
constant moves = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}}
<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: #0000FF;">,</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;">2</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;">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: #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;">2</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;">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: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
function onboard(integer row, integer col)
return row>=1 and row<=size and col>=nchars and col<=nchars*size
<span style="color: #008080;">function</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">row</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">size</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;">size</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure init_warnsdorffs()
integer nrow,ncol
<span style="color: #008080;">procedure</span> <span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</span>
for row=1 to size do
<span style="color: #008080;">for</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">size</span> <span style="color: #008080;">do</span>
for col=nchars to nchars*size by nchars do
<span style="color: #008080;">for</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nchars</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nchars</span><span style="color: #0000FF;">*</span><span style="color: #000000;">size</span> <span style="color: #008080;">by</span> <span style="color: #000000;">nchars</span> <span style="color: #008080;">do</span>
for move=1 to length(moves) do
<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>
nrow = row+moves[move][ROW]
<span style="color: #004080;">integer</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>
ncol = col+moves[move][COL]*nchars
<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>
if onboard(nrow,ncol) then
<span style="color: #008080;">if</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
-- (either of these would work)
<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>
warnsdorffs[row][col] += 1
-- <span warnsdorffs[nrow][ncol]style="color: #008080;">end</span> <span +style="color: 1#008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: if#008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
end for
end procedure
<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;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
atom t0 = time()
<span style="color: #004080;">integer</span> <span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">backtracks</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
integer tries = 0, backtracks = 0
<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>
atom t1 = time()+1
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
function solve(integer row, integer col, integer n)
<span style="color: #0000FF;">?{</span><span style="color: #000000;">row</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">floor</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: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">}</span>
integer nrow, ncol
<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: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
if time()>t1 then
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
?{row,floor(col/nchars),n,tries}
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
puts(1,join(board,"\n"))
<span style="color: #000000;">tries</span><span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
t1 = time()+1
<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>
-- if wait_key()='!' then ?9/0 end if
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ncol</span>
tries+= 1
<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>
if n>limit then return 1 end if
<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>
sequence wmoves = {}
<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>
for move=1 to length(moves) do
<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>
nrow = row+moves[move][ROW]
<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>
ncol = col+moves[move][COL]*nchars
<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>
if onboard(nrow,ncol)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
and board[nrow][ncol]=' ' then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
wmoves = append(wmoves,{warnsdorffs[nrow][ncol],nrow,ncol})
<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>
end if
<span style="color: #000080;font-style:italic;">-- avoid creating orphans</span>
end for
<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>
wmoves = sort(wmoves)
<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>
-- avoid creating orphans
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
if length(wmoves)<2 or wmoves[2][1]>1 then
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
for m=1 to length(wmoves) do
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
{?,nrow,ncol} = wmoves[m]
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
warnsdorffs[nrow][ncol] -= 1
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #004080;">integer</span> <span style="color: #000000;">scol</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>
for m=1 to length(wmoves) do
<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;">scol</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>
{?,nrow,ncol} = wmoves[m]
<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>
board[nrow][ncol-nchars+1..ncol] = sprintf(fmt,n)
<span style="color: #000000;">backtracks</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
if solve(nrow,ncol,n+1) then return 1 end if
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">scol</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>
backtracks += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
board[nrow][ncol-nchars+1..ncol] = blank
<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>
end for
<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>
for m=1 to length(wmoves) do
<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>
{?,nrow,ncol} = wmoves[m]
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
warnsdorffs[nrow][ncol] += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
return 0
end function
<span style="color: #008080;">procedure</span> <span style="color: #000000;">holyknight</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: #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>
procedure holyknight(sequence s)
<span style="color: #000000;">size</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>
integer y, ch, sx, sy
<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;">size</span><span style="color: #0000FF;">*</span><span style="color: #000000;">size</span><span style="color: #0000FF;">))</span>
s = split(s,'\n')
<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>
size = length(s)
<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>
nchars = length(sprintf(" %d",size*size))
<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;">size</span><span style="color: #0000FF;">*</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">),</span><span style="color: #000000;">size</span><span style="color: #0000FF;">)</span>
fmt = sprintf(" %%%dd",nchars-1)
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
blank = repeat(' ',nchars)
<span style="color: #004080;">integer</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sy</span>
board = repeat(repeat(' ',size*nchars),size)
<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;">size</span> <span style="color: #008080;">do</span>
limit = 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nchars</span>
for x=1 to size do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">size</span> <span style="color: #008080;">do</span>
y = nchars
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</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: #008000;">'-'</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;">j</span><span style="color: #0000FF;">])</span>
for j=1 to size do
<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>
if j>length(s[x]) then
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'-'</span>
ch = '-'
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
ch = s[x][j]
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end if
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'1'</span> <span style="color: #008080;">then</span>
if ch=' ' then
<span style="color: #000000;">sx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
ch = '-'
<span style="color: #000000;">sy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span>
elsif ch='0' then
<span style="color: #008080;">end</span> ch<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>
limit += 1
<span style="color: #000000;">y</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">nchars</span>
elsif ch='1' then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
sx = x
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
sy = y
<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;">size</span><span style="color: #0000FF;">*</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">),</span><span style="color: #000000;">size</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</span>
board[x][y] = ch
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
y += nchars
<span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
end for
<span style="color: #000000;">backtracks</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
end for
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
warnsdorffs = repeat(repeat(0,size*nchars),size)
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
init_warnsdorffs()
<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>
t0 = time()
<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, %d backtracks (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">,</span><span style="color: #000000;">backtracks</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>
tries = 0
<span style="color: #008080;">else</span>
backtracks = 0
<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>
t1 = time()+1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if solve(sx,sy,2) then
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
puts(1,join(board,"\n"))
printf(1,"\nsolution found in %d tries, %d backtracks (%3.2fs)\n",{tries,backtracks,time()-t0})
<span style="color: #008080;">constant</span> <span style="color: #000000;">board1</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
else
000
puts(1,"no solutions found\n")
0 end if00
0000000
end procedure
000 0 0
 
0 0 000
constant board1 = """
1000000
000
0 00 0
000"""</span>
0000000
000 0 0
<span style="color: #000000;">holyknight</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board1</span><span style="color: #0000FF;">)</span>
0 0 000
1000000
<span style="color: #008080;">constant</span> <span style="color: #000000;">board2</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
00 0
-----1-0-----
000"""
-----0-0-----
 
----00000----
holyknight(board1)
-----000-----
 
--0--0-0--0--
constant board2 = """
00000---00000
-----1-0-----
--00---0-0---00--
- 00000---00000----
--0--0-000-0--0--
--0--0-0000---0--
00000 ----00000----
--00---0-0---00--
-----0-0-----"""</span>
00000---00000
--0--0-0--0--
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
-----000-----
<span style="color: #000000;">holyknight</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board2</span><span style="color: #0000FF;">)</span>
----00000----
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-----0-0-----
-----0-0-----"""
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
 
<!--</syntaxhighlight>-->
holyknight(board2)
 
{} = wait_key()</lang>
{{out}}
<pre>
Line 2,226 ⟶ 3,721:
- - - - - 27 - 29 - - - - -
solution found in 61341542 tries, 61341486 backtracks (180.56s)
</pre>
 
=={{header|Picat}}==
<syntaxhighlight lang="picat">import sat.
 
main =>
S = {".000....",
".0.00...",
".0000000",
"000..0.0",
"0.0..000",
"1000000.",
"..00.0..",
"...000.."},
MaxR = len(S),
MaxC = len(S[1]),
M = new_array(MaxR,MaxC),
StartR = _, % make StartR and StartC global
StartC = _,
foreach (R in 1..MaxR)
fill_row(R, S[R], M[R], 1, StartR, StartC)
end,
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],
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 Neibs, M[R1,C1] !== 0],
hcp(Vs,Es),
foreach ({(R,C),(R1,C1),B} in Es)
B #/\ (R1 #!= StartR #\/ C1 #!= StartC) #=> 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.
 
neibs(M,MaxR,MaxC,R,C,Neibs) =>
Connected = [(R+1, C+2),
(R+1, C-2),
(R-1, C+2),
(R-1, C-2),
(R+2, C+1),
(R+2, C-1),
(R-2, C+1),
(R-2, C-1)],
Neibs = [(R1,C1) : (R1,C1) in Connected,
R1 >= 1, R1 =< MaxR, C1 >= 1, C1 =< MaxC,
M[R1,C1] !== 0].
 
fill_row(_R, [], _Row, _C, _StartR, _StartC) => true.
fill_row(R, ['.'|Str], Row, C, StartR, StartC) =>
Row[C] = 0,
fill_row(R,Str, Row, C+1, StartR, StartC).
fill_row(R, ['0'|Str], Row, C, StartR, StartC) =>
fill_row(R, Str, Row, C+1, StartR, StartC).
fill_row(R, ['1'|Str], Row, C, StartR, StartC) =>
Row[C] = 1,
StartR = R,
StartC = C,
fill_row(R, Str, Row, C+1, StartR, StartC).
</syntaxhighlight>
{{out}}
<pre>
. 7 4 25 . . . .
. 26 . 8 5 . . .
. 29 6 3 24 9 18 11
27 2 23 . . 12 . 16
30 . 28 . . 17 10 19
1 22 31 34 13 20 15 .
. . 36 21 . 33 . .
. . . 32 35 14 . .
</pre>
 
=={{header|Python}}==
<syntaxhighlight lang="python">
from sys import stdout
moves = [
[-1, -2], [1, -2], [-1, 2], [1, 2],
[-2, -1], [-2, 1], [2, -1], [2, 1]
]
 
 
def solve(pz, sz, sx, sy, idx, cnt):
if idx > cnt:
return 1
 
for i in range(len(moves)):
x = sx + moves[i][0]
y = sy + moves[i][1]
if sz > x > -1 and sz > y > -1 and pz[x][y] == 0:
pz[x][y] = idx
if 1 == solve(pz, sz, x, y, idx + 1, cnt):
return 1
pz[x][y] = 0
 
return 0
 
 
def find_solution(pz, sz):
p = [[-1 for j in range(sz)] for i in range(sz)]
idx = x = y = cnt = 0
for j in range(sz):
for i in range(sz):
if pz[idx] == "x":
p[i][j] = 0
cnt += 1
elif pz[idx] == "s":
p[i][j] = 1
cnt += 1
x = i
y = j
idx += 1
 
if 1 == solve(p, sz, x, y, 2, cnt):
for j in range(sz):
for i in range(sz):
if p[i][j] != -1:
stdout.write(" {:0{}d}".format(p[i][j], 2))
else:
stdout.write(" ")
print()
else:
print("Cannot solve this puzzle!")
 
 
# entry point
find_solution(".xxx.....x.xx....xxxxxxxxxx..x.xx.x..xxxsxxxxxx...xx.x.....xxx..", 8)
print()
find_solution(".....s.x..........x.x.........xxxxx.........xxx.......x..x.x..x..xxxxx...xxxxx..xx.....xx..xxxxx...xxxxx..x..x.x..x.......xxx.........xxxxx.........x.x..........x.x.....", 13)
</syntaxhighlight>
{{out}}<pre>
17 14 29
28 18 15
13 16 27 30 19 32 07
25 02 11 06 20
12 26 31 08 33
01 24 03 10 05 34 21
36 23 09
04 35 22
01 05
10 12
02 13 04 09 06
08 11 14
36 03 07 16
35 42 33 44 37 15 20 27 22 25
38 41 17 24
39 34 43 32 45 19 28 21 26 23
40 31 29 18
46 51 56
52 55 30 47 50
48 54
53 49
</pre>
 
Line 2,236 ⟶ 3,893:
It solves the tasked problem, as well as the "extra credit" from [[#Ada]].
 
<langsyntaxhighlight lang="racket">#lang racket
(require "hidato-family-solver.rkt")
 
Line 2,273 ⟶ 3,930:
#(- - - - 0 0 0 0 0 - - - -)
#(- - - - - 0 - 0 - - - - -)
#(- - - - - 0 - 0 - - - - -)))))</langsyntaxhighlight>
 
{{out}}
Line 2,298 ⟶ 3,955:
_ _ _ _ _ 38 _ 34 _ _ _ _ _
_ _ _ _ _ 35 _ 15 _ _ _ _ _</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 =
[ -2, -1], [ -2, 1],
[-1,-2], [-1,+2],
[+1,-2], [+1,+2],
[ +2, -1], [ +2, 1];
 
put "\n" xx 60;
 
solveboard q:to/END/;
. 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
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>
 
{{out}}
<pre> 25 14 27
36 24 15
31 26 13 28 23 6 17
35 12 29 16 22
30 32 7 18 5
1 34 11 8 19 4 21
2 33 9
10 3 20
84 tries</pre>
 
=={{header|REXX}}==
This REXX program is essentially a modified &nbsp; ''knight's tour'' &nbsp; REXX program with support to place pennies on the chessboard.
 
<br>Also supported is the specification of the size of the chessboard and the placement of the knight (initial position).
Also supported is the specification of the size of the chessboard and the placement of the knight (initial position).
<lang rexx>/*REXX program solves the holy knight's tour problem for a (general) NxN chessboard.*/
 
This is an &nbsp; ''open tour'' &nbsp; solution. &nbsp; (See this task's &nbsp; ''discussion'' &nbsp; page for an explanation &nbsp; [in the first section]).
<syntaxhighlight lang="rexx">/*REXX program solves the holy knight's tour problem for a (general) NxN chessboard.*/
blank=pos('//', space(arg(1), 0))\==0 /*see if the pennies are to be shown. */
parse arg ops '/' cent /*obtain the options and the pennies. */
Line 2,365 ⟶ 4,150:
end /*try a different move. */
end /*t*/ /* [↑] all moves tried.*/
return 0 /*tour isn't possible. */</langsyntaxhighlight>
'''output''' &nbsp; when the following is used for input:
<br><tt> , 3 1 /1,1 3 /1,7 2 /2,1 2 /2,5 /2,7 2 /3,8 /4,2 /4,4 2 /5,4 2 /5,7 /6,1 /7,1 /7,3 /7,6 3 /8,1 /8,5 4 </tt>
Line 2,417 ⟶ 4,202:
=={{header|Ruby}}==
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#With_Warnsdorff | here]]
<langsyntaxhighlight lang="ruby">require 'HLPsolver'
 
ADJACENT = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
Line 2,433 ⟶ 4,218:
t0 = Time.now
HLPsolver.new(boardy).solve
puts " #{Time.now - t0} sec"</langsyntaxhighlight>
 
Which produces:
Line 2,463 ⟶ 4,248:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.6
 
oo::class create HKTSolver {
Line 2,560 ⟶ 4,345:
HKTSolver create hkt $puzzle
hkt solve
showPuzzle [hkt solution] "Output"</langsyntaxhighlight>
{{out}}
<pre>
Line 2,582 ⟶ 4,367:
20 35 24
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
 
var moves = [ [-1, -2], [1, -2], [-1, 2], [1, 2], [-2, -1], [-2, 1], [2, -1], [2, 1] ]
 
var board1 =
" xxx " +
" x xx " +
" xxxxxxx" +
"xxx x x" +
"x x xxx" +
"sxxxxxx " +
" xx x " +
" xxx "
 
var board2 =
".....s.x....." +
".....x.x....." +
"....xxxxx...." +
".....xxx....." +
"..x..x.x..x.." +
"xxxxx...xxxxx" +
"..xx.....xx.." +
"xxxxx...xxxxx" +
"..x..x.x..x.." +
".....xxx....." +
"....xxxxx...." +
".....x.x....." +
".....x.x....."
 
var solve // recursive
solve = Fn.new { |pz, sz, sx, sy, idx, cnt|
if (idx > cnt) return true
for (i in 0...moves.count) {
var x = sx + moves[i][0]
var y = sy + moves[i][1]
if ((x >= 0 && x < sz) && (y >= 0 && y < sz) && pz[x][y] == 0) {
pz[x][y] = idx
if (solve.call(pz, sz, x, y, idx + 1, cnt)) return true
pz[x][y] = 0
}
}
return false
}
 
var findSolution = Fn.new { |b, sz|
var pz = List.filled(sz, null)
for (i in 0...sz) pz[i] = List.filled(sz, -1)
var x = 0
var y = 0
var idx = 0
var cnt = 0
for (j in 0...sz) {
for (i in 0...sz) {
if (b[idx] == "x") {
pz[i][j] = 0
cnt = cnt + 1
} else if (b[idx] == "s") {
pz[i][j] = 1
cnt = cnt + 1
x = i
y = j
}
idx = idx + 1
}
}
 
if (solve.call(pz, sz, x, y, 2, cnt)) {
for (j in 0...sz) {
for (i in 0...sz) {
if (pz[i][j] != -1) {
Fmt.write("$02d ", pz[i][j])
} else {
System.write("-- ")
}
}
System.print()
}
} else {
System.print("Cannot solve this puzzle!")
}
}
 
findSolution.call(board1, 8)
System.print()
findSolution.call(board2, 13)</syntaxhighlight>
 
{{out}}
<pre>
-- 17 14 29 -- -- -- --
-- 28 -- 18 15 -- -- --
-- 13 16 27 30 19 32 07
25 02 11 -- -- 06 -- 20
12 -- 26 -- -- 31 08 33
01 24 03 10 05 34 21 --
-- -- 36 23 -- 09 -- --
-- -- -- 04 35 22 -- --
 
-- -- -- -- -- 01 -- 05 -- -- -- -- --
-- -- -- -- -- 10 -- 12 -- -- -- -- --
-- -- -- -- 02 13 04 09 06 -- -- -- --
-- -- -- -- -- 08 11 14 -- -- -- -- --
-- -- 36 -- -- 03 -- 07 -- -- 16 -- --
35 42 33 44 37 -- -- -- 15 20 27 22 25
-- -- 38 41 -- -- -- -- -- 17 24 -- --
39 34 43 32 45 -- -- -- 19 28 21 26 23
-- -- 40 -- -- 31 -- 29 -- -- 18 -- --
-- -- -- -- -- 46 51 56 -- -- -- -- --
-- -- -- -- 52 55 30 47 50 -- -- -- --
-- -- -- -- -- 48 -- 54 -- -- -- -- --
-- -- -- -- -- 53 -- 49 -- -- -- -- --
</pre>
 
[[Category:Puzzles]]
Peak
2,502

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/247441...365453"