Does everybody know about the 'knight's tour' ? 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.)

we did this in discrete math a couple years ago... too bad i do not have my notes with me. all you have to do is look at the chess board as a graph and find a hamiltonian path. i will see if i can find one without getting fired today.

We did this in 1973 on an IBM 1130 with, uggh, Fortran and punch cards. It would be interesting to see a pure OO solution.

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

Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451

posted

0

Should the Knight start at his home position, ie KKt1 or QKt1 or any position?

Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012

posted

0

we did it from any position... there are over 100 paths. however, i think there are a couple starting points that will not work.

Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8829

5

posted

0

Michael, Capablanca, et al, 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 ]

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

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.)

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

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

I'm pretty sure that the positions I showed are sufficient for starting positions. However I should have noted it's not exactly an 1/8 - there are 10 squares there, not 8, so it's 10/64 = 5/32. I overlooked the thickness of an edge, so to speak - the guys on the diagonal are half outside the triangle whose area is exactly 1/8 of the total. 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.

Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8829

5

posted

0

Jim - Welcome back from JavaOne ! I'm pretty sure it's a quarter... -Bert

Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451

posted

0

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.

Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451

posted

0

For anyone interested, here are the patterns I figured for a quadrant: 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.

Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8829

5

posted

0

Michael - I'm happy I was able to keep you off the streets for a while... Come on, ya gotta admit it's fun! -Bert

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

[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. 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).

Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451

posted

0

Hey Jimbo, was beginning to think you got lost on the way home from JavaOne or somethin' Anyway it's good to see ya back.

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

Hey, I never said I was coming directly back after JavaOne. I had planned to be gone a bit longer, but had to modify plans when the front fork of my mountain bike was stolen. Ah well... meeting the gang at JavaOne was a blast. 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.

Not sure if this is reasonable, it came up with this result in about 15 minutes (from square 1, 0-based) 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.

Well, Here it is...The knights tour in Java!: 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(); } }