Sheriff

The idea is for a chess - knight to start on one square of the 8 x 8 board and to travel the entire board in 63 moves, landing on each square once. (For non-chess players, knights move in an 'L' shape, 2 squares vertically or horizontally, then 1 square left or right. A knight in the middle of the board can make 8 moves)

Anyway - there is a fairly simple and elegant way to calculate a knight's tour - the puzzle is to describe the simple solution in high level design terms...

(if you're bored you could actually code it up)

Spot false dilemmas now, ask me how!

(If you're not on the edge, you're taking up too much room.)

MH

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

Sheriff

You can start anywhere on the board, and yes a list of positions traveled is correct.

Also - there are millions of solutions!

Michael - wow - my first computer job was as an operator and programmer using an IBM 1130 - mostly FORTRAN some COBOL - 1974, yikes!

Another clue - this 'elegant' solution is MUCH faster than most 'normal' solutions I've seen.

[ June 06, 2003: Message edited by: Bert Bates ]

Spot false dilemmas now, ask me how!

(If you're not on the edge, you're taking up too much room.)

Originally posted by Greg Harris:

all you have to do is look at the chess board as a graph and find a hamiltonian path.

Yep hamiltonian path seems like the right way to model it. My guess is, if you're smart, you can make use of the symmetry inherent in the board to reduce the problem to half or maybe even a quarter of its size.

--Mark

Sheriff

**My guess is, if you're smart, you can make use of the symmetry inherent in the board to reduce the problem to half or maybe even a quarter of its size.**

An eighth, I think, considering both reflections and rotations. Consider only these starting points:

If the first move is on the diagonal, then require that the second move be somewhere in the lower right half of the board, to break the symmetry. (If it were possible to make two consecutive moves on the same diagonal this would require further elaboration, but with knight's move this is not an issue.)

"I'm not back." - Bill Harding, *Twister*

Ranch Hand

Author and Instructor, my book

Originally posted by Jim Yingst:

My guess is, if you're smart, you can make use of the symmetry inherent in the board to reduce the problem to half or maybe even a quarter of its size.

An eighth, I think, considering both reflections and rotations.

Are you sure it's an eighth? I had considered that, but was under the impression the pattern was not that small. Although I guess maybe with rotations. But it's not clear that rotations count; otherwise every knights move is a rotation of any other one. Hmm, that's not quite right, but something says it's more of a stretch to get the pattern down to an eight.

--Mark

Sheriff

Time is short at the moment, so if you want further justification of my claims, we can argue over a beer in a few days.

"I'm not back." - Bill Harding, *Twister*

Sheriff

Originally posted by Bert Bates:

Jim -

Welcome back from JavaOne !

I'm pretty sure it's a quarter...

-Bert

Bert Bates you are an evil dude for posting this obsessive problem. I've been working on an approach that divides the board into quadrants. I wrote a routine to run all combinations from any size board (of course on an 8x8 you will get the expected OutOfMemory error after about fifteen minutes of processing). For a 4x4 I discovered that you can clear 15 of 16 when starting from any of the outer squares and 14 of 16 from any interior square. Clearing 15 squares in each quadrant before moving to the next will always fail because you will paint yourself into a corner when coming back to pickup the missed squares in each quadrant. I'm now trying to figure a generic way to strategically place missed squares per quadrant so that at the end the knight will have a way to pick them up.

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

**Key: %=starting square, O=covered square, X=missed square, *=ending square**

I'm assuming that these patterns are symmetrical both horizontally and vertically, so that we only need to check the lower four positions.

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

Sheriff

Sheriff

**[MH]: Are you sure it's an eighth?**

[BB]: I'm pretty sure it's a quarter...

[MM]: I'm assuming that these patterns are symmetrical both horizontally and vertically, so that we only need to check the lower four positions.

[BB]: I'm pretty sure it's a quarter...

[MM]: I'm assuming that these patterns are symmetrical both horizontally and vertically, so that we only need to check the lower four positions.

Unbelievers! You doubt my word? Actually I doubted it slightly above when I amended 1/8 to 10/64; I am now going back to the original 1/8 figure. It turns out that for first moves on the diagonal, you can do half as much work as for first moves off the diaganal, because half the solutions will be diagonal reflections of the other half.

As an example, let's consider solutions which begin with three particular moves, indicated here:

For every solution that fits this pattern, I can create three other equivalent solutions by horizontal and vertical reflection. I will call these patterns P1, P2, P3, P4:

Additionally, I can rotate the original pattern 90 degrees clockwise:

And then create 3 more patterns via reflection:

This gives us a total of 8 "unique" patterns with are actually equivalent to the one original. (Errr... well one of them

*is*the original.) Other combinations of reflection and rotation will end up duplicating one of the patterns already listed. E.g. if we rotate P1 180 degrees, that's actually equivalent to one horizontal reflection plus one vertical reflection - which is P4. Or rotating 90 degrees

*counterclockwise*is equivalent to rotating 90 degrees clockwise and then reflecting once horizonatally and once vertically - which is P8. Or I could have generated some of these patterns by reflecting across one of the diagonals rather than horizontally or vertically, but again, these are always equivalent to other combinations already stated. E.g. reflecting P1 across the diagonal from upper left to lower right is the same as rotating 90 degrees clockwise and then reflecting vertically, which gets P6. Reflecting P1 across the other diagonal gets P7.

I will stop short of attemting to demonstrate rigorously that there are

*only*8 equivalent variations for any given pattern (though I'm confident it's true.) I guarantee though that given any one solution to the knight's tour problem, it's simple to generate 7 others by combinations of reflection and rotation as described above; thus it's possible to reduce the total work in this problem by a factor of 1/8 by considering only a certain subset of solutions (e.g. as detailed in my first post).

"I'm not back." - Bill Harding, *Twister*

Sheriff

Anyway, here's some code for y'all. It's a simple brute-force algorithm except that it takes advantage of the symmetries previously discussed to reduce the workload by 1/8.

I'm assuming the JIT will do a decent job of inlining method calls; if not we can always do that manually. Also there's some room for minor optimizations rearranging some of the code in isValidMove() and considerSubsequentMovesFrom() to reduce the total number of checks that need to be made - but that seemed to interfere too much with readability so I ignored it for now. There are probably much more significant algorithmic improvements possible; I haven't checked the literature.

Note that you can specify the board size - there are no solutions for boards smaller than 5 x 5, and no solutions which start from the center square until you look at 7 x 7. (I put those first so we'd see them - otherwise we'd wait forever and a day for all the other solutions to be generated first.) We can easily see a complete set of solutions for the 5 x 5 board. For everything else - well, even 36! (for 6x6) is a really big number, and for the 8x8 64! is well beyond my patience to see a complete list. I'm not surprised at how long it takes to look at the whole tree (or 1/8 of it anyway), but I am surpised at how many valid solutions there actually are within that tree.

"I'm not back." - Bill Harding, *Twister*

1,11,5,15,21,4,10,0,17,2,8,18,3,9,19,13,7,22,12,6,23,29,14,20,26,16,33,27,37,31,46,36,30,45,39,54,44,59,49,32,42,48,58,43,60,50,56,41,24,34,28,38,55,61,51,57,40,25,35,52,62,47,53,63

I hope I have the code tags right, this time.

My friend did it not me!

public class KnightsTour {

static int board [][] = new int [9][9];

static int access [][] = new int [9][9];

static int count = 1, num = 1, min;

static int rowT, colT, row = 1, col = 1;

static boolean done;

public static void main (String[] args) {

fillArray();

board[1][1] = count;

access[1][1] = 100;

while (count <= 64) {

min = -1;

count++;

int move = findAccess();

if (!done) {

go(move);

minusAccess(move);

}

}

print();

}

static void fillArray() {

int temp;

TextReader inFile = new TextReader("access.txt");

for (int r = 1; r < 9; r++) {

for (int c = 1; c < 9; c++) {

temp = inFile.readInt();

access[r][c] = temp;

}

}

}

static int findAccess() {

done = false;

int temp = 9, move = 0;

for (int num = 1; num < 9; num++) {

switch (num) {

case 1: rowT = -2; colT = -1; break;

case 2: rowT = -2; colT = 1; break;

case 3: rowT = -1; colT = -2; break;

case 4: rowT = -1; colT = 2; break;

case 5: rowT = 2; colT = 1; break;

case 6: rowT = 2; colT = -1; break;

case 7: rowT = 1; colT = -2; break;

case 8: rowT = 1; colT = 2; break;

default: break;

}

row = row + rowT;

col = col + colT;

if (row < 9 && row > 0 && col < 9 && col > 0) {

if (access[row][col] <= temp) {

min = access[row][col];

temp = min;

move = num;

}

else if (access[row][col] == temp)

min = temp;

done = false;

}

if (min == -1) {

done = true;

}

row = row - rowT;

col = col - colT;

}

return move;

}

static void go (int move) {

switch (move) {

case 1: rowT = -2; colT = -1; break;

case 2: rowT = -2; colT = 1; break;

case 3: rowT = -1; colT = -2; break;

case 4: rowT = -1; colT = 2; break;

case 5: rowT = 2; colT = 1; break;

case 6: rowT = 2; colT = -1; break;

case 7: rowT = 1; colT = -2; break;

case 8: rowT = 1; colT = 2; break;

default: break;

}

row += rowT;

col += colT;

board[row][col] = count;

access[row][col] = 100;

return;

}

static void minusAccess (int move) {

for (int num = 1; num < 9; num++) {

switch (num) {

case 1: rowT = -2; colT = -1; break;

case 2: rowT = -2; colT = 1; break;

case 3: rowT = -1; colT = -2; break;

case 4: rowT = -1; colT = 2; break;

case 5: rowT = 2; colT = 1; break;

case 6: rowT = 2; colT = -1; break;

case 7: rowT = 1; colT = -2; break;

case 8: rowT = 1; colT = 2; break;

default: break;

}

row += rowT;

col += colT;

if (row < 9 && row > 0 && col < 9 && col > 0)

access[row][col]--;

row -= rowT;

col -= colT;

}

return;

}

static void print() {

for (int x = 0; x < board.length; x++){

if (x == 0){

for (int z = 0; z <= board[0].length-1; z++){

if (z == 0)

System.out.print(Format.right (" ", 4));

else

System.out.print(Format.right (z, 4));

}

System.out.println("\n");

for (int k = 1; k <= board[0].length; k++){

if (k == 1)

System.out.print(Format.right (" ", 4));

else

System.out.print(Format.right ("_", 4));

}

System.out.println("\n");

}

else {

System.out.print(Format.right(x+"|", 4));

for (int y = 1; y < board[x].length; y++)

System.out.print(Format.right(board[x][y],4));

System.out.print(" |");

System.out.println("\n\n");

}

}

for(int i=0;i<=board.length-1;i++){

if(i==0)

System.out.print(Format.right (" ", 4));

else

System.out.print(Format.right("_",4));

}

System.out.println();

}

}

I started with nothing and have most of it left.

Don't get me started about those stupid light bulbs. |