Knight's tour: Difference between revisions
m (→{{header|C}}: might as well allow non-square boards) |
|||
Line 1,356: | Line 1,356: | ||
%%EOF</lang> |
%%EOF</lang> |
||
=={{header|Prolog}}== |
|||
Worlks with SWI-Prolog.<br> |
|||
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
|||
<lang Prolog>% N is the number of lines of the chessboard |
|||
knight(N) :- |
|||
Max is N * N, |
|||
length(L, Max), |
|||
knight(N, 0, Max, 0, 0, L), |
|||
display(N, 0, L). |
|||
% knight(NbCol, Coup, Max, Lig, Col, L), |
|||
% NbCol : number of columns per line |
|||
% Coup : number of the current move |
|||
% Max : maximum number of moves |
|||
% Lig/ Col : current position of the knight |
|||
% L : the "chessboard" |
|||
% the game is over |
|||
knight(_, Max, Max, _, _, _) :- !. |
|||
knight(NbCol, N, MaxN, Lg, Cl, L) :- |
|||
% Is the move legal |
|||
Lg >= 0, Cl >= 0, Lg < NbCol, Cl < NbCol, |
|||
Pos is Lg * NbCol + Cl, |
|||
N1 is N+1, |
|||
% is the place free |
|||
nth0(Pos, L, N1), |
|||
LgM1 is Lg - 1, LgM2 is Lg - 2, LgP1 is Lg + 1, LgP2 is Lg + 2, |
|||
ClM1 is Cl - 1, ClM2 is Cl - 2, ClP1 is Cl + 1, ClP2 is Cl + 2, |
|||
maplist(best_move(NbCol, L), |
|||
[(LgP1, ClM2), (LgP2, ClM1), (LgP2, ClP1),(LgP1, ClP2), |
|||
(LgM1, ClM2), (LgM2, ClM1), (LgM2, ClP1),(LgM1, ClP2)], |
|||
R), |
|||
sort(R, RS), |
|||
pairs_values(RS, Moves), |
|||
move(NbCol, N1, MaxN, Moves, L). |
|||
move(NbCol, N1, MaxN, [(Lg, Cl) | R], L) :- |
|||
knight(NbCol, N1, MaxN, Lg, Cl, L); |
|||
move(NbCol, N1, MaxN, R, L). |
|||
%% An illegal move is scored 1000 |
|||
best_move(NbCol, _L, (Lg, Cl), 1000-(Lg, Cl)) :- |
|||
( Lg < 0 ; Cl < 0; Lg >= NbCol; Cl >= NbCol), !. |
|||
best_move(NbCol, L, (Lg, Cl), 1000-(Lg, Cl)) :- |
|||
Pos is Lg*NbCol+Cl, |
|||
nth0(Pos, L, V), |
|||
\+var(V), !. |
|||
%% a legal move is scored with the number of moves a knight can make |
|||
best_move(NbCol, L, (Lg, Cl), R-(Lg, Cl)) :- |
|||
LgM1 is Lg - 1, LgM2 is Lg - 2, LgP1 is Lg + 1, LgP2 is Lg + 2, |
|||
ClM1 is Cl - 1, ClM2 is Cl - 2, ClP1 is Cl + 1, ClP2 is Cl + 2, |
|||
include(possible_move(NbCol, L), |
|||
[(LgP1, ClM2), (LgP2, ClM1), (LgP2, ClP1),(LgP1, ClP2), |
|||
(LgM1, ClM2), (LgM2, ClM1), (LgM2, ClP1),(LgM1, ClP2)], |
|||
Res), |
|||
length(Res, Len), |
|||
( Len = 0 -> R = 1000; R = Len). |
|||
% test if a place is enabled |
|||
possible_move(NbCol, L, (Lg, Cl)) :- |
|||
% move must be legal |
|||
Lg >= 0, Cl >= 0, Lg < NbCol, Cl < NbCol, |
|||
Pos is Lg * NbCol + Cl, |
|||
% place must be free |
|||
nth0(Pos, L, V), |
|||
var(V). |
|||
display(_, _, []). |
|||
display(N, N, L) :- |
|||
nl, |
|||
display(N, 0, L). |
|||
display(N, M, [H | T]) :- |
|||
writef('%3r', [H]), |
|||
M1 is M + 1, |
|||
display(N, M1, T). |
|||
</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 20:57, 22 September 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.
C
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>
OpenGL
OpenGL program with glut. Compile with gcc -std=c99 -lglut -lGL -lGLU
, run with a.out -s [size]
. Program will print a help message at start.
<lang c>#include <GL/glut.h>
- include <GL/gl.h>
- include <GL/glu.h>
- include <stdio.h>
- include <time.h>
- include <unistd.h>
- include <sys/time.h>
- include <string.h>
struct timeval last_update, last_move; /* board width */ int bw = 7; /* power of 2 */ int twid = 1; int W = 240, H = 240, gwin;
void *board; typedef struct { int x, y; } cell_t; cell_t *moves; cell_t ofs[8] = {{2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}}; cell_t start; int n_moves, need_move = 1, stopped = 0, failed = 0, paused = 0, skip_draw = 0; int delay = 1024 * 128;
GLubyte *tex; GLuint texture;
int good(int x) { return x >= 0 && x < bw; }
void init_board() { int (*b)[bw] = board; for (int i = 0; i < bw; i++) memset(b[i], 0, sizeof(int) * bw);
n_moves = b[start.y][start.x] = 1; moves[0] = start; need_move = 1; stopped = 0; }
int n_vacant(int x, int y) { int (*b)[bw] = board; int cnt = 0;
for (int i = 0; i < 8; i++) { int nx = x + ofs[i].x; if (!good(nx)) continue;
int ny = y + ofs[i].y; if (!good(ny)) continue;
if (!b[ny][nx]) cnt++; }
return cnt; }
int restart() { if (++start.x < bw) { init_board(); return 1; } start.x = 0; if (++start.y < bw) { init_board(); return 1; } start.y = 0; printf("Already tried all starting positions\n"); need_move = 0; failed = 1; return 0; }
int next_move() { if (!need_move || stopped || paused) return 0;
int (*b)[bw] = board; cell_t cur = moves[n_moves - 1]; cell_t dest; int least = 9;
for (int i = 0; i < 8; i++) { int x = cur.x + ofs[i].x; if (!good(x)) continue;
int y = cur.y + ofs[i].y; if (!good(y)) continue;
if (b[y][x]) continue;
int n = n_vacant(x, y); if (n < least) { least = n; dest.x = x; dest.y = y; } }
if (least == 9) { stopped = 1; need_move = 0; if (n_moves == bw * bw) printf("Tour complete.\n"); else printf("Stuck at %d moves\n", n_moves); printf("Press SPACE to continue\n"); return 0; }
moves[n_moves++] = dest; b[dest.y][dest.x] = 1;
need_move = 1; return 1; }
void resize(int w, int h) { int dx = 0, dy = 0; W = w; H = h;
if (w > h) dx = w - h; else dy = h - w;
glViewport(dx / 2, dy / 2, W - dx, H - dy); glOrtho(0, bw, 0, bw, -1, 1); }
void render() { double tw = (double) bw / twid;
struct timeval tv; gettimeofday(&tv, 0); long usec = (tv.tv_sec - last_move.tv_sec) * 1000000 + tv.tv_usec - last_move.tv_usec; if (usec > delay || skip_draw) { next_move(); last_move = tv; }
if (skip_draw && !stopped) return;
usec = (tv.tv_sec - last_update.tv_sec) * 1000000 + tv.tv_usec - last_update.tv_usec; if (usec < 25000) return; last_update = tv;
glClear(GL_COLOR_BUFFER_BIT); glLoadIdentity(); glBindTexture(GL_TEXTURE_2D, texture);
glColor3f(1, 1, 1); glBegin(GL_QUADS); glTexCoord2f( 0, 0); glVertex2i(0, 0); glTexCoord2f( 0, tw); glVertex2i(0, bw); glTexCoord2f(tw, tw); glVertex2i(bw, bw); glTexCoord2f(tw, 0); glVertex2i(bw, 0); glEnd();
glBegin(GL_QUADS); glColor3f(0, .5, 1); int x = moves[0].x, y = moves[0].y;
glVertex2i(x + 0, y + 0); glVertex2i(x + 0, y + 1); glVertex2i(x + 1, y + 1); glVertex2i(x + 1, y + 0);
glColor4f(.5, .7, .5, .7); for (int i = (n_moves == bw * bw) ? n_moves - 1 : 1; i < n_moves; i++) { if (i == n_moves - 1) glColor3f(1, 0, 0); x = moves[i].x, y = moves[i].y; glVertex2f(x + 0, y + 0); glVertex2f(x + 0, y + 1); glVertex2f(x + 1, y + 1); glVertex2f(x + 1, y + 0); } glEnd();
glBegin(GL_LINE_STRIP); if (n_moves == bw * bw) glColor3f(0, .4, .4); else glColor3f(0, 0, 0);
for (int i = 0; i < n_moves; i++) glVertex2f(moves[i].x + .5, moves[i].y + .5); glEnd();
glFlush(); glFinish(); need_move = 1; }
void init_texture() { int i, j; while (twid < bw) twid <<= 1;
GLubyte * ptr = tex = malloc(twid * twid * 3);
for (i = 0; i < twid; i++) for (j = 0; j < twid; j++, ptr += 3) if ((i & 1) != (j & 1)) ptr[0] = ptr[1] = ptr[2] = 255; else ptr[0] = 120, ptr[1] = 255, ptr[2] = 200;
glEnable(GL_TEXTURE_2D); glGenTextures(1, &texture); glBindTexture(GL_TEXTURE_2D, texture); glTexImage2D(GL_TEXTURE_2D, 0, 3, twid, twid, 0, GL_RGB, GL_UNSIGNED_BYTE, tex);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
free(tex); }
void set_delay(int inc) { if (inc) { delay *= 2; if (!delay) delay = 1; if (delay >= 1 << 20) { delay = 1 << 20; paused = 1; printf("Pased\n"); return; } } else delay /= 2; paused = 0; printf("Delay = %d usec\n", delay); }
void keypress(unsigned char key, int x, int y) { switch(key) { case ' ': if (stopped && !failed) restart(); break; case 'q': case 27: glFinish(); glutDestroyWindow(gwin); return; case ',': case '<': set_delay(1); return; case '.': case '>': set_delay(0); return; case 's': skip_draw = !skip_draw; return; } }
void init_graphics(int c, char **v) { glutInit(&c, v); glutInitDisplayMode(GLUT_RGBA); glutInitWindowSize(W, H); glutDisplayFunc(render); glutIdleFunc(render); glutDisplayFunc(render);
gwin = glutCreateWindow("Board");
glutKeyboardFunc(keypress); glutReshapeFunc(resize);
glClearColor(.2, .2, .2, 1);
glMatrixMode(GL_PROJECTION); glLoadIdentity(); glOrtho(0, bw, 0, bw, -1, 1); glMatrixMode(GL_MODELVIEW);
glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
init_texture(); }
int main(int c, char **v) { if (c >= 3 && !strcmp(v[1], "-s")) { bw = atoi(v[2]); if (bw < 3) { printf("bad argument -s %s, size set to 3\n", v[2]); bw = 3; } } printf("Keys:\n\tQ, Esc: exit\n\t<: slow down\n\t>: speed up\n\t" "s: skip to finish\n<space>: try a new tour\n");
int b[bw][bw]; cell_t g[bw * bw]; moves = g; board = b; start.x = start.y = 0;
init_board();
init_graphics(c, v); gettimeofday(&last_update, 0); last_move = last_update;
glutMainLoop(); 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;
}</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
D
<lang d>import std.stdio, std.typecons, std.random, std.conv,
std.typetuple, std.range, std.algorithm;
int[N][N] knightTour(size_t N=8)(in string start) {
alias Tuple!(int, "x", int, "y") P; // is enum slower than immutable here? immutable P[8] moves = [P(2,1), P(1,2), P(-1,2), P(-2,1), P(-2,-1), P(-1,-2), P(1,-2), P(2,-1)]; int[N][N] data;
int[8] sortMoves(in int x, in int y) { int[2][8] counts; foreach (i, ref d1; moves) { int c = 0; foreach (ref d2; moves) { immutable p = P(x + d1.x + d2.x, y + d1.y + d2.y); if (p.x >= 0 && p.x < N && p.y >= 0 && p.y < N && data[p.y][p.x] == 0) c++; } //counts[i] = [c, i]; // slow counts[i][0] = c; counts[i][1] = i; }
randomShuffle(counts[]); // shuffle to randomly break ties counts[].sort(); // lexicographic sort
int[8] result; copy(transversal(counts[], 1), result[]); return result; }
assert(start.length >= 2); immutable P p0 = P(start[0] - 'a', N - to!int(start[1..$])); data[p0.y][p0.x] = 1;
Tuple!(int, int, int, int[8])[N*N] order; order[0] = tuple(p0.x, p0.y, 0, sortMoves(p0.x, p0.y));
int n = 0; while (n < N*N-1) { immutable int x = order[n][0]; immutable int y = order[n][1]; bool ok = false; foreach (i; order[n][2] .. 8) { immutable P d = moves[order[n][3][i]]; if (x+d.x < 0 || x+d.x >= N || y+d.y < 0 || y+d.y >= N) continue;
if (data[y + d.y][x + d.x] == 0) { order[n][2] = i + 1; n++; data[y + d.y][x + d.x] = n+1; order[n]= tuple(x+d.x,y+d.y,0,sortMoves(x+d.x,y+d.y)); ok = true; break; } }
if (!ok) { // Failed. Backtrack. data[y][x] = 0; n--; } }
return data;
}
void main() {
foreach (i, side; TypeTuple!(5, 8, 31)) { immutable form = "%" ~ text(text(side ^^ 2).length) ~ "d"; foreach (ref row; knightTour!side(["c3", "b5", "a1"][i])) writefln(form, row); writeln(); }
}</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]
Haskell
<lang Haskell> import System (getArgs) import Data.Char (ord, chr) import Data.List (minimumBy, (\\), intercalate, sort) import Data.Ord (comparing)
type Square = (Int, Int)
board :: [Square] board = [ (x,y) | x <- [1..8], y <- [1..8] ]
knightMoves :: Square -> [Square] knightMoves (x,y) = filter (flip elem board) jumps
where jumps = [ (x+i,y+j) | i <- jv, j <- jv, abs i /= abs j ] jv = [1,-1,2,-2]
knightTour :: [Square] -> [Square] knightTour moves
| candMoves == [] = reverse moves | otherwise = knightTour $ newSquare : moves where newSquare = minimumBy (comparing (length . findMoves)) candMoves candMoves = findMoves $ head moves findMoves sq = knightMoves sq \\ moves
main :: IO () main = do
sq <- fmap (toSq . head) getArgs printTour $ map toAlg $ knightTour [sq] where toAlg (x,y) = chr (x + 96) : chr (y + 48) : [] toSq [x,y] = ((ord x) - 96, (ord y) - 48) printTour [] = return () printTour tour = do putStrLn $ intercalate " -> " $ take 8 tour printTour $ drop 8 tour
</lang>
Output:
e5 -> f7 -> h8 -> g6 -> h4 -> g2 -> e1 -> f3 g1 -> h3 -> g5 -> h7 -> f8 -> d7 -> b8 -> a6 b4 -> a2 -> c1 -> d3 -> b2 -> a4 -> b6 -> a8 c7 -> e8 -> g7 -> h5 -> f4 -> e6 -> d8 -> b7 c5 -> b3 -> a1 -> c2 -> a3 -> b1 -> d2 -> c4 a5 -> c6 -> a7 -> c8 -> d6 -> b5 -> d4 -> e2 c3 -> d1 -> f2 -> h1 -> g3 -> e4 -> f6 -> g8 h6 -> g4 -> h2 -> f1 -> e3 -> f5 -> e7 -> d5
Icon and Unicon
This implements Warnsdorff's algorithm using unordered sets.
- The board must be square (it has only been tested on 8x8 and 7x7). Currently the maximum size board (due to square notation) is 26x26.
- Tie breaking is selectable with 3 variants supplied (first in list, random, and Roth's distance heuristic).
- A debug log can be generated showing the moves and choices considered for tie breaking.
The algorithm doesn't always generate a complete tour. <lang Icon>link printf
procedure main(A) ShowTour(KnightsTour(Board(8))) end
procedure KnightsTour(B,sq,tbrk,debug) #: Warnsdorff’s algorithm
/B := Board(8) # create 8x8 board if none given /sq := ?B.files || ?B.ranks # random initial position (default) sq2fr(sq,B) # validate initial sq if type(tbrk) == "procedure" then
B.tiebreak := tbrk # override tie-breaker
if \debug then write("Debug log : move#, move : (accessibility) choices")
choices := [] # setup to track moves and choices every (movesto := table())[k := key(B.movesto)] := copy(B.movesto[k])
B.tour := [] # new tour repeat {
put(B.tour,sq) # record move ac := 9 # accessibility counter > maximum while get(choices) # empty choices for tiebreak every delete(movesto[nextsq := !movesto[sq]],sq) do { # make sq unavailable if ac >:= *movesto[nextsq] then # reset to lower accessibility count while get(choices) # . re-empty choices if ac = *movesto[nextsq] then put(choices,nextsq) # keep least accessible sq and any ties } if \debug then { # move#, move, (accessibility), choices writes(sprintf("%d. %s : (%d) ",*B.tour,sq,ac)) every writes(" ",!choices|"\n") } sq := B.tiebreak(choices,B) | break # choose next sq until out of choices }
return B end
procedure RandomTieBreaker(S,B) # random choice return ?S end
procedure FirstTieBreaker(S,B) # first one in the list return !S end
procedure RothTieBreaker(S,B) # furthest from the center if *S = 0 then fail # must fail if [] every fr := sq2fr(s := !S,B) do {
d := sqrt(abs(fr[1]-1 - (B.N-1)*0.5)^2 + abs(fr[2]-1 - (B.N-1)*0.5)^2) if (/md := d) | ( md >:= d) then msq := s # save sq }
return msq end
record board(N,ranks,files,movesto,tiebreak,tour) # structure for board
procedure Board(N) #: create board N := *&lcase >=( 0 < integer(N)) | stop("N=",image(N)," is out of range.") B := board(N,[],&lcase[1+:N],table(),RandomTieBreaker) # setup every put(B.ranks,N to 1 by -1) # add rank #s every sq := !B.files || !B.ranks do # for each sq add
every insert(B.movesto[sq] := set(), KnightMoves(sq,B)) # moves to next sq
return B end
procedure sq2fr(sq,B) #: return numeric file & rank f := find(sq[1],B.files) | runerr(205,sq) r := integer(B.ranks[sq[2:0]]) | runerr(205,sq) return [f,r] end
procedure KnightMoves(sq,B) #: generate all Kn accessible moves from sq fr := sq2fr(sq,B) every ( i := -2|-1|1|2 ) & ( j := -2|-1|1|2 ) do
if (abs(i)~=abs(j)) & (0<(ri:=fr[2]+i)<=B.N) & (0<(fj:=fr[1]+j)<=B.N) then suspend B.files[fj]||B.ranks[ri]
end
procedure ShowTour(B) #: show the tour write("Board size = ",B.N) write("Tour length = ",*B.tour) write("Tie Breaker = ",image(B.tiebreak))
every !(squares := list(B.N)) := list(B.N,"-") every fr := sq2fr(B.tour[m := 1 to *B.tour],B) do
squares[fr[2],fr[1]] := m
every (hdr1 := " ") ||:= right(!B.files,3) every (hdr2 := " +") ||:= repl((1 to B.N,"-"),3) | "-+"
every write(hdr1|hdr2) every r := 1 to B.N do {
writes(right(B.ranks[r],3)," |") every writes(right(squares[r,f := 1 to B.N],3)) write(" |",right(B.ranks[r],3)) }
every write(hdr2|hdr1|&null) end</lang>
The following can be used when debugging to validate the board structure and to image the available moves on the board. <lang Icon>procedure DumpBoard(B) #: Dump Board internals write("Board size=",B.N) write("Available Moves at start of tour:", ImageMovesTo(B.movesto)) end
procedure ImageMovesTo(movesto) #: image of available moves every put(K := [],key(movesto)) every (s := "\n") ||:= (k := !sort(K)) || " : " do
every s ||:= " " || (!sort(movesto[k])|"\n")
return s end</lang>
Sample output:
Board size = 8 Tour length = 64 Tie Breaker = procedure RandomTieBreaker a b c d e f g h +-------------------------+ 8 | 53 10 29 26 55 12 31 16 | 8 7 | 28 25 54 11 30 15 48 13 | 7 6 | 9 52 27 62 47 56 17 32 | 6 5 | 24 61 38 51 36 45 14 49 | 5 4 | 39 8 63 46 57 50 33 18 | 4 3 | 64 23 60 37 42 35 44 3 | 3 2 | 7 40 21 58 5 2 19 34 | 2 1 | 22 59 6 41 20 43 4 1 | 1 +-------------------------+ a b c d e f g h
Two 7x7 boards:
Board size = 7 Tour length = 33 Tie Breaker = procedure RandomTieBreaker a b c d e f g +----------------------+ 7 | 33 4 15 - 29 6 17 | 7 6 | 14 - 30 5 16 - 28 | 6 5 | 3 32 - - - 18 7 | 5 4 | - 13 - 31 - 27 - | 4 3 | 23 2 - - - 8 19 | 3 2 | 12 - 24 21 10 - 26 | 2 1 | 1 22 11 - 25 20 9 | 1 +----------------------+ a b c d e f g Board size = 7 Tour length = 49 Tie Breaker = procedure RothTieBreaker a b c d e f g +----------------------+ 7 | 35 14 21 46 7 12 9 | 7 6 | 20 49 34 13 10 23 6 | 6 5 | 15 36 45 22 47 8 11 | 5 4 | 42 19 48 33 40 5 24 | 4 3 | 37 16 41 44 27 32 29 | 3 2 | 18 43 2 39 30 25 4 | 2 1 | 1 38 17 26 3 28 31 | 1 +----------------------+ a b c d e f g
J
Solution:
The Knight's tour essay on the Jwiki shows a couple of solutions including one using Warnsdorffs algorithm.
<lang j>NB. knight moves for each square of a (y,y) board
kmoves=: monad define
t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1 (*./"1 t e. i.y) <@#"1 y#.t
)
ktourw=: monad define
M=. >kmoves y p=. k=. 0 b=. 1 $~ *:y for. i.<:*:y do. b=. 0 k}b p=. p,k=. ((i.<./) +/"1 b{~j{M){j=. ({&b # ]) k{M end. assert. ~:p (,~y)$/:p
)</lang>
Example Use: <lang j> ktourw 8 NB. solution for an 8 x 8 board
0 25 14 23 28 49 12 31
15 22 27 50 13 30 63 48 26 1 24 29 62 59 32 11 21 16 51 58 43 56 47 60
2 41 20 55 52 61 10 33
17 38 53 42 57 44 7 46 40 3 36 19 54 5 34 9 37 18 39 4 35 8 45 6
9!:37]0 64 4 4 NB. truncate lines longer than 64 characters and only show first and last four lines
ktourw 202 NB. 202x202 board -- this implementation failed for 200 and 201 0 401 414 405 398 403 424 417 396 419 43... 413 406 399 402 425 416 397 420 439 430 39... 400 1 426 415 404 423 448 429 418 437 4075... 409 412 407 446 449 428 421 440 40739 40716 43...
...
550 99 560 569 9992 779 786 773 10002 9989 78... 555 558 553 778 563 570 775 780 785 772 1000... 100 551 556 561 102 777 572 771 104 781 57... 557 554 101 552 571 562 103 776 573 770 10...</lang>
Perl
Knight's tour using Warnsdorffs algorithm <lang perl>use strict; use warnings;
- Find a knight's tour
my @board;
- Choose starting position - may be passed in on command line; if
- not, choose random square.
my ($i, $j); if (my $sq = shift @ARGV) {
die "$0: illegal start square '$sq'\n" unless ($i, $j) = from_algebraic($sq);
} else {
($i, $j) = (int rand 8, int rand 8);
}
- Move sequence
my @moves = ();
foreach my $move (1..64) {
# Record current move push @moves, to_algebraic($i,$j); $board[$i][$j] = $move++;
# Get list of possible next moves my @targets = possible_moves($i,$j);
# Find the one with the smallest degree my @min = (9); foreach my $target (@targets) { my ($ni, $nj) = @$target; my $next = possible_moves($ni,$nj); @min = ($next, $ni, $nj) if $next < $min[0]; }
# And make it ($i, $j) = @min[1,2];
}
- Print the move list
for (my $i=0; $i<4; ++$i) {
for (my $j=0; $j<16; ++$j) { my $n = $i*16+$j; print $moves[$n]; print ', ' unless $n+1 >= @moves; } print "\n";
} print "\n";
- And the board, with move numbers
for (my $i=0; $i<8; ++$i) {
for (my $j=0; $j<8; ++$j) { # Assumes (1) ANSI sequences work, and (2) output # is light text on a dark background. print "\e[7m" if ($i%2==$j%2); printf " %2d", $board[$i][$j]; print "\e[0m"; } print "\n";
}
- Find the list of positions the knight can move to from the given square
sub possible_moves {
my ($i, $j) = @_; return grep { $_->[0] >= 0 && $_->[0] < 8 && $_->[1] >= 0 && $_->[1] < 8 && !$board[$_->[0]][$_->[1]] } ( [$i-2,$j-1], [$i-2,$j+1], [$i-1,$j-2], [$i-1,$j+2], [$i+1,$j-2], [$i+1,$j+2], [$i+2,$j-1], [$i+2,$j+1]);
}
- Return the algebraic name of the square identified by the coordinates
- i=rank, 0=black's home row; j=file, 0=white's queen's rook
sub to_algebraic {
my ($i, $j) = @_; chr(ord('a') + $j) . (8-$i);
}
- Return the coordinates matching the given algebraic name
sub from_algebraic {
my $square = shift; return unless $square =~ /^([a-h])([1-8])$/; return (8-$2, ord($1) - ord('a'));
}</lang>
Sample output (start square c3):
Perl 6
<lang perl6>my @board;
my $I = 8; my $J = 8; my $F = $I*$J > 99 ?? "%3d" !! "%2d";
- Choose starting position - may be passed in on command line; if
- not, choose random square.
my ($i, $j);
if my $sq = shift @*ARGS {
die "$*PROGRAM_NAME: illegal start square '$sq'\n" unless ($i, $j) = from_algebraic($sq);
} else {
($i, $j) = (^$I).pick, (^$J).pick;
}
- Move sequence
my @moves = ();
for 1 .. $I * $J -> $move {
# Record current move push @moves, to_algebraic($i,$j); # @board[$i] //= []; # (uncomment if autoviv is broken) @board[$i][$j] = $move; # Find move with the smallest degree my @min = (9); for possible_moves($i,$j) -> @target { my ($ni, $nj) = @target; my $next = possible_moves($ni,$nj); @min = $next, $ni, $nj if $next < @min[0]; } # And make it ($i, $j) = @min[1,2];
}
- Print the move list
for @moves.kv -> $i, $m {
print ',', $i %% 16 ?? "\n" !! " " if $i; print $m;
} say "\n";
- And the board, with move numbers
for ^$I -> $i {
for ^$J -> $j { # Assumes (1) ANSI sequences work, and (2) output # is light text on a dark background. print "\e[7m" if $i % 2 == $j % 2; printf $F, @board[$i][$j]; print "\e[0m"; } print "\n";
}
- Find the list of positions the knight can move to from the given square
sub possible_moves($i,$j) {
grep -> [$ni, $nj] { $ni ~~ ^$I and $nj ~~ ^$J and !@board[$ni][$nj] }, [$i-2,$j-1], [$i-2,$j+1], [$i-1,$j-2], [$i-1,$j+2], [$i+1,$j-2], [$i+1,$j+2], [$i+2,$j-1], [$i+2,$j+1];
}
- Return the algebraic name of the square identified by the coordinates
- i=rank, 0=black's home row; j=file, 0=white's queen's rook
sub to_algebraic($i,$j) {
chr(ord('a') + $j) ~ ($I - $i);
}
- Return the coordinates matching the given algebraic name
sub from_algebraic($square where /^ (<[a..z]>) (\d+) $/) {
$I - $1, ord(~$0) - ord('a');
}</lang> (Output identical to Perl's above.)
PicoLisp
<lang PicoLisp>(load "@lib/simul.l")
- Build board
(grid 8 8)
- Generate legal moves for a given position
(de moves (Tour)
(extract '((Jump) (let? Pos (Jump (car Tour)) (unless (memq Pos Tour) Pos ) ) ) (quote # (taken from "games/chess.l") ((This) (: 0 1 1 0 -1 1 0 -1 1)) # South Southwest ((This) (: 0 1 1 0 -1 1 0 1 1)) # West Southwest ((This) (: 0 1 1 0 -1 -1 0 1 1)) # West Northwest ((This) (: 0 1 1 0 -1 -1 0 -1 -1)) # North Northwest ((This) (: 0 1 -1 0 -1 -1 0 -1 -1)) # North Northeast ((This) (: 0 1 -1 0 -1 -1 0 1 -1)) # East Northeast ((This) (: 0 1 -1 0 -1 1 0 1 -1)) # East Southeast ((This) (: 0 1 -1 0 -1 1 0 -1 1)) ) ) ) # South Southeast
- Build a list of moves, using Warnsdorff’s algorithm
(let Tour '(b1) # Start at b1
(while (mini '((P) (length (moves (cons P Tour)))) (moves Tour) ) (push 'Tour @) ) (flip Tour) )</lang>
Output:
-> (b1 a3 b5 a7 c8 b6 a8 c7 a6 b8 d7 f8 h7 g5 h3 g1 e2 c1 a2 b4 c2 a1 b3 a5 b7 d8 c6 d4 e6 c5 a4 c3 d1 b2 c4 d2 f1 h2 f3 e1 d3 e5 f7 h8 g6 h4 g2 f4 d5 e7 g8 h6 g4 e3 f5 d6 e8 g7 h5 f6 e4 g3 h1 f2)
PostScript
You probably shouldn't send this to a printer. Solution using Warnsdorffs algorithm. <lang postscript>%!PS-Adobe-3.0 %%BoundingBox: 0 0 300 300
/s { 300 n div } def /l { rlineto } def
% draws a square /bx { s mul exch s mul moveto s 0 l 0 s l s neg 0 l 0 s neg l } def
% draws checker board /xbd { 1 setgray
0 0 moveto 300 0 l 0 300 l -300 0 l fill .7 1 .6 setrgbcolor 0 1 n1 { dup 2 mod 2 n1 { 1 index bx fill } for pop } for 0 setgray
} def
/ar1 { [ exch { 0 } repeat ] } def /ar2 { [ exch dup { dup ar1 exch } repeat pop ] } def
/neighbors {
-1 2 0 1 2 0 2 1 0 2 -1 0 1 -2 0 -1 -2 0 -2 -1 0 -2 1 0 %24 x y add 3 mul roll
} def
/func { 0 dict begin mark } def /var { counttomark -1 1 { 2 add -1 roll def } for cleartomark } def
% x y can_goto -> bool /can_goto {
func /x /y var x 0 ge x n lt y 0 ge y n lt and and and { occupied x get y get 0 eq } { false } ifelse end
} def
% x y num_access -> number of cells reachable from (x,y) /num_access {
func /x /y var /count 0 def x y can_goto { neighbors 8 { pop y add exch x add exch can_goto { /count count 1 add def } if } repeat count 0 gt { count } { 9 } ifelse } { 10 } ifelse end
} def
% a circle /marker { x s mul y s mul s 20 div 0 360 arc fill } def
% n solve -> draws board of size n x n, calcs path and draws it /solve {
func /n var /n1 n 1 sub def
/c false def
8 n div setlinewidth gsave
0 1 n1 { /x exch def c not { 0 1 n1 { /occupied n ar2 def c not { /c true def /y exch def grestore xbd gsave s 2 div dup translate n n mul 2 sub -1 0 { /iter exch def c { 0 setgray marker x s mul y s mul moveto occupied x get y 1 put neighbors 8 { pop y add exch x add exch 2 copy num_access 24 3 roll } repeat 7 { dup 4 index lt { 6 3 roll } if pop pop pop } repeat
9 ge iter 0 gt and { /c false def } if /y exch def /x exch def .2 setgray x s mul y s mul lineto stroke } if } for % to be nice, draw box at final position .5 0 0 setrgbcolor marker y .5 sub x .5 sub bx 1 setlinewidth stroke stroke } if } for } if } for showpage grestore end
} def
3 1 100 { solve } for
%%EOF</lang>
Prolog
Worlks with SWI-Prolog.
Knights tour using Warnsdorffs algorithm
<lang Prolog>% N is the number of lines of the chessboard knight(N) :- Max is N * N, length(L, Max), knight(N, 0, Max, 0, 0, L), display(N, 0, L).
% knight(NbCol, Coup, Max, Lig, Col, L), % NbCol : number of columns per line % Coup : number of the current move % Max : maximum number of moves % Lig/ Col : current position of the knight % L : the "chessboard"
% the game is over knight(_, Max, Max, _, _, _) :- !.
knight(NbCol, N, MaxN, Lg, Cl, L) :- % Is the move legal Lg >= 0, Cl >= 0, Lg < NbCol, Cl < NbCol,
Pos is Lg * NbCol + Cl, N1 is N+1, % is the place free nth0(Pos, L, N1),
LgM1 is Lg - 1, LgM2 is Lg - 2, LgP1 is Lg + 1, LgP2 is Lg + 2, ClM1 is Cl - 1, ClM2 is Cl - 2, ClP1 is Cl + 1, ClP2 is Cl + 2, maplist(best_move(NbCol, L), [(LgP1, ClM2), (LgP2, ClM1), (LgP2, ClP1),(LgP1, ClP2), (LgM1, ClM2), (LgM2, ClM1), (LgM2, ClP1),(LgM1, ClP2)], R), sort(R, RS), pairs_values(RS, Moves),
move(NbCol, N1, MaxN, Moves, L).
move(NbCol, N1, MaxN, [(Lg, Cl) | R], L) :- knight(NbCol, N1, MaxN, Lg, Cl, L); move(NbCol, N1, MaxN, R, L).
%% An illegal move is scored 1000 best_move(NbCol, _L, (Lg, Cl), 1000-(Lg, Cl)) :- ( Lg < 0 ; Cl < 0; Lg >= NbCol; Cl >= NbCol), !.
best_move(NbCol, L, (Lg, Cl), 1000-(Lg, Cl)) :- Pos is Lg*NbCol+Cl, nth0(Pos, L, V), \+var(V), !.
%% a legal move is scored with the number of moves a knight can make best_move(NbCol, L, (Lg, Cl), R-(Lg, Cl)) :- LgM1 is Lg - 1, LgM2 is Lg - 2, LgP1 is Lg + 1, LgP2 is Lg + 2, ClM1 is Cl - 1, ClM2 is Cl - 2, ClP1 is Cl + 1, ClP2 is Cl + 2, include(possible_move(NbCol, L), [(LgP1, ClM2), (LgP2, ClM1), (LgP2, ClP1),(LgP1, ClP2), (LgM1, ClM2), (LgM2, ClM1), (LgM2, ClP1),(LgM1, ClP2)], Res), length(Res, Len), ( Len = 0 -> R = 1000; R = Len).
% test if a place is enabled possible_move(NbCol, L, (Lg, Cl)) :- % move must be legal Lg >= 0, Cl >= 0, Lg < NbCol, Cl < NbCol, Pos is Lg * NbCol + Cl, % place must be free nth0(Pos, L, V), var(V).
display(_, _, []).
display(N, N, L) :-
nl,
display(N, 0, L).
display(N, M, [H | T]) :- writef('%3r', [H]), M1 is M + 1, display(N, M1, T). </lang>
Python
Knights tour using Warnsdorffs algorithm <lang python>import copy
boardsize=6 _kmoves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))
def chess2index(chess, boardsize=boardsize):
'Convert Algebraic chess notation to internal index format' chess = chess.strip().lower() x = ord(chess[0]) - ord('a') y = boardsize - int(chess[1:]) return (x, y)
def boardstring(board, boardsize=boardsize):
r = range(boardsize) lines = for y in r: lines += '\n' + ','.join('%2i' % board[(x,y)] if board[(x,y)] else ' ' for x in r) return lines
def knightmoves(board, P, boardsize=boardsize):
Px, Py = P kmoves = set((Px+x, Py+y) for x,y in _kmoves) kmoves = set( (x,y) for x,y in kmoves if 0 <= x < boardsize and 0 <= y < boardsize and not board[(x,y)] ) return kmoves
def accessibility(board, P, boardsize=boardsize):
access = [] brd = copy.deepcopy(board) for pos in knightmoves(board, P, boardsize=boardsize): brd[pos] = -1 access.append( (len(knightmoves(brd, pos, boardsize=boardsize)), pos) ) brd[pos] = 0 return access
def knights_tour(start, boardsize=boardsize, _debug=False):
board = {(x,y):0 for x in range(boardsize) for y in range(boardsize)} move = 1 P = chess2index(start, boardsize) board[P] = move move += 1 if _debug: print(boardstring(board, boardsize=boardsize)) while move <= len(board): P = min(accessibility(board, P, boardsize))[1] board[P] = move move += 1 if _debug: print(boardstring(board, boardsize=boardsize)) input('\n%2i next: ' % move) return board
if __name__ == '__main__':
while 1: boardsize = int(input('\nboardsize: ')) if boardsize < 5: continue start = input('Start position: ') board = knights_tour(start, boardsize) print(boardstring(board, boardsize=boardsize))</lang>
- Sample runs
boardsize: 5 Start position: c3 19,12,17, 6,21 2, 7,20,11,16 13,18, 1,22, 5 8, 3,24,15,10 25,14, 9, 4,23 boardsize: 8 Start position: h8 38,41,18, 3,22,27,16, 1 19, 4,39,42,17, 2,23,26 40,37,54,21,52,25,28,15 5,20,43,56,59,30,51,24 36,55,58,53,44,63,14,29 9, 6,45,62,57,60,31,50 46,35, 8,11,48,33,64,13 7,10,47,34,61,12,49,32 boardsize: 10 Start position: e6 29, 4,57,24,73, 6,95,10,75, 8 58,23,28, 5,94,25,74, 7,100,11 3,30,65,56,27,72,99,96, 9,76 22,59, 2,63,68,93,26,81,12,97 31,64,55,66, 1,82,71,98,77,80 54,21,60,69,62,67,92,79,88,13 49,32,53,46,83,70,87,42,91,78 20,35,48,61,52,45,84,89,14,41 33,50,37,18,47,86,39,16,43,90 36,19,34,51,38,17,44,85,40,15 boardsize: 200 Start position: a1 510,499,502,101,508,515,504,103,506,5021 ... 195,8550,6691,6712,197,6704,201,6696,199 501,100,509,514,503,102,507,5020,5005,10 ... 690,6713,196,8553,6692,6695,198,6703,202 498,511,500,4989,516,5019,5004,505,5022, ... ,30180,8559,6694,6711,8554,6705,200,6697 99,518,513,4992,5003,4990,5017,5044,5033 ... 30205,8552,30181,8558,6693,6702,203,6706 512,497,4988,517,5018,5001,5034,5011,504 ... 182,30201,30204,8555,6710,8557,6698,6701 519,98,4993,5002,4991,5016,5043,5052,505 ... 03,30546,30183,30200,30185,6700,6707,204 496,4987,520,5015,5000,5035,5012,5047,51 ... 4,30213,30202,31455,8556,6709,30186,6699 97,522,4999,4994,5013,5042,5051,5060,505 ... 7,31456,31329,30184,30199,30190,205,6708 4986,495,5014,521,5036,4997,5048,5101,50 ... 1327,31454,30195,31472,30187,30198,30189 523,96,4995,4998,5041,5074,5061,5050,507 ... ,31330,31471,31328,31453,30196,30191,206 ... 404,731,704,947,958,1013,966,1041,1078,1 ... 9969,39992,39987,39996,39867,39856,39859 5,706,735,960,955,972,957,1060,1025,106 ... ,39978,39939,39976,39861,39990,297,39866 724,403,730,705,946,967,1012,971,1040,10 ... 9975,39972,39991,39868,39863,39860,39855 707, 4,723,736,729,956,973,996,1061,1026 ... ,39850,39869,39862,39973,39852,39865,298 402,725,708,943,968,945,970,1011,978,997 ... 6567,39974,39851,39864,36571,39854,36573 3,722,737,728,741,942,977,974,995,1010, ... ,39800,39849,36570,39853,36574,299,14088 720,401,726,709,944,969,742,941,980,975, ... ,14091,36568,36575,14084,14089,36572,843 711, 2,721,738,727,740,715,976,745,940,9 ... 65,36576,14083,14090,36569,844,14087,300 400,719,710,713,398,717,746,743,396,981, ... ,849,304,14081,840,847,302,14085,842,845 1,712,399,718,739,714,397,716,747,744,3 ... 4078,839,848,303,14082,841,846,301,14086
The 200x200 example warmed my study in its computation but did return a tour.
P.S. There is a slight deviation to a strict interpretation of Warnsdorffs algorithm in that as a conveniance, tuples of the length of the night moves followed by the position are minimized so knights moves with the same length will try and break the ties based on their minimum x,y position. In practice, it seems to give comparable results to the original algorithm.
Tcl
<lang tcl>package require Tcl 8.6; # For object support, which makes coding simpler
oo::class create KnightsTour {
variable width height visited
constructor {{w 8} {h 8}} {
set width $w set height $h set visited {}
}
method ValidMoves {square} {
lassign $square c r set moves {} foreach {dx dy} {-1 -2 -2 -1 -2 1 -1 2 1 2 2 1 2 -1 1 -2} { set col [expr {($c % $width) + $dx}] set row [expr {($r % $height) + $dy}] if {$row >= 0 && $row < $height && $col >=0 && $col < $width} { lappend moves [list $col $row] } } return $moves
}
method CheckSquare {square} {
set moves 0 foreach site [my ValidMoves $square] { if {$site ni $visited} { incr moves } } return $moves
}
method Next {square} {
set minimum 9 set nextSquare {-1 -1} foreach site [my ValidMoves $square] { if {$site ni $visited} { set count [my CheckSquare $site] if {$count < $minimum} { set minimum $count set nextSquare $site } elseif {$count == $minimum} { set nextSquare [my Edgemost $nextSquare $site] } } } return $nextSquare
}
method Edgemost {a b} {
lassign $a ca ra lassign $b cb rb # Calculate distances to edge set da [expr {min($ca, $width - 1 - $ca, $ra, $height - 1 - $ra)}] set db [expr {min($cb, $width - 1 - $cb, $rb, $height - 1 - $rb)}] if {$da < $db} {return $a} else {return $b}
}
method FormatSquare {square} {
lassign $square c r format %c%d [expr {97 + $c}] [expr {1 + $r}]
}
method constructFrom {initial} {
while 1 { set visited [list $initial] set square $initial while 1 { set square [my Next $square] if {$square eq {-1 -1}} { 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