Knight's tour: Difference between revisions
Content added Content deleted
Line 6,059: | 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 |
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> |
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}}== |
=={{header|Perl}}== |