Knight's tour: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (48 intermediate revisions by 15 users not shown) | |||
Line 21:
* [[Solve the no connection puzzle]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V _kmoves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
F chess2index(=chess, boardsize)
‘Convert Algebraic chess notation to internal index format’
chess = chess.lowercase()
V x = chess[0].code - ‘a’.code
V y = boardsize - Int(chess[1..])
R (x, y)
F boardstring(board, boardsize)
V r = 0 .< boardsize
V lines = ‘’
L(y) r
lines ‘’= "\n"r.map(x -> (I @board[(x, @y)] {‘#2’.format(@board[(x, @y)])} E ‘ ’)).join(‘,’)
R lines
F knightmoves(board, P, boardsize)
V (Px, Py) = P
V kmoves = Set(:_kmoves.map((x, y) -> (@Px + x, @Py + y)))
kmoves = Set(Array(kmoves).filter((x, y) -> x C 0 .< @boardsize & y C 0 .< @boardsize & !@board[(x, y)]))
R kmoves
F accessibility(board, P, boardsize)
[(Int, (Int, Int))] access
V brd = copy(board)
L(pos) knightmoves(board, P, boardsize' boardsize)
brd[pos] = -1
access.append((knightmoves(brd, pos, boardsize' boardsize).len, pos))
brd[pos] = 0
R access
F knights_tour(start, boardsize, _debug = 0B)
[(Int, Int) = Int] board
L(x) 0 .< boardsize
L(y) 0 .< boardsize
board[(x, y)] = 0
V move = 1
V P = chess2index(start, boardsize)
board[P] = move
move++
I _debug
print(boardstring(board, boardsize' boardsize))
L move <= board.len
P = min(accessibility(board, P, boardsize))[1]
board[P] = move
move++
I _debug
print(boardstring(board, boardsize' boardsize))
input("\n#2 next: ".format(move))
R board
L(boardsize, start) [(5, ‘c3’), (8, ‘h8’), (10, ‘e6’)]
print(‘boardsize: ’boardsize)
print(‘Start position: ’start)
V board = knights_tour(start, boardsize)
print(boardstring(board, boardsize' boardsize))
print()</syntaxhighlight>
{{out}}
<pre>
boardsize: 5
Start position: c3
19,12,17, 6,21
2, 7,20,11,16
13,18, 1,22, 5
8, 3,24,15,10
25,14, 9, 4,23
boardsize: 8
Start position: h8
38,41,18, 3,22,27,16, 1
19, 4,39,42,17, 2,23,26
40,37,54,21,52,25,28,15
5,20,43,56,59,30,51,24
36,55,58,53,44,63,14,29
9, 6,45,62,57,60,31,50
46,35, 8,11,48,33,64,13
7,10,47,34,61,12,49,32
boardsize: 10
Start position: e6
29, 4,57,24,73, 6,95,10,75, 8
58,23,28, 5,94,25,74, 7,100,11
3,30,65,56,27,72,99,96, 9,76
22,59, 2,63,68,93,26,81,12,97
31,64,55,66, 1,82,71,98,77,80
54,21,60,69,62,67,92,79,88,13
49,32,53,46,83,70,87,42,91,78
20,35,48,61,52,45,84,89,14,41
33,50,37,18,47,86,39,16,43,90
36,19,34,51,38,17,44,85,40,15
</pre>
=={{header|360 Assembly}}==
{{trans|BBC PASIC}}
<
KNIGHT CSECT
USING KNIGHT,R13 base registers
Line 278 ⟶ 378:
PG DC CL128' ' buffer
YREGS
END KNIGHT</
{{out}}
<pre>
Line 296 ⟶ 396:
First, we specify a naive implementation the package Knights_Tour with naive backtracking. It is a bit more general than required for this task, by providing a mechanism '''not''' to visit certain coordinates. This mechanism is actually useful for the task [[Solve a Holy Knight's tour#Ada]], which also uses the package Knights_Tour.
<
Size: Integer;
package Knights_Tour is
Line 317 ⟶ 417:
-- writes The_Tour to the output using Ada.Text_IO;
end Knights_Tour;</
Here is the implementation:
<
package body Knights_Tour is
Line 405 ⟶ 505:
end Tour_IO;
end Knights_Tour;</
Here is the main program:
<
procedure Test_Knight is
Line 419 ⟶ 519:
begin
KT.Tour_IO(KT.Get_Tour(1, 1));
end Test_Knight;</
For small sizes, this already works well (< 1 sec for size 8). Sample output:
Line 433 ⟶ 533:
For larger sizes we'll use Warnsdorff's heuristic (without any thoughtful tie breaking). We enhance the specification adding a function Warnsdorff_Get_Tour. This enhancement of the package Knights_Tour will also be used for the task [[Solve a Holy Knight's tour#Ada]]. The specification of Warnsdorff_Get_Tour is the following.
<syntaxhighlight lang="ada">
function Warnsdorff_Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty)
return Tour;
-- uses Warnsdorff heurisitic to find a tour faster
-- same interface as Get_Tour</
Its implementation is as follows.
<
return Tour is
Done: Boolean;
Line 526 ⟶ 626:
end if;
return Visited;
end Warnsdorff_Get_Tour;</
The modification for the main program is trivial:
<
procedure Test_Fast is
Line 539 ⟶ 639:
begin
KT.Tour_IO(KT.Warnsdorff_Get_Tour(1, 1));
end Test_Fast;</
This works still well for somewhat larger sizes:
Line 570 ⟶ 670:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
# If there are multiple choices, backtrack if the first choice doesn't #
# find a solution #
Line 857 ⟶ 957:
FI
)</
{{out}}
<pre>
Line 873 ⟶ 973:
</pre>
=={{header|
<syntaxhighlight lang="ats">(*
Find Knight’s Tours.
Using Warnsdorff’s heuristic, find multiple solutions.
Optionally accept only closed tours.
Compile with:
patscc -O3 -DATS_MEMALLOC_GCBDW -o knights_tour knights_tour.dats -lgc
Usage: ./knights_tour [START_POSITION [MAX_TOURS [closed]]]
Examples:
./knights_tour (prints one tour starting from a1)
./knights_tour c5
./knights_tour c5 2000
./knights_tour c5 2000 closed
*)
#define ATS_DYNLOADFLAG 0 (* No initialization is needed. *)
#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"
#define EMPTY_SQUARE ~1
macdef nil_move = @(~1, ~1)
fn
int_right_justified
{i : int}
{n : int | 0 <= n; n < 100}
(i : int i,
n : int n) :
string =
let
var buffer : @[char][100] = @[char][100] ('\0')
val _ = $extfcall (int, "snprintf", buffer, 100, "%*i", n, i)
in
strnptr2string (string1_copy ($UNSAFE.cast{string n} buffer))
end
typedef move_t (i : int,
j : int) =
@(int i, int j)
typedef move_t =
[i, j : int]
move_t (i, j)
fn
move_t_is_nil (move : move_t) :<>
bool =
let
val @(i, j) = move
val @(i_nil, j_nil) = nil_move
in
(i = i_nil && j = j_nil)
end
fn
move_t_fprint (f : FILEref,
move : move_t) :
void =
let
val @(i, j) = move
val letter = char2i 'a' + j - 1
val digit = char2i '0' + i
in
fileref_putc (f, letter);
fileref_putc (f, digit);
end
vtypedef chessboard_vt (t : t@ype,
n_ranks : int,
n_files : int,
p : addr) =
@{
pf_board = @[t][n_ranks * n_files] @ p |
n_ranks = uint n_ranks,
n_files = uint n_files,
n_squares = uint (n_ranks * n_files),
p_board = ptr p
}
vtypedef chessboard_vt (t : t@ype,
n_ranks : int,
n_files : int) =
[p : addr]
chessboard_vt (t, n_ranks, n_files, p)
vtypedef chessboard_vt (t : t@ype) =
[n_ranks, n_files : int]
chessboard_vt (t, n_ranks, n_files)
fn {t : t@ype}
chessboard_vt_make
{n_ranks, n_files : pos}
(n_ranks : uint n_ranks,
n_files : uint n_files,
fill : t) :
chessboard_vt (t, n_ranks, n_files) =
let
val size = u2sz (n_ranks * n_files)
val @(pf, pfgc | p) = array_ptr_alloc<t> (size)
val _ = array_initize_elt<t> (!p, size, fill)
prval _ = mfree_gc_v_elim pfgc (* Let the memory leak. *)
in
@{
pf_board = pf |
n_ranks = n_ranks,
n_files = n_files,
n_squares = n_ranks * n_files,
p_board = p
}
end
fn {t : t@ype}
chessboard_vt_get
{n_ranks, n_files : pos}
{i, j : int}
(chessboard : !chessboard_vt (t, n_ranks, n_files),
i : int i,
j : int j) :
t =
let
val index = (i - 1) + (u2i (chessboard.n_ranks) * (j - 1))
val _ = assertloc (0 <= index)
val _ = assertloc (index < u2i (chessboard.n_squares))
in
array_get_at (!(chessboard.p_board), index)
end
fn {t : t@ype}
chessboard_vt_set
{n_ranks, n_files : pos}
{i, j : int}
(chessboard : !chessboard_vt (t, n_ranks, n_files),
i : int i,
j : int j,
value : t) :
void =
let
val index = (i - 1) + (u2i (chessboard.n_ranks) * (j - 1))
val _ = assertloc (0 <= index)
val _ = assertloc (index < u2i (chessboard.n_squares))
in
array_set_at (!(chessboard.p_board), index, value)
end
extern fn {t : t@ype}
find_nth_position$equal (x : t,
y : t) :
bool
fn {t : t@ype}
find_nth_position
{n_ranks, n_files : pos}
(chessboard : !chessboard_vt (t, n_ranks, n_files),
n : t) :
[i, j : int]
move_t (i, j) =
let
val n_ranks = chessboard.n_ranks
val n_files = chessboard.n_files
fun
outer_loop {i : pos | i <= n_ranks + 1} .<n_ranks + 1 - i>.
(chessboard : !chessboard_vt (t, n_ranks, n_files),
i : int i) :
[i, j : int]
move_t (i, j) =
let
fun
inner_loop {j : pos | j <= n_files + 1} .<n_files + 1 - j>.
(chessboard : !chessboard_vt (t, n_ranks, n_files),
j : int j) :
[j : int]
int j =
if u2i n_files < j then
j
else
let
val v = chessboard_vt_get<t> (chessboard, i, j)
in
if find_nth_position$equal<t> (n, v) then
j
else
inner_loop (chessboard, succ j)
end
in
if u2i n_ranks < i then
nil_move
else
let
val j = inner_loop (chessboard, 1)
in
if j <= u2i n_files then
@(i, j)
else
outer_loop (chessboard, succ i)
end
end
in
outer_loop (chessboard, 1)
end
implement
find_nth_position$equal<int> (x, y) =
x = y
fn
knights_tour_is_closed
{n_ranks, n_files : pos}
(chessboard : !chessboard_vt (int, n_ranks, n_files)) :
bool =
let
val n_squares = chessboard.n_squares
val @(i1, j1) = find_nth_position<int> (chessboard, 1)
val @(i2, j2) = find_nth_position<int> (chessboard, u2i n_squares)
val i_diff = abs (i1 - i2)
val j_diff = abs (j1 - j2)
in
(i_diff = 1 && j_diff = 2) || (i_diff = 2 && j_diff = 1)
end
fn
knights_tour_board_fprint
{n_ranks, n_files : pos}
(f : FILEref,
chessboard : !chessboard_vt (int, n_ranks, n_files)) :
void =
{
val n_ranks = chessboard.n_ranks
val n_files = chessboard.n_files
fun
outer_loop {i : int | 0 <= i; i <= n_ranks} .<i>.
(chessboard : !chessboard_vt (int, n_ranks, n_files),
i : int i) :
void =
if 0 < i then
{
val _ = fileref_puts (f, " ")
val _ =
let
var j : [j : int] int j
in
for (j := 1; j <= u2i n_files; j := succ j)
fileref_puts (f, "+----")
end
val _ = fileref_puts (f, "+\n")
val _ = fileref_puts (f, int_right_justified (i, 2))
val _ = fileref_puts (f, " ")
fun
inner_loop {j : int | 1 <= j; j <= n_files + 1}
(chessboard : !chessboard_vt (int, n_ranks,
n_files),
j : int j) :
void =
if j <= u2i n_files then
{
val v = chessboard_vt_get<int> (chessboard, i, j)
val v = g1ofg0 v
val _ = fileref_puts (f, " | ")
val _ =
if v = EMPTY_SQUARE then
fileref_puts (f, " ")
else
fileref_puts (f, int_right_justified (g1ofg0 v, 2))
val _ = inner_loop (chessboard, succ j)
}
val _ = inner_loop (chessboard, 1)
val _ = fileref_puts (f, " |\n")
val _ = outer_loop (chessboard, pred i)
}
val _ = outer_loop (chessboard, u2i n_ranks)
val _ = fileref_puts (f, " ")
val _ =
let
var j : [j : int] int j
in
for (j := 1; j <= u2i n_files; j := succ j)
fileref_puts (f, "+----")
end
val _ = fileref_puts (f, "+\n")
val _ = fileref_puts (f, " ")
val _ =
let
var j : [j : int] int j
in
for (j := 1; j <= u2i n_files; j := succ j)
let
val letter = char2i 'a' + j - 1
in
fileref_puts (f, " ");
fileref_putc (f, letter)
end
end
}
fn
knights_tour_moves_fprint
{n_ranks, n_files : pos}
(f : FILEref,
chessboard : !chessboard_vt (int, n_ranks, n_files)) :
void =
{
prval _ = mul_pos_pos_pos (mul_make {n_ranks, n_files} ())
val n_ranks = chessboard.n_ranks
val n_files = chessboard.n_files
val n_squares = chessboard.n_squares
val @(pf, pfgc | p_positions) =
array_ptr_alloc<move_t> (u2sz n_squares)
val _ = array_initize_elt<move_t> (!p_positions, u2sz n_squares,
nil_move)
macdef positions = !p_positions
fun
loop {k : int | 0 <= k; k <= n_ranks * n_files}
.<n_ranks * n_files - k>.
(positions : &(@[move_t][n_ranks * n_files]),
chessboard : !chessboard_vt (int, n_ranks, n_files),
k : int k) :
void =
if k < u2i n_squares then
{
val i = u2i ((i2u k) mod n_ranks) + 1
val j = u2i ((i2u k) / n_ranks) + 1
val v = chessboard_vt_get<int> (chessboard, i, j)
val v = g1ofg0 v
val _ = assertloc (1 <= v)
val _ = assertloc (v <= u2i n_squares)
val _ = positions[v - 1] := @(i, j)
val _ = loop (positions, chessboard, succ k)
}
val _ = loop (positions, chessboard, 0)
fun
loop {k : int | 0 <= k; k < n_ranks * n_files}
.<n_ranks * n_files - k>.
(positions : &(@[move_t][n_ranks * n_files]),
k : int k) :
void =
if k < u2i (pred n_squares) then
{
val _ = move_t_fprint (f, positions[k])
val line_end = (((i2u (k + 1)) mod n_files) = 0U)
val _ =
fileref_puts (f, (if line_end then " ->\n" else " -> "))
val _ = loop (positions, succ k)
}
val _ = loop (positions, 0)
val _ = move_t_fprint (f, positions[pred n_squares])
val _ =
if knights_tour_is_closed (chessboard) then
fileref_puts (f, " -> cycle")
val _ = array_ptr_free (pf, pfgc | p_positions)
}
typedef knights_moves_t =
@(move_t, move_t, move_t, move_t,
move_t, move_t, move_t, move_t)
fn
possible_moves {n_ranks, n_files : pos}
{i, j : int}
(chessboard : !chessboard_vt (int, n_ranks, n_files),
i : int i,
j : int j) :
knights_moves_t =
let
fn
try_move {istride, jstride : int}
(chessboard : !chessboard_vt (int, n_ranks, n_files),
istride : int istride,
jstride : int jstride) :
move_t =
let
val i1 = i + istride
val j1 = j + jstride
in
if i1 < 1 then
nil_move
else if u2i (chessboard.n_ranks) < i1 then
nil_move
else if j1 < 1 then
nil_move
else if u2i (chessboard.n_files) < j1 then
nil_move
else
let
val v = chessboard_vt_get (chessboard, i1, j1) : int
in
if v <> EMPTY_SQUARE then
nil_move
else
@(i1, j1)
end
end
val move0 = try_move (chessboard, 1, 2)
val move1 = try_move (chessboard, 2, 1)
val move2 = try_move (chessboard, 1, ~2)
val move3 = try_move (chessboard, 2, ~1)
val move4 = try_move (chessboard, ~1, 2)
val move5 = try_move (chessboard, ~2, 1)
val move6 = try_move (chessboard, ~1, ~2)
val move7 = try_move (chessboard, ~2, ~1)
in
@(move0, move1, move2, move3, move4, move5, move6, move7)
end
fn
count_following_moves
{n_ranks, n_files : pos}
{i, j : int}
{n_position : int}
(chessboard : !chessboard_vt (int, n_ranks, n_files),
move : move_t (i, j),
n_position : int n_position) :
uint =
if move_t_is_nil move then
0U
else
let
fn
succ_if_move_is_not_nil
{i, j : int}
(w : uint,
move : move_t (i, j)) :<>
uint =
if move_t_is_nil move then
w
else
succ w
val @(i, j) = move
val _ = chessboard_vt_set<int> (chessboard, i, j,
succ n_position)
val following_moves = possible_moves (chessboard, i, j)
val w = 0U
val w = succ_if_move_is_not_nil (w, following_moves.0)
val w = succ_if_move_is_not_nil (w, following_moves.1)
val w = succ_if_move_is_not_nil (w, following_moves.2)
val w = succ_if_move_is_not_nil (w, following_moves.3)
val w = succ_if_move_is_not_nil (w, following_moves.4)
val w = succ_if_move_is_not_nil (w, following_moves.5)
val w = succ_if_move_is_not_nil (w, following_moves.6)
val w = succ_if_move_is_not_nil (w, following_moves.7)
val _ = chessboard_vt_set<int> (chessboard, i, j, EMPTY_SQUARE)
in
w
end
fn
pick_w (w0 : uint,
w1 : uint,
w2 : uint,
w3 : uint,
w4 : uint,
w5 : uint,
w6 : uint,
w7 : uint) :<>
uint =
let
fn
next_pick (u : uint,
v : uint) :<>
uint =
if v = 0U then
u
else if u = 0U then
v
else
min (u, v)
val w = 0U
val w = next_pick (w, w0)
val w = next_pick (w, w1)
val w = next_pick (w, w2)
val w = next_pick (w, w3)
val w = next_pick (w, w4)
val w = next_pick (w, w5)
val w = next_pick (w, w6)
val w = next_pick (w, w7)
in
w
end
fn
next_moves {n_ranks, n_files : pos}
{i, j : int}
{n_position : int}
(chessboard : !chessboard_vt (int, n_ranks, n_files),
i : int i,
j : int j,
n_position : int n_position) :
knights_moves_t =
(* Prune and sort the moves according to Warnsdorff’s heuristic,
keeping only moves that have the minimum number of legal
following moves. *)
let
val moves = possible_moves (chessboard, i, j)
val w0 = count_following_moves (chessboard, moves.0, n_position)
val w1 = count_following_moves (chessboard, moves.1, n_position)
val w2 = count_following_moves (chessboard, moves.2, n_position)
val w3 = count_following_moves (chessboard, moves.3, n_position)
val w4 = count_following_moves (chessboard, moves.4, n_position)
val w5 = count_following_moves (chessboard, moves.5, n_position)
val w6 = count_following_moves (chessboard, moves.6, n_position)
val w7 = count_following_moves (chessboard, moves.7, n_position)
val w = pick_w (w0, w1, w2, w3, w4, w5, w6, w7)
in
if w = 0U then
@(nil_move, nil_move, nil_move, nil_move,
nil_move, nil_move, nil_move, nil_move)
else
@(if w0 = w then moves.0 else nil_move,
if w1 = w then moves.1 else nil_move,
if w2 = w then moves.2 else nil_move,
if w3 = w then moves.3 else nil_move,
if w4 = w then moves.4 else nil_move,
if w5 = w then moves.5 else nil_move,
if w6 = w then moves.6 else nil_move,
if w7 = w then moves.7 else nil_move)
end
fn
make_and_fprint_tours
{n_ranks, n_files : int}
{i, j : int}
{max_tours : int}
(f : FILEref,
n_ranks : int n_ranks,
n_files : int n_files,
i : int i,
j : int j,
max_tours : int max_tours,
closed_only : bool) :
void =
{
val n_ranks = max (1, n_ranks)
val n_files = max (1, n_files)
val i = max (1, min (n_ranks, i))
val j = max (1, min (n_files, j))
val max_tours = max (1, max_tours)
val n_ranks = i2u n_ranks
val n_files = i2u n_files
val i_start = i
val j_start = j
var tours_printed : int = 0
val chessboard =
chessboard_vt_make<int> (n_ranks, n_files, g1ofg0 EMPTY_SQUARE)
fun
explore {n_ranks, n_files : pos}
{i, j : int}
{n_position : int}
(chessboard : !chessboard_vt (int, n_ranks, n_files),
i : int i,
j : int j,
n_position : int n_position,
tours_printed : &int) :
void =
if tours_printed < max_tours then
let
fn
print_board {i1, j1 : int}
(chessboard : !chessboard_vt (int, n_ranks,
n_files),
tours_printed : &int) :
void =
begin
tours_printed := succ tours_printed;
fprintln! (f, "Tour number ", tours_printed);
knights_tour_moves_fprint (f, chessboard);
fprintln! (f);
knights_tour_board_fprint (f, chessboard);
fprintln! (f);
fprintln! (f)
end
fn
satisfies_closedness
{i1, j1 : int}
(move : move_t (i1, j1)) :
bool =
if closed_only then
let
val @(i1, j1) = move
val i_diff = abs (i1 - i_start)
val j_diff = abs (j1 - j_start)
in
(i_diff = 1 && j_diff = 2)
|| (i_diff = 2 && j_diff = 1)
end
else
true
fn
try_last_move
{i1, j1 : int}
(chessboard : !chessboard_vt (int, n_ranks,
n_files),
move : move_t (i1, j1),
tours_printed : &int) :
void =
if ~move_t_is_nil move && satisfies_closedness move then
let
val @(i1, j1) = move
in
chessboard_vt_set<int> (chessboard, i1, j1,
n_position + 1);
print_board (chessboard, tours_printed);
chessboard_vt_set<int> (chessboard, i1, j1,
EMPTY_SQUARE)
end
fun
explore_inner (chessboard : !chessboard_vt (int, n_ranks,
n_files),
tours_printed : &int) :
void =
if u2i (chessboard.n_squares) - n_position = 1 then
(* Is the last move possible? If so, make it and print
the board. (Only zero or one of the moves can be
non-nil.) *)
let
val moves = possible_moves (chessboard, i, j)
in
try_last_move (chessboard, moves.0, tours_printed);
try_last_move (chessboard, moves.1, tours_printed);
try_last_move (chessboard, moves.2, tours_printed);
try_last_move (chessboard, moves.3, tours_printed);
try_last_move (chessboard, moves.4, tours_printed);
try_last_move (chessboard, moves.5, tours_printed);
try_last_move (chessboard, moves.6, tours_printed);
try_last_move (chessboard, moves.7, tours_printed)
end
else
let
val moves = next_moves (chessboard, i, j, n_position)
macdef explore_move (move) =
begin
if ~move_t_is_nil ,(move) then
explore (chessboard, (,(move)).0, (,(move)).1,
succ n_position, tours_printed)
end
in
explore_move (moves.0);
explore_move (moves.1);
explore_move (moves.2);
explore_move (moves.3);
explore_move (moves.4);
explore_move (moves.5);
explore_move (moves.6);
explore_move (moves.7)
end
in
chessboard_vt_set<int> (chessboard, i, j, n_position);
explore_inner (chessboard, tours_printed);
chessboard_vt_set<int> (chessboard, i, j, EMPTY_SQUARE)
end
val _ = explore (chessboard, i, j, 1, tours_printed)
val _ = $UNSAFE.castvwtp0{void} chessboard
}
fn
algebraic_notation_to_move (s : string) :
move_t =
let
val s = g1ofg0 s
val n = string_length s
in
if n = 2 then
let
val i = g1ofg0 (char2i (s[1]) - char2i ('0'))
val j = g1ofg0 (char2i (s[0]) - char2i ('a') + 1)
in
@(i, j)
end
else
@(1, 1)
end
implement
main0 (argc, argv) =
{
val @(i, j) =
begin
if 2 <= argc then
algebraic_notation_to_move (argv[1])
else
@(1, 1)
end : move_t
val max_tours =
begin
if 3 <= argc then
$extfcall (int, "atoi", argv[2])
else
1
end : int
val max_tours = g1ofg0 max_tours
val closed_only =
begin
if 4 <= argc then
argv[3] = "closed"
else
false
end : bool
val _ = make_and_fprint_tours (stdout_ref, 8, 8, i, j, max_tours,
closed_only)
}</syntaxhighlight>
{{out}}
$ ./knights_tour c5 2 closed
<pre>Tour number 1
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> e8 -> d6 -> b5 -> d4 -> f5 -> g7 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 58 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 63 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 60 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 61 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
Tour number 2
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> b5 -> d6 -> e8 -> g7 -> f5 -> d4 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 60 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 61 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 58 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 63 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
</pre>
=={{header|AutoHotkey}}==
{{libheader|GDIP}}
<
#NoEnv
SetBatchLines, -1
Line 1,052 ⟶ 1,858:
If (A_Gui = 1)
PostMessage, 0xA1, 2
}</
{{out}}
For start at b3
Line 1,059 ⟶ 1,865:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f KNIGHTS_TOUR.AWK [-v sr=x] [-v sc=x]
#
Line 1,128 ⟶ 1,934:
}
}
</syntaxhighlight>
<p>output:</p>
<pre>
Line 1,142 ⟶ 1,948:
</pre>
=={{header|
==={{header|ANSI BASIC}}===
{{trans|BBC BASIC}}
[[File:Knights_Tour.gif|right]]
{{works with|Decimal BASIC}}
ANSI BASIC does not allow function parameters to be passed by reference, so X and Y were made global variables.
<syntaxhighlight lang="basic">100 DECLARE EXTERNAL FUNCTION choosemove
110 !
120 RANDOMIZE
130 PUBLIC NUMERIC X, Y, TRUE, FALSE
140 LET TRUE = -1
150 LET FALSE = 0
160 !
170 SET WINDOW 1,512,1,512
180 SET AREA COLOR "black"
190 FOR x=0 TO 512-128 STEP 128
200 FOR y=0 TO 512-128 STEP 128
210 PLOT AREA:x+64,y;x+128,y;x+128,y+64;x+64,y+64
220 PLOT AREA:x,y+64;x+64,y+64;x+64,y+128;x,y+128
230 NEXT y
240 NEXT x
250 !
260 SET LINE COLOR "red"
270 SET LINE WIDTH 6
280 !
290 PUBLIC NUMERIC Board(0 TO 7,0 TO 7)
300 LET X = 0
310 LET Y = 0
320 LET Total = 0
330 DO
340 LET Board(X,Y) = TRUE
350 PLOT LINES: X*64+32,Y*64+32;
360 LET Total = Total + 1
370 LOOP UNTIL choosemove(X, Y) = FALSE
380 IF Total <> 64 THEN STOP
390 END
400 !
410 EXTERNAL FUNCTION choosemove(X1, Y1)
420 DECLARE EXTERNAL SUB trymove
430 LET M = 9
440 CALL trymove(X1+1, Y1+2, M, newx, newy)
450 CALL trymove(X1+1, Y1-2, M, newx, newy)
460 CALL trymove(X1-1, Y1+2, M, newx, newy)
470 CALL trymove(X1-1, Y1-2, M, newx, newy)
480 CALL trymove(X1+2, Y1+1, M, newx, newy)
490 CALL trymove(X1+2, Y1-1, M, newx, newy)
500 CALL trymove(X1-2, Y1+1, M, newx, newy)
510 CALL trymove(X1-2, Y1-1, M, newx, newy)
520 IF M=9 THEN
530 LET choosemove = FALSE
540 EXIT FUNCTION
550 END IF
560 LET X = newx
570 LET Y = newy
580 LET choosemove = TRUE
590 END FUNCTION
600 !
610 EXTERNAL SUB trymove(X, Y, M, newx, newy)
620 !
630 DECLARE EXTERNAL FUNCTION validmove
640 IF validmove(X,Y) = 0 THEN EXIT SUB
650 IF validmove(X+1,Y+2) <> 0 THEN LET N = N + 1
660 IF validmove(X+1,Y-2) <> 0 THEN LET N = N + 1
670 IF validmove(X-1,Y+2) <> 0 THEN LET N = N + 1
680 IF validmove(X-1,Y-2) <> 0 THEN LET N = N + 1
690 IF validmove(X+2,Y+1) <> 0 THEN LET N = N + 1
700 IF validmove(X+2,Y-1) <> 0 THEN LET N = N + 1
710 IF validmove(X-2,Y+1) <> 0 THEN LET N = N + 1
720 IF validmove(X-2,Y-1) <> 0 THEN LET N = N + 1
730 IF N>M THEN EXIT SUB
740 IF N=M AND RND<.5 THEN EXIT SUB
750 LET M = N
760 LET newx = X
770 LET newy = Y
780 END SUB
790 !
800 EXTERNAL FUNCTION validmove(X,Y)
810 LET validmove = FALSE
820 IF X<0 OR X>7 OR Y<0 OR Y>7 THEN EXIT FUNCTION
830 IF Board(X,Y)=FALSE THEN LET validmove = TRUE
840 END FUNCTION</syntaxhighlight>
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
[[Image:knights_tour_bbc.gif|right]]
<
VDU 23,23,4;0;0;0;
OFF
Line 1,204 ⟶ 2,092:
DEF FNvalidmove(X%,Y%)
IF X%<0 OR X%>7 OR Y%<0 OR Y%>7 THEN = FALSE
= NOT(Board%(X%,Y%))</
=={{header|Bracmat}}==
<
= validmoves WarnsdorffSort algebraicNotation init solve
, x y fieldsToVisit
Line 1,311 ⟶ 2,199:
$ (algebraicNotation$(solve$((!x.!y).!fieldsToVisit)))
)
& out$(knightsTour$a1);</
<pre>a1 b3 a5 b7 d8 f7 h8 g6 f8 h7 g5 h3 g1 e2 c1 a2 b4 a6 b8 c6 a7 c8 e7 g8 h6 g4 h2 f1 d2 b1 a3 c2 e1 f3 h4 g2 e3 d1 b2 a4 c3 b5 d4 f5 d6 c4 e5 d3 f2 h1 g3 e4 c5 d7 b6 a8 c7 d5 f4 e6 g7 e8 f6 h5</pre>
Line 1,319 ⟶ 2,207:
The following draws on console the progress of the horsie. Specify board size on commandline, or use default 8.
<
#include <stdlib.h>
#include <string.h>
Line 1,421 ⟶ 2,309:
return 0;
}</
=={{header|C sharp}}==
<
using System.Collections.Generic;
Line 1,507 ⟶ 2,395:
}
}
}</
=={{header|C++}}==
Line 1,514 ⟶ 2,402:
Uses Warnsdorff's rule and (iterative) backtracking if that fails.
<
#include <iomanip>
#include <array>
Line 1,657 ⟶ 2,545:
cout << b3 << endl;
return 0;
}</
Output:
Line 1,712 ⟶ 2,600:
This interactive program will ask for a starting case in algebraic notation and, also, whether a closed tour is desired. Each next move is selected according to Warnsdorff's rule; ties are broken at random.
The closed tour algorithm is quite crude: just find tours over and
This code is quite verbose: I tried to make it easy for myself and for
For some reason, the interactive part does not work with
<
;;; Solving the knight's tour. ;;;
;;; Warnsdorff's rule with random tie break. ;;;
Line 1,904 ⟶ 2,792:
(prompt)
(main)</
{{out}}
<pre>Starting case (leave blank for random)? a8
Line 1,923 ⟶ 2,811:
=={{header|Clojure}}==
Using warnsdorff's rule
<syntaxhighlight lang="clojure">
(defn isin? [x li]
(not= [] (filter #(= x %) li)))
Line 1,949 ⟶ 2,837:
(let [np (next-move mov pmoves n)]
(recur (conj mov np) (inc x)))))))
</syntaxhighlight>
{{out}}
<pre>
Line 1,966 ⟶ 2,854:
=={{header|CoffeeScript}}==
This algorithm finds 100,000 distinct solutions to the 8x8 problem in about 30 seconds. It precomputes knight moves up front, so it turns into a pure graph traversal problem. The program uses iteration and backtracking to find solutions.
<
graph_tours = (graph, max_num_solutions) ->
# graph is an array of arrays
Line 2,081 ⟶ 2,969:
illustrate_knights_tour tours[0], BOARD_WIDTH
illustrate_knights_tour tours.pop(), BOARD_WIDTH
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> time coffee knight.coffee
100000 tours found (showing first and last)
Line 2,111 ⟶ 2,999:
user 0m25.656s
sys 0m0.253s
</syntaxhighlight>
=={{header|D}}==
===Fast Version===
{{trans|C++}}
<
std.conv, std.typecons, std.typetuple;
Line 2,192 ⟶ 3,080:
writeln();
}
}</
{{out}}
<pre>23 16 11 6 21
Line 2,243 ⟶ 3,131:
===Shorter Version===
{{trans|Haskell}}
<
alias Square = Tuple!(int,"x", int,"y");
Line 2,269 ⟶ 3,157:
const board = iota(1, 9).cartesianProduct(iota(1, 9)).map!Square.array;
writefln("%(%-(%s -> %)\n%)", board.knightTour([sq]).map!toAlg.chunks(8));
}</
{{out}}
<pre>e5 -> d7 -> b8 -> a6 -> b4 -> a2 -> c1 -> b3
Line 2,279 ⟶ 3,167:
d6 -> e4 -> c5 -> d3 -> e1 -> g2 -> h4 -> f5
d4 -> e2 -> f4 -> e6 -> g5 -> f3 -> g1 -> h3</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|Forms,Types,SysUtils,Graphics,ExtCtrls}}
[[File:DelphiKnightsTour.png|thumb|none]]
Brute force method. Takes a long time for most solutions, so some optimization should be used. However, it has nice graphics.
<syntaxhighlight lang="Delphi">
{ These routines would normally be in a library,
but are presented here for clarity }
function PointAdd(V1,V2: TPoint): TPoint;
{Add V1 and V2}
begin
Result.X:= V1.X+V2.X;
Result.Y:= V1.Y+V2.Y;
end;
const KnightMoves: array [0..7] of TPoint = (
(X: 2; Y:1),(X: 2; Y:-1),
(X:-2; Y:1),(X:-2; Y:-1),
(X:1; Y: 2),(X:-1; Y: 2),
(X:1; Y:-2),(X:-1; Y:-2));
var Board: array [0..7,0..7] of boolean;
var Path: array of TPoint;
var CellSize,BoardSize: integer;
var CurPos: TPoint;
var BestPath: integer;
{-------------------------------------------------------------}
procedure DrawBestPath(Image: TImage);
begin
Image.Canvas.TextOut(BoardSize+5,5, IntToStr(BestPath));
end;
procedure PushPath(P: TPoint);
begin
SetLength(Path,Length(Path)+1);
Path[High(Path)]:=P;
if Length(Path)>BestPath then BestPath:=Length(Path);
end;
function PopPath: TPoint;
begin
if Length(Path)<1 then exit;
Result:=Path[High(Path)];
SetLength(Path,Length(Path)-1);
end;
procedure ClearPath;
begin
SetLength(Path,0);
end;
{-------- Routines to draw chess board and path --------------}
function GetCellCenter(P: TPoint): TPoint;
{Get pixel position of the center of cell}
begin
Result.X:=CellSize div 2 + CellSize * P.X;
Result.Y:=CellSize div 2 + CellSize * P.Y;
end;
procedure DrawPoint(Canvas: TCanvas; P: TPoint);
{Draw a point on the board}
begin
Canvas.Pen.Color:=clYellow;
Canvas.MoveTo(P.X-1,P.Y-1);
Canvas.LineTo(P.X+1,P.Y+1);
Canvas.MoveTo(P.X+1,P.Y-1);
Canvas.LineTo(P.X-1,P.Y+1);
end;
procedure DrawPathLine(Canvas: TCanvas; P1,P2: TPoint);
{Draw the path line}
var PS1,PS2: TPoint;
begin
PS1:=GetCellCenter(P1);
PS2:=GetCellCenter(P2);
Canvas.Pen.Width:=5;
Canvas.Pen.Color:=clRed;
Canvas.MoveTo(PS1.X,PS1.Y);
Canvas.LineTo(PS2.X,PS2.Y);
DrawPoint(Canvas,PS1);
DrawPoint(Canvas,PS2);
end;
procedure DrawPath(Canvas: TCanvas);
{Draw all points on the path}
var I: integer;
begin
for I:=0 to High(Path)-1 do
begin
DrawPathLine(Canvas, Path[I],Path[I+1]);
end;
end;
procedure DrawBoard(Canvas: TCanvas);
{Draw the chess board}
var R,R2: TRect;
var X,Y: integer;
var Color: TColor;
begin
Canvas.Pen.Color:=clBlack;
R:=Rect(0,0,BoardSize,BoardSize);
Canvas.Rectangle(R);
R:=Rect(0,0,CellSize,CellSize);
for Y:=0 to High(Board[0]) do
for X:=0 to High(Board) do
begin
R2:=R;
if ((X+Y) mod 2)=0 then Color:=clWhite
else Color:=clBlack;
Canvas.Brush.Color:=Color;
OffsetRect(R2,X * CellSize, Y * CellSize);
Canvas.Rectangle(R2);
end;
DrawPath(Canvas);
end;
function AllVisited: boolean;
{Test if all squares have been visit by path}
var X,Y: integer;
begin
Result:=False;
for Y:=0 to High(Board[0]) do
for X:=0 to High(Board) do
if not Board[X,Y] then exit;
Result:=True;
end;
procedure ClearBoard;
{Clear all board positions}
var X,Y: integer;
begin
for Y:=0 to High(Board[0]) do
for X:=0 to High(Board) do
Board[X,Y]:=False;
end;
function IsValidMove(Pos,Move: TPoint): boolean;
{Test if potential move is valid}
var NP: TPoint;
begin
Result:=False;
NP:=PointAdd(Pos,Move);
if (NP.X<0) or (NP.X>High(Board)) or
(NP.Y<0) or (NP.Y>High(Board[0])) then exit;
if Board[NP.X,NP.Y] then exit;
Result:=True;
end;
procedure ConfigureScreen(Image: TImage);
{Configure screen size}
begin
if Image.Width<Image.Height then BoardSize:=Image.Width
else BoardSize:=Image.Height;
CellSize:=BoardSize div 8;
end;
procedure SetPosition(Image: TImage; P: TPoint; Value: boolean);
{Set a new position by adding it to path}
{Marking position as used and redrawing board}
begin
if Value then PushPath(P)
else P:=PopPath;
Board[P.X,P.Y]:=Value;
DrawBoard(Image.Canvas);
DrawBestPath(Image);
Image.Repaint;
end;
procedure TryAllMoves(Image: TImage; Pos: TPoint);
{Recursively try all moves}
var I: integer;
var NewPos: TPoint;
begin
SetPosition(Image,Pos,True);
if AllVisited then exit;
for I:=0 to High(KnightMoves) do
begin
if AbortFlag then Exit;
if IsValidMove(Pos,KnightMoves[I]) then
begin
NewPos:=PointAdd(Pos,KnightMoves[I]);
TryAllMoves(Image,NewPos);
end;
end;
SetPosition(Image,Pos,False);
Application.ProcessMessages;
end;
procedure DoKnightsTour(Image: TImage);
{Solve Knights tour by testing all paths}
begin
BestPath:=0;
ConfigureScreen(Image);
ClearPath;
ClearBoard;
DrawBoard(Image.Canvas);
TryAllMoves(Image, Point(0,0));
end;
</syntaxhighlight>
{{out}}
<pre>
</pre>
=={{header|EchoLisp}}==
The algorithm uses iterative backtracking and Warnsdorff's heuristic. It can output closed or non-closed tours.
<
(require 'plot)
(define *knight-moves*
Line 2,352 ⟶ 3,476:
(play starter 0 starter (dim n) wants-open)
(catch (hit mess) (show-steps n wants-open))))
</syntaxhighlight>
{{out}}
<
(k-tour 8 0 #f)
♞-closed-tour: 66 tries.
Line 2,390 ⟶ 3,514:
79 76 83 18 91 74 137 16 169 72 153 14 167 70 157 12 63 68 55 10
82 19 80 75 84 17 92 73 152 15 168 71 154 13 62 69 54 11 52 67
</syntaxhighlight>
;Plotting:
64 shades of gray. We plot the move sequence in shades of gray, from black to white. The starting square is red. The ending square is green. One can observe that the squares near the border are played first (dark squares).
<
(define (step-color x y n last-one)
(letrec ((sq (square (floor x) (floor y) n))
Line 2,404 ⟶ 3,528:
(define ( k-plot n)
(plot-rgb (lambda (x y) (step-color x y n (dim n))) (- n epsilon) (- n epsilon)))
</syntaxhighlight>
Line 2,413 ⟶ 3,537:
=={{header|Elixir}}==
{{trans|Ruby}}
<
import Integer, only: [is_odd: 1]
Line 2,476 ⟶ 3,600:
Board.knight_tour(4,9,1,1)
Board.knight_tour(5,5,1,2)
Board.knight_tour(12,12,2,2)</
{{out}}
Line 2,522 ⟶ 3,646:
=={{header|Elm}}==
<
import Browser exposing (element)
import Html as H
import Html.Attributes as HA
import
import
import String exposing (join)
import Svg exposing (g, line, rect, svg)
import Svg.Attributes exposing (fill, height, style, version, viewBox, width, x, x1, x2, y, y1, y2)
import Svg.Events exposing (onClick)
import Time exposing (every)
import Tuple
type alias Cell =
( Int, Int )
type alias BoardSize =
( Int, Int )
type alias Model =
{ path : List Cell
, board : List Cell
, pause_ms : Float
, size : BoardSize
}
type Msg
= Tick Time.Posix
| SetStart Cell
|
| SetPause Float
boardsize_width: BoardSize -> Int
boardsize_width bs =
Tuple.second bs
boardsize_height: BoardSize -> Int
boardsize_height bs =
Tuple.first bs
boardsize_dec: Int -> Int
boardsize_dec n =
let
minimum_size = 3
in
if n <= minimum_size then
minimum_size
else
n - 1
boardsize_inc: Int -> Int
boardsize_inc n =
let
maximum_size = 40
in
if n >= maximum_size then
maximum_size
else
n + 1
pause_inc: Float -> Float
pause_inc n =
n + 10
-- decreasing pause time (ms) increases speed
pause_dec: Float -> Float
pause_dec n =
let
minimum_pause = 0
in
if n <= minimum_pause then
minimum_pause
else
n - 10
board_init : BoardSize -> List Cell
board_init board_size =
List.range 0 (boardsize_height board_size - 1)
|> andThen
(\r ->
List.range 0 (boardsize_width board_size - 1)
|> andThen
(\c ->
[ ( r, c ) ]
)
)
nextMoves : Model -> Cell -> List Cell
nextMoves model ( stRow, stCol ) =
let
c =
[ 1, 2, -1, -2 ]
km =
c
|> andThen
(\cRow ->
c
|> andThen
(\cCol ->
if abs cRow == abs cCol then
[]
else
[ ( cRow, cCol ) ]
)
)
jumps =
List.map (\( kmRow, kmCol ) -> ( kmRow + stRow, kmCol + stCol )) km
in
List.filter (\j -> List.member j model.board && not (List.member j model.path)) jumps
bestMove : Model -> Maybe Cell
bestMove model =
case List.head model.path of
Just mph ->
minimumBy (List.length << nextMoves model) (nextMoves model mph)
_ ->
Nothing
-- Initialize the application - https://guide.elm-lang.org/effects/
init : () -> ( Model, Cmd Msg )
init _ =
let
-- Initial board height and
initial_size
-- Initial chess board
initial_board =
board_init (initial_size,
initial_pause =
10
in
( Model initial_path initial_board initial_pause (initial_size, initial_size), Cmd.none )
-- View the model - https://guide.elm-lang.org/effects/
view : Model -> H.Html Msg
view model =
let
showChecker row col =
rect
[
showMove ( row0, col0 ) ( row1, col1 )
[ x1 <| String.fromFloat (toFloat col0 + 0.5)
, y1 <| String.fromFloat (toFloat row0 + 0.5)
, x2 <| String.fromFloat (toFloat col1 + 0.5)
, y2 <| String.fromFloat (toFloat row1 + 0.5)
, style "stroke:yellow;stroke-width:0.05"
]
[]
render mdl =
let
checkers
|>
(\( r, c )
case List.tail mdl.path of
Nothing ->
[]
Just tl ->
List.map2 showMove mdl.path tl
in
checkers ++ moves
unvisited =
length model.board - length model.path
center =
[ HA.style "text-align" "center" ]
table =
[ HA.style "text-align" "center", HA.style "display" "table", HA.style "width" "auto", HA.style "margin" "auto" ]
table_row =
[ HA.style "display" "table-row", HA.style "width" "auto" ]
table_cell =
[ HA.style "display" "table-cell", HA.style "width" "auto", HA.style "padding" "1px 3px" ]
rows =
boardsize_height model.size
cols =
boardsize_width model.size
in
-- controls
[ H.div
[
[ H.text ""]
,
[ H.text "Pause (ms)"]
]
, H.div
table_row
[ H.div -- Increase
table_cell
[ H.button [onClick <| SetSize ( boardsize_inc rows, cols )] [ H.text "▲"] ]
, H.div
table_cell
[ H.button [onClick <| SetSize ( rows, boardsize_inc cols )] [ H.text "▲"] ]
, H.div
table_cell
[ H.text ""]
, H.div
table_cell
[ H.button [onClick <| SetPause ( pause_inc model.pause_ms )] [ H.text "▲"] ]
]
, H.div
table_row
[ H.div -- Value
table_cell
[ H.text <| String.fromInt rows ]
, H.div
table_cell
[ H.text <| String.fromInt cols]
, H.div
table_cell
[ H.text ""]
, H.div
table_cell
[ H.text <| String.fromFloat model.pause_ms]
]
, H.div
table_row
[ H.div -- Decrease
table_cell
[ H.button [onClick <| SetSize ( boardsize_dec rows, cols )] [ H.text "▼"] ]
, H.div
table_cell
[ H.button [onClick <| SetSize ( rows, boardsize_dec cols )] [ H.text "▼"] ]
, H.div
table_cell
[ H.text ""]
, H.div
table_cell
[ H.button [onClick <| SetPause ( pause_dec model.pause_ms )] [ H.text "▼"] ]
]
]
, H.h2 center [ H.text "(pick a square)" ]
, H.div -- chess board
center
[ svg
[ version "1.1"
, width (String.fromInt (25 * cols))
, height (String.fromInt (25 * rows))
, viewBox
(join " "
[ String.fromInt 0
, String.fromInt 0
, String.fromInt cols
, String.fromInt rows
]
)
]
[ g [] <| render model ]
]
, H.h3 center [ H.text <| "Unvisited count : " ++ String.fromInt unvisited ]
]
-- Update the model - https://guide.elm-lang.org/effects/
update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
let
mo =
case msg of
SetPause pause ->
{ model | pause_ms = pause }
SetSize board_size ->
{ model | board = board_init board_size, path = [], size = board_size }
{ model | path = [ start ] }
Tick _ ->
case model.path of
[] ->
model
_ ->
case bestMove model
Nothing ->
model
Just best ->
{ model | path = best :: model.path }
in
( mo, Cmd.none )
-- Subscribe to https://guide.elm-lang.org/effects/
subscriptions : Model -> Sub Msg
subscriptions
Time.every
-- Application entry point
main: Program () Model Msg
main =
element -- https://package.elm-lang.org/packages/elm/browser/latest/Browser#element
{ init = init
, view = view
, update = update
, subscriptions = subscriptions
}
</syntaxhighlight>
Link to live demo: https://dmcbane.github.io/knights-tour/
=={{header|Erlang}}==
Again I use backtracking. It seemed easier this time.
<syntaxhighlight lang="erlang">
-module( knights_tour ).
-export( [display/1, solve/1, task/0] ).
display( Moves ) ->
%% The knigh walks the moves {Position, Step_nr} order.
%% Top left corner is {$a, 8}, Bottom right is {$h, 1}.
io:fwrite( "Moves:" ),
lists:foldl( fun display_moves/2, erlang:length(Moves), lists:keysort(2, Moves) ),
io:nl(),
[display_row(Y, Moves) || Y <- lists:seq(8, 1, -1)].
solve( First_square ) ->
try
bt_loop( 1, next_moves(First_square), [{First_square, 1}] )
catch
_:{ok, Moves} -> Moves
end.
task() ->
io:fwrite( "Starting {a, 1}~n" ),
Moves = solve( {$a, 1} ),
display( Moves ).
bt( N, Move, Moves ) -> bt_reject( is_not_allowed_knight_move(Move, Moves), N, Move, [{Move, N} | Moves] ).
bt_accept( true, _N, _Move, Moves ) -> erlang:throw( {ok, Moves} );
bt_accept( false, N, Move, Moves ) -> bt_loop( N, next_moves(Move), Moves ).
bt_loop( N, New_moves, Moves ) -> [bt( N+1, X, Moves ) || X <- New_moves].
bt_reject( true, _N, _Move, _Moves ) -> backtrack;
bt_reject( false, N, Move, Moves ) -> bt_accept( is_all_knights(Moves), N, Move, Moves ).
display_moves( {{X, Y}, 1}, Max ) ->
io:fwrite(" ~p. N~c~p", [1, X, Y]),
Max;
display_moves( {{X, Y}, Max}, Max ) ->
io:fwrite(" N~c~p~n", [X, Y]),
Max;
display_moves( {{X, Y}, Step_nr}, Max ) when Step_nr rem 8 =:= 0 ->
io:fwrite(" N~c~p~n~p. N~c~p", [X, Y, Step_nr, X, Y]),
Max;
display_moves( {{X, Y}, Step_nr}, Max ) ->
io:fwrite(" N~c~p ~p. N~c~p", [X, Y, Step_nr, X, Y]),
Max.
display_row( Row, Moves ) ->
[io:fwrite(" ~2b", [proplists:get_value({X, Row}, Moves)]) || X <- [$a, $b, $c, $d, $e, $f, $g, $h]],
io:nl().
is_all_knights( Moves ) when erlang:length(Moves) =:= 64 -> true;
is_all_knights( _Moves ) -> false.
is_asymetric( Start_column, Start_row, Stop_column, Stop_row ) ->
erlang:abs( Start_column - Stop_column ) =/= erlang:abs( Start_row - Stop_row ).
is_not_allowed_knight_move( Move, Moves ) ->
no_such_move =/= proplists:get_value( Move, Moves, no_such_move ).
next_moves( {Column, Row} ) ->
[{X, Y} || X <- next_moves_column(Column), Y <- next_moves_row(Row), is_asymetric(Column, Row, X, Y)].
next_moves_column( $a ) -> [$b, $c];
next_moves_column( $b ) -> [$a, $c, $d];
next_moves_column( $g ) -> [$e, $f, $h];
next_moves_column( $h ) -> [$g, $f];
next_moves_column( C ) -> [C - 2, C - 1, C + 1, C + 2].
next_moves_row( 1 ) -> [2, 3];
next_moves_row( 2 ) -> [1, 3, 4];
next_moves_row( 7 ) -> [5, 6, 8];
next_moves_row( 8 ) -> [6, 7];
next_moves_row( N ) -> [N - 2, N - 1, N + 1, N + 2].
</syntaxhighlight>
{{out}}
<pre>
17> knights_tour:task().
Starting {a, 1}
Moves: 1. Na1 Nb3 2. Nb3 Na5 3. Na5 Nb7 4. Nb7 Nc5 5. Nc5 Na4 6. Na4 Nb2 7. Nb2 Nc4
8. Nc4 Na3 9. Na3 Nb1 10. Nb1 Nc3 11. Nc3 Na2 12. Na2 Nb4 13. Nb4 Na6 14. Na6 Nb8 15. Nb8 Nc6
16. Nc6 Na7 17. Na7 Nb5 18. Nb5 Nc7 19. Nc7 Na8 20. Na8 Nb6 21. Nb6 Nc8 22. Nc8 Nd6 23. Nd6 Ne4
24. Ne4 Nd2 25. Nd2 Nf1 26. Nf1 Ne3 27. Ne3 Nc2 28. Nc2 Nd4 29. Nd4 Ne2 30. Ne2 Nc1 31. Nc1 Nd3
32. Nd3 Ne1 33. Ne1 Ng2 34. Ng2 Nf4 35. Nf4 Nd5 36. Nd5 Ne7 37. Ne7 Ng8 38. Ng8 Nh6 39. Nh6 Nf5
40. Nf5 Nh4 41. Nh4 Ng6 42. Ng6 Nh8 43. Nh8 Nf7 44. Nf7 Nd8 45. Nd8 Ne6 46. Ne6 Nf8 47. Nf8 Nd7
48. Nd7 Ne5 49. Ne5 Ng4 50. Ng4 Nh2 51. Nh2 Nf3 52. Nf3 Ng1 53. Ng1 Nh3 54. Nh3 Ng5 55. Ng5 Nh7
56. Nh7 Nf6 57. Nf6 Ne8 58. Ne8 Ng7 59. Ng7 Nh5 60. Nh5 Ng3 61. Ng3 Nh1 62. Nh1 Nf2 63. Nf2 Nd1
20 15 22 45 58 47 38 43
17 4 19 48 37 44 59 56
14 21 16 23 46 57 42 39
3 18 5 36 49 40 55 60
6 13 8 29 24 35 50 41
9 2 11 32 27 52 61 54
12 7 28 25 30 63 34 51
1 10 31 64 33 26 53 62
</pre>
=={{header|ERRE}}==
Taken from ERRE distribution disk. Comments are in Italian.
<syntaxhighlight lang="erre">
! **********************************************************************
! * *
Line 2,890 ⟶ 4,312:
UNTIL A$<>""
END PROGRAM
</syntaxhighlight>
{{out}}
<pre> *** LA GALOPPATA DEL CAVALIERE ***
Line 2,911 ⟶ 4,333:
=={{header|FreeBASIC}}==
<
Dim Shared As Integer tamano, xc, yc, nm
Dim As Integer f, qm, nmov, n = 0
Line 2,969 ⟶ 4,391:
Sleep
End
</syntaxhighlight>
{{out}}
[https://www.dropbox.com/s/s3bpwechpoueum4/Knights%20Tour%20FreeBasic.png?dl=0 Knights Tour FreeBasic image]
Line 2,994 ⟶ 4,416:
=={{header|Fōrmulæ}}==
=={{header|Fortran}}==
===FORTRAN 77===
{{trans|ATS}}
{{works with|gfortran|11.2.1}}
{{works with|f2c}}
<syntaxhighlight lang="fortran">C-----------------------------------------------------------------------
C
C Find Knight’s Tours.
C
C Using Warnsdorff’s heuristic, find multiple solutions.
C Optionally accept only closed tours.
C
C This program is migrated from my implementation for ATS/Postiats.
C Arrays with dimension 1:64 take the place of stack frames.
C
C Compile with, for instance:
C
C gfortran -O2 -g -std=legacy -o knights_tour knights_tour.f
C
C or
C
C f2c knights_tour.f
C cc -O -o knights_tour knights_tour.c -lf2c
C
C Usage examples:
C
C One tour starting at a1, either open or closed:
C
C echo "a1 1 F" | ./knights_tour
C
C No more than 2000 closed tours starting at c5:
C
C echo "c5 2000 T" | ./knights_tour
C
C-----------------------------------------------------------------------
program ktour
implicit none
character*2 alg
integer i, j
integer mxtour
logical closed
read (*,*) alg, mxtour, closed
call alg2ij (alg, i, j)
call explor (i, j, mxtour, closed)
end
C-----------------------------------------------------------------------
subroutine explor (istart, jstart, mxtour, closed)
implicit none
C Explore the space of 'Warnsdorffian' knight’s paths, looking for
C and printing complete tours.
integer istart, jstart ! The starting position.
integer mxtour ! The maximum number of tours to print.
logical closed ! Closed tours only?
integer board(1:8,1:8)
integer imove(1:8,1:64)
integer jmove(1:8,1:64)
integer nmove(1:64)
integer n
integer itours
logical goodmv
logical isclos
itours = 0
call initbd (board)
n = 1
nmove(1) = 8
imove(8, 1) = istart
jmove(8, 1) = jstart
1000 if (itours .lt. mxtour .and. n .ne. 0) then
if (nmove(n) .eq. 9) then
n = n - 1
if (n .ne. 0) then
call unmove (board, imove, jmove, nmove, n)
nmove(n) = nmove(n) + 1
end if
else if (goodmv (imove, nmove, n)) then
call mkmove (board, imove, jmove, nmove, n)
if (n .eq. 64) then
if (.not. closed) then
itours = itours + 1
call prnt (board, itours)
else if (isclos (board)) then
itours = itours + 1
call prnt (board, itours)
end if
call unmove (board, imove, jmove, nmove, n)
nmove(n) = 9
else if (n .eq. 63) then
call possib (board, n, imove, jmove, nmove)
n = n + 1
nmove(n) = 1
else
call nxtmov (board, n, imove, jmove, nmove)
n = n + 1
nmove(n) = 1
end if
else
nmove(n) = nmove(n) + 1
end if
goto 1000
end if
end
C-----------------------------------------------------------------------
subroutine initbd (board)
implicit none
C Initialize a chessboard with empty squares.
integer board(1:8,1:8)
integer i, j
do 1010 j = 1, 8
do 1000 i = 1, 8
board(i, j) = -1
1000 continue
1010 continue
end
C-----------------------------------------------------------------------
subroutine mkmove (board, imove, jmove, nmove, n)
implicit none
C Fill a square with a move number.
integer board(1:8, 1:8)
integer imove(1:8, 1:64)
integer jmove(1:8, 1:64)
integer nmove(1:64)
integer n
board(imove(nmove(n), n), jmove(nmove(n), n)) = n
end
C-----------------------------------------------------------------------
subroutine unmove (board, imove, jmove, nmove, n)
implicit none
C Unmake a mkmove.
integer board(1:8, 1:8)
integer imove(1:8, 1:64)
integer jmove(1:8, 1:64)
integer nmove(1:64)
integer n
board(imove(nmove(n), n), jmove(nmove(n), n)) = -1
end
C-----------------------------------------------------------------------
function goodmv (imove, nmove, n)
implicit none
logical goodmv
integer imove(1:8, 1:64)
integer nmove(1:64)
integer n
goodmv = (imove(nmove(n), n) .ne. -1)
end
C-----------------------------------------------------------------------
subroutine prnt (board, itours)
implicit none
C Print a knight's tour.
integer board(1:8,1:8)
integer itours
10000 format (1X)
C The following plethora of format statements seemed a simple way to
C get this working with f2c. (For gfortran, the 'I0' format
C sufficed.)
10010 format (1X, "Tour number ", I1)
10020 format (1X, "Tour number ", I2)
10030 format (1X, "Tour number ", I3)
10040 format (1X, "Tour number ", I4)
10050 format (1X, "Tour number ", I5)
10060 format (1X, "Tour number ", I6)
10070 format (1X, "Tour number ", I20)
if (itours .lt. 10) then
write (*, 10010) itours
else if (itours .lt. 100) then
write (*, 10020) itours
else if (itours .lt. 1000) then
write (*, 10030) itours
else if (itours .lt. 10000) then
write (*, 10040) itours
else if (itours .lt. 100000) then
write (*, 10050) itours
else if (itours .lt. 1000000) then
write (*, 10060) itours
else
write (*, 10070) itours
end if
call prntmv (board)
call prntbd (board)
write (*, 10000)
end
C-----------------------------------------------------------------------
subroutine prntbd (board)
implicit none
C Print a chessboard with the move number in each square.
integer board(1:8,1:8)
integer i, j
10000 format (1X, " ", 8("+----"), "+")
10010 format (1X, I2, " ", 8(" | ", I2), " | ")
10020 format (1X, " ", 8(" ", A1))
do 1000 i = 8, 1, -1
write (*, 10000)
write (*, 10010) i, (board(i, j), j = 1, 8)
1000 continue
write (*, 10000)
write (*, 10020) 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'
end
C-----------------------------------------------------------------------
subroutine prntmv (board)
implicit none
C Print the moves of a knight's path, in algebraic notation.
integer board(1:8,1:8)
integer ipos(1:64)
integer jpos(1:64)
integer numpos
character*2 alg(1:64)
integer columns(1:8)
integer k
integer m
character*72 lines(1:8)
10000 format (1X, A)
call bd2pos (board, ipos, jpos, numpos)
C Convert the positions to algebraic notation.
do 1000 k = 1, numpos
call ij2alg (ipos(k), jpos(k), alg(k))
1000 continue
C Fill lines with algebraic notations.
do 1020 m = 1, 8
columns(m) = 1
1020 continue
m = 1
do 1100 k = 1, numpos
lines(m)(columns(m) : columns(m) + 1) = alg(k)(1:2)
columns(m) = columns(m) + 2
if (k .ne. numpos) then
lines(m)(columns(m) : columns(m) + 3) = " -> "
columns(m) = columns(m) + 4
else if (numpos .eq. 64 .and.
$ ((abs (ipos(numpos) - ipos(1)) .eq. 2
$ .and. abs (jpos(numpos) - jpos(1)) .eq. 1) .or.
$ ((abs (ipos(numpos) - ipos(1)) .eq. 1
$ .and. abs (jpos(numpos) - jpos(1)) .eq. 2)))) then
lines(m)(columns(m) : columns(m) + 8) = " -> cycle"
columns(m) = columns(m) + 9
endif
if (mod (k, 8) .eq. 0) m = m + 1
1100 continue
C Print the lines that have stuff in them.
do 1200 m = 1, 8
if (columns(m) .ne. 1) then
write (*, 10000) lines(m)(1 : columns(m) - 1)
end if
1200 continue
end
C-----------------------------------------------------------------------
function isclos (board)
implicit none
C Is a board a closed tour?
logical isclos
integer board(1:8,1:8)
integer ipos(1:64) ! The i-positions in order.
integer jpos(1:64) ! The j-positions in order.
integer numpos ! The number of positions so far.
call bd2pos (board, ipos, jpos, numpos)
isclos = (numpos .eq. 64 .and.
$ ((abs (ipos(numpos) - ipos(1)) .eq. 2
$ .and. abs (jpos(numpos) - jpos(1)) .eq. 1) .or.
$ ((abs (ipos(numpos) - ipos(1)) .eq. 1
$ .and. abs (jpos(numpos) - jpos(1)) .eq. 2))))
end
C-----------------------------------------------------------------------
subroutine bd2pos (board, ipos, jpos, numpos)
implicit none
C Convert from a board to a list of board positions.
integer board(1:8,1:8)
integer ipos(1:64) ! The i-positions in order.
integer jpos(1:64) ! The j-positions in order.
integer numpos ! The number of positions so far.
integer i, j
numpos = 0
do 1010 i = 1, 8
do 1000 j = 1, 8
if (board(i, j) .ne. -1) then
numpos = max (board(i, j), numpos)
ipos(board(i, j)) = i
jpos(board(i, j)) = j
end if
1000 continue
1010 continue
end
C-----------------------------------------------------------------------
subroutine nxtmov (board, n, imove, jmove, nmove)
implicit none
C Find possible next moves. Prune and sort the moves according to
C Warnsdorff's heuristic, keeping only those that have the minimum
C number of legal following moves.
integer board(1:8,1:8)
integer n
integer imove(1:8,1:64)
integer jmove(1:8,1:64)
integer nmove(1:64)
integer w1, w2, w3, w4, w5, w6, w7, w8
integer w
integer n1
integer pickw
call possib (board, n, imove, jmove, nmove)
n1 = n + 1
nmove(n1) = 1
call countf (board, n1, imove, jmove, nmove, w1)
nmove(n1) = 2
call countf (board, n1, imove, jmove, nmove, w2)
nmove(n1) = 3
call countf (board, n1, imove, jmove, nmove, w3)
nmove(n1) = 4
call countf (board, n1, imove, jmove, nmove, w4)
nmove(n1) = 5
call countf (board, n1, imove, jmove, nmove, w5)
nmove(n1) = 6
call countf (board, n1, imove, jmove, nmove, w6)
nmove(n1) = 7
call countf (board, n1, imove, jmove, nmove, w7)
nmove(n1) = 8
call countf (board, n1, imove, jmove, nmove, w8)
w = pickw (w1, w2, w3, w4, w5, w6, w7, w8)
if (w .eq. 0) then
call disabl (imove(1, n1), jmove(1, n1))
call disabl (imove(2, n1), jmove(2, n1))
call disabl (imove(3, n1), jmove(3, n1))
call disabl (imove(4, n1), jmove(4, n1))
call disabl (imove(5, n1), jmove(5, n1))
call disabl (imove(6, n1), jmove(6, n1))
call disabl (imove(7, n1), jmove(7, n1))
call disabl (imove(8, n1), jmove(8, n1))
else
if (w .ne. w1) call disabl (imove(1, n1), jmove(1, n1))
if (w .ne. w2) call disabl (imove(2, n1), jmove(2, n1))
if (w .ne. w3) call disabl (imove(3, n1), jmove(3, n1))
if (w .ne. w4) call disabl (imove(4, n1), jmove(4, n1))
if (w .ne. w5) call disabl (imove(5, n1), jmove(5, n1))
if (w .ne. w6) call disabl (imove(6, n1), jmove(6, n1))
if (w .ne. w7) call disabl (imove(7, n1), jmove(7, n1))
if (w .ne. w8) call disabl (imove(8, n1), jmove(8, n1))
end if
end
C-----------------------------------------------------------------------
subroutine countf (board, n, imove, jmove, nmove, w)
implicit none
C Count the number of moves possible after an nth move.
integer board(1:8,1:8)
integer n
integer imove(1:8,1:64)
integer jmove(1:8,1:64)
integer nmove(1:64)
integer w
logical goodmv
integer n1
if (goodmv (imove, nmove, n)) then
call mkmove (board, imove, jmove, nmove, n)
call possib (board, n, imove, jmove, nmove)
n1 = n + 1
w = 0
if (imove(1, n1) .ne. -1) w = w + 1
if (imove(2, n1) .ne. -1) w = w + 1
if (imove(3, n1) .ne. -1) w = w + 1
if (imove(4, n1) .ne. -1) w = w + 1
if (imove(5, n1) .ne. -1) w = w + 1
if (imove(6, n1) .ne. -1) w = w + 1
if (imove(7, n1) .ne. -1) w = w + 1
if (imove(8, n1) .ne. -1) w = w + 1
call unmove (board, imove, jmove, nmove, n)
else
C The nth move itself is impossible.
w = 0
end if
end
C-----------------------------------------------------------------------
function pickw (w1, w2, w3, w4, w5, w6, w7, w8)
implicit none
C From w1..w8, pick out the least nonzero value (or zero if they all
C equal zero).
integer pickw
integer w1, w2, w3, w4, w5, w6, w7, w8
integer w
integer pickw1
w = 0
w = pickw1 (w, w1)
w = pickw1 (w, w2)
w = pickw1 (w, w3)
w = pickw1 (w, w4)
w = pickw1 (w, w5)
w = pickw1 (w, w6)
w = pickw1 (w, w7)
w = pickw1 (w, w8)
pickw = w
end
C-----------------------------------------------------------------------
function pickw1 (u, v)
implicit none
C A small function used by pickw.
integer pickw1
integer u, v
if (v .eq. 0) then
pickw1 = u
else if (u .eq. 0) then
pickw1 = v
else
pickw1 = min (u, v)
end if
end
C-----------------------------------------------------------------------
subroutine possib (board, n, imove, jmove, nmove)
implicit none
C Find moves that are possible from an nth-move position.
integer board(1:8,1:8)
integer n
integer imove(1:8,1:64)
integer jmove(1:8,1:64)
integer nmove(1:64)
integer i, j
integer n1
i = imove(nmove(n), n)
j = jmove(nmove(n), n)
n1 = n + 1
call trymov (board, i + 1, j + 2, imove(1, n1), jmove(1, n1))
call trymov (board, i + 2, j + 1, imove(2, n1), jmove(2, n1))
call trymov (board, i + 1, j - 2, imove(3, n1), jmove(3, n1))
call trymov (board, i + 2, j - 1, imove(4, n1), jmove(4, n1))
call trymov (board, i - 1, j + 2, imove(5, n1), jmove(5, n1))
call trymov (board, i - 2, j + 1, imove(6, n1), jmove(6, n1))
call trymov (board, i - 1, j - 2, imove(7, n1), jmove(7, n1))
call trymov (board, i - 2, j - 1, imove(8, n1), jmove(8, n1))
end
C-----------------------------------------------------------------------
subroutine trymov (board, i, j, imove, jmove)
implicit none
C Try a move to square (i, j).
integer board(1:8,1:8)
integer i, j
integer imove, jmove
call disabl (imove, jmove)
if (1 .le. i .and. i .le. 8 .and. 1 .le. j .and. j .le. 8) then
if (board(i,j) .eq. -1) then
call enable (i, j, imove, jmove)
end if
end if
end
C-----------------------------------------------------------------------
subroutine enable (i, j, imove, jmove)
implicit none
C Enable a potential move.
integer i, j
integer imove, jmove
imove = i
jmove = j
end
C-----------------------------------------------------------------------
subroutine disabl (imove, jmove)
implicit none
C Disable a potential move.
integer imove, jmove
imove = -1
jmove = -1
end
C-----------------------------------------------------------------------
subroutine alg2ij (alg, i, j)
implicit none
C Convert, for instance, 'c5' to i=3,j=5.
character*2 alg
integer i, j
if (alg(1:1) .eq. 'a') j = 1
if (alg(1:1) .eq. 'b') j = 2
if (alg(1:1) .eq. 'c') j = 3
if (alg(1:1) .eq. 'd') j = 4
if (alg(1:1) .eq. 'e') j = 5
if (alg(1:1) .eq. 'f') j = 6
if (alg(1:1) .eq. 'g') j = 7
if (alg(1:1) .eq. 'h') j = 8
if (alg(2:2) .eq. '1') i = 1
if (alg(2:2) .eq. '2') i = 2
if (alg(2:2) .eq. '3') i = 3
if (alg(2:2) .eq. '4') i = 4
if (alg(2:2) .eq. '5') i = 5
if (alg(2:2) .eq. '6') i = 6
if (alg(2:2) .eq. '7') i = 7
if (alg(2:2) .eq. '8') i = 8
end
C-----------------------------------------------------------------------
subroutine ij2alg (i, j, alg)
implicit none
C Convert, for instance, i=3,j=5 to 'c5'.
integer i, j
character*2 alg
character alg1
character alg2
if (j .eq. 1) alg1 = 'a'
if (j .eq. 2) alg1 = 'b'
if (j .eq. 3) alg1 = 'c'
if (j .eq. 4) alg1 = 'd'
if (j .eq. 5) alg1 = 'e'
if (j .eq. 6) alg1 = 'f'
if (j .eq. 7) alg1 = 'g'
if (j .eq. 8) alg1 = 'h'
if (i .eq. 1) alg2 = '1'
if (i .eq. 2) alg2 = '2'
if (i .eq. 3) alg2 = '3'
if (i .eq. 4) alg2 = '4'
if (i .eq. 5) alg2 = '5'
if (i .eq. 6) alg2 = '6'
if (i .eq. 7) alg2 = '7'
if (i .eq. 8) alg2 = '8'
alg(1:1) = alg1
alg(2:2) = alg2
end
C-----------------------------------------------------------------------</syntaxhighlight>
{{out}}
$ echo "c5 2 T" | ./knights_tour
<pre> Tour number 1
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> e8 -> d6 -> b5 -> d4 -> f5 -> g7 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 58 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 63 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 60 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 61 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
Tour number 2
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> b5 -> d6 -> e8 -> g7 -> f5 -> d4 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 60 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 61 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 58 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 63 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
</pre>
===Fortran 95===
{{works with|gfortran|11.2.1}}
{{trans|ATS}}
<syntaxhighlight lang="fortran">!-----------------------------------------------------------------------
!
! Find Knight’s Tours.
!
! Using Warnsdorff’s heuristic, find multiple solutions.
! Optionally accept only closed tours.
!
! This program is migrated from my implementation for
! ATS/Postiats. Unlike my FORTRAN 77 implementation (which simply
! cannot do so), it uses a recursive call.
!
! Compile with, for instance:
!
! gfortran -O2 -g -std=f95 -o knights_tour knights_tour.f90
!
! Usage examples:
!
! One tour starting at a1, either open or closed:
!
! echo "a1 1 F" | ./knights_tour
!
! No more than 2000 closed tours starting at c5:
!
! echo "c5 2000 T" | ./knights_tour
!
!-----------------------------------------------------------------------
program knights_tour
implicit none
character(len = 2) inp__alg
integer inp__istart
integer inp__jstart
integer inp__max_tours
logical inp__closed
read (*,*) inp__alg, inp__max_tours, inp__closed
call alg2ij (inp__alg, inp__istart, inp__jstart)
call main (inp__istart, inp__jstart, inp__max_tours, inp__closed)
contains
subroutine main (istart, jstart, max_tours, closed)
integer, intent(in) :: istart, jstart ! The starting position.
integer, intent(in) :: max_tours ! The max. no. of tours to print.
logical, intent(in) :: closed ! Closed tours only?
integer board(1:8,1:8)
integer num_tours_printed
num_tours_printed = 0
call init_board (board)
call explore (board, 1, istart, jstart, max_tours, &
& num_tours_printed, closed)
end subroutine main
recursive subroutine explore (board, n, i, j, max_tours, &
& num_tours_printed, closed)
! Recursively the space of 'Warnsdorffian' knight’s paths, looking
! for and printing complete tours.
integer, intent(inout) :: board(1:8,1:8)
integer, intent(in) :: n
integer, intent(in) :: i, j
integer, intent(in) :: max_tours
integer, intent(inout) :: num_tours_printed
logical, intent(in) :: closed
integer imove(1:8)
integer jmove(1:8)
integer k
if (num_tours_printed < max_tours .and. n /= 0) then
if (is_good_move (i, j)) then
call mkmove (board, i, j, n)
if (n == 63) then
call find_possible_moves (board, i, j, imove, jmove)
call try_last_move (board, n + 1, imove(1), jmove(1), &
& num_tours_printed, closed)
call try_last_move (board, n + 1, imove(2), jmove(2), &
& num_tours_printed, closed)
call try_last_move (board, n + 1, imove(3), jmove(3), &
& num_tours_printed, closed)
call try_last_move (board, n + 1, imove(4), jmove(4), &
& num_tours_printed, closed)
call try_last_move (board, n + 1, imove(5), jmove(5), &
& num_tours_printed, closed)
call try_last_move (board, n + 1, imove(6), jmove(6), &
& num_tours_printed, closed)
call try_last_move (board, n + 1, imove(7), jmove(7), &
& num_tours_printed, closed)
call try_last_move (board, n + 1, imove(8), jmove(8), &
& num_tours_printed, closed)
else
call find_next_moves (board, n, i, j, imove, jmove)
do k = 1, 8
if (is_good_move (imove(k), jmove(k))) then
!
! Here is the recursive call.
!
call explore (board, n + 1, imove(k), jmove(k), &
& max_tours, num_tours_printed, closed)
end if
end do
end if
call unmove (board, i, j)
end if
end if
end subroutine explore
subroutine try_last_move (board, n, i, j, num_tours_printed, closed)
integer, intent(inout) :: board(1:8,1:8)
integer, intent(in) :: n
integer, intent(in) :: i, j
integer, intent(inout) :: num_tours_printed
logical, intent(in) :: closed
integer ipos(1:64)
integer jpos(1:64)
integer numpos
integer idiff
integer jdiff
if (is_good_move (i, j)) then
call mkmove (board, i, j, n)
if (.not. closed) then
num_tours_printed = num_tours_printed + 1
call print_tour (board, num_tours_printed)
else
call board2positions (board, ipos, jpos, numpos)
idiff = abs (i - ipos(1))
jdiff = abs (j - jpos(1))
if ((idiff == 1 .and. jdiff == 2) .or. &
(idiff == 2 .and. jdiff == 1)) then
num_tours_printed = num_tours_printed + 1
call print_tour (board, num_tours_printed)
end if
end if
call unmove (board, i, j)
end if
end subroutine try_last_move
subroutine init_board (board)
! Initialize a chessboard with empty squares.
integer, intent(out) :: board(1:8,1:8)
integer i, j
do j = 1, 8
do i = 1, 8
board(i, j) = -1
end do
end do
end subroutine init_board
subroutine mkmove (board, i, j, n)
! Fill a square with a move number.
integer, intent(inout) :: board(1:8, 1:8)
integer, intent(in) :: i, j
integer, intent(in) :: n
board(i, j) = n
end subroutine mkmove
subroutine unmove (board, i, j)
! Unmake a mkmove.
integer, intent(inout) :: board(1:8, 1:8)
integer, intent(in) :: i, j
board(i, j) = -1
end subroutine unmove
function is_good_move (i, j)
logical is_good_move
integer, intent(in) :: i, j
is_good_move = (i /= -1 .and. j /= -1)
end function is_good_move
subroutine print_tour (board, num_tours_printed)
! Print a knight's tour.
integer, intent(in) :: board(1:8,1:8)
integer, intent(in) :: num_tours_printed
write (*, '("Tour number ", I0)') num_tours_printed
call print_moves (board)
call print_board (board)
write (*, '()')
end subroutine print_tour
subroutine print_board (board)
! Print a chessboard with the move number in each square.
integer, intent(in) :: board(1:8,1:8)
integer i, j
do i = 8, 1, -1
write (*, '(" ", 8("+----"), "+")')
write (*, '(I2, " ", 8(" | ", I2), " | ")') &
i, (board(i, j), j = 1, 8)
end do
write (*, '(" ", 8("+----"), "+")')
write (*, '(" ", 8(" ", A1))') &
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'
end subroutine print_board
subroutine print_moves (board)
! Print the moves of a knight's path, in algebraic notation.
integer, intent(in) :: board(1:8,1:8)
integer ipos(1:64)
integer jpos(1:64)
integer numpos
character(len = 2) alg(1:64)
integer columns(1:8)
integer k
integer m
character(len = 72) lines(1:8)
call board2positions (board, ipos, jpos, numpos)
! Convert the positions to algebraic notation.
do k = 1, numpos
call ij2alg (ipos(k), jpos(k), alg(k))
end do
! Fill lines with algebraic notations.
do m = 1, 8
columns(m) = 1
end do
m = 1
do k = 1, numpos
lines(m)(columns(m) : columns(m) + 1) = alg(k)(1:2)
columns(m) = columns(m) + 2
if (k /= numpos) then
lines(m)(columns(m) : columns(m) + 3) = " -> "
columns(m) = columns(m) + 4
else if (numpos == 64 .and. &
((abs (ipos(numpos) - ipos(1)) == 2 &
.and. abs (jpos(numpos) - jpos(1)) == 1) .or. &
((abs (ipos(numpos) - ipos(1)) == 1 &
.and. abs (jpos(numpos) - jpos(1)) == 2)))) then
lines(m)(columns(m) : columns(m) + 8) = " -> cycle"
columns(m) = columns(m) + 9
endif
if (mod (k, 8) == 0) m = m + 1
end do
! Print the lines that have stuff in them.
do m = 1, 8
if (columns(m) /= 1) then
write (*, '(A)') lines(m)(1 : columns(m) - 1)
end if
end do
end subroutine print_moves
function is_closed (board)
! Is a board a closed tour?
logical is_closed
integer board(1:8,1:8)
integer ipos(1:64) ! The i-positions in order.
integer jpos(1:64) ! The j-positions in order.
integer numpos ! The number of positions so far.
call board2positions (board, ipos, jpos, numpos)
is_closed = (numpos == 64 .and. &
((abs (ipos(numpos) - ipos(1)) == 2 &
.and. abs (jpos(numpos) - jpos(1)) == 1) .or. &
((abs (ipos(numpos) - ipos(1)) == 1 &
.and. abs (jpos(numpos) - jpos(1)) == 2))))
end function is_closed
subroutine board2positions (board, ipos, jpos, numpos)
! Convert from a board to a list of board positions.
integer, intent(in) :: board(1:8,1:8)
integer, intent(out) :: ipos(1:64) ! The i-positions in order.
integer, intent(out) :: jpos(1:64) ! The j-positions in order.
integer, intent(out) :: numpos ! The number of positions so far.
integer i, j
numpos = 0
do i = 1, 8
do j = 1, 8
if (board(i, j) /= -1) then
numpos = max (board(i, j), numpos)
ipos(board(i, j)) = i
jpos(board(i, j)) = j
end if
end do
end do
end subroutine board2positions
subroutine find_next_moves (board, n, i, j, imove, jmove)
! Find possible next moves. Prune and sort the moves according to
! Warnsdorff's heuristic, keeping only those that have the minimum
! number of legal following moves.
integer, intent(inout) :: board(1:8,1:8)
integer, intent(in) :: n
integer, intent(in) :: i, j
integer, intent(inout) :: imove(1:8)
integer, intent(inout) :: jmove(1:8)
integer w1, w2, w3, w4, w5, w6, w7, w8
integer w
call find_possible_moves (board, i, j, imove, jmove)
call count_following (board, n + 1, imove(1), jmove(1), w1)
call count_following (board, n + 1, imove(2), jmove(2), w2)
call count_following (board, n + 1, imove(3), jmove(3), w3)
call count_following (board, n + 1, imove(4), jmove(4), w4)
call count_following (board, n + 1, imove(5), jmove(5), w5)
call count_following (board, n + 1, imove(6), jmove(6), w6)
call count_following (board, n + 1, imove(7), jmove(7), w7)
call count_following (board, n + 1, imove(8), jmove(8), w8)
w = pick_w (w1, w2, w3, w4, w5, w6, w7, w8)
if (w == 0) then
call disable (imove(1), jmove(1))
call disable (imove(2), jmove(2))
call disable (imove(3), jmove(3))
call disable (imove(4), jmove(4))
call disable (imove(5), jmove(5))
call disable (imove(6), jmove(6))
call disable (imove(7), jmove(7))
call disable (imove(8), jmove(8))
else
if (w /= w1) call disable (imove(1), jmove(1))
if (w /= w2) call disable (imove(2), jmove(2))
if (w /= w3) call disable (imove(3), jmove(3))
if (w /= w4) call disable (imove(4), jmove(4))
if (w /= w5) call disable (imove(5), jmove(5))
if (w /= w6) call disable (imove(6), jmove(6))
if (w /= w7) call disable (imove(7), jmove(7))
if (w /= w8) call disable (imove(8), jmove(8))
end if
end subroutine find_next_moves
subroutine count_following (board, n, i, j, w)
! Count the number of moves possible after an nth move.
integer, intent(inout) :: board(1:8,1:8)
integer, intent(in) :: n
integer, intent(in) :: i, j
integer, intent(out) :: w
integer imove(1:8)
integer jmove(1:8)
if (is_good_move (i, j)) then
call mkmove (board, i, j, n)
call find_possible_moves (board, i, j, imove, jmove)
w = 0
if (is_good_move (imove(1), jmove(1))) w = w + 1
if (is_good_move (imove(2), jmove(2))) w = w + 1
if (is_good_move (imove(3), jmove(3))) w = w + 1
if (is_good_move (imove(4), jmove(4))) w = w + 1
if (is_good_move (imove(5), jmove(5))) w = w + 1
if (is_good_move (imove(6), jmove(6))) w = w + 1
if (is_good_move (imove(7), jmove(7))) w = w + 1
if (is_good_move (imove(8), jmove(8))) w = w + 1
call unmove (board, i, j)
else
! The nth move itself is impossible.
w = 0
end if
end subroutine count_following
function pick_w (w1, w2, w3, w4, w5, w6, w7, w8) result (w)
! From w1..w8, pick out the least nonzero value (or zero if they
! all equal zero).
integer, intent(in) :: w1, w2, w3, w4, w5, w6, w7, w8
integer w
w = 0
w = pick_w1 (w, w1)
w = pick_w1 (w, w2)
w = pick_w1 (w, w3)
w = pick_w1 (w, w4)
w = pick_w1 (w, w5)
w = pick_w1 (w, w6)
w = pick_w1 (w, w7)
w = pick_w1 (w, w8)
end function pick_w
function pick_w1 (u, v)
! A small function used by pick_w.
integer pick_w1
integer, intent(in) :: u, v
if (v == 0) then
pick_w1 = u
else if (u == 0) then
pick_w1 = v
else
pick_w1 = min (u, v)
end if
end function pick_w1
subroutine find_possible_moves (board, i, j, imove, jmove)
! Find moves that are possible from a position.
integer, intent(in) :: board(1:8,1:8)
integer, intent(in) :: i, j
integer, intent(out) :: imove(1:8)
integer, intent(out) :: jmove(1:8)
call trymov (board, i + 1, j + 2, imove(1), jmove(1))
call trymov (board, i + 2, j + 1, imove(2), jmove(2))
call trymov (board, i + 1, j - 2, imove(3), jmove(3))
call trymov (board, i + 2, j - 1, imove(4), jmove(4))
call trymov (board, i - 1, j + 2, imove(5), jmove(5))
call trymov (board, i - 2, j + 1, imove(6), jmove(6))
call trymov (board, i - 1, j - 2, imove(7), jmove(7))
call trymov (board, i - 2, j - 1, imove(8), jmove(8))
end subroutine find_possible_moves
subroutine trymov (board, i, j, imove, jmove)
! Try a move to square (i, j).
integer, intent(in) :: board(1:8,1:8)
integer, intent(in) :: i, j
integer, intent(inout) :: imove, jmove
call disable (imove, jmove)
if (1 <= i .and. i <= 8 .and. 1 <= j .and. j <= 8) then
if (square_is_empty (board, i, j)) then
call enable (i, j, imove, jmove)
end if
end if
end subroutine trymov
function square_is_empty (board, i, j)
logical square_is_empty
integer, intent(in) :: board(1:8,1:8)
integer, intent(in) :: i, j
square_is_empty = (board(i, j) == -1)
end function square_is_empty
subroutine enable (i, j, imove, jmove)
! Enable a potential move.
integer, intent(in) :: i, j
integer, intent(inout) :: imove, jmove
imove = i
jmove = j
end subroutine enable
subroutine disable (imove, jmove)
! Disable a potential move.
integer, intent(out) :: imove, jmove
imove = -1
jmove = -1
end subroutine disable
subroutine alg2ij (alg, i, j)
! Convert, for instance, 'c5' to i=3,j=5.
character(len = 2), intent(in) :: alg
integer, intent(out) :: i, j
if (alg(1:1) == 'a') j = 1
if (alg(1:1) == 'b') j = 2
if (alg(1:1) == 'c') j = 3
if (alg(1:1) == 'd') j = 4
if (alg(1:1) == 'e') j = 5
if (alg(1:1) == 'f') j = 6
if (alg(1:1) == 'g') j = 7
if (alg(1:1) == 'h') j = 8
if (alg(2:2) == '1') i = 1
if (alg(2:2) == '2') i = 2
if (alg(2:2) == '3') i = 3
if (alg(2:2) == '4') i = 4
if (alg(2:2) == '5') i = 5
if (alg(2:2) == '6') i = 6
if (alg(2:2) == '7') i = 7
if (alg(2:2) == '8') i = 8
end subroutine alg2ij
subroutine ij2alg (i, j, alg)
! Convert, for instance, i=3,j=5 to 'c5'.
integer, intent(in) :: i, j
character(len = 2), intent(out) :: alg
character alg1
character alg2
if (j == 1) alg1 = 'a'
if (j == 2) alg1 = 'b'
if (j == 3) alg1 = 'c'
if (j == 4) alg1 = 'd'
if (j == 5) alg1 = 'e'
if (j == 6) alg1 = 'f'
if (j == 7) alg1 = 'g'
if (j == 8) alg1 = 'h'
if (i == 1) alg2 = '1'
if (i == 2) alg2 = '2'
if (i == 3) alg2 = '3'
if (i == 4) alg2 = '4'
if (i == 5) alg2 = '5'
if (i == 6) alg2 = '6'
if (i == 7) alg2 = '7'
if (i == 8) alg2 = '8'
alg(1:1) = alg1
alg(2:2) = alg2
end subroutine ij2alg
end program
!-----------------------------------------------------------------------</syntaxhighlight>
{{out}}
$ echo "c5 2 T" | ./knights_tour
<pre>Tour number 1
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> e8 -> d6 -> b5 -> d4 -> f5 -> g7 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 58 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 63 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 60 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 61 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
Tour number 2
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> b5 -> d6 -> e8 -> g7 -> f5 -> d4 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 60 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 61 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 58 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 63 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
</pre>
===Fortran 2008===
{{works with|gfortran|11.2.1}}
(This one is ''not'' a translation of my ATS implementation. I wrote it earlier.)
<syntaxhighlight lang="fortran">!!!
!!! Find a Knight’s Tour.
!!!
!!! Use Warnsdorff’s heuristic, but write the program so it should not
!!! be able to terminate unsuccessfully.
!!!
module knights_tour
use, intrinsic :: iso_fortran_env, only: output_unit, error_unit
implicit none
private
public :: find_a_knights_tour
public :: notation_is_a_square
integer, parameter :: number_of_ranks = 8
integer, parameter :: number_of_files = 8
integer, parameter :: number_of_squares = number_of_ranks * number_of_files
! ‘Algebraic’ chess notation.
character, parameter :: rank_notation(1:8) = (/ '1', '2', '3', '4', '5', '6', '7', '8' /)
character, parameter :: file_notation(1:8) = (/ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' /)
type :: board_square_t
! Squares are represented by their algebraic notation.
character(2) :: algebraic_notation
contains
procedure, pass :: output => board_square_t_output
procedure, pass :: knight_moves => board_square_t_knight_moves
procedure, pass :: equal => board_square_t_equal
generic :: operator(==) => equal
end type board_square_t
type :: knight_moves_t
integer :: number_of_squares
type(board_square_t) :: squares(1:8)
end type knight_moves_t
type :: path_t
integer :: length
type(board_square_t) :: squares(1:number_of_squares)
contains
procedure, pass :: output => path_t_output
end type path_t
contains
pure function notation_is_a_square (notation) result (bool)
character(*), intent(in) :: notation
logical :: bool
integer :: length
integer :: rank_no
integer :: file_no
length = len_trim (notation)
if (length /= 2) then
bool = .false.
else
rank_no = findloc (rank_notation, notation(2:2), 1)
file_no = findloc (file_notation, notation(1:1), 1)
bool = (1 <= rank_no .and. rank_no <= number_of_ranks) &
& .and. (1 <= file_no .and. file_no <= number_of_files)
end if
end function notation_is_a_square
subroutine path_t_output (path, unit)
!
! Print a path in algebraic notation.
!
class(path_t), intent(in) :: path
integer, intent(in) :: unit
integer :: moves_counter
integer :: i
moves_counter = 1
if (1 <= path%length) then
call path%squares(1)%output(unit)
do i = 2, path%length
if (moves_counter == 8) then
write (unit, '(" ->")', advance = 'yes')
moves_counter = 1
else
write (unit, '(" -> ")', advance = 'no')
moves_counter = moves_counter + 1
end if
call path%squares(i)%output(unit)
end do
end if
write (output_unit, '()')
end subroutine path_t_output
subroutine board_square_t_output (square, unit)
!
! Print a square in algebraic notation.
!
class(board_square_t), intent(in) :: square
integer, intent(in) :: unit
write (unit, '(A2)', advance = 'no') square%algebraic_notation
end subroutine board_square_t_output
elemental function board_square_t_equal (p, q) result (bool)
class(board_square_t), intent(in) :: p, q
logical :: bool
bool = (p%algebraic_notation == q%algebraic_notation)
end function board_square_t_equal
pure function board_square_t_knight_moves (square) result (moves)
!
! Return all possible moves of a knight from a given square.
!
class(board_square_t), intent(in) :: square
type(knight_moves_t) :: moves
integer, parameter :: rank_stride(1:number_of_ranks) = (/ +1, +2, +1, +2, -1, -2, -1, -2 /)
integer, parameter :: file_stride(1:number_of_files) = (/ +2, +1, -2, -1, +2, +1, -2, -1 /)
integer :: rank_no, file_no
integer :: new_rank_no, new_file_no
integer :: i
character(2) :: notation
rank_no = findloc (rank_notation, square%algebraic_notation(2:2), 1)
file_no = findloc (file_notation, square%algebraic_notation(1:1), 1)
moves%number_of_squares = 0
do i = 1, 8
new_rank_no = rank_no + rank_stride(i)
new_file_no = file_no + file_stride(i)
if (1 <= new_rank_no &
& .and. new_rank_no <= number_of_ranks &
& .and. 1 <= new_file_no &
& .and. new_file_no <= number_of_files) then
moves%number_of_squares = moves%number_of_squares + 1
notation(2:2) = rank_notation(new_rank_no)
notation(1:1) = file_notation(new_file_no)
moves%squares(moves%number_of_squares) = board_square_t (notation)
end if
end do
end function board_square_t_knight_moves
pure function unvisited_knight_moves (path) result (moves)
!
! Return moves of a knight from a given square, but only those
! that have not been visited already.
!
class(path_t), intent(in) :: path
type(knight_moves_t) :: moves
type(knight_moves_t) :: all_moves
integer :: i
all_moves = path%squares(path%length)%knight_moves()
moves%number_of_squares = 0
do i = 1, all_moves%number_of_squares
if (all (.not. all_moves%squares(i) == path%squares(1:path%length))) then
moves%number_of_squares = moves%number_of_squares + 1
moves%squares(moves%number_of_squares) = all_moves%squares(i)
end if
end do
end function unvisited_knight_moves
pure function potential_knight_moves (path) result (moves)
!
! Return moves of a knight from a given square, but only those
! that are unvisited, and from which another unvisited move can be
! made.
!
! Sort the returned moves in nondecreasing order of the number of
! possible moves after the first. (This is how we implement
! Warnsdorff’s heuristic.)
!
class(path_t), intent(in) :: path
type(knight_moves_t) :: moves
type(knight_moves_t) :: unvisited_moves
type(knight_moves_t) :: next_moves
type(path_t) :: next_path
type(board_square_t) :: unpruned_squares(1:8)
integer :: warnsdorff_numbers(1:8)
integer :: number_of_unpruned_squares
integer :: i
if (path%length == number_of_squares - 1) then
!
! There is only one square left on the board. Either the knight
! can reach it or it cannot.
!
moves = unvisited_knight_moves (path)
else
!
! Use Warnsdorff’s heuristic: return unvisited moves, but try
! first those with the least number of possible moves following
! it.
!
! If the number of possible moves following is zero, prune the
! move, because it is a dead end.
!
number_of_unpruned_squares = 0
unvisited_moves = unvisited_knight_moves (path)
do i = 1, unvisited_moves%number_of_squares
next_path%length = path%length + 1
next_path%squares(1:path%length) = path%squares(1:path%length)
next_path%squares(next_path%length) = unvisited_moves%squares(i)
next_moves = unvisited_knight_moves (next_path)
if (next_moves%number_of_squares /= 0) then
number_of_unpruned_squares = number_of_unpruned_squares + 1
unpruned_squares(number_of_unpruned_squares) = unvisited_moves%squares(i)
warnsdorff_numbers(number_of_unpruned_squares) = next_moves%number_of_squares
end if
end do
! In-place insertion sort of the unpruned squares.
block
type(board_square_t) :: square
integer :: w_number
integer :: i, j
i = 2
do while (i <= number_of_unpruned_squares)
square = unpruned_squares(i)
w_number = warnsdorff_numbers(i)
j = i - 1
do while (1 <= j .and. w_number < warnsdorff_numbers(j))
unpruned_squares(j + 1) = unpruned_squares(j)
warnsdorff_numbers(j + 1) = warnsdorff_numbers(j)
j = j - 1
end do
unpruned_squares(j + 1) = square
warnsdorff_numbers(j + 1) = w_number
i = i + 1
end do
end block
moves%number_of_squares = number_of_unpruned_squares
moves%squares(1:number_of_unpruned_squares) = &
& unpruned_squares(1:number_of_unpruned_squares)
end if
end function potential_knight_moves
subroutine find_a_knights_tour (starting_square)
!
! Find and print a full knight’s tour.
!
character(2), intent(in) :: starting_square
type(path_t) :: path
path%length = 1
path%squares(1) = board_square_t (starting_square)
path = try_paths (path)
if (path%length /= 0) then
call path%output(output_unit)
else
write (error_unit, '("The program terminated without finding a solution.")')
write (error_unit, '("This is supposed to be impossible for an 8-by-8 board.")')
write (error_unit, '("The program is wrong.")')
error stop
end if
contains
recursive function try_paths (path) result (solution)
!
! Recursively try all possible paths, but using Warnsdorff’s
! heuristic to speed up the search.
!
class(path_t), intent(in) :: path
type(path_t) :: solution
type(path_t) :: new_path
type(knight_moves_t) :: moves
integer :: i
if (path%length == number_of_squares) then
solution = path
else
solution%length = 0
moves = potential_knight_moves (path)
if (moves%number_of_squares /= 0) then
new_path%length = path%length + 1
new_path%squares(1:path%length) = path%squares(1:path%length)
i = 1
do while (solution%length == 0 .and. i <= moves%number_of_squares)
new_path%squares(new_path%length) = moves%squares(i)
solution = try_paths (new_path)
i = i + 1
end do
end if
end if
end function try_paths
end subroutine find_a_knights_tour
end module knights_tour
program knights_tour_main
use, intrinsic :: iso_fortran_env, only: output_unit
use, non_intrinsic :: knights_tour
implicit none
character(200) :: arg
integer :: arg_count
integer :: i
arg_count = command_argument_count ()
do i = 1, arg_count
call get_command_argument (i, arg)
arg = adjustl (arg)
if (1 < i) write (output_unit, '()')
if (notation_is_a_square (arg)) then
call find_a_knights_tour (arg)
else
write (output_unit, '("This is not algebraic notation: ", A)') arg
end if
end do
end program knights_tour_main</syntaxhighlight>
$ ./knights_tour a1 b2 c3
<pre>a1 -> c2 -> a3 -> b1 -> d2 -> f1 -> h2 -> g4 ->
h6 -> g8 -> e7 -> c8 -> a7 -> b5 -> c7 -> a8 ->
b6 -> a4 -> b2 -> d1 -> f2 -> h1 -> g3 -> h5 ->
g7 -> e8 -> f6 -> h7 -> f8 -> d7 -> b8 -> a6 ->
b4 -> a2 -> c3 -> d5 -> e3 -> f5 -> h4 -> g2 ->
e1 -> f3 -> g1 -> h3 -> g5 -> e4 -> d6 -> c4 ->
a5 -> b7 -> d8 -> f7 -> h8 -> g6 -> e5 -> c6 ->
d4 -> e6 -> f4 -> e2 -> c1 -> d3 -> c5 -> b3
b2 -> a4 -> b6 -> a8 -> c7 -> e8 -> g7 -> h5 ->
g3 -> h1 -> f2 -> d1 -> c3 -> a2 -> c1 -> e2 ->
g1 -> h3 -> f4 -> g2 -> h4 -> g6 -> h8 -> f7 ->
d8 -> b7 -> a5 -> b3 -> a1 -> c2 -> e1 -> d3 ->
b4 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> e6 ->
c5 -> e4 -> f6 -> g8 -> h6 -> g4 -> h2 -> f1 ->
d2 -> b1 -> a3 -> c4 -> e5 -> f3 -> d4 -> b5 ->
d6 -> c8 -> a7 -> c6 -> e7 -> f5 -> e3 -> d5
c3 -> a2 -> c1 -> e2 -> g1 -> h3 -> g5 -> h7 ->
f8 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f1 -> h2 -> f3 ->
h4 -> g2 -> e1 -> d3 -> f4 -> h5 -> g7 -> e8 ->
f6 -> g8 -> h6 -> g4 -> e5 -> d7 -> b8 -> a6 ->
b4 -> c6 -> a7 -> c8 -> e7 -> d5 -> b6 -> a8 ->
c7 -> e6 -> c5 -> a4 -> b2 -> c4 -> e3 -> d1 ->
f2 -> h1 -> g3 -> e4 -> d6 -> f5 -> d4 -> b5</pre>
=={{header|Go}}==
===Warnsdorf's rule===
<
import (
Line 3,109 ⟶ 6,224:
}
return true
}</
{{out}}
<pre>
Line 3,122 ⟶ 6,237:
</pre>
===Ant colony===
<
by Philip Hingston and Graham Kendal,
PDF at http://www.cs.nott.ac.uk/~gxk/papers/cec05knights.pdf. */
Line 3,313 ⟶ 6,428:
tourCh <- moves
}
}</
Output:
<pre>
Line 3,329 ⟶ 6,444:
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.Bifunctor (bimap)
import Data.Char (chr, ord)
import Data.List (intercalate, minimumBy, sort, (\\)
import Data.Ord (comparing)
import
---------------------- KNIGHT'S TOUR ---------------------
type Square = (Int, Int)
Line 3,343 ⟶ 6,459:
| otherwise = knightTour $ newSquare : moves
where
newSquare =
minimumBy
(comparing (length . findMoves))
possibilities
possibilities = findMoves $ head moves
findMoves = (\\ moves) . knightOptions
Line 3,349 ⟶ 6,468:
knightOptions :: Square -> [Square]
knightOptions (x, y) =
knightMoves >>= go . bimap (+ x) (+ y)
where
go
| uncurry (&&) (both
| otherwise = []
knightMoves :: [(Int, Int)]
knightMoves =
where
go i x
| abs i /= abs x = [(i, x)]
| otherwise = []
onBoard :: Int -> Bool
onBoard = (&&) . (0 <) <*> (9 >)
both :: (a -> b) -> (a, a) -> (b, b)
both = join bimap
--------------------------- TEST -------------------------
startPoint :: String
startPoint = "e5"
Line 3,373 ⟶ 6,498:
main =
printTour $
algebraic
<$> knightTour
[(\[x, y] -> (ord x - 96, ord y - 48)) startPoint]
where
printTour [] = return ()
printTour tour = do
putStrLn $ intercalate " -> " $ take 8 tour
printTour $ drop 8 tour</
{{Out}}
<pre>e5 -> f7 -> h8 -> g6 -> h4 -> g2 -> e1 -> f3
Line 3,396 ⟶ 6,523:
The algorithm doesn't always generate a complete tour.
<
procedure main(A)
Line 3,496 ⟶ 6,623:
}
every write(hdr2|hdr1|&null)
end</
The following can be used when debugging to validate the board structure and to image the available moves on the board.
<
write("Board size=",B.N)
write("Available Moves at start of tour:", ImageMovesTo(B.movesto))
Line 3,509 ⟶ 6,636:
every s ||:= " " || (!sort(movesto[k])|"\n")
return s
end</
Line 3,561 ⟶ 6,688:
'''Solution:'''<br>
[[j:Essays/Knight's Tour|The Knight's tour essay on the Jwiki]] shows a couple of solutions including one using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]].
<
kmoves=: monad define
t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1
Line 3,577 ⟶ 6,704:
assert. ~:p
(,~y)$/:p
)</
'''Example Use:'''
<
0 25 14 23 28 49 12 31
15 22 27 50 13 30 63 48
Line 3,601 ⟶ 6,728:
555 558 553 778 563 570 775 780 785 772 1000...
100 551 556 561 102 777 572 771 104 781 57...
557 554 101 552 571 562 103 776 573 770 10...</
=={{header|Java}}==
{{Works with|Java|7}}
<
public class KnightsTour {
Line 3,702 ⟶ 6,829:
}
}
}</
<pre>34 17 20 3 36 7 22 5
19 2 35 40 21 4 37 8
Line 3,713 ⟶ 6,840:
===More efficient non-trackback solution===
{{Works with|Java|8}}
<syntaxhighlight lang="text">
package com.knight.tour;
import java.util.ArrayList;
Line 3,872 ⟶ 6,999:
}
}
</syntaxhighlight>
<pre>
Found a path for 8 X 8 chess board.
Line 3,889 ⟶ 7,016:
You can test it [http://paulo-jorente.de/webgames/repos/knightsTour/ here].
<
class KnightTour {
constructor() {
Line 4,105 ⟶ 7,232:
}
new KnightTour();
</syntaxhighlight>
To test it, you'll need an index.html
<pre>
Line 4,175 ⟶ 7,302:
A composition of values, drawing on generic abstractions:
{{Trans|Haskell}}
<
'use strict';
Line 4,468 ⟶ 7,595:
// MAIN ---
return main();
})();</
{{Out}}
<pre>(Board size 8*8)
Line 4,497 ⟶ 7,624:
=={{header|Julia}}==
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task.
<
const chessboard = """
Line 4,515 ⟶ 7,642:
hidatosolve(board, maxmoves, knightmoves, fixed, starts[1][1], starts[1][2], 1)
printboard(board)
</
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Line 4,538 ⟶ 7,665:
{{trans|Haskell}}
<
val board = Array(8 * 8, { Square(it / 8 + 1, it % 8 + 1) })
Line 4,566 ⟶ 7,693:
col = (col + 1) % 8
}
}</
{{out}}
Line 4,582 ⟶ 7,709:
Influenced by the Python version, although computed tours are different.
<
20 input "Board size: ",size
30 input "Start position: ",a$
Line 4,628 ⟶ 7,755:
450 ' skip this move
460 next
470 return</
[[File:Knights tour Locomotive Basic.png]]
=={{header|Lua}}==
<
moves = { {1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2} }
Line 4,683 ⟶ 7,810:
print( string.format( "%s%d - %s%d", string.sub("ABCDEFGH",last[1],last[1]), last[2], string.sub("ABCDEFGH",lst[i][1],lst[i][1]), lst[i][2] ) )
last = lst[i]
end</
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Function KnightTour$(StartW=1, StartH=1){
def boolean swapH, swapV=True
Line 4,788 ⟶ 7,915:
Clipboard ex$
Report ex$
</syntaxhighlight>
{{out}}
<pre>
Line 4,829 ⟶ 7,956:
</pre>
=={{header|
Warnsdorff’s rule, with random tie-breaks. The program keeps trying
until it finds a solution. Running time can vary a lot.
Beware the program writes to a file ‘__random_number__’ in the working directory. (This can be avoided in GNU m4 by using ‘esyscmd’ instead of ‘syscmd’. I do not know how to avoid it in general.)
<syntaxhighlight lang="m4">divert(-1)
----------------------------------------------------------------------
This is free and unencumbered software released into the public
domain.
Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.
In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
For more information, please refer to <http://unlicense.org/>
----------------------------------------------------------------------
Find a Knight's tour, via Warnsdorff's rule.
For very old or 'Heirloom' m4, you may need to increase the sizes of
internal structures, with, say,
m4 -S 1000 -B 100000 knights_tour.m4
But I would use one of OpenBSD m4, GNU m4, etc., instead.
----------------------------------------------------------------------
dnl Get a random number from 0 to one less than $1.
dnl (Note that this is not a very good RNG. Also it writes a file.)
define(`randnum',
`syscmd(`echo $RANDOM > __random_number__')eval(include(__random_number__) % ( $1 ))')
dnl The left deconstructors for strings.
define(`string_car',`substr($1,0,1)')
define(`string_cdr',`substr($1,1)')
dnl Algebraic notation to 'i0j0', with i the ranks and j the files. Bad
dnl algebraic notation gets tranformed to '99999999'.
define(`alg2ij',
`ifelse($1,`a1',`1010',$1,`a2',`2010',$1,`a3',`3010',$1,`a4',`4010',
$1,`a5',`5010',$1,`a6',`6010',$1,`a7',`7010',$1,`a8',`8010',
$1,`b1',`1020',$1,`b2',`2020',$1,`b3',`3020',$1,`b4',`4020',
$1,`b5',`5020',$1,`b6',`6020',$1,`b7',`7020',$1,`b8',`8020',
$1,`c1',`1030',$1,`c2',`2030',$1,`c3',`3030',$1,`c4',`4030',
$1,`c5',`5030',$1,`c6',`6030',$1,`c7',`7030',$1,`c8',`8030',
$1,`d1',`1040',$1,`d2',`2040',$1,`d3',`3040',$1,`d4',`4040',
$1,`d5',`5040',$1,`d6',`6040',$1,`d7',`7040',$1,`d8',`8040',
$1,`e1',`1050',$1,`e2',`2050',$1,`e3',`3050',$1,`e4',`4050',
$1,`e5',`5050',$1,`e6',`6050',$1,`e7',`7050',$1,`e8',`8050',
$1,`f1',`1060',$1,`f2',`2060',$1,`f3',`3060',$1,`f4',`4060',
$1,`f5',`5060',$1,`f6',`6060',$1,`f7',`7060',$1,`f8',`8060',
$1,`g1',`1070',$1,`g2',`2070',$1,`g3',`3070',$1,`g4',`4070',
$1,`g5',`5070',$1,`g6',`6070',$1,`g7',`7070',$1,`g8',`8070',
$1,`h1',`1080',$1,`h2',`2080',$1,`h3',`3080',$1,`h4',`4080',
$1,`h5',`5080',$1,`h6',`6080',$1,`h7',`7080',$1,`h8',`8080',
`99999999')')
dnl The reverse of alg2ij. Bad 'i0j0' get transformed to 'z0'.
define(`ij2alg',
`ifelse($1,`1010',`a1',$1,`2010',`a2',$1,`3010',`a3',$1,`4010',`a4',
$1,`5010',`a5',$1,`6010',`a6',$1,`7010',`a7',$1,`8010',`a8',
$1,`1020',`b1',$1,`2020',`b2',$1,`3020',`b3',$1,`4020',`b4',
$1,`5020',`b5',$1,`6020',`b6',$1,`7020',`b7',$1,`8020',`b8',
$1,`1030',`c1',$1,`2030',`c2',$1,`3030',`c3',$1,`4030',`c4',
$1,`5030',`c5',$1,`6030',`c6',$1,`7030',`c7',$1,`8030',`c8',
$1,`1040',`d1',$1,`2040',`d2',$1,`3040',`d3',$1,`4040',`d4',
$1,`5040',`d5',$1,`6040',`d6',$1,`7040',`d7',$1,`8040',`d8',
$1,`1050',`e1',$1,`2050',`e2',$1,`3050',`e3',$1,`4050',`e4',
$1,`5050',`e5',$1,`6050',`e6',$1,`7050',`e7',$1,`8050',`e8',
$1,`1060',`f1',$1,`2060',`f2',$1,`3060',`f3',$1,`4060',`f4',
$1,`5060',`f5',$1,`6060',`f6',$1,`7060',`f7',$1,`8060',`f8',
$1,`1070',`g1',$1,`2070',`g2',$1,`3070',`g3',$1,`4070',`g4',
$1,`5070',`g5',$1,`6070',`g6',$1,`7070',`g7',$1,`8070',`g8',
$1,`1080',`h1',$1,`2080',`h2',$1,`3080',`h3',$1,`4080',`h4',
$1,`5080',`h5',$1,`6080',`h6',$1,`7080',`h7',$1,`8080',`h8',
`z0')')
dnl Move a knight from one square to another by an ij-vector. Both input
dnl and output are algebraic notation. If the move is illegal, it comes
dnl out as 'z0'.
define(`move_by',`ij2alg(eval(alg2ij($3) + 1000 * ( $1 ) + 10 * ( $2 )))')
dnl For example, a1d3c5 -> 3
define(`path_length',`eval(len($1) / 2)')
dnl The left deconstructors for paths.
define(`path_car',`substr($1,0,2)')
define(`path_cdr',`substr($1,2)')
dnl The right deconstructors for paths.
define(`path_last',`substr($1,eval(len($1) - 2))')
define(`path_drop_last',`substr($1,0,eval(len($1) - 2))')
dnl Extract the nth position from the path.
define(`path_nth',`substr($1,eval(( $2 ) * 2),2)')
define(`random_move',`path_nth($1,randnum(path_length($1)))')
dnl Is the position $1 contained in the path $2?
define(`path_contains',`ifelse(index($2,$1),-1,0,1)')
dnl Find all moves from position $1 that are not already in
dnl the path $2.
define(`possible_moves',
`ifelse(path_contains(move_by(1,2,$1),$2`'z0),`0',move_by(1,2,$1))`'dnl
ifelse(path_contains(move_by(2,1,$1),$2`'z0),`0',move_by(2,1,$1))`'dnl
ifelse(path_contains(move_by(1,-2,$1),$2`'z0),`0',move_by(1,-2,$1))`'dnl
ifelse(path_contains(move_by(2,-1,$1),$2`'z0),`0',move_by(2,-1,$1))`'dnl
ifelse(path_contains(move_by(-1,2,$1),$2`'z0),`0',move_by(-1,2,$1))`'dnl
ifelse(path_contains(move_by(-2,1,$1),$2`'z0),`0',move_by(-2,1,$1))`'dnl
ifelse(path_contains(move_by(-1,-2,$1),$2`'z0),`0',move_by(-1,-2,$1))`'dnl
ifelse(path_contains(move_by(-2,-1,$1),$2`'z0),`0',move_by(-2,-1,$1))')
dnl Count how many moves can follow each move in $1.
define(`follows_counts',
`ifelse($1,`',`',
`path_length(possible_moves(path_car($1),$2))`'follows_counts(path_cdr($1),$2)')')
dnl Find the smallest positive digit, or zero.
define(`min_positive',
`ifelse($1,`',0,
`pushdef(`min1',min_positive(string_cdr($1)))`'dnl
pushdef(`val1',string_car($1))`'dnl
ifelse(min1,0,val1,
val1,0,min1,
eval(val1 < min1),1,val1,min1)`'dnl
popdef(`min1',`val1')')')
dnl Change everything to zero that is not the minimum positive.
define(`apply_warnsdorff',`_$0(min_positive($1),$1)')
define(`_apply_warnsdorff',
`ifelse($2,`',`',`ifelse(string_car($2),$1,$1,0)`'$0($1,string_cdr($2))')')
dnl Find potential next moves that satisfy Warnsdorff's rule.
define(`warnsdorff_moves',
`pushdef(`moves',`possible_moves($1,$2)')`'dnl
pushdef(`selections',`apply_warnsdorff(follows_counts(moves))')`'dnl
_$0(moves,selections)`'dnl
popdef(`moves',`selections')')
define(`_warnsdorff_moves',
`ifelse($1,`',`',
`ifelse(string_car($2),0,`$0(path_cdr($1),string_cdr($2))',
`path_car($1)`'$0(path_cdr($1),string_cdr($2))')')')
dnl Find potential next moves for the given path.
define(`next_moves',
`ifelse(path_length($1),63,`possible_moves(path_last($1),$1)',
`warnsdorff_moves(path_last($1),$1)')')
define(`find_tour',
`ifelse($2,`',`find_tour($1,$1)',
path_length($2),64,$2,
`pushdef(`moves',next_moves($2))`'dnl
ifelse(moves,`',`find_tour($1)',
`find_tour($1,$2`'random_move(next_moves($2)))')`'dnl
popdef(`moves')')')
divert`'dnl
dnl
find_tour(a1)
find_tour(c5)
find_tour(h8)</syntaxhighlight>
{{out}}
This is just a sample. Outputs are random.
$ m4 knights_tour.m4
<pre>a1c2a3b1d2f1h2g4h6g8e7c8a7b5c7a8b6a4b2d1f2h1g3h5g7e8f6h7f8d7b8a6b4a2c1e2g1h3g5f7h8g6h4g2e1d3c5b7d8e6f4d5c3e4d6f5e3c4a5b3d4c6e5f3
c5b7d8f7h8g6h4g2e1c2a1b3c1a2b4a6b8d7f8h7g5h3g1e2g3h1f2d1b2a4b6a8c7e8g7h5f6g8h6g4h2f1d2b1a3b5a7c8e7d5c3e4d6f5e3c4a5c6d4e6f4d3e5f3
h8g6f8h7g5h3g1e2c1a2b4a6b8d7b6a8c7e8g7h5g3h1f2d1b2a4c5b7a5b3a1c2e1g2h4f3h2f1d2b1a3b5a7c8e7g8h6f7d8e6f4d3e5g4f6d5c3e4d6c4e3f5d4c6</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
'''Solution'''
<syntaxhighlight lang="mathematica">knightsTourMoves[start_] :=
Module[{
vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64], knightsGraph,
Line 4,840 ⟶ 8,159:
hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]];
end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]];
FindShortestPath[g, start, end]]</syntaxhighlight>
'''Usage'''
<syntaxhighlight lang="mathematica">knightsTourMoves["d8"]
(* out *)
Line 4,851 ⟶ 8,168:
"c7", "a8", "b6", "c8", "d6", "e4", "d2", "f1", "e3", "d1", "f2", "h1", "g3", "e2", "c1", "d3", "e1", "g2", "h4", "f5", "e7", "d5", \
"f4", "h5", "g7", "e8", "f6", "g8", "h6", "g4", "h2", "f3", "g1", "h3", "g5", "h7", "f8", "d7", "e5", "g6", "h8", "f7"}
</syntaxhighlight>
'''Analysis'''
'''vertexLabels''' replaces the default vertex (i.e. square) names of the chessboard with the standard algebraic names "a1", "a2",...,"h8".
<syntaxhighlight lang="mathematica">
vertexLabels = (# -> ToString@c[[Quotient[# - 1, 8] + 1]] <> ToString[Mod[# - 1, 8] + 1]) & /@ Range[64]
Line 4,867 ⟶ 8,184:
41 -> "f1", 42 -> "f2", 43 -> "f3", 44 -> "f4", 45 -> "f5", 46 -> "f6", 47 -> "f7", 48 -> "f8",
49 -> "g1", 50 -> "g2", 51 -> "g3", 52 -> "g4", 53 -> "g5", 54 -> "g6",55 -> "g7", 56 -> "g8",
57 -> "h1", 58 -> "h2", 59 -> "h3", 60 -> "h4", 61 -> "h5", 62 -> "h6", 63 -> "h7", 64 -> "h8"}</syntaxhighlight>
'''knightsGraph''' creates a graph of the solution space.
<syntaxhighlight lang="mathematica">knightsGraph = KnightTourGraph[i, i, VertexLabels -> vertexLabels, ImagePadding -> 15];</syntaxhighlight>
[[File:KnightsTour-3.png]]
Find a Hamiltonian cycle (a path that visits each square exactly one time.)
<syntaxhighlight lang="mathematica">hamiltonianCycle = ((FindHamiltonianCycle[knightsGraph] /. UndirectedEdge -> DirectedEdge) /. labels)[[1]];</syntaxhighlight>
Find the end square:
<syntaxhighlight lang="mathematica">end = Cases[hamiltonianCycle, (x_ \[DirectedEdge] start) :> x][[1]];</syntaxhighlight>
Find shortest path from the start square to the end square.
<syntaxhighlight lang="mathematica">FindShortestPath[g, start, end]]</syntaxhighlight>
=={{header|Mathprog}}==
Line 4,902 ⟶ 8,209:
2. It is possible to specify which square is used for any Knights Move.
<syntaxhighlight lang="text">
/*Knights.mathprog
Line 4,964 ⟶ 8,271:
end;
</syntaxhighlight>
Produces:
<syntaxhighlight lang="text">
GLPSOL: GLPK LP/MIP Solver, v4.47
Parameter(s) specified in the command line:
Line 5,014 ⟶ 8,321:
23 10 21 16 25
Model has been successfully processed
</syntaxhighlight>
and
<syntaxhighlight lang="text">
/*Knights.mathprog
Line 5,083 ⟶ 8,390:
end;
</syntaxhighlight>
Produces:
<syntaxhighlight lang="text">
GLPSOL: GLPK LP/MIP Solver, v4.47
Parameter(s) specified in the command line:
Line 5,152 ⟶ 8,459:
10 55 20 57 12 37 40 1
Model has been successfully processed
</syntaxhighlight>
=={{header|Nim}}==
{{trans|C++}}
This is a translation of the C++ and D versions with some changes, the most important being the addition of a check to detect that there is no solution. Without this check, the program crashes with an IndexError as Nim in debug and in release modes generates code to insure that indexes are valid.
We have added a case to test the absence of solution. Note that, in this case, there is a lot of backtracking which considerably slows down the execution.
<syntaxhighlight lang="nim">import algorithm, options, random, parseutils, strutils, strformat
type
Board[N: static Positive] = array[N, array[N, int]]
Move = tuple[x, y: int]
MoveList = array[8, Move]
MoveIndexes = array[8, int]
const Moves: MoveList = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
proc `$`(board: Board): string =
## Display the board.
let size = len($(board.N * board.N)) + 1
for row in board:
for val in row:
stdout.write ($val).align(size)
echo ""
proc sortedMoves(board: Board; x, y: int): MoveIndexes =
## Return the list of moves sorted by count of possible moves.
var counts: array[8, tuple[value, index: int]]
for i, d1 in Moves:
var count = 0
for d2 in Moves:
let x2 = x + d1.x + d2.x
let y2 = y + d1.y + d2.y
if x2 in 0..<board.N and y2 in 0..<board.N and board[y2][x2] == 0:
inc count
counts[i] = (count, i)
counts.shuffle() # Shuffle to randomly break ties.
counts.sort() # Lexicographic sort.
for i, count in counts:
result[i] = count.index
proc knightTour[N: static Positive](start: string): Option[Board[N]] =
## Return the knight tour for a board of size N x N and the starting
## position "start.
## If no solution is found, return "node" else return "some".
# Initialize the board with the starting position.
var board: Board[N]
var startx, starty: int
startx = ord(start[0]) - ord('a')
if startx notin 0..<N:
raise newException(ValueError, "wrong column.")
if parseInt(start, starty, 1) != start.len - 1 or starty notin 1..N:
raise newException(ValueError, "wrong line.")
starty = N - starty
board[starty][startx] = 1
type OrderItem = tuple[x, y, idx: int; mi: MoveIndexes]
var order: array[N * N, OrderItem]
order[0] = (startx, starty, 0, board.sortedMoves(startx, starty))
# Search a tour.
var n = 0
while n < N * N - 1:
let x = order[n].x
let y = order[n].y
var ok = false
for i in order[n].idx..7:
let d = Moves[order[n].mi[i]]
if x + d.x notin 0..<N or y + d.y notin 0..<N: continue
if board[y + d.y][x + d.x] == 0:
order[n].idx = i + 1
inc n
board[y + d.y][x + d.x] = n + 1
order[n] = (x + d.x, y + d.y, 0, board.sortedMoves(x + d.x, y + d.y))
ok = true
break
if not ok:
# Failed: backtrack.
echo "backtrack"
board[y][x] = 0
dec n
if n < 0: return none(Board[N]) # No solution found.
result = some(board)
proc run[N: static Positive](start: string) =
## Run the algorithm and display the result.
let result = knightTour[N](start)
echo &"Board size: {N}x{N}, starting position: {start}."
if result.isSome(): echo result.get()
else: echo "No solution found.\n"
when isMainModule:
randomize()
run[5]("c3")
#run[5]("c4") # No solution, so very slow compared to other cases.
run[8]("b5")
run[31]("a1")</syntaxhighlight>
{{out}}
<pre>Board size: 5x5, starting position: c3.
23 16 11 6 21
10 5 22 17 12
15 24 1 20 7
4 9 18 13 2
25 14 3 8 19
Board size: 5x5, starting position: c4.
No solution found.
Board size: 8x8, starting position: b5.
63 20 3 24 59 36 5 26
2 23 64 37 4 25 58 35
19 62 21 50 55 60 27 6
22 1 54 61 38 45 34 57
53 18 49 44 51 56 7 28
12 15 52 39 46 31 42 33
17 48 13 10 43 40 29 8
14 11 16 47 30 9 32 41
Board size: 31x31, starting position: a1.
275 112 19 116 277 604 21 118 823 770 23 120 961 940 25 122 943 926 27 124 917 898 29 126 911 872 31 128 197 870 33
18 115 276 601 20 117 772 767 22 119 958 851 24 121 954 941 26 123 936 925 28 125 912 899 30 127 910 871 32 129 198
111 274 113 278 605 760 603 822 771 824 769 948 957 960 939 944 953 942 927 916 929 918 897 908 913 900 873 196 875 34 869
114 17 600 273 602 775 766 773 768 949 850 959 852 947 952 955 932 937 930 935 924 915 920 905 894 909 882 901 868 199 130
271 110 279 606 759 610 761 776 821 764 825 816 951 956 853 938 945 934 923 928 919 896 893 914 907 904 867 874 195 876 35
16 581 272 599 280 607 774 765 762 779 950 849 826 815 946 933 854 931 844 857 890 921 906 895 886 883 902 881 200 131 194
109 270 281 580 609 758 611 744 777 820 763 780 817 848 827 808 811 846 855 922 843 858 889 892 903 866 885 192 877 36 201
282 15 582 269 598 579 608 757 688 745 778 819 754 783 814 847 828 807 810 845 856 891 842 859 884 887 880 863 202 193 132
267 108 283 578 583 612 689 614 743 756 691 746 781 818 753 784 809 812 829 806 801 840 835 888 865 862 203 878 191 530 37
14 569 268 585 284 597 576 619 690 687 742 755 692 747 782 813 752 785 802 793 830 805 860 841 836 879 864 529 204 133 190
107 266 285 570 577 584 613 686 615 620 695 684 741 732 711 748 739 794 751 786 803 800 839 834 861 528 837 188 531 38 205
286 13 568 265 586 575 596 591 618 685 616 655 696 693 740 733 712 749 738 795 792 831 804 799 838 833 722 527 206 189 134
263 106 287 508 571 590 587 574 621 592 639 694 683 656 731 710 715 734 787 750 737 796 791 832 721 798 207 532 187 474 39
12 417 264 567 288 509 572 595 588 617 654 657 640 697 680 713 730 709 716 735 788 727 720 797 790 723 526 473 208 135 186
105 262 289 416 507 566 589 512 573 622 593 638 653 682 659 698 679 714 729 708 717 736 789 726 719 472 533 184 475 40 209
290 11 418 261 502 415 510 565 594 513 562 641 658 637 652 681 660 699 678 669 728 707 718 675 724 525 704 471 210 185 136
259 104 291 414 419 506 503 514 511 564 623 548 561 642 551 636 651 670 661 700 677 674 725 706 703 534 211 476 183 396 41
10 331 260 493 292 501 420 495 504 515 498 563 624 549 560 643 662 635 650 671 668 701 676 673 524 705 470 395 212 137 182
103 258 293 330 413 494 505 500 455 496 547 516 485 552 625 550 559 644 663 634 649 672 667 702 535 394 477 180 397 42 213
294 9 332 257 492 329 456 421 490 499 458 497 546 517 484 553 626 543 558 645 664 633 648 523 666 469 536 393 220 181 138
255 102 295 328 333 412 491 438 457 454 489 440 459 486 545 518 483 554 627 542 557 646 665 632 537 478 221 398 179 214 43
8 319 256 335 296 345 326 409 422 439 436 453 488 441 460 451 544 519 482 555 628 541 522 647 468 631 392 219 222 139 178
101 254 297 320 327 334 411 346 437 408 423 368 435 452 487 442 461 450 445 520 481 556 629 538 479 466 399 176 215 44 165
298 7 318 253 336 325 344 349 410 347 360 407 424 383 434 427 446 443 462 449 540 521 480 467 630 391 218 223 164 177 140
251 100 303 300 321 316 337 324 343 350 369 382 367 406 425 384 433 428 447 444 463 430 539 390 465 400 175 216 169 166 45
6 299 252 317 304 301 322 315 348 361 342 359 370 381 366 405 426 385 432 429 448 389 464 401 174 217 224 163 150 141 168
99 250 241 302 235 248 307 338 323 314 351 362 341 358 371 380 365 404 377 386 431 402 173 388 225 160 153 170 167 46 143
240 5 98 249 242 305 234 247 308 339 232 313 352 363 230 357 372 379 228 403 376 387 226 159 154 171 162 149 142 151 82
63 2 239 66 97 236 243 306 233 246 309 340 231 312 353 364 229 356 373 378 227 158 375 172 161 148 155 152 83 144 47
4 67 64 61 238 69 96 59 244 71 94 57 310 73 92 55 354 75 90 53 374 77 88 51 156 79 86 49 146 81 84
1 62 3 68 65 60 237 70 95 58 245 72 93 56 311 74 91 54 355 76 89 52 157 78 87 50 147 80 85 48 145</pre>
=={{header|ObjectIcon}}==
{{trans|ATS}}
<syntaxhighlight lang="objecticon">#
# Find Knight’s Tours.
#
# Using Warnsdorff’s heuristic, find multiple solutions.
#
# Based on my ATS/Postiats program.
#
# The main difference from the ATS is this program uses a
# co-expression pair to make a generator of solutions, whereas the ATS
# simply prints solutions where they are found.
#
# Usage: ./knights_tour [START_POSITION [MAX_TOURS [closed]]]
# Examples:
# ./knights_tour (prints one tour starting from a1)
# ./knights_tour c5
# ./knights_tour c5 2000
# ./knights_tour c5 2000 closed
#
$define DEFAULT_NUMBER_OF_RANKS 8
$define DEFAULT_NUMBER_OF_FILES 8
import io
procedure main(args)
local f_out
local tours
local tour_board
local n_tour
local starting_position
local i, j
local max_tours
local closed_only
starting_position := \algebraic_notation_to_i_j(args[1]) | [1, 1]
i := starting_position[1]
j := starting_position[2]
max_tours := integer(args[2]) | 1
closed_only := if \args[3] === "closed" then &yes else &no
f_out := FileStream.stdout
tours := KnightsTours()
n_tour := 0
if n_tour < max_tours then
every tour_board := tours.generate(i, j, closed_only) do
{
n_tour +:= 1
write("Tour number ", n_tour)
f_out.write(tour_board.make_moves_display())
f_out.write(tour_board.make_board_display())
f_out.write()
if max_tours <= n_tour then
break
}
end
procedure algebraic_notation_to_i_j(s)
return [integer(s[2]), ord(s[1]) - ord('a') + 1]
end
class Move()
public const i
public const j
public new(rank, file)
i := rank
j := file
return
end
public make_display(n_ranks)
return char(ord('a') + j - 1) || i
end
end
class Chessboard()
public const n_ranks
public const n_files
public const n_squares
private board
public new(num_ranks, num_files)
/num_ranks := DEFAULT_NUMBER_OF_RANKS
/num_files := DEFAULT_NUMBER_OF_FILES
n_files := num_files
n_ranks := num_ranks
n_squares := n_ranks * n_files
board := list(n_squares)
return
end
public copy()
local new_board
local i
new_board := Chessboard(n_files, n_ranks)
every i := 1 to n_squares do
new_board.board[i] := board[i]
return new_board
end
public square(i, j)
# The board is stored in column-major order.
return board[i + (n_ranks * (j - 1))]
end
public try(i, j, value)
# Backtracking assignment. Though we use it for ordinary
# assignment.
#
# The board is stored in column-major order.
suspend board[i + (n_ranks * (j - 1))] <- value
end
public make_board_display()
local s
local i, j
s := ""
every i := n_ranks to 1 by -1 do
{
s ||:= " "
every j := 1 to n_files do
s ||:= "+----"
s ||:= "+\n"
s ||:= right(i, 2) || " "
every j := 1 to n_files do
s ||:= " | " || (\right(square(i, j), 2))
s ||:= " |\n"
}
s ||:= " "
every j := 1 to n_files do
s ||:= "+----"
s ||:= "+\n"
s ||:= " "
every j := 1 to n_files do
s ||:= " " || char(ord('a') + j - 1)
return s
end
public make_moves_display()
local positions
local i, j
local s
local first_position, last_position
positions := list(n_squares)
every i := 1 to n_ranks do
every j := 1 to n_files do
positions[square(i, j)] := Move(i, j)
s := ""
every j := 1 to n_squares - 1 do
{
s ||:= positions[j].make_display()
s ||:= (if j % n_files = 0 then " ->\n" else " -> ")
}
s ||:= positions[n_squares].make_display()
first_position := find_nth_position(1)
last_position := find_nth_position(n_squares)
if knight_positions_are_attacking(first_position.i,
first_position.j,
last_position.i,
last_position.j) then
s ||:= " -> cycle"
return s
end
public find_nth_position(n)
local i, j
local position
position := &null
i := 1
while /position & i <= n_ranks do
{
j := 1
while /position & j <= n_files do
{
if square(i, j) = n then
position := Move(i, j)
j +:= 1
}
i +:= 1
}
return position
end
end
class KnightsTours()
public const n_ranks
public const n_files
public const n_squares
private board
public new(num_ranks, num_files, i, j, closed_only)
board := Chessboard(num_ranks, num_files)
n_ranks := board.n_ranks
n_files := board.n_files
n_squares := board.n_squares
return
end
public generate(i, j, closed_only)
# i,j = starting position.
local consumer
local explorer
local tour_board
# Simple coroutines. The consumer receives complete tours (each in
# the form of a Chessboard) from the explorer.
consumer := ¤t
explorer := create explore(consumer, i, j, 1,
closed_only, i, j)
while tour_board := @explorer do
suspend tour_board
end
private explore(consumer, i, j, n_position,
closed_only, i_start, j_start)
# i,j = starting position.
board.try(i, j, n_position)
explore_inner(consumer, i, j, n_position,
closed_only, i_start, j_start)
board.try(i, j, &null)
end
private explore_inner(consumer, i, j, n_position,
closed_only, i_start, j_start)
local moves, mv
if n_squares - n_position = 1 then
{
# Is the last move possible? If so, make it and output the
# board. (Only zero or one of the moves can be non-null.)
moves := possible_moves(i, j)
every try_last_move(consumer, moves[1 to 8],
closed_only, i_start, j_start)
}
else
{
moves := next_moves(i, j, n_position)
every mv := !moves do
if \mv then
explore(consumer, mv.i, mv.j, n_position + 1,
closed_only, i_start, j_start)
}
end
private try_last_move(consumer, move, closed_only, i_start, j_start)
if \move then
if (/closed_only |
knight_positions_are_attacking(move.i, move.j,
i_start, j_start)) then
{
board.try(move.i, move.j, n_squares)
(board.copy())@consumer
board.try(move.i, move.j, &null)
}
end
private next_moves(i, j, n_position)
local moves
local w_list, w
local k
moves := possible_moves(i, j)
w_list := list(8)
every k := 1 to 8 do
w_list[k] := count_following_moves(moves[k], n_position)
w := pick_w(w_list)
if w = 0 then
# A dead end.
moves := list(8, &null)
else
# w is least positive number of following moves. Nullify any
# move that has either zero following moves (it is a dead end)
# or more than w following moves (it violates Warnsdorff’s
# heuristic).
every k := 1 to 8 do
if w_list[k] ~= w then
moves[k] := &null
return moves
end
private count_following_moves(move, n_position)
local w
local following_moves
w := 0
if \move then
{
board.try(move.i, move.j, n_position + 1)
following_moves := possible_moves(move.i, move.j)
every ( \following_moves[1 to 8] & w +:= 1 )
board.try(move.i, move.j, &null)
}
return w
end
private pick_w(w_list)
local w
w := 0
every w := next_pick (w, w_list[1 to 8])
return w
end
private next_pick(u, v)
local w
if v = 0 then
w := u
else if u = 0 then
w := v
else
w := min (u, v)
return w
end
private possible_moves(i, j)
local move1, move2, move3, move4
local move5, move6, move7, move8
move1 := try_move(i + 1, j + 2)
move2 := try_move(i + 2, j + 1)
move3 := try_move(i + 1, j - 2)
move4 := try_move(i + 2, j - 1)
move5 := try_move(i - 1, j + 2)
move6 := try_move(i - 2, j + 1)
move7 := try_move(i - 1, j - 2)
move8 := try_move(i - 2, j - 1)
return [move1, move2, move3, move4,
move5, move6, move7, move8]
end
private try_move(i1, j1)
return (1 <= i1 <= n_ranks &
1 <= j1 <= n_files &
/board.square(i1, j1) &
Move(i1, j1)) | &null
end
end
procedure knight_positions_are_attacking(i1, j1, i2, j2)
local i_diff, j_diff
i_diff := abs(i1 - i2)
j_diff := abs(j1 - j2)
return (((i_diff = 2 & j_diff = 1) |
(i_diff = 1 & j_diff = 2)) & &yes) | fail
end</syntaxhighlight>
{{out}}
$ ./knights_tour c5 2 closed
<pre>Tour number 1
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> e8 -> d6 -> b5 -> d4 -> f5 -> g7 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 58 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 63 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 60 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 61 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
Tour number 2
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> b5 -> d6 -> e8 -> g7 -> f5 -> d4 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 60 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 61 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 58 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 63 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
</pre>
=={{header|Perl}}==
Knight's tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]
<
use warnings;
# Find a knight's tour
Line 5,242 ⟶ 9,137:
return unless $square =~ /^([a-h])([1-8])$/;
return (8-$2, ord($1) - ord('a'));
}</
Sample output (start square c3):
Line 5,250 ⟶ 9,145:
=={{header|Phix}}==
This is pretty fast (<<1s) up to size 48, before some sizes start to take quite some time to complete. It will even solve a 200x200 in 0.67s
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">size</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</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: #000080;font-style:italic;">-- to simplify output, each square is nchars</span>
<span style="color: #004080;">sequence</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: #000080;font-style:italic;">-- keep current counts, immediately backtrack if any hit 0
-- (in line with the above, we only use every nth entry)</span>
<span style="color: #004080;">sequence</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: #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: #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: #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;">size</span><span style="color: #0000FF;">*</span><span style="color: #000000;">size</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;">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: #000000;">init_warnsdorffs</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'1'</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nchars</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nsolution found in %d tries (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"no solutions found\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 5,348 ⟶ 9,243:
50 27 12 35 64 25 10 7
solution found in 64 tries (0.00s)
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">import cp.
main =>
N = 8,
A = new_array(N,N),
foreach (R in 1..N, C in 1..N)
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)],
A[R,C] :: [(R1-1)*N+C1 : (R1,C1) in Connected, R1 >= 1, R1 =< N, C1 >= 1, C1 =< N]
end,
V = vars(A),
circuit(V),
solve([ff],V),
OutputM = new_array(N,N),
fill_output_matrix(N,OutputM,V,1,1),
foreach (R in 1..N)
foreach (C in 1..N)
printf("%3d ", OutputM[R,C])
end,
nl
end.
fill_output_matrix(N,OutputM,V,I,Count) =>
if Count =< N*N then
R = (I-1) div N + 1,
C = (I-1) mod N + 1,
OutputM[R,C] = Count,
fill_output_matrix(N,OutputM,V,V[I],Count+1)
end.
</syntaxhighlight>
{{out}}
<pre>
1 62 5 10 13 24 55 8
4 11 2 63 6 9 14 23
61 64 35 12 25 56 7 54
34 3 26 59 36 15 22 57
39 60 37 18 27 58 53 16
30 33 40 43 46 17 50 21
41 38 31 28 19 48 45 52
32 29 42 47 44 51 20 49
</pre>
=={{header|PicoLisp}}==
<
# Build board
Line 5,380 ⟶ 9,325:
(moves Tour) )
(push 'Tour @) )
(flip Tour) )</
Output:
<pre>-> (b1 a3 b5 a7 c8 b6 a8 c7 a6 b8 d7 f8 h7 g5 h3 g1 e2 c1 a2 b4 c2 a1 b3 a5 b7
Line 5,388 ⟶ 9,333:
=={{header|PostScript}}==
You probably shouldn't send this to a printer. Solution using Warnsdorffs algorithm.
<
%%BoundingBox: 0 0 300 300
Line 5,497 ⟶ 9,442:
3 1 100 { solve } for
%%EOF</
=={{header|Prolog}}==
Line 5,503 ⟶ 9,448:
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]
<
knight(N) :-
Max is N * N,
Line 5,583 ⟶ 9,528:
M1 is M + 1,
display(N, M1, T).
</syntaxhighlight>
Output :
Line 5,622 ⟶ 9,567:
===Alternative version===
{{Works with|GNU Prolog}}
<
Line 5,678 ⟶ 9,623:
main :- make_graph, hamiltonian(5*3,Pn), show_path(Pn), halt.</
{{Output}}
<pre> 5 18 35 22 3 16 55 24
Line 5,692 ⟶ 9,637:
=={{header|Python}}==
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]
<
boardsize=6
Line 5,756 ⟶ 9,701:
start = input('Start position: ')
board = knights_tour(start, boardsize)
print(boardstring(board, boardsize=boardsize))</
;Sample runs
Line 5,837 ⟶ 9,782:
Based on a slight modification of [[wp:Knight%27s_tour#Warnsdorff.27s_rule|Warnsdorff's algorithm]], in that if a dead-end is reached, the program backtracks to the next best move.
<
# M x N Chess Board.
Line 5,905 ⟶ 9,850:
# Begin tour.
setboard(position, 1); knightTour(position, 2)</
Output:
Line 5,923 ⟶ 9,868:
=={{header|Racket}}==
<
#lang racket
(define N 8)
Line 5,948 ⟶ 9,893:
" "))))
(draw (tour (random N) (random N)))
</syntaxhighlight>
{{out}}
<pre>
Line 5,964 ⟶ 9,909:
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku" line>my @board;
my $I = 8;
Line 5,988 ⟶ 9,932:
# Record current move
push @moves, to_algebraic($i,$j);
@board[$i][$j] = $move;
Line 6,038 ⟶ 9,981:
sub from_algebraic($square where /^ (<[a..z]>) (\d+) $/) {
$I - $1, ord(~$0) - ord('a');
}</
(Output identical to Perl's above.)
=={{Header|RATFOR}}==
{{trans|ATS}}
For use with the public domain ratfor77 translator and a FORTRAN 77 compiler.
<syntaxhighlight lang="ratfor">#-----------------------------------------------------------------------
#
# Find Knight’s Tours.
#
# Using Warnsdorff’s heuristic, find multiple solutions.
# Optionally accept only closed tours.
#
# This program is migrated from my implementation for ATS/Postiats.
# Arrays with dimension 1:64 take the place of stack frames.
#
# Compile with, for instance:
#
# ratfor77 knights_tour.r > knights_tour.f
# gfortran -O2 -g -std=legacy -o knights_tour knights_tour.f
#
# or
#
# ratfor77 knights_tour.r > knights_tour.f
# f2c knights_tour.f
# cc -O -o knights_tour knights_tour.c -lf2c
#
# Usage examples:
#
# One tour starting at a1, either open or closed:
#
# echo "a1 1 F" | ./knights_tour
#
# No more than 2000 closed tours starting at c5:
#
# echo "c5 2000 T" | ./knights_tour
#
#-----------------------------------------------------------------------
program ktour
implicit none
character*2 alg
integer i, j
integer mxtour
logical closed
read (*,*) alg, mxtour, closed
call alg2ij (alg, i, j)
call explor (i, j, mxtour, closed)
end
#-----------------------------------------------------------------------
subroutine explor (istart, jstart, mxtour, closed)
implicit none
# Explore the space of 'Warnsdorffian' knight’s paths, looking for
# and printing complete tours.
integer istart, jstart # The starting position.
integer mxtour # The maximum number of tours to print.
logical closed # Closed tours only?
integer board(1:8,1:8)
integer imove(1:8,1:64)
integer jmove(1:8,1:64)
integer nmove(1:64)
integer n
integer itours
logical goodmv
logical isclos
itours = 0
call initbd (board)
n = 1
nmove(1) = 8
imove(8, 1) = istart
jmove(8, 1) = jstart
while (itours < mxtour && n != 0) {
if (nmove(n) == 9) {
n = n - 1
if (n != 0) {
call unmove (board, imove, jmove, nmove, n)
nmove(n) = nmove(n) + 1
}
} else if (goodmv (imove, nmove, n)) {
call mkmove (board, imove, jmove, nmove, n)
if (n == 64) {
if (.not. closed) {
itours = itours + 1
call prnt (board, itours)
} else if (isclos (board)) {
itours = itours + 1
call prnt (board, itours)
}
call unmove (board, imove, jmove, nmove, n)
nmove(n) = 9
} else if (n == 63) {
call possib (board, n, imove, jmove, nmove)
n = n + 1
nmove(n) = 1
} else {
call nxtmov (board, n, imove, jmove, nmove)
n = n + 1
nmove(n) = 1
}
} else {
nmove(n) = nmove(n) + 1
}
}
end
#-----------------------------------------------------------------------
subroutine initbd (board)
implicit none
# Initialize a chessboard with empty squares.
integer board(1:8,1:8)
integer i, j
do j = 1, 8 {
do i = 1, 8 {
board(i, j) = -1
}
}
end
#-----------------------------------------------------------------------
subroutine mkmove (board, imove, jmove, nmove, n)
implicit none
# Fill a square with a move number.
integer board(1:8, 1:8)
integer imove(1:8, 1:64)
integer jmove(1:8, 1:64)
integer nmove(1:64)
integer n
board(imove(nmove(n), n), jmove(nmove(n), n)) = n
end
#-----------------------------------------------------------------------
subroutine unmove (board, imove, jmove, nmove, n)
implicit none
# Unmake a mkmove.
integer board(1:8, 1:8)
integer imove(1:8, 1:64)
integer jmove(1:8, 1:64)
integer nmove(1:64)
integer n
board(imove(nmove(n), n), jmove(nmove(n), n)) = -1
end
#-----------------------------------------------------------------------
function goodmv (imove, nmove, n)
implicit none
logical goodmv
integer imove(1:8, 1:64)
integer nmove(1:64)
integer n
goodmv = (imove(nmove(n), n) != -1)
end
#-----------------------------------------------------------------------
subroutine prnt (board, itours)
implicit none
# Print a knight's tour.
integer board(1:8,1:8)
integer itours
10000 format (1X)
# The following plethora of format statements seemed a simple way to
# get this working with f2c. (For gfortran, the 'I0' format
# sufficed.)
10010 format (1X, "Tour number ", I1)
10020 format (1X, "Tour number ", I2)
10030 format (1X, "Tour number ", I3)
10040 format (1X, "Tour number ", I4)
10050 format (1X, "Tour number ", I5)
10060 format (1X, "Tour number ", I6)
10070 format (1X, "Tour number ", I20)
if (itours < 10) {
write (*, 10010) itours
} else if (itours < 100) {
write (*, 10020) itours
} else if (itours < 1000) {
write (*, 10030) itours
} else if (itours < 10000) {
write (*, 10040) itours
} else if (itours < 100000) {
write (*, 10050) itours
} else if (itours < 1000000) {
write (*, 10060) itours
} else {
write (*, 10070) itours
}
call prntmv (board)
call prntbd (board)
write (*, 10000)
end
#-----------------------------------------------------------------------
subroutine prntbd (board)
implicit none
# Print a chessboard with the move number in each square.
integer board(1:8,1:8)
integer i, j
10000 format (1X, " ", 8("+----"), "+")
10010 format (1X, I2, " ", 8(" | ", I2), " | ")
10020 format (1X, " ", 8(" ", A1))
do i = 8, 1, -1 {
write (*, 10000)
write (*, 10010) i, (board(i, j), j = 1, 8)
}
write (*, 10000)
write (*, 10020) 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'
end
#-----------------------------------------------------------------------
subroutine prntmv (board)
implicit none
# Print the moves of a knight's path, in algebraic notation.
integer board(1:8,1:8)
integer ipos(1:64)
integer jpos(1:64)
integer numpos
character*2 alg(1:64)
integer columns(1:8)
integer k
integer m
character*72 lines(1:8)
10000 format (1X, A)
call bd2pos (board, ipos, jpos, numpos)
# Convert the positions to algebraic notation.
do k = 1, numpos {
call ij2alg (ipos(k), jpos(k), alg(k))
}
# Fill lines with algebraic notations.
do m = 1, 8 {
columns(m) = 1
}
m = 1
do k = 1, numpos {
lines(m)(columns(m) : columns(m) + 1) = alg(k)(1:2)
columns(m) = columns(m) + 2
if (k != numpos) {
lines(m)(columns(m) : columns(m) + 3) = " -> "
columns(m) = columns(m) + 4
} else if (numpos == 64 && _
((abs (ipos(numpos) - ipos(1)) == 2 _
&& abs (jpos(numpos) - jpos(1)) == 1) _
|| ((abs (ipos(numpos) - ipos(1)) == 1 _
&& abs (jpos(numpos) - jpos(1)) == 2)))) {
lines(m)(columns(m) : columns(m) + 8) = " -> cycle"
columns(m) = columns(m) + 9
}
if (mod (k, 8) == 0) m = m + 1
}
# Print the lines that have stuff in them.
do m = 1, 8 {
if (columns(m) != 1) {
write (*, 10000) lines(m)(1 : columns(m) - 1)
}
}
end
#-----------------------------------------------------------------------
function isclos (board)
implicit none
# Is a board a closed tour?
logical isclos
integer board(1:8,1:8)
integer ipos(1:64) # The i-positions in order.
integer jpos(1:64) # The j-positions in order.
integer numpos # The number of positions so far.
call bd2pos (board, ipos, jpos, numpos)
isclos = (numpos == 64 && _
((abs (ipos(numpos) - ipos(1)) == 2 _
&& abs (jpos(numpos) - jpos(1)) == 1) _
|| ((abs (ipos(numpos) - ipos(1)) == 1 _
&& abs (jpos(numpos) - jpos(1)) == 2))))
end
#-----------------------------------------------------------------------
subroutine bd2pos (board, ipos, jpos, numpos)
implicit none
# Convert from a board to a list of board positions.
integer board(1:8,1:8)
integer ipos(1:64) # The i-positions in order.
integer jpos(1:64) # The j-positions in order.
integer numpos # The number of positions so far.
integer i, j
numpos = 0
do i = 1, 8 {
do j = 1, 8 {
if (board(i, j) != -1) {
numpos = max (board(i, j), numpos)
ipos(board(i, j)) = i
jpos(board(i, j)) = j
}
}
}
end
#-----------------------------------------------------------------------
subroutine nxtmov (board, n, imove, jmove, nmove)
implicit none
# Find possible next moves. Prune and sort the moves according to
# Warnsdorff's heuristic, keeping only those that have the minimum
# number of legal following moves.
integer board(1:8,1:8)
integer n
integer imove(1:8,1:64)
integer jmove(1:8,1:64)
integer nmove(1:64)
integer w1, w2, w3, w4, w5, w6, w7, w8
integer w
integer n1
integer pickw
call possib (board, n, imove, jmove, nmove)
n1 = n + 1
nmove(n1) = 1
call countf (board, n1, imove, jmove, nmove, w1)
nmove(n1) = 2
call countf (board, n1, imove, jmove, nmove, w2)
nmove(n1) = 3
call countf (board, n1, imove, jmove, nmove, w3)
nmove(n1) = 4
call countf (board, n1, imove, jmove, nmove, w4)
nmove(n1) = 5
call countf (board, n1, imove, jmove, nmove, w5)
nmove(n1) = 6
call countf (board, n1, imove, jmove, nmove, w6)
nmove(n1) = 7
call countf (board, n1, imove, jmove, nmove, w7)
nmove(n1) = 8
call countf (board, n1, imove, jmove, nmove, w8)
w = pickw (w1, w2, w3, w4, w5, w6, w7, w8)
if (w == 0) {
call disabl (imove(1, n1), jmove(1, n1))
call disabl (imove(2, n1), jmove(2, n1))
call disabl (imove(3, n1), jmove(3, n1))
call disabl (imove(4, n1), jmove(4, n1))
call disabl (imove(5, n1), jmove(5, n1))
call disabl (imove(6, n1), jmove(6, n1))
call disabl (imove(7, n1), jmove(7, n1))
call disabl (imove(8, n1), jmove(8, n1))
} else {
if (w != w1) call disabl (imove(1, n1), jmove(1, n1))
if (w != w2) call disabl (imove(2, n1), jmove(2, n1))
if (w != w3) call disabl (imove(3, n1), jmove(3, n1))
if (w != w4) call disabl (imove(4, n1), jmove(4, n1))
if (w != w5) call disabl (imove(5, n1), jmove(5, n1))
if (w != w6) call disabl (imove(6, n1), jmove(6, n1))
if (w != w7) call disabl (imove(7, n1), jmove(7, n1))
if (w != w8) call disabl (imove(8, n1), jmove(8, n1))
}
end
#-----------------------------------------------------------------------
subroutine countf (board, n, imove, jmove, nmove, w)
implicit none
# Count the number of moves possible after an nth move.
integer board(1:8,1:8)
integer n
integer imove(1:8,1:64)
integer jmove(1:8,1:64)
integer nmove(1:64)
integer w
logical goodmv
integer n1
if (goodmv (imove, nmove, n)) {
call mkmove (board, imove, jmove, nmove, n)
call possib (board, n, imove, jmove, nmove)
n1 = n + 1
w = 0
if (imove(1, n1) != -1) w = w + 1
if (imove(2, n1) != -1) w = w + 1
if (imove(3, n1) != -1) w = w + 1
if (imove(4, n1) != -1) w = w + 1
if (imove(5, n1) != -1) w = w + 1
if (imove(6, n1) != -1) w = w + 1
if (imove(7, n1) != -1) w = w + 1
if (imove(8, n1) != -1) w = w + 1
call unmove (board, imove, jmove, nmove, n)
} else {
# The nth move itself is impossible.
w = 0
}
end
#-----------------------------------------------------------------------
function pickw (w1, w2, w3, w4, w5, w6, w7, w8)
implicit none
# From w1..w8, pick out the least nonzero value (or zero if they all
# equal zero).
integer pickw
integer w1, w2, w3, w4, w5, w6, w7, w8
integer w
integer pickw1
w = 0
w = pickw1 (w, w1)
w = pickw1 (w, w2)
w = pickw1 (w, w3)
w = pickw1 (w, w4)
w = pickw1 (w, w5)
w = pickw1 (w, w6)
w = pickw1 (w, w7)
w = pickw1 (w, w8)
pickw = w
end
#-----------------------------------------------------------------------
function pickw1 (u, v)
implicit none
# A small function used by pickw.
integer pickw1
integer u, v
if (v == 0) {
pickw1 = u
} else if (u == 0) {
pickw1 = v
} else {
pickw1 = min (u, v)
}
end
#-----------------------------------------------------------------------
subroutine possib (board, n, imove, jmove, nmove)
implicit none
# Find moves that are possible from an nth-move position.
integer board(1:8,1:8)
integer n
integer imove(1:8,1:64)
integer jmove(1:8,1:64)
integer nmove(1:64)
integer i, j
integer n1
i = imove(nmove(n), n)
j = jmove(nmove(n), n)
n1 = n + 1
call trymov (board, i + 1, j + 2, imove(1, n1), jmove(1, n1))
call trymov (board, i + 2, j + 1, imove(2, n1), jmove(2, n1))
call trymov (board, i + 1, j - 2, imove(3, n1), jmove(3, n1))
call trymov (board, i + 2, j - 1, imove(4, n1), jmove(4, n1))
call trymov (board, i - 1, j + 2, imove(5, n1), jmove(5, n1))
call trymov (board, i - 2, j + 1, imove(6, n1), jmove(6, n1))
call trymov (board, i - 1, j - 2, imove(7, n1), jmove(7, n1))
call trymov (board, i - 2, j - 1, imove(8, n1), jmove(8, n1))
end
#-----------------------------------------------------------------------
subroutine trymov (board, i, j, imove, jmove)
implicit none
# Try a move to square (i, j).
integer board(1:8,1:8)
integer i, j
integer imove, jmove
call disabl (imove, jmove)
if (1 <= i && i <= 8 && 1 <= j && j <= 8) {
if (board(i,j) == -1) {
call enable (i, j, imove, jmove)
}
}
end
#-----------------------------------------------------------------------
subroutine enable (i, j, imove, jmove)
implicit none
# Enable a potential move.
integer i, j
integer imove, jmove
imove = i
jmove = j
end
#-----------------------------------------------------------------------
subroutine disabl (imove, jmove)
implicit none
# Disable a potential move.
integer imove, jmove
imove = -1
jmove = -1
end
#-----------------------------------------------------------------------
subroutine alg2ij (alg, i, j)
implicit none
# Convert, for instance, 'c5' to i=3,j=5.
character*2 alg
integer i, j
if (alg(1:1) == 'a') j = 1
if (alg(1:1) == 'b') j = 2
if (alg(1:1) == 'c') j = 3
if (alg(1:1) == 'd') j = 4
if (alg(1:1) == 'e') j = 5
if (alg(1:1) == 'f') j = 6
if (alg(1:1) == 'g') j = 7
if (alg(1:1) == 'h') j = 8
if (alg(2:2) == '1') i = 1
if (alg(2:2) == '2') i = 2
if (alg(2:2) == '3') i = 3
if (alg(2:2) == '4') i = 4
if (alg(2:2) == '5') i = 5
if (alg(2:2) == '6') i = 6
if (alg(2:2) == '7') i = 7
if (alg(2:2) == '8') i = 8
end
#-----------------------------------------------------------------------
subroutine ij2alg (i, j, alg)
implicit none
# Convert, for instance, i=3,j=5 to 'c5'.
integer i, j
character*2 alg
character alg1
character alg2
if (j == 1) alg1 = 'a'
if (j == 2) alg1 = 'b'
if (j == 3) alg1 = 'c'
if (j == 4) alg1 = 'd'
if (j == 5) alg1 = 'e'
if (j == 6) alg1 = 'f'
if (j == 7) alg1 = 'g'
if (j == 8) alg1 = 'h'
if (i == 1) alg2 = '1'
if (i == 2) alg2 = '2'
if (i == 3) alg2 = '3'
if (i == 4) alg2 = '4'
if (i == 5) alg2 = '5'
if (i == 6) alg2 = '6'
if (i == 7) alg2 = '7'
if (i == 8) alg2 = '8'
alg(1:1) = alg1
alg(2:2) = alg2
end
#-----------------------------------------------------------------------</syntaxhighlight>
{{out}}
$ echo "c5 2 T" | ./knights_tour
<pre> Tour number 1
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> e8 -> d6 -> b5 -> d4 -> f5 -> g7 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 58 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 63 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 60 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 61 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
Tour number 2
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
c7 -> b5 -> d6 -> e8 -> g7 -> f5 -> d4 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
8 | 56 | 3 | 50 | 21 | 60 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
7 | 51 | 22 | 57 | 4 | 49 | 20 | 61 | 6 |
+----+----+----+----+----+----+----+----+
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
5 | 23 | 58 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
4 | 38 | 13 | 54 | 63 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
</pre>
=={{header|REXX}}==
Line 6,047 ⟶ 10,706:
This is an ''open tour'' solution. (See this task's ''discussion'' page for an explanation, the section is ''The 7x7 problem''.)
<
parse arg N sRank sFile . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N=8 /*No boardsize specified? Use default.*/
Line 6,084 ⟶ 10,743:
end /*try different move. */
end /*t*/ /* [↑] all moves tried.*/
return 0 /*tour is not possible. */</
'''output''' when using the default input:
<pre>
Line 6,110 ⟶ 10,769:
=={{header|Ruby}}==
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]]
<
Cell = Struct.new(:value, :adj) do
def self.end=(end_val)
Line 6,181 ⟶ 10,840:
knight_tour(5,5,0,1)
knight_tour(12,12,1,1)</
Which produces:
<pre>
Line 6,227 ⟶ 10,886:
=={{header|Rust}}==
<
const SIZE: usize = 8;
Line 6,337 ⟶ 10,996:
None => println!("Fail!"),
}
}</
{{out}}
<pre>
Line 6,353 ⟶ 11,012:
=={{header|Scala}}==
<syntaxhighlight lang="scala">
val b=Seq.tabulate(8,8,8,8)((x,y,z,t)=>(1L<<(x*8+y),1L<<(z*8+t),f"${97+z}%c${49+t}%c",(x-z)*(x-z)+(y-t)*(y-t)==5)).flatten.flatten.flatten.filter(_._4).groupBy(_._1)
def f(p:Long,s:Long,v:Any){if(-1L!=s)b(p).foreach(x=>if((s&x._2)==0)f(x._2,s|x._2,v+x._3))else println(v)}
f(1,1,"a1")
</syntaxhighlight>
<pre>
a1b3a5b7c5a4b2c4a3b1c3a2b4a6b8c6a7b5c7a8b6c8d6e4d2f1e3c2d4e2c1d3e1g2f4d5e7g8h6f5h4g6h8f7d8e6f8d7e5g4h2f3g1h3g5h7f6e8g7h5g3h1f2d1
Line 6,363 ⟶ 11,022:
=={{header|Scheme}}==
<
;;/usr/bin/petite
;;encoding:utf-8
Line 6,410 ⟶ 11,069:
(display (map (lambda(x) (decode x)) result)))
(go (renew position))))
</syntaxhighlight>
{{out}}
<pre>
Line 6,419 ⟶ 11,078:
=={{header|SequenceL}}==
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_rule|Warnsdorffs rule]] (No Backtracking)
<syntaxhighlight lang="sequencel">
import <Utilities/Sequence.sl>;
import <Utilities/Conversion.sl>;
Line 6,470 ⟶ 11,129:
value when x = i and y = j else
board[i,j] foreach i within 1 ... size(board), j within 1 ... size(board[1]);
</syntaxhighlight>
{{out}}
8 X 8 board:
Line 6,509 ⟶ 11,168:
=={{header|Sidef}}==
{{trans|Raku}}
<
var I = 8
var J = 8
Line 6,569 ⟶ 11,228:
}
print "\n"
}</
=={{header|Swift}}==
Line 6,575 ⟶ 11,234:
{{trans|Rust}}
<
public var x: Int
public var y: Int
Line 6,704 ⟶ 11,363:
}
b.printBoard()</
{{out}}
Line 6,719 ⟶ 11,378:
=={{header|Tcl}}==
<
oo::class create KnightsTour {
Line 6,825 ⟶ 11,484:
expr {$a in [my ValidMoves $b]}
}
}</
Demonstrating:
<
$kt constructRandom
$kt print
Line 6,834 ⟶ 11,493:
} else {
puts "This is an open tour"
}</
Sample output:
<pre>
Line 6,846 ⟶ 11,505:
</pre>
The above code supports other sizes of boards and starting from nominated locations:
<
$kt constructFrom {0 0}
$kt print
Line 6,853 ⟶ 11,512:
} else {
puts "This is an open tour"
}</
Which could produce this output:
<pre>
Line 6,862 ⟶ 11,521:
-> c3
This is an open tour
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">class Square {
construct new(x, y) {
_x = x
_y = y
}
x { _x }
y { _y }
==(other) { _x == other.x && _y == other.y }
}
var board = List.filled(8 * 8, null)
for (i in 0...board.count) board[i] = Square.new((i/8).floor + 1, i%8 + 1)
var axisMoves = [1, 2, -1, -2]
var allPairs = Fn.new { |a|
var pairs = []
for (i in a) {
for (j in a) pairs.add([i, j])
}
return pairs
}
var knightMoves = Fn.new { |s|
var moves = allPairs.call(axisMoves).where { |p| p[0].abs != p[1].abs }
var onBoard = Fn.new { |s| board.any { |i| i == s } }
return moves.map { |p| Square.new(s.x + p[0], s.y + p[1]) }.where(onBoard)
}
var knightTour // recursive
knightTour = Fn.new { |moves|
var findMoves = Fn.new { |s|
return knightMoves.call(s).where { |m| !moves.any { |m2| m2 == m } }.toList
}
var fm = findMoves.call(moves[-1])
if (fm.isEmpty) return moves
var lowest = findMoves.call(fm[0]).count
var lowestIndex = 0
for (i in 1...fm.count) {
var count = findMoves.call(fm[i]).count
if (count < lowest) {
lowest = count
lowestIndex = i
}
}
var newSquare = fm[lowestIndex]
return knightTour.call(moves + [newSquare])
}
var knightTourFrom = Fn.new { |start| knightTour.call([start]) }
var col = 0
for (p in knightTourFrom.call(Square.new(1, 1))) {
System.write("%(p.x),%(p.y)")
System.write((col == 7) ? "\n" : " ")
col = (col + 1) % 8
}</syntaxhighlight>
{{out}}
<pre>
1,1 2,3 3,1 1,2 2,4 1,6 2,8 4,7
6,8 8,7 7,5 8,3 7,1 5,2 7,3 8,1
6,2 4,1 2,2 1,4 2,6 1,8 3,7 5,8
7,7 8,5 6,6 7,8 8,6 7,4 8,2 6,1
4,2 2,1 3,3 5,4 3,5 4,3 5,1 6,3
8,4 7,2 6,4 5,6 4,8 2,7 1,5 3,6
1,7 3,8 5,7 4,5 5,3 6,5 4,4 3,2
1,3 2,5 4,6 3,4 5,5 6,7 8,8 7,6
</pre>
=={{header|XPL0}}==
<
int LegalX, LegalY; \arrays of legal moves
def IntSize=4; \number of bytes in an integer (4 or 2)
Line 6,915 ⟶ 11,647:
]
else Text(0, "No Solution.^M^J");
]</
Example output:
Line 6,934 ⟶ 11,666:
First we build a generic package for solving any kind of tour over the chess board. Here it is…
<syntaxhighlight lang="text">
<xsl:package xsl:version="3.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
Line 6,991 ⟶ 11,723:
</xsl:package>
</syntaxhighlight>
And now for the style-sheet to solve the Knight’s tour…
<syntaxhighlight lang="text">
<xsl:stylesheet version="3.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
Line 7,034 ⟶ 11,766:
</xsl:stylesheet>
</syntaxhighlight>
So an input like this…
<syntaxhighlight lang="text">
<tt>
<knight>
Line 7,044 ⟶ 11,776:
</knight>
</tt>
</syntaxhighlight>
…should be transformed in something like this…
<syntaxhighlight lang="text">
<tt>
<knight>
Line 7,057 ⟶ 11,789:
</knight>
</tt>
</syntaxhighlight>
=={{header|zkl}}==
<
// linear time.
// See Pohl, Ira (July 1967),
Line 7,107 ⟶ 11,839:
fcn(ns){ vm.arglist.apply("%2s".fmt).concat(",")+"\n" });
}
}</
<
b.println();</
{{out}}
<pre>
Line 7,123 ⟶ 11,855:
</pre>
Check that a solution for all squares is found:
<
{ b:=Board(); n:=b.knightsTour(x,y); if(n!=64) b.println(">>>",x,",",y) } ]];</
{{out}}Nada
| |||