Knight's tour: Difference between revisions
m (moved Knight's Tour to Knight's tour: Task naming rules: only first word is capitalised.) |
(Added C++ version) |
||
Line 9: | Line 9: | ||
;Cf. |
;Cf. |
||
* [[N-queens problem]] |
* [[N-queens problem]] |
||
=={{header|C++}}== |
|||
{{works with|C++0x}} |
|||
Uses Warnsdorff's rule and (iterative) backtracking if that fails. |
|||
<lang cpp>#include <iostream> |
|||
#include <iomanip> |
|||
#include <array> |
|||
#include <string> |
|||
#include <tuple> |
|||
using namespace std; |
|||
template<size_t N = 8> |
|||
class Board |
|||
{ |
|||
public: |
|||
array<array<int, N>, N> data; |
|||
array<pair<int, int>, 8> moves; |
|||
int sx, sy; |
|||
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) |
|||
{ |
|||
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); |
|||
} |
|||
random_shuffle(counts.begin(), counts.end()); // Shuffle to randomly break ties |
|||
sort(counts.begin(), counts.end()); // Lexicographic sort |
|||
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 x = start[0] - 'a'; |
|||
int y = N - (start[1] - '0'); |
|||
data[y][x] = 1; |
|||
sx = x; |
|||
sy = y; |
|||
array<tuple<int, int, int, array<int, 8>>, N*N> order; |
|||
order[0] = make_tuple(sx, sy, 0, sortMoves(sx, sy)); |
|||
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) |
|||
{ |
|||
get<2>(order[n]) = i+1; |
|||
++n; |
|||
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; |
|||
Board<8> b2; |
|||
Board<31> b3; // Max size for <1000 squares |
|||
b1.solve("c3"); |
|||
cout << b1 << endl; |
|||
b2.solve("b5"); |
|||
cout << b2 << endl; |
|||
b3.solve("a1"); |
|||
cout << b3 << endl; |
|||
}</lang> |
|||
Output: |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 20:47, 29 May 2011
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.
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++
Uses Warnsdorff's rule and (iterative) backtracking if that fails.
<lang cpp>#include <iostream>
- include <iomanip>
- include <array>
- include <string>
- include <tuple>
using namespace std;
template<size_t N = 8> class Board { public:
array<array<int, N>, N> data; array<pair<int, int>, 8> moves; int sx, sy;
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) { 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); }
random_shuffle(counts.begin(), counts.end()); // Shuffle to randomly break ties sort(counts.begin(), counts.end()); // Lexicographic sort 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 x = start[0] - 'a'; int y = N - (start[1] - '0'); data[y][x] = 1; sx = x; sy = y;
array<tuple<int, int, int, array<int, 8>>, N*N> order; order[0] = make_tuple(sx, sy, 0, sortMoves(sx, sy));
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) { get<2>(order[n]) = i+1;
++n; 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; Board<8> b2; Board<31> b3; // Max size for <1000 squares
b1.solve("c3"); cout << b1 << endl;
b2.solve("b5"); cout << b2 << endl;
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
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):
knightmoves(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