Knight's tour: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added C++ version)
(Added Perl implementation.)
Line 212: Line 212:
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
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>
</pre>
=={{header|Perl}}==
Knight's tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]]
<lang perl># Find a knight's tour

# The map ensures that each row gets its own array,
# rather than all being references to a single one.
my @board = map { [ @{[ @$_ ]} ] } ( [ (0) x 8 ] ) x 8;

# 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])$/;
$j = ord($1) - ord('a'); $i = 8 - $2;
return ($i, $j);
}</lang>


=={{header|Python}}==
=={{header|Python}}==

Revision as of 02:12, 30 May 2011

Knight's tour is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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++

Works with: C++0x

Uses Warnsdorff's rule and (iterative) backtracking if that fails.

<lang cpp>#include <iostream>

  1. include <iomanip>
  2. include <array>
  3. include <string>
  4. 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

Perl

Knight's tour using Warnsdorffs algorithm <lang perl># Find a knight's tour

  1. The map ensures that each row gets its own array,
  2. rather than all being references to a single one.

my @board = map { [ @{[ @$_ ]} ] } ( [ (0) x 8 ] ) x 8;

  1. Choose starting position - may be passed in on command line; if
  2. 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);

}

  1. 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];

}

  1. 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";

  1. 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";

}

  1. 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]);

}

  1. Return the algebraic name of the square identified by the coordinates
  2. 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);

}

  1. Return the coordinates matching the given algebraic name

sub from_algebraic { 

  my $square = shift;
  return unless $square =~ /^([a-h])([1-8])$/;
  $j = ord($1) - ord('a'); $i = 8 - $2; 
  return ($i, $j);

}</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): 

   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
Retrieved from "https://rosettacode.org/wiki/Knight%27s_tour?oldid=183295"