Knight's tour: Difference between revisions
→{{header|Perl}}
Line 6,059:
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}}==
This program can print multiple solutions by applying Warnsdorff’s heuristic, by trying in turn each ‘Warnsdorff move’.
<lang objecticon># -*- ObjectIcon -*-
#
# Find Knight’s Tours.
#
# Using Warnsdorff’s heuristic, find multiple solutions.
#
$define DEFAULT_NUMBER_OF_RANKS 8
$define DEFAULT_NUMBER_OF_FILES 8
import io
procedure main(args)
local f_out
local tours
local make_tour
local tour_board
local n_tour
local starting_position
local i_start, j_start
local max_tours
starting_position :=
(\algebraic_notation_to_i_j(args[1]) |
usage_error())
i_start := starting_position[1]
j_start := starting_position[2]
max_tours := integer(args[2]) | 1
f_out := FileStream.stdout
tours := KnightsTours()
make_tour := create tours.generate(i_start, j_start)
n_tour := 0
while n_tour < max_tours & tour_board := @make_tour 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()
}
end
procedure usage_error()
write("Usage: ", &progname, " POSITION [MAX_TOURS=1]")
write("Examples: ")
write(" ", &progname, " c5 2")
write(" ", &progname, " a1")
exit(0)
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
# Note that the i,j order here is in mathematician’s matrix
# notation, not chess ‘algebraic notation’. Thus square b3 is
# written square(5,2).
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)
# 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
positions := list(n_squares)
every i := 1 to n_ranks do
every j := 1 to n_ranks 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()
return s
end
end
class KnightsTours()
public const n_ranks
public const n_files
public const n_squares
private board
public new(num_ranks, num_files)
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, n_position)
local move
local tour_board
# Generate boards recursively.
/n_position := 1
board.try(i, j, n_position)
if n_squares - n_position = 1 then {
every move := possible_moves(i, j) do {
board.try(move.i, move.j, n_position + 1)
suspend board.copy()
board.try(i, j, &null)
}
} else {
every move := next_moves(i, j, n_position) do
every tour_board := generate(move.i, move.j,
n_position + 1) do
suspend tour_board.copy()
board.try(i, j, &null)
}
end
private next_moves(i, j, n_position)
local good_moves
local n_following
local move
local n
#
# Prune and sort the moves according to Warnsdorff’s heuristic,
# keeping only moves that have the minimum number of legal
# following moves.
#
# There may be more than one such move, from a given position. For
# reproducibility of the results, order them stably.
#
good_moves := []
n_following := &null
every move := possible_moves(i, j) do {
board.try(move.i, move.j, n_position)
n := 0
every possible_moves(move.i, move.j) do
n +:= 1
if n ~= 0 then {
if /n_following | n < n_following[1] then {
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)
}
every suspend !good_moves
end
private possible_moves(i, j)
local stride
local i1, j1
static strides_list
initial strides_list :=
[[+1, +2], [+2, +1], [+1, -2], [+2, -1],
[-1, +2], [-2, +1], [-1, -2], [-2, -1]]
every stride := !strides_list do {
i1 := i + stride[1]
j1 := j + stride[2]
if 1 <= i1 <= n_ranks then
if 1 <= j1 <= n_files then
if /board.square(i1, j1) then
suspend Move(i1, j1)
}
end
end</lang>
{{out}}
$ ./knights_tour-oi a1 2
<pre>Tour number 1:
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
+----+----+----+----+----+----+----+----+
8 | 16 | 31 | 12 | 51 | 26 | 29 | 10 | 53 |
+----+----+----+----+----+----+----+----+
7 | 13 | 50 | 15 | 30 | 11 | 52 | 25 | 28 |
+----+----+----+----+----+----+----+----+
6 | 32 | 17 | 56 | 47 | 58 | 27 | 54 | 9 |
+----+----+----+----+----+----+----+----+
5 | 49 | 14 | 63 | 36 | 55 | 38 | 45 | 24 |
+----+----+----+----+----+----+----+----+
4 | 18 | 33 | 48 | 57 | 46 | 59 | 8 | 39 |
+----+----+----+----+----+----+----+----+
3 | 3 | 64 | 35 | 62 | 37 | 42 | 23 | 44 |
+----+----+----+----+----+----+----+----+
2 | 34 | 19 | 2 | 5 | 60 | 21 | 40 | 7 |
+----+----+----+----+----+----+----+----+
1 | 1 | 4 | 61 | 20 | 41 | 6 | 43 | 22 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
Tour number 2:
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 -> b3 -> c5 -> d3
+----+----+----+----+----+----+----+----+
8 | 16 | 31 | 12 | 51 | 26 | 29 | 10 | 53 |
+----+----+----+----+----+----+----+----+
7 | 13 | 50 | 15 | 30 | 11 | 52 | 25 | 28 |
+----+----+----+----+----+----+----+----+
6 | 32 | 17 | 56 | 47 | 58 | 27 | 54 | 9 |
+----+----+----+----+----+----+----+----+
5 | 49 | 14 | 63 | 36 | 55 | 38 | 45 | 24 |
+----+----+----+----+----+----+----+----+
4 | 18 | 33 | 48 | 57 | 46 | 59 | 8 | 39 |
+----+----+----+----+----+----+----+----+
3 | 3 | 62 | 35 | 64 | 37 | 42 | 23 | 44 |
+----+----+----+----+----+----+----+----+
2 | 34 | 19 | 2 | 5 | 60 | 21 | 40 | 7 |
+----+----+----+----+----+----+----+----+
1 | 1 | 4 | 61 | 20 | 41 | 6 | 43 | 22 |
+----+----+----+----+----+----+----+----+
a b c d e f g h
</pre>
=={{header|Perl}}==
| |||