Knight's tour: Difference between revisions

Content added Content deleted
Line 6,782: Line 6,782:


=={{header|ObjectIcon}}==
=={{header|ObjectIcon}}==
{{trans|ATS}}
This program can print multiple solutions by applying Warnsdorff’s heuristic, by trying in turn each ‘Warnsdorff move’.
<lang objecticon># -*- ObjectIcon -*-
<lang objecticon># -*- ObjectIcon -*-


Line 6,789: Line 6,789:
#
#
# Using Warnsdorff’s heuristic, find multiple solutions.
# 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
#
#


Line 6,799: Line 6,812:
local f_out
local f_out
local tours
local tours
local make_tour
local tour_board
local tour_board
local n_tour
local n_tour
local starting_position
local starting_position
local i_start, j_start
local i, j
local max_tours
local max_tours
local closed_only


starting_position :=
starting_position := \algebraic_notation_to_i_j(args[1]) | [1, 1]
i := starting_position[1]
(\algebraic_notation_to_i_j(args[1]) |
j := starting_position[2]
usage_error())
i_start := starting_position[1]
j_start := starting_position[2]


max_tours := integer(args[2]) | 1
max_tours := integer(args[2]) | 1
closed_only := if \args[3] === "closed" then &yes else &no


f_out := FileStream.stdout
f_out := FileStream.stdout


tours := KnightsTours()
tours := KnightsTours()
make_tour := create tours.generate(i_start, j_start)
n_tour := 0
n_tour := 0
while n_tour < max_tours & tour_board := @make_tour do {
if n_tour < max_tours then
every tour_board := tours.generate(i, j, closed_only) do {
n_tour +:= 1
write("Tour number ", n_tour, ":")
n_tour +:= 1
f_out.write(tour_board.make_moves_display())
write("Tour number ", n_tour, ":")
f_out.write(tour_board.make_board_display())
f_out.write(tour_board.make_moves_display())
f_out.write()
f_out.write(tour_board.make_board_display())
f_out.write()
}
if max_tours <= n_tour then
break
}
end
end


procedure usage_error()
procedure usage_error()
write("Usage: ", &progname, " POSITION [MAX_TOURS=1]")
write("Usage: ", &progname, " POSITION [MAX_TOURS=1 [closed]]")
write("Examples: ")
write("Examples: ")
write(" ", &progname, " c5 2")
write(" ", &progname, " a1")
write(" ", &progname, " a1")
write(" ", &progname, " c5 2")
write(" ", &progname, " e3 200 closed")
exit(0)
exit(0)
end
end
Line 6,889: Line 6,904:


public try(i, j, value)
public try(i, j, value)
# Backtracking assignment. Though we use it for ordinary
# assignment.
#
# The board is stored in column-major order.
# The board is stored in column-major order.
suspend board[i + (n_ranks * (j - 1))] <- value
suspend board[i + (n_ranks * (j - 1))] <- value
Line 6,898: Line 6,916:


