Knight's tour: Difference between revisions
(Added Bracmat) |
(CoffeeScript) |
||
Line 514: | Line 514: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{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. |
|||
<lang coffeescript> |
|||
graph_tours = (graph, max_num_solutions) -> |
|||
# graph is an array of arrays |
|||
# graph[3] = [4, 5] means nodes 4 and 5 are reachable from node 3 |
|||
# |
|||
# Returns an array of tours (up to max_num_solutions in size), where |
|||
# each tour is an array of nodes visited in order, and where each |
|||
# tour visits every node in the graph exactly once. |
|||
# |
|||
complete_tours = [] |
|||
visited = (false for node in graph) |
|||
dead_ends = ({} for node in graph) |
|||
tour = [0] |
|||
valid_neighbors = (i) -> |
|||
arr = [] |
|||
for neighbor in graph[i] |
|||
continue if visited[neighbor] |
|||
continue if dead_ends[i][neighbor] |
|||
arr.push neighbor |
|||
arr |
|||
next_square_to_visit = (i) -> |
|||
arr = valid_neighbors i |
|||
return null if arr.length == 0 |
|||
# We traverse to our neighbor who has the fewest neighbors itself. |
|||
fewest_neighbors = valid_neighbors(arr[0]).length |
|||
neighbor = arr[0] |
|||
for i in [1...arr.length] |
|||
n = valid_neighbors(arr[i]).length |
|||
if n < fewest_neighbors |
|||
fewest_neighbors = n |
|||
neighbor = arr[i] |
|||
neighbor |
|||
while tour.length > 0 |
|||
current_square = tour[tour.length - 1] |
|||
visited[current_square] = true |
|||
next_square = next_square_to_visit current_square |
|||
if next_square? |
|||
tour.push next_square |
|||
if tour.length == graph.length |
|||
complete_tours.push (n for n in tour) # clone |
|||
break if complete_tours.length == max_num_solutions |
|||
# pessimistically call this a dead end |
|||
dead_ends[current_square][next_square] = true |
|||
current_square = next_square |
|||
else |
|||
# we backtrack |
|||
doomed_square = tour.pop() |
|||
dead_ends[doomed_square] = {} |
|||
visited[doomed_square] = false |
|||
complete_tours |
|||
knight_graph = (board_width) -> |
|||
# Turn the Knight's Tour into a pure graph-traversal problem |
|||
# by precomputing all the legal moves. Returns an array of arrays, |
|||
# where each element in any subarray is the index of a reachable node. |
|||
index = (i, j) -> |
|||
# index squares from 0 to n*n - 1 |
|||
board_width * i + j |
|||
reachable_squares = (i, j) -> |
|||
deltas = [ |
|||
[ 1, 2] |
|||
[ 1, -2] |
|||
[ 2, 1] |
|||
[ 2, -1] |
|||
[-1, 2] |
|||
[-1, -2] |
|||
[-2, 1] |
|||
[-2, -1] |
|||
] |
|||
neighbors = [] |
|||
for delta in deltas |
|||
[di, dj] = delta |
|||
ii = i + di |
|||
jj = j + dj |
|||
if 0 <= ii < board_width |
|||
if 0 <= jj < board_width |
|||
neighbors.push index(ii, jj) |
|||
neighbors |
|||
graph = [] |
|||
for i in [0...board_width] |
|||
for j in [0...board_width] |
|||
graph[index(i, j)] = reachable_squares i, j |
|||
graph |
|||
illustrate_knights_tour = (tour, board_width) -> |
|||
pad = (n) -> |
|||
return " _" if !n? |
|||
return " " + n if n < 10 |
|||
"#{n}" |
|||
console.log "\n------" |
|||
moves = {} |
|||
for square, i in tour |
|||
moves[square] = i + 1 |
|||
for i in [0...board_width] |
|||
s = '' |
|||
for j in [0...board_width] |
|||
s += " " + pad moves[i*board_width + j] |
|||
console.log s |
|||
BOARD_WIDTH = 8 |
|||
MAX_NUM_SOLUTIONS = 100000 |
|||
graph = knight_graph BOARD_WIDTH |
|||
tours = graph_tours graph, MAX_NUM_SOLUTIONS |
|||
console.log "#{tours.length} tours found (showing first and last)" |
|||
illustrate_knights_tour tours[0], BOARD_WIDTH |
|||
illustrate_knights_tour tours.pop(), BOARD_WIDTH |
|||
</lang> |
|||
output |
|||
<lang> |
|||
> time coffee knight.coffee |
|||
100000 tours found (showing first and last) |
|||
------ |
|||
1 4 57 20 47 6 49 22 |
|||
34 19 2 5 58 21 46 7 |
|||
3 56 35 60 37 48 23 50 |
|||
18 33 38 55 52 59 8 45 |
|||
39 14 53 36 61 44 51 24 |
|||
32 17 40 43 54 27 62 9 |
|||
13 42 15 30 11 64 25 28 |
|||
16 31 12 41 26 29 10 63 |
|||
------ |
|||
1 4 41 20 63 6 61 22 |
|||
34 19 2 5 42 21 44 7 |
|||
3 40 35 64 37 62 23 60 |
|||
18 33 38 47 56 43 8 45 |
|||
39 14 57 36 49 46 59 24 |
|||
32 17 48 55 58 27 50 9 |
|||
13 54 15 30 11 52 25 28 |
|||
16 31 12 53 26 29 10 51 |
|||
real 0m29.741s |
|||
user 0m25.656s |
|||
sys 0m0.253s |
|||
</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
Line 641: | Line 792: | ||
[ 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|Go}}== |
=={{header|Go}}== |
||
<lang go>/* Adapted from "Enumerating Knight's Tours using an Ant Colony Algorithm" |
<lang go>/* Adapted from "Enumerating Knight's Tours using an Ant Colony Algorithm" |
Revision as of 21:21, 18 December 2011
You are encouraged to solve this task according to the task description, using any language you may know.
Problem: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once. Note that it is not a requirement that the knight should end within a knight's move of its start position, (this would have then been a closed tour).
Input and output may be textual or graphical, according to the conventions of the programming environment. If textual, squares should be indicated in Algebraic Notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered ordering to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard.
Input: starting square
Output: move sequence
- Cf.
Bracmat
<lang> ( knightsTour
= validmoves WarnsdorffSort algebraicNotation init solve , x y fieldsToVisit . ~ | ( validmoves = x y jumps moves . !arg:(?x.?y) & :?moves & ( jumps = dx dy Fs fxs fys fx fy . !arg:(?dx.?dy) & 1 -1:?Fs & !Fs:?fxs & whl ' ( !fxs:%?fx ?fxs & !Fs:?fys & whl ' ( !fys:%?fy ?fys & ( (!x+!fx*!dx.!y+!fy*!dy) : (>0:<9.>0:<9) | ) !moves : ?moves ) ) ) & jumps$(1.2) & jumps$(2.1) & !moves ) & ( init = fields x y . :?fields & 0:?x & whl ' ( 1+!x:<9:?x & 0:?y & whl ' ( 1+!y:<9:?y & (!x.!y) !fields:?fields ) ) & !fields ) & init$:?fieldsToVisit & ( WarnsdorffSort = sum moves elm weightedTerms . ( weightedTerms = pos alts fieldsToVisit moves move weight . !arg:(%?pos ?alts.?fieldsToVisit) & ( !fieldsToVisit:!pos & (0.!pos) | !fieldsToVisit:? !pos ? & validmoves$!pos:?moves & 0:?weight & whl ' ( !moves:%?move ?moves & ( !fieldsToVisit:? !move ? & !weight+1:?weight | ) ) & (!weight.!pos) | 0 ) + weightedTerms$(!alts.!fieldsToVisit) | 0 ) & weightedTerms$!arg:?sum & :?moves & whl ' ( !sum:(#.?elm)+?sum & !moves !elm:?moves ) & !moves ) & ( solve = pos alts fieldsToVisit A Z tailOfSolution . !arg:(%?pos ?alts.?fieldsToVisit) & ( !fieldsToVisit:?A !pos ?Z & ( !A !Z:& | solve $ ( WarnsdorffSort$(validmoves$!pos.!A !Z) . !A !Z ) ) | solve$(!alts.!fieldsToVisit) ) : ?tailOfSolution & !pos !tailOfSolution ) & ( algebraicNotation = x y . !arg:(?x.?y) ?arg & str$(chr$(asc$a+!x+-1) !y " ") algebraicNotation$!arg | ) & @(!arg:?x #?y) & asc$!x+-1*asc$a+1:?x & str $ (algebraicNotation$(solve$((!x.!y).!fieldsToVisit))) )
& out$(knightsTour$a1);</lang>
<lang>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 </lang>
C
For an animated version using OpenGL, see Knight's tour/C.
The following draws on console the progress of the horsie. Specify board size on commandline, or use default 8. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <unistd.h>
typedef unsigned char cell; int dx[] = { -2, -2, -1, 1, 2, 2, 1, -1 }; int dy[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
void init_board(int w, int h, cell **a, cell **b) { int i, j, k, x, y, p = w + 4, q = h + 4; /* b is board; a is board with 2 rows padded at each side */ a[0] = (cell*)(a + q); b[0] = a[0] + 2;
for (i = 1; i < q; i++) { a[i] = a[i-1] + p; b[i] = a[i] + 2; }
memset(a[0], 255, p * q); for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { for (k = 0; k < 8; k++) { x = j + dx[k], y = i + dy[k]; if (b[i+2][j] == 255) b[i+2][j] = 0; b[i+2][j] += x >= 0 && x < w && y >= 0 && y < h; } } } }
- define E "\033["
int walk_board(int w, int h, int x, int y, cell **b) { int i, nx, ny, least; int steps = 0; printf(E"H"E"J"E"%d;%dH"E"32m[]"E"m", y + 1, 1 + 2 * x);
while (1) { /* occupy cell */ b[y][x] = 255;
/* reduce all neighbors' neighbor count */ for (i = 0; i < 8; i++) b[ y + dy[i] ][ x + dx[i] ]--;
/* find neighbor with lowest neighbor count */ least = 255; for (i = 0; i < 8; i++) { if (b[ y + dy[i] ][ x + dx[i] ] < least) { nx = x + dx[i]; ny = y + dy[i]; least = b[ny][nx]; } }
if (least > 7) { printf(E"%dH", h + 2); return steps == w * h - 1; }
if (steps++) printf(E"%d;%dH[]", y + 1, 1 + 2 * x); x = nx, y = ny; printf(E"%d;%dH"E"31m[]"E"m", y + 1, 1 + 2 * x); fflush(stdout); usleep(120000); } }
int solve(int w, int h) { int x = 0, y = 0; cell **a, **b; a = malloc((w + 4) * (h + 4) + sizeof(cell*) * (h + 4)); b = malloc((h + 4) * sizeof(cell*));
while (1) { init_board(w, h, a, b); if (walk_board(w, h, x, y, b + 2)) { printf("Success!\n"); return 1; } if (++x >= w) x = 0, y++; if (y >= h) { printf("Failed to find a solution\n"); return 0; } printf("Any key to try next start position"); getchar(); } }
int main(int c, char **v) { int w, h; if (c < 2 || (w = atoi(v[1])) <= 0) w = 8; if (c < 3 || (h = atoi(v[2])) <= 0) h = w; solve(w, h);
return 0; }</lang>
C++
Uses Warnsdorff's rule and (iterative) backtracking if that fails.
<lang cpp>#include <iostream>
- include <iomanip>
- include <array>
- include <string>
- include <tuple>
- include <algorithm>
using namespace std;
template<int N = 8> class Board { public:
array<pair<int, int>, 8> moves; array<array<int, N>, N> data;
Board() { moves[0] = make_pair(2, 1); moves[1] = make_pair(1, 2); moves[2] = make_pair(-1, 2); moves[3] = make_pair(-2, 1); moves[4] = make_pair(-2, -1); moves[5] = make_pair(-1, -2); moves[6] = make_pair(1, -2); moves[7] = make_pair(2, -1); }
array<int, 8> sortMoves(int x, int y) const { array<tuple<int, int>, 8> counts; for(int i = 0; i < 8; ++i) { int dx = get<0>(moves[i]); int dy = get<1>(moves[i]);
int c = 0; for(int j = 0; j < 8; ++j) { int x2 = x + dx + get<0>(moves[j]); int y2 = y + dy + get<1>(moves[j]);
if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= N) continue; if(data[y2][x2] != 0) continue;
c++; }
counts[i] = make_tuple(c, i); }
// Shuffle to randomly break ties random_shuffle(counts.begin(), counts.end());
// Lexicographic sort sort(counts.begin(), counts.end());
array<int, 8> out; for(int i = 0; i < 8; ++i) out[i] = get<1>(counts[i]); return out; }
void solve(string start) { for(int v = 0; v < N; ++v) for(int u = 0; u < N; ++u) data[v][u] = 0;
int x0 = start[0] - 'a'; int y0 = N - (start[1] - '0'); data[y0][x0] = 1;
array<tuple<int, int, int, array<int, 8>>, N*N> order; order[0] = make_tuple(x0, y0, 0, sortMoves(x0, y0));
int n = 0; while(n < N*N-1) { int x = get<0>(order[n]); int y = get<1>(order[n]);
bool ok = false; for(int i = get<2>(order[n]); i < 8; ++i) { int dx = moves[get<3>(order[n])[i]].first; int dy = moves[get<3>(order[n])[i]].second;
if(x+dx < 0 || x+dx >= N || y+dy < 0 || y+dy >= N) continue; if(data[y + dy][x + dx] != 0) continue;
++n; get<2>(order[n]) = i + 1; data[y+dy][x+dx] = n + 1; order[n] = make_tuple(x+dx, y+dy, 0, sortMoves(x+dx, y+dy)); ok = true; break; }
if(!ok) // Failed. Backtrack. { data[y][x] = 0; --n; } } }
template<int N> friend ostream& operator<<(ostream &out, const Board<N> &b);
};
template<int N> ostream& operator<<(ostream &out, const Board<N> &b) {
for (int v = 0; v < N; ++v) { for (int u = 0; u < N; ++u) { if (u != 0) out << ","; out << setw(3) << b.data[v][u]; } out << endl; } return out;
}
int main() {
Board<5> b1; b1.solve("c3"); cout << b1 << endl;
Board<8> b2; b2.solve("b5"); cout << b2 << endl;
Board<31> b3; // Max size for <1000 squares b3.solve("a1"); cout << b3 << endl; return 0;
}</lang>
Output:
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 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 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
C#
<lang csharp>using System; using System.Collections.Generic;
namespace prog { class MainClass { const int N = 8;
readonly static int[,] moves = { {+1,-2},{+2,-1},{+2,+1},{+1,+2}, {-1,+2},{-2,+1},{-2,-1},{-1,-2} }; struct ListMoves { public int x, y; public ListMoves( int _x, int _y ) { x = _x; y = _y; } }
public static void Main (string[] args) { int[,] board = new int[N,N]; board.Initialize();
int x = 0, // starting position y = 0;
List<ListMoves> list = new List<ListMoves>(N*N); list.Add( new ListMoves(x,y) );
do { if ( Move_Possible( board, x, y ) ) { int move = board[x,y]; board[x,y]++; x += moves[move,0]; y += moves[move,1]; list.Add( new ListMoves(x,y) ); } else { if ( board[x,y] >= 8 ) { board[x,y] = 0; list.RemoveAt(list.Count-1); if ( list.Count == 0 ) { Console.WriteLine( "No solution found." ); return; } x = list[list.Count-1].x; y = list[list.Count-1].y; } board[x,y]++; } } while( list.Count < N*N );
int last_x = list[0].x, last_y = list[0].y; string letters = "ABCDEFGH"; for( int i=1; i<list.Count; i++ ) { Console.WriteLine( string.Format("{0,2}: ", i) + letters[last_x] + (last_y+1) + " - " + letters[list[i].x] + (list[i].y+1) );
last_x = list[i].x; last_y = list[i].y; } }
static bool Move_Possible( int[,] board, int cur_x, int cur_y ) { if ( board[cur_x,cur_y] >= 8 ) return false;
int new_x = cur_x + moves[board[cur_x,cur_y],0], new_y = cur_y + moves[board[cur_x,cur_y],1];
if ( new_x >= 0 && new_x < N && new_y >= 0 && new_y < N && board[new_x,new_y] == 0 ) return true;
return false; } } }</lang>
==[[:Category:|]] [[Category:]] { break } lappend visited $square } if {[llength $visited] == $height*$width} { return } puts stderr "rejecting path of length [llength $visited]..." }
}
method constructRandom {} {
my constructFrom [list \ [expr {int(rand()*$width)}] [expr {int(rand()*$height)}]]
}
method print {} {
set s " " foreach square $visited { puts -nonewline "$s[my FormatSquare $square]" if {[incr i]%12} { set s " -> " } else { set s "\n -> " } } puts ""
}
method isClosed {} {
set a [lindex $visited 0] set b [lindex $visited end] expr {$a in [my ValidMoves $b]}
}
}</lang> Demonstrating: <lang tcl>set kt [KnightsTour new] $kt constructRandom $kt print if {[$kt isClosed]} {
puts "This is a closed tour"
} else {
puts "This is an open tour"
}</lang> Sample output:
e6 -> f8 -> h7 -> g5 -> h3 -> g1 -> e2 -> c1 -> a2 -> b4 -> a6 -> b8 -> d7 -> b6 -> a8 -> c7 -> e8 -> g7 -> h5 -> g3 -> h1 -> f2 -> d1 -> b2 -> a4 -> c3 -> b1 -> a3 -> b5 -> a7 -> c8 -> e7 -> g8 -> h6 -> f7 -> h8 -> g6 -> h4 -> g2 -> f4 -> d5 -> f6 -> g4 -> h2 -> f1 -> e3 -> f5 -> d6 -> e4 -> d2 -> c4 -> a5 -> b7 -> d8 -> c6 -> e5 -> f3 -> e1 -> d3 -> c5 -> b3 -> a1 -> c2 -> d4 This is a closed tour
The above code supports other sizes of boards and starting from nominated locations: <lang tcl>set kt [KnightsTour new 7 7] $kt constructFrom {0 0} $kt print if {[$kt isClosed]} {
puts "This is a closed tour"
} else {
puts "This is an open tour"
}</lang> Which could produce this output:
a1 -> c2 -> e1 -> g2 -> f4 -> g6 -> e7 -> f5 -> g7 -> e6 -> g5 -> f7 -> d6 -> b7 -> a5 -> b3 -> c1 -> a2 -> b4 -> a6 -> c7 -> b5 -> a7 -> c6 -> d4 -> e2 -> g1 -> f3 -> d2 -> f1 -> g3 -> e4 -> f2 -> g4 -> f6 -> d7 -> e5 -> d3 -> c5 -> a4 -> b2 -> d1 -> e3 -> d5 -> b6 -> c4 -> a3 -> b1 -> c3 This is an open tour