Solve a Holy Knight's tour: Difference between revisions
m
→{{header|Wren}}: Minor tidy
mNo edit summary |
m (→{{header|Wren}}: Minor tidy) |
||
(47 intermediate revisions by 17 users not shown) | |||
Line 1:
{{task}}
[[File:chess_white_knight.jpg|200px||right]]
Chess coaches have been known to inflict a kind of torture on beginners by taking a chess board, placing pennies on some squares and requiring that a Knight's tour be constructed that avoids the squares with pennies.
Line 6 ⟶ 8:
The present task is to produce a solution to such problems. At least demonstrate your program by solving the following:
;Example:
<pre>
0 0 0
Line 17 ⟶ 20:
0 0 0
</pre>
Note that the zeros represent the available squares, not the pennies.
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>
=={{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 30 ⟶ 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.
<
procedure Holy_Knight is
Line 65 ⟶ 156:
Ada.Text_IO.Put_Line("Tour:");
KT.Tour_IO(KT.Warnsdorff_Get_Tour(Start_X, Start_Y, Board));
end Holy_Knight;</
{{out}}
Line 125 ⟶ 216:
- - - - - 14 - 40 - - - - -
- - - - - 43 - 13 - - - - -</pre>
=={{header|ALGOL 68}}==
Uses a modified version of the [[Knight's Tour#ALGOL 68]] solution.
<syntaxhighlight lang="algol68"># directions for moves #
INT nne = 1, ne = 2, se = 3, sse = 4;
INT ssw = 5, sw = 6, nw = 7, nnw = 8;
INT lowest move = nne;
INT highest move = nnw;
# the vertical position changes of the moves #
[]INT offset v = ( -2, -1, 1, 2, 2, 1, -1, -2 );
# the horizontal position changes of the moves #
[]INT offset h = ( 1, 2, 2, 1, -1, -2, -2, -1 );
MODE SQUARE = STRUCT( INT move # the number of the move that caused #
# the knight to reach this square #
, INT direction # the direction of the move that #
# brought the knight here - one of #
# nne, ne, se, sse, ssw, sw, nw or #
# nnw #
);
# get the size of the board - must be between 4 and 8 #
INT board size = 8;
# the board #
[ board size, board size ]SQUARE board;
# starting position #
INT start row := 1;
INT start col := 1;
# the tour will be complete when we have made as many moves #
# as there are free squares in the initial board #
INT final move := 0;
# initialise the board setting the free squares from the supplied pttern #
# the pattern has the rows in revers order #
PROC initialise board = ( []STRING pattern )VOID:
BEGIN
INT pattern row := UPB board;
FOR row FROM 1 LWB board TO 1 UPB board
DO
FOR col FROM 2 LWB board TO 2 UPB board
DO
IF pattern[ pattern row ][ col ] = "-"
THEN
# can't use this square #
board[ row, col ] := ( -1, -1 )
ELSE
# available square #
board[ row, col ] := ( 0, 0 );
final move +:= 1;
IF pattern[ pattern row ][ col ] = "1"
THEN
# have the start position #
start row := row;
start col := col
FI
FI
OD;
pattern row -:= 1
OD
END; # initialise board #
# statistics #
INT iterations := 0;
INT backtracks := 0;
# prints the board #
PROC print tour = VOID:
BEGIN
# format "number" into at least two characters #
PROC n2 = ( INT number )STRING:
IF number < 0
THEN
" -"
ELIF number < 10 AND number >= 0
THEN
" " + whole( number, 0 )
ELSE
whole( number, 0 )
FI; # n2 #
print( ( " a b c d e f g h", newline ) );
print( ( " ________________________", newline ) );
FOR row FROM 1 UPB board BY -1 TO 1 LWB board
DO
print( ( n2( row ) ) );
print( ( "|" ) );
FOR col FROM 2 LWB board TO 2 UPB board
DO
print( ( " " ) );
print( ( n2( move OF board[ row, col ] ) ) )
OD;
print( ( newline ) )
OD
END; # print tour #
# update the board to the first knight's tour found starting from #
# "start row" and "start col". #
# return TRUE if one was found, FALSE otherwise #
PROC find tour = BOOL:
BEGIN
BOOL result := TRUE;
INT move number := 1;
INT row := start row;
INT col := start col;
INT direction := lowest move - 1;
# the first move is to place the knight on the starting square #
board[ row, col ] := ( move number, lowest move - 1 );
# attempt to find a sequence of moves that will reach each square once #
WHILE
move number < final move AND result
DO
IF direction < highest move
THEN
# try the next move from this position #
direction +:= 1;
INT new row = row + offset v[ direction ];
INT new col = col + offset h[ direction ];
IF new row <= 1 UPB board
AND new row >= 1 LWB board
AND new col <= 2 UPB board
AND new col >= 2 LWB board
THEN
# the move is legal, check the new square is unused #
IF move OF board[ new row, new col ] = 0
THEN
# can move here #
iterations +:= 1;
row := new row;
col := new col;
move number +:= 1;
board[ row, col ] := ( move number, direction );
direction := lowest move - 1
FI
FI
ELSE
# no more moves from this position - backtrack #
IF move number = 1
THEN
# at the starting position - no solution #
result := FALSE
ELSE
# not at the starting position - undo the latest move #
backtracks +:= 1;
move number -:= 1;
INT curr row := row;
INT curr col := col;
row -:= offset v[ direction OF board[ curr row, curr col ] ];
col -:= offset h[ direction OF board[ curr row, curr col ] ];
# determine which direction to try next #
direction := direction OF board[ curr row, curr col ];
# reset the square we just backtracked from #
board[ curr row, curr col ] := ( 0, 0 )
FI
FI
OD;
result
END; # find tour #
main:(
initialise board( ( "-000----"
, "-0-00---"
, "-0000000"
, "000--0-0"
, "0-0--000"
, "1000000-"
, "--00-0--"
, "---000--"
)
);
IF find tour
THEN
# found a solution #
print tour
ELSE
# couldn't find a solution #
print( ( "Solution not found", newline ) )
FI;
print( ( iterations, " iterations, ", backtracks, " backtracks", newline ) )
)</syntaxhighlight>
{{out}}
<pre>
a b c d e f g h
________________________
8| - 21 34 25 - - - -
7| - 24 - 20 7 - - -
6| - 35 22 33 26 11 6 9
5| 23 32 19 - - 8 - 12
4| 36 - 16 - - 27 10 5
3| 1 18 31 28 15 4 13 -
2| - - 2 17 - 29 - -
1| - - - 30 3 14 - -
+578929 iterations, +578894 backtracks
</pre>
=={{header|Bracmat}}==
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.
<
= begin colWidth crumbs non-empty pairs path parseLine
, display isolateStartCell minDistance numberElementsAndSort
Line 341 ⟶ 626:
& whl'(!boards:%?board ?boards&Holy-Knight$!board)
& done
);</
Output:
<pre>
Line 389 ⟶ 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++}}==
<
#include <vector>
#include <sstream>
Line 527 ⟶ 988:
return system( "pause" );
}
</syntaxhighlight>
{{out}}
Line 558 ⟶ 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.
<
std.typecons, std.typetuple;
Line 690 ⟶ 1,151:
writefln("One solution:\n%(%-(%2s %)\n%)\n", solution);
}
}</
{{out}}
<pre>One solution:
Line 718 ⟶ 1,179:
Run-time about 0.58 seconds with ldc2 compiler (using a switch statement if you don't have the predSwitch yet in Phobos), about 23 times faster than the Haskell entry.
=={{header|Elixir}}==
{{trans|Ruby}}
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]]
<syntaxhighlight lang="elixir"># require HLPsolver
adjacent = [{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}]
"""
. . 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
"""
|> HLPsolver.solve(adjacent)
"""
_ _ _ _ _ 1 _ 0
_ _ _ _ _ 0 _ 0
_ _ _ _ 0 0 0 0 0
_ _ _ _ _ 0 0 0
_ _ 0 _ _ 0 _ 0 _ _ 0
0 0 0 0 0 _ _ _ 0 0 0 0 0
_ _ 0 0 _ _ _ _ _ 0 0
0 0 0 0 0 _ _ _ 0 0 0 0 0
_ _ 0 _ _ 0 _ 0 _ _ 0
_ _ _ _ _ 0 0 0
_ _ _ _ 0 0 0 0 0
_ _ _ _ _ 0 _ 0
_ _ _ _ _ 0 _ 0
"""
|> HLPsolver.solve(adjacent)</syntaxhighlight>
{{out}}
<pre>
Problem:
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
Solution:
18 21 36
13 19 22
17 20 35 14 25 6 23
31 12 15 34 26
16 32 7 24 5
1 30 11 8 33 4 27
2 29 9
10 3 28
Problem:
1 0
0 0
0 0 0 0 0
0 0 0
0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0
0 0 0
0 0 0 0 0
0 0
0 0
Solution:
1 55
34 36
2 37 56 33 54
32 35 38
28 3 53 44
29 6 25 4 31 39 52 41 50 43
30 27 45 48
7 26 5 24 9 47 40 51 42 49
8 23 15 46
10 19 22
18 21 16 11 14
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
(Array, (//), (!), assocs, elems, bounds, listArray)
import
import Data.List (intercalate, transpose)
import Data.Maybe
type Position = (Int, Int)
type KnightBoard = Array Position (Maybe Int)
toSlot :: Char -> Maybe Int
toSlot '0' = Just 0
toSlot '1' = Just 1
toSlot _
toString :: Maybe Int -> String
toString Nothing
toString (Just n) = replicate (3 - length nn) ' ' ++ nn
where
Line 741 ⟶ 1,416:
chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs =
let (chunk, rest) = splitAt n xs
in chunk : chunksOf n rest
showBoard :: KnightBoard -> String
showBoard board =
where
(_, (_, height)) =
toBoard :: [String] -> KnightBoard
Line 754 ⟶ 1,431:
where
height = length strs
width
board =
listArray ((0, 0), (width - 1, height - 1)) . map toSlot . concat .
take width <$> strs
add
=> (a, a) -> (a, a) -> (a, a)
add (a, b) (x, y) = (a + x, b + y)
within
:: Ord a
=> ((a,
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 771 ⟶ 1,450:
validMoves board position = filter isValid plausible
where
bound
plausible
add position <$>
isValid pos = within bound pos && maybe False (== 0) (board ! pos)
isSolved :: KnightBoard -> Bool
isSolved =
-- Solve the knight's tour with a simple Depth First Search.
Line 783 ⟶ 1,463:
solveKnightTour board = solve board 1 initPosition
where
initPosition = fst $ head $ filter ((==
solve boardA depth position =
let boardB = boardA
in if isSolved boardB
then Just boardB
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_
[tourExA, tourExB]
case solveKnightTour $ toBoard board of
Nothing -> putStrLn "No solution.\n"
Just solution -> putStrLn $ showBoard solution ++ "\n")</syntaxhighlight>
{{out}}
<pre> 19 26 17
Line 849 ⟶ 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 #-}
import
import qualified Data.Array.Unboxed as AU
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 861 ⟶ 1,554:
toSlot '0' = 0
toSlot '1' = 1
toSlot _
toString :: Int -> String
toString (-1) = replicate 3 ' '
toString n
where
nn = show n
Line 871 ⟶ 1,564:
chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs =
showBoard :: KnightBoard -> String
showBoard board =
where
(_, (_, height)) = AU.bounds board
Line 884 ⟶ 1,577:
where
height = length strs
width
board =
AU.listArray ((0, 0), (width - 1, height - 1)) . map toSlot . concat .
take width <$> strs
add
:: Num a
=> (a, a) -> (a, a) -> (a, a)
add (a, b) (x, y) = (a + x, b + y)
within
:: Ord a
=> ((a,
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 let assocs = AU.assocs board
array <-
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]
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_
[tourExA, tourExB]
(\board ->
case solveKnightTour
Nothing ->
Just solution -> putStrLn $ showBoard solution ++ "\n")</syntaxhighlight>
This version is similar to the previous one but:
* the working code is cleaned up slightly with minor optimisations here and there
* 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
* vector is used instead of array to take advantage of any fusion
This results in 117x speedup over the very first version. This speed up comes from a smarter traversal rather than from minor code optimisations.
<syntaxhighlight lang="haskell">
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -ddump-simpl -ddump-to-file -ddump-stg -O2 -fforce-recomp #-}
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)
tourExA :: [String]
tourExA =
[
,
,
,
,
,
,
,
]
tourExB :: [String]
tourExB =
[
,
,
,
,
,
,
,
,
,
,
,
,
]
main :: IO ()
main =
for_
[tourExA, tourExB]
(\board -> do
case solveKnightTour $ toBoard board of
Just solution -> putStrLn $ showBoard solution ++ "\n")
</syntaxhighlight>
==Icon and {{header|Unicon}}==
This is a Unicon-specific solution:
<
record Pos(r,c)
Line 1,077 ⟶ 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</
Sample run:
Line 1,109 ⟶ 1,950:
->
</pre>
=={{header|J}}==
Line 1,143 ⟶ 1,955:
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):
<
unpack=:verb define
Line 1,175 ⟶ 1,987:
moves=. (#~ (0{a.)={&y) moves
moves y adverb def (':';'y x} m')"0 (x+1){a.
)</
Letting that cook:
<
48422 8 8</
That's 48422 solutions. Here's one of them:
<
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
Line 1,192 ⟶ 2,004:
1 24 3 34 5 18 7 __
__ __ 36 19 __ 33 __ __
__ __ __ 4 35 6 __ __</
and here's a couple more:
<
__ 5 8 31 __ __ __ __
__ 32 __ 6 9 __ __ __
Line 1,213 ⟶ 2,025:
1 36 17 30 27 4 23 __
__ __ 2 21 __ 29 __ __
__ __ __ 28 3 22 __ __</
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.
Line 1,219 ⟶ 2,031:
So, let's just find one solution:
<
mask=. +./' '~:y
board=. __ 0 1 {~ {.@:>:@:"."0 mask#"1 y
Line 1,261 ⟶ 2,073:
moves=. (#~ 0={&y) moves
moves y adverb def (':';'y x} m')"0 x+1
)</
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):
<
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
Line 1,273 ⟶ 2,085:
1 24 3 34 5 18 7 __
__ __ 36 19 __ 33 __ __
__ __ __ 4 35 6 __ __</
[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.]
Line 1,279 ⟶ 2,091:
With this tool in hand, we can now attempt bigger problems:
<
1 0
0 0
Line 1,293 ⟶ 2,105:
0 0
0 0
)</
Finding a solution for this looks like:
<
__ __ __ __ __ 1 __ 5 __ __ __ __ __
__ __ __ __ __ 6 __ 46 __ __ __ __ __
Line 1,310 ⟶ 2,122:
__ __ __ __ 24 21 26 17 28 __ __ __ __
__ __ __ __ __ 18 __ 20 __ __ __ __ __
__ __ __ __ __ 25 __ 27 __ __ __ __ __</
=={{header|Java}}==
{{works with|Java|8}}
<
public class HolyKnightsTour {
Line 1,417 ⟶ 2,229:
}
}
}</
<pre> 19 26 21
28 18 25
Line 1,427 ⟶ 2,239:
4 11 14 </pre>
=={{header|
===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' ? '' : [];
})() :
// 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: true
}, rows);
// 2 or more arguments
// curry :: Function -> Function
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|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.
<syntaxhighlight 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
# required locations to visit.
use strict;
use overload '""' => "as_string";
use English;
# 'locations' must be a reference to an array of 2-element array references,
# where the first element is the rank index and the second is the file index.
use Class::Tiny qw(N locations);
use List::Util qw(all);
sub BUILD {
my $self = shift;
$self->{N} //= 8;
$self->{N} >= 3 or die "N must be at least 3";
all {ref($ARG) eq 'ARRAY' && scalar(@{$ARG}) == 2} @{$self->{locations}}
or die "At least one element of 'locations' is invalid";
return;
}
sub as_string {
my $self = shift;
my %idxs;
my $idx = 1;
foreach my $loc (@{$self->locations}) {
$idxs{join(q{K},@{$loc})} = $idx++;
}
my $str;
{
my $w = int(log(scalar(@{$self->locations}))/log(10.)) + 2;
my $fmt = "%${w}d";
my $N = $self->N;
my $non_tour = q{ } x ($w-1) . q{-};
for (my $r=0; $r<$N; $r++) {
for (my $f=0; $f<$N; $f++) {
my $k = join(q{K}, $r, $f);
$str .= exists($idxs{$k}) ? sprintf($fmt, $idxs{$k}) : $non_tour;
}
$str .= "\n";
}
}
return $str;
}
sub as_idx_hash {
my $self = shift;
my $N = $self->N;
my $result;
foreach my $pair (@{$self->locations}) {
my ($r, $f) = @{$pair};
$result->{$r * $N + $f}++;
}
return $result;
}
package KnightsTour;
use strict;
# If supplied, 'str' is parsed to set 'N', 'start_location', and
# 'locations_to_visit'. 'legal_move_idxs' is for improving performance.
use Class::Tiny qw( N start_location locations_to_visit str legal_move_idxs );
use English;
use Parallel::ForkManager;
use Time::HiRes qw( gettimeofday tv_interval );
sub BUILD {
my $self = shift;
if ($self->{str}) {
my ($n, $sl, $ltv) = _parse_input_string($self->{str});
$self->{N} = $n;
$self->{start_location} = $sl;
$self->{locations_to_visit} = $ltv;
}
$self->{N} //= 8;
$self->{N} >= 3 or die "N must be at least 3";
exists($self->{start_location}) or die "Must supply start_location";
die "start_location is invalid"
if ref($self->{start_location}) ne 'ARRAY' ||
scalar(@{$self->{start_location}}) != 2;
exists($self->{locations_to_visit}) or die "Must supply locations_to_visit";
ref($self->{locations_to_visit}) eq 'KT_Locations'
or die "locations_to_visit must be a KT_Locations instance";
$self->{N} == $self->{locations_to_visit}->N
or die "locations_to_visit has mismatched board size";
$self->precompute_legal_moves();
return;
}
sub _parse_input_string {
my @rows = split(/[\r\n]+/s, shift);
my $N = scalar(@rows);
my ($start_location, @to_visit);
for (my $r=0; $r<$N; $r++) {
my $row_r = $rows[$r];
for (my $f=0; $f<$N; $f++) {
my $c = substr($row_r, $f, 1);
if ($c eq '1') { $start_location = [$r, $f]; }
elsif ($c eq '0') { push @to_visit, [$r, $f]; }
}
}
$start_location or die "No starting location provided";
return ($N,
$start_location,
KT_Locations->new(N => $N, locations => \@to_visit));
}
sub precompute_legal_moves {
my $self = shift;
my $N = $self->{N};
my $ktl_ixs = $self->{locations_to_visit}->as_idx_hash();
for (my $r=0; $r<$N; $r++) {
for (my $f=0; $f<$N; $f++) {
my $k = $r * $N + $f;
$self->{legal_move_idxs}->{$k} =
_precompute_legal_move_idxs($r, $f, $N, $ktl_ixs);
}
}
return;
}
sub _precompute_legal_move_idxs {
my ($r, $f, $N, $ktl_ixs) = @ARG;
my $r_plus_1 = $r + 1; my $r_plus_2 = $r + 2;
my $r_minus_1 = $r - 1; my $r_minus_2 = $r - 2;
my $f_plus_1 = $f + 1; my $f_plus_2 = $f + 2;
my $f_minus_1 = $f - 1; my $f_minus_2 = $f - 2;
my @result = grep { exists($ktl_ixs->{$ARG}) }
map { $ARG->[0] * $N + $ARG->[1] }
grep {$ARG->[0] >= 0 && $ARG->[0] < $N &&
$ARG->[1] >= 0 && $ARG->[1] < $N}
([$r_plus_2, $f_minus_1], [$r_plus_2, $f_plus_1],
[$r_minus_2, $f_minus_1], [$r_minus_2, $f_plus_1],
[$r_plus_1, $f_plus_2], [$r_plus_1, $f_minus_2],
[$r_minus_1, $f_plus_2], [$r_minus_1, $f_minus_2]);
return \@result;
}
sub find_tour {
my $self = shift;
my $num_to_visit = scalar(@{$self->locations_to_visit->locations});
my $N = $self->N;
my $start_loc_idx =
$self->start_location->[0] * $N + $self->start_location->[1];
my $visited; for (my $i=0; $i<$N*$N; $i++) { vec($visited, $i, 1) = 0; }
vec($visited, $start_loc_idx, 1) = 1;
# We unwind the search by one level and use Parallel::ForkManager to search
# the top-level sub-trees concurrently, assuming there are enough cores.
my @next_loc_idxs = @{$self->legal_move_idxs->{$start_loc_idx}};
my $pm = new Parallel::ForkManager(scalar(@next_loc_idxs));
foreach my $next_loc_idx (@next_loc_idxs) {
$pm->start and next; # Do the fork
my $t0 = [gettimeofday];
vec($visited, $next_loc_idx, 1) = 1; # (The fork cloned $visited.)
my $tour = _find_tour_helper($N,
$num_to_visit - 1,
$next_loc_idx,
$visited,
$self->legal_move_idxs);
my $elapsed = tv_interval($t0);
my ($r, $f) = _idx_to_rank_and_file($next_loc_idx, $N);
if (defined $tour) {
my @tour_locs =
map { [_idx_to_rank_and_file($ARG, $N)] }
($start_loc_idx, $next_loc_idx, split(/\s+/s, $tour));
my $kt_locs = KT_Locations->new(N => $N, locations => \@tour_locs);
print "Found a tour after first move ($r, $f) ",
"in $elapsed seconds:\n", $kt_locs, "\n";
}
else {
print "No tour found after first move ($r, $f). ",
"Took $elapsed seconds.\n";
}
$pm->finish; # Do the exit in the child process
}
$pm->wait_all_children;
return;
}
sub _idx_to_rank_and_file {
my ($idx, $N) = @ARG;
my $f = $idx % $N;
my $r = ($idx - $f) / $N;
return ($r, $f);
}
sub _find_tour_helper {
my ($N, $num_to_visit, $current_loc_idx, $visited, $legal_move_idxs) = @ARG;
# The performance hot spot.
local *inner_helper = sub {
my ($num_to_visit, $current_loc_idx, $visited) = @ARG;
if ($num_to_visit == 0) {
return q{ }; # Solution found.
}
my @next_loc_idxs = @{$legal_move_idxs->{$current_loc_idx}};
my $num_to_visit2 = $num_to_visit - 1;
foreach my $loc_idx2 (@next_loc_idxs) {
next if vec($visited, $loc_idx2, 1);
my $visited2 = $visited;
vec($visited2, $loc_idx2, 1) = 1;
my $recursion = inner_helper($num_to_visit2, $loc_idx2, $visited2);
return $loc_idx2 . q{ } . $recursion if defined $recursion;
}
return;
};
return inner_helper($num_to_visit, $current_loc_idx, $visited);
}
package main;
use strict;
solve_size_8_problem();
solve_size_13_problem();
exit 0;
sub solve_size_8_problem {
my $problem = <<"END_SIZE_8_PROBLEM";
--000---
--0-00--
-0000000
000--0-0
0-0--000
1000000-
--00-0--
---000--
END_SIZE_8_PROBLEM
my $kt = KnightsTour->new(str => $problem);
print "Finding a tour for an 8x8 problem...\n";
$kt->find_tour();
return;
}
sub solve_size_13_problem {
my $problem = <<"END_SIZE_13_PROBLEM";
-----1-0-----
-----0-0-----
Line 1,571 ⟶ 3,335:
----00000----
-----0-0-----
-----0-0-----
END_SIZE_13_PROBLEM
my $kt = KnightsTour->new(str => $problem);
print "Finding a tour for a 13x13 problem...\n";
$kt->find_tour();
return;
}</syntaxhighlight>
{{out}}
The timings shown below were obtained on a Dell Optiplex 9020 with 4 cores.
<pre>...>holy_knights_tour.pl
Finding a tour for an 8x8 problem...
Found a tour after first move (6, 2) in 0.018372 seconds:
- - 18 31 16 - - -
- - 23 - 33 30 - -
- 19 32 17 24 15 34 29
7 22 5 - - 28 - 26
20 - 8 - - 25 14 35
1 6 21 4 11 36 27 -
- - 2 9 - 13 - -
- - - 12 3 10 - -
Found a tour after first move (4, 2) in 0.010491 seconds:
- - 30 23 20 - - -
- - 9 - 31 22 - -
- 29 24 21 10 19 32 15
25 8 27 - - 16 - 18
28 - 2 - - 11 14 33
1 26 7 12 5 34 17 -
- - 36 3 - 13 - -
- - - 6 35 4 - -
Found a tour after first move (3, 1) in 0.048164 seconds:
- - 28 11 14 - - -
- - 13 - 9 30 - -
- 27 10 29 12 15 18 31
23 2 25 - - 8 - 16
26 - 22 - - 17 32 19
1 24 3 34 5 20 7 -
- - 36 21 - 33 - -
- - - 4 35 6 - -
Finding a tour for a 13x13 problem...
Found a tour after first move (2, 6) in 78.827185 seconds:
- - - - - 1 - 21 - - - - -
- - - - - 22 - 6 - - - - -
- - - - 4 7 2 23 20 - - - -
- - - - - 24 5 8 - - - - -
- - 34 - - 3 - 19 - - 56 - -
35 30 37 28 25 - - - 9 18 11 16 13
- - 26 33 - - - - - 55 14 - -
31 36 29 38 27 - - - 53 10 17 12 15
- - 32 - - 39 - 45 - - 54 - -
- - - - - 46 49 52 - - - - -
- - - - 40 51 42 47 44 - - - -
- - - - - 48 - 50 - - - - -
- - - - - 41 - 43 - - - - -
Found a tour after first move (2, 4) in 100.327934 seconds:
- - - - - 1 - 23 - - - - -
- - - - - 24 - 20 - - - - -
- - - - 2 19 4 25 22 - - - -
- - - - - 26 21 18 - - - - -
- - 36 - - 3 - 5 - - 12 - -
37 32 39 30 27 - - - 17 6 15 8 13
- - 28 35 - - - - - 11 56 - -
33 38 31 40 29 - - - 55 16 7 14 9
- - 34 - - 41 - 47 - - 10 - -
- - - - - 48 51 54 - - - - -
- - - - 42 53 44 49 46 - - - -
- - - - - 50 - 52 - - - - -
- - - - - 43 - 45 - - - - -
Found a tour after first move (1, 7) in 1443.340089 seconds:
- - - - - 1 - 21 - - - - -
- - - - - 22 - 2 - - - - -
- - - - 18 3 16 23 20 - - - -
- - - - - 24 19 4 - - - - -
- - 34 - - 17 - 15 - - 56 - -
35 30 37 28 25 - - - 5 14 7 12 9
- - 26 33 - - - - - 55 10 - -
31 36 29 38 27 - - - 53 6 13 8 11
- - 32 - - 39 - 45 - - 54 - -
- - - - - 46 49 52 - - - - -
- - - - 40 51 42 47 44 - - - -
- - - - - 48 - 50 - - - - -
- - - - - 41 - 43 - - - - - </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)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">warnsdorffs</span>
<span style="color: #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>
<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>
<span style="color: #008080;">function</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">row</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">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>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">size</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nchars</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nchars</span><span style="color: #0000FF;">*</span><span style="color: #000000;">size</span> <span style="color: #008080;">by</span> <span style="color: #000000;">nchars</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #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>
<span style="color: #000000;">ncol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">COL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">nchars</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #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>
<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>
<span style="color: #008080;">function</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">tries</span><span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">limit</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ncol</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">nrow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ROW</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">ncol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">+</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">move</span><span style="color: #0000FF;">][</span><span style="color: #000000;">COL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">nchars</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">onboard</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">],</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">wmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- avoid creating orphans</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">2</span> <span style="color: #008080;">or</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
<span style="color: #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>
<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>
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">backtracks</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</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;">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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wmoves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{?,</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wmoves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">warnsdorffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nrow</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ncol</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">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>
<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>
<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>
<span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" %%%dd"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">blank</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">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>
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">sx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sy</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">size</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nchars</span>
<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>
<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>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'-'</span>
<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>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">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>
<span style="color: #000000;">sx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #000000;">sy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">nchars</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">warnsdorffs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">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>
<span style="color: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</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;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">backtracks</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</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>
<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>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nsolution found in %d tries, %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>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"no solutions found\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board1</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
000
0 00
0000000
000 0 0
0 0 000
1000000
00 0
000"""</span>
<span style="color: #000000;">holyknight</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">board2</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
-----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-----"""</span>
<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>
<span style="color: #000000;">holyknight</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,602 ⟶ 3,595:
- - - - - 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 1,612 ⟶ 3,767:
It solves the tasked problem, as well as the "extra credit" from [[#Ada]].
<
(require "hidato-family-solver.rkt")
Line 1,649 ⟶ 3,804:
#(- - - - 0 0 0 0 0 - - - -)
#(- - - - - 0 - 0 - - - - -)
#(- - - - - 0 - 0 - - - - -)))))</
{{out}}
Line 1,674 ⟶ 3,829:
_ _ _ _ _ 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 ''knight's tour'' REXX program with support to place pennies on the chessboard.
Also supported is the specification of the size of the chessboard and the placement of the knight (initial position).
This is an ''open tour'' solution. (See this task's ''discussion'' page for an explanation [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. */
parse var ops N sRank sFile . /*boardsize, starting position, pennys.*/
if N=='' | N=="," then N=8 /*no boardsize specified? Use default.*/
if sRank=='' | sRank=="," then sRank=N /*starting rank given? " " */
if sFile=='' | sFile=="," then sFile=1 /* " file " " " */
NN=N**2; NxN='a ' N"x"N ' chessboard' /*file [↓] [↓] r=rank */
@.=; do r=1 for N; do f=1 for N; @.r.f=.; end /*f*/; end /*r*/
/*[↑] create an empty NxN chessboard.*/
cent=space( translate( cent, , ','
cents=0 /*number of pennies on the chessboard. */
do while cent\='' /* [↓] possibly place the pennies. */
Line 1,694 ⟶ 3,977:
if x='' then x=1 /*if number not specified, use 1 penny.*/
if cr='' then iterate /*support the "blanking" option. */
end
/* [↓] traipse through the chessboard.*/
do r=1 for N; do f=1 for N;
/* [↑] count the number of pennies. */
if cents\==0 then say cents 'pennies placed on chessboard.'
target=NN -
parse var Kr Kr.1 Kr.2 Kr.3 Kr.4 Kr.5 Kr.6 Kr.7 Kr.8 /*parse the legal moves by hand.*/
parse var Kf Kf.1 Kf.2 Kf.3 Kf.4 Kf.5 Kf.6 Kf.7 Kf.8 /* " " " " " " */
beg= '-1-' /* [↑] create the NxN chessboard. */
if @.sRank.sFile ==. then @.sRank.sFile=beg /*the knight's starting position. */
if @.sRank.sFile\==beg then do sRank=1 for N /*find starting rank for the knight.*/
do sFile=1 for N /* " " file " " " */
Line 1,715 ⟶ 3,998:
@.sRank.sFile=beg /*the knight's starting position. */
leave sRank /*we have a spot, so leave all this.*/
end /*
end /*
@hkt= "holy knight's tour" /*a
if \move(2,sRank,sFile) & \(N==1) then say 'No' @hkt "solution for" NxN'.'
else say 'A solution for the' @hkt "on" NxN':'
/*show chessboard with moves
!=left('', 9 * (n<18) );
_=substr( copies("┼───", N), 2)
do r=N for N by -1; if r\==N then say ! '├'_"┤"; L=@.
do f=1 for N; ?=@.r.f; if ?==target then ?='end'; L=L'│'center(?,3)
end /*f*/
if blank then L=translate(L,,'¢') /*blank out the pennies on chessboard ?*/
Line 1,734 ⟶ 4,017:
/*──────────────────────────────────────────────────────────────────────────────────────*/
move: procedure expose @. Kr. Kf. target; parse arg #,rank,file /*obtain move,rank,file.*/
if #==target
if move(#+1,nr,nf)
@.nr.nf=.
'''output''' 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 1,766 ⟶ 4,049:
└───┴───┴───┴───┴───┴───┴───┴───┘
</pre>
'''output''' when the following (for a "cleaner" chessboard, no pennies are shown) 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>
<pre>
Line 1,793 ⟶ 4,076:
=={{header|Ruby}}==
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#With_Warnsdorff | here]]
<
ADJACENT = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
Line 1,809 ⟶ 4,092:
t0 = Time.now
HLPsolver.new(boardy).solve
puts " #{Time.now - t0} sec"</
Which produces:
Line 1,839 ⟶ 4,122:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
oo::class create HKTSolver {
Line 1,936 ⟶ 4,219:
HKTSolver create hkt $puzzle
hkt solve
showPuzzle [hkt solution] "Output"</
{{out}}
<pre>
Line 1,958 ⟶ 4,241:
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]]
|