s := ""
s := ""
every i := n_ranks to 1 by -1 do {
every i := n_ranks to 1 by -1 do
{
s ||:= " "
s ||:= " "
every j := 1 to n_files do
every j := 1 to n_files do
Line 6,922: Line 6,941:
local i, j
local i, j
local s
local s
local first_position, last_position


positions := list(n_squares)
positions := list(n_squares)
Line 6,929: Line 6,949:


s := ""
s := ""
every j := 1 to n_squares - 1 do {
every j := 1 to n_squares - 1 do
{
s ||:= positions[j].make_display()
s ||:= positions[j].make_display()
s ||:= (if j % n_files = 0 then " ->\n" else " -> ")
s ||:= (if j % n_files = 0 then " ->\n" else " -> ")
}
}
s ||:= positions[n_squares].make_display()
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
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


Line 6,946: Line 6,996:
private board
private board


public new(num_ranks, num_files)
public new(num_ranks, num_files, i, j, closed_only)
board := Chessboard(num_ranks, num_files)
board := Chessboard(num_ranks, num_files)
n_ranks := board.n_ranks
n_ranks := board.n_ranks
Line 6,954: Line 7,004:
end
end


public generate(i, j, n_position)
public generate(i, j, closed_only)
# i,j = starting position.
local move

local consumer
local explorer
local tour_board
local tour_board


# Simple coroutines. The consumer receives complete tours (each in
# Generate boards recursively.
# the form of a Chessboard) from the explorer.
consumer := &current
explorer := create explore(consumer, i, j, 1,
closed_only, i, j)


/n_position := 1
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)
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 {
if n_squares - n_position = 1 then {
every move := possible_moves(i, j) do {
# Is the last move possible? If so, make it and output the
board.try(move.i, move.j, n_position + 1)
# board. (Only zero or one of the moves can be non-null.)
suspend board.copy()
moves := possible_moves(i, j)
board.try(i, j, &null)
every try_last_move(consumer, moves[1 to 8],
closed_only, i_start, j_start)
}
} else {
} else {
every move := next_moves(i, j, n_position) do
moves := next_moves(i, j, n_position)
every tour_board := generate(move.i, move.j,
every mv := !moves do
if \mv then
n_position + 1) do
explore(consumer, mv.i, mv.j, n_position + 1,
suspend tour_board.copy()
board.try(i, j, &null)
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
end


private next_moves(i, j, n_position)
private next_moves(i, j, n_position)
local good_moves
local moves
local n_following
local w_list, w
local move
local k
local n


moves := possible_moves(i, j)
#
w_list := list(8)
# Prune and sort the moves according to Warnsdorff’s heuristic,
every k := 1 to 8 do
# keeping only moves that have the minimum number of legal
w_list[k] := count_following_moves(moves[k], n_position)
# following moves.
w := pick_w(w_list)
#
if w = 0 then
# There may be more than one such move, from a given position. For
# A dead end.
# reproducibility of the results, order them stably.
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)
good_moves := []
n_following := &null
local w
local following_moves
every move := possible_moves(i, j) do {

board.try(move.i, move.j, n_position)
n := 0
w := 0
every possible_moves(move.i, move.j) do
if \move then {
n +:= 1
board.try(move.i, move.j, n_position + 1)
following_moves := possible_moves(move.i, move.j)
if n ~= 0 then {
if /n_following | n < n_following[1] then {
every ( \following_moves[1 to 8] & w +:= 1 )
good_moves := [move]
n_following := [n]
} else if n = n_following[1] then {
put(good_moves, move)
put(n_following, n)
}
}
board.try(move.i, move.j, &null)
board.try(move.i, move.j, &null)
}
}
return w
every suspend !good_moves
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
end


private possible_moves(i, j)
private possible_moves(i, j)
local stride
local move1, move2, move3, move4
local i1, j1
local move5, move6, move7, move8


move1 := try_move(i + 1, j + 2)
static strides_list
move2 := try_move(i + 2, j + 1)
initial strides_list :=
[[+1, +2], [+2, +1], [+1, -2], [+2, -1],
move3 := try_move(i + 1, j - 2)
[-1, +2], [-2, +1], [-1, -2], [-2, -1]]
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)
every stride := !strides_list do {
i1 := i + stride[1]
return (1 <= i1 <= n_ranks &
j1 := j + stride[2]
1 <= j1 <= n_files &
if 1 <= i1 <= n_ranks then
/board.square(i1, j1) &
if 1 <= j1 <= n_files then
Move(i1, j1)) | &null
if /board.square(i1, j1) then
suspend Move(i1, j1)
}
end
end


end</lang>
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</lang>
{{out}}
{{out}}
$ ./knights_tour-oi a1 2
$ ./knights_tour c5 2 closed
<pre>Tour number 1:
<pre>Tour number 1:
a1 -> c2 -> a3 -> b1 -> d2 -> f1 -> h2 -> g4 ->
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
h6 -> g8 -> e7 -> c8 -> a7 -> b5 -> c7 -> a8 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
b6 -> a4 -> b2 -> d1 -> f2 -> h1 -> g3 -> h5 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
g7 -> e8 -> f6 -> h7 -> f8 -> d7 -> b8 -> a6 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
b4 -> a2 -> c3 -> d5 -> e3 -> f5 -> h4 -> g2 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e1 -> f3 -> g1 -> h3 -> g5 -> e4 -> d6 -> c4 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
a5 -> b7 -> d8 -> f7 -> h8 -> g6 -> e5 -> c6 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
d4 -> e6 -> f4 -> e2 -> c1 -> d3 -> c5 -> b3
c7 -> e8 -> d6 -> b5 -> d4 -> f5 -> g7 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
8 | 16 | 31 | 12 | 51 | 26 | 29 | 10 | 53 |
8 | 56 | 3 | 50 | 21 | 58 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
7 | 13 | 50 | 15 | 30 | 11 | 52 | 25 | 28 |
7 | 51 | 22 | 57 | 4 | 49 | 20 | 63 | 6 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
6 | 32 | 17 | 56 | 47 | 58 | 27 | 54 | 9 |
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
5 | 49 | 14 | 63 | 36 | 55 | 38 | 45 | 24 |
5 | 23 | 60 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
4 | 18 | 33 | 48 | 57 | 46 | 59 | 8 | 39 |
4 | 38 | 13 | 54 | 61 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
3 | 3 | 64 | 35 | 62 | 37 | 42 | 23 | 44 |
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
2 | 34 | 19 | 2 | 5 | 60 | 21 | 40 | 7 |
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
1 | 1 | 4 | 61 | 20 | 41 | 6 | 43 | 22 |
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
a b c d e f g h
a b c d e f g h


Tour number 2:
Tour number 2:
a1 -> c2 -> a3 -> b1 -> d2 -> f1 -> h2 -> g4 ->
c5 -> a6 -> b8 -> d7 -> f8 -> h7 -> g5 -> h3 ->
h6 -> g8 -> e7 -> c8 -> a7 -> b5 -> c7 -> a8 ->
g1 -> e2 -> c1 -> a2 -> b4 -> d3 -> e1 -> g2 ->
b6 -> a4 -> b2 -> d1 -> f2 -> h1 -> g3 -> h5 ->
h4 -> g6 -> h8 -> f7 -> d8 -> b7 -> a5 -> b3 ->
g7 -> e8 -> f6 -> h7 -> f8 -> d7 -> b8 -> a6 ->
a1 -> c2 -> a3 -> b1 -> d2 -> f3 -> h2 -> f1 ->
b4 -> a2 -> c3 -> d5 -> e3 -> f5 -> h4 -> g2 ->
g3 -> h1 -> f2 -> e4 -> c3 -> a4 -> b2 -> d1 ->
e1 -> f3 -> g1 -> h3 -> g5 -> e4 -> d6 -> c4 ->
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 ->
a5 -> b7 -> d8 -> f7 -> h8 -> g6 -> e5 -> c6 ->
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 ->
d4 -> e6 -> f4 -> e2 -> c1 -> b3 -> c5 -> d3
c7 -> b5 -> d6 -> e8 -> g7 -> f5 -> d4 -> e6 -> cycle
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
8 | 16 | 31 | 12 | 51 | 26 | 29 | 10 | 53 |
8 | 56 | 3 | 50 | 21 | 60 | 5 | 44 | 19 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
7 | 13 | 50 | 15 | 30 | 11 | 52 | 25 | 28 |
7 | 51 | 22 | 57 | 4 | 49 | 20 | 61 | 6 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
6 | 32 | 17 | 56 | 47 | 58 | 27 | 54 | 9 |
6 | 2 | 55 | 52 | 59 | 64 | 45 | 18 | 43 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
5 | 49 | 14 | 63 | 36 | 55 | 38 | 45 | 24 |
5 | 23 | 58 | 1 | 48 | 53 | 62 | 7 | 46 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
4 | 18 | 33 | 48 | 57 | 46 | 59 | 8 | 39 |
4 | 38 | 13 | 54 | 63 | 36 | 47 | 42 | 17 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
3 | 3 | 62 | 35 | 64 | 37 | 42 | 23 | 44 |
3 | 27 | 24 | 37 | 14 | 41 | 30 | 33 | 8 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
2 | 34 | 19 | 2 | 5 | 60 | 21 | 40 | 7 |
2 | 12 | 39 | 26 | 29 | 10 | 35 | 16 | 31 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
1 | 1 | 4 | 61 | 20 | 41 | 6 | 43 | 22 |
1 | 25 | 28 | 11 | 40 | 15 | 32 | 9 | 34 |
+----+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+----+
a b c d e f g h
a b c d e f g h
Retrieved from "https://rosettacode.org/wiki/Knight%27s_tour"