Knight's tour: Difference between revisions
Content added Content deleted
Line 1,198: | Line 1,198: | ||
in |
in |
||
array_set_at (!(chessboard.p_board), index, value) |
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 |
end |
||
Line 1,335: | Line 1,411: | ||
val _ = loop (positions, 0) |
val _ = loop (positions, 0) |
||
val _ = move_t_fprint (f, positions[pred n_squares]) |
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) |
val _ = array_ptr_free (pf, pfgc | p_positions) |
||
Line 1,715: | Line 1,794: | ||
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 -> |
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 -> |
||
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 -> |
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 -> |
||
c7 -> e8 -> d6 -> b5 -> d4 -> f5 -> g7 -> e6 |
c7 -> e8 -> d6 -> b5 -> d4 -> f5 -> g7 -> e6 -> cycle |
||
+----+----+----+----+----+----+----+----+ |
+----+----+----+----+----+----+----+----+ |
||
8 | 56 | 3 | 50 | 21 | 58 | 5 | 44 | 19 | |
8 | 56 | 3 | 50 | 21 | 58 | 5 | 44 | 19 | |
||
Line 1,743: | Line 1,822: | ||
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 -> |
e3 -> g4 -> h6 -> g8 -> f6 -> h5 -> f4 -> d5 -> |
||
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 -> |
e7 -> c8 -> a7 -> c6 -> e5 -> c4 -> b6 -> a8 -> |
||
c7 -> b5 -> d6 -> e8 -> g7 -> f5 -> d4 -> e6 |
c7 -> b5 -> d6 -> e8 -> g7 -> f5 -> d4 -> e6 -> cycle |
||
+----+----+----+----+----+----+----+----+ |
+----+----+----+----+----+----+----+----+ |
||
8 | 56 | 3 | 50 | 21 | 60 | 5 | 44 | 19 | |
8 | 56 | 3 | 50 | 21 | 60 | 5 | 44 | 19 | |