• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Knight's tour

 
author
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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)
 
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Calculate the tour means,knight path (for e.g. board[0][0]-->board[2][1]-- etc) should be the expected output from the program,Am I right?
 
Ranch Hand
Posts: 1012
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 3451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Michael Morris
Ranch Hand
Posts: 3451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Should the Knight start at his home position, ie KKt1 or QKt1 or any position?
 
Greg Harris
Ranch Hand
Posts: 1012
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Author
Posts: 6055
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.)
 
Author
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have seen the answer for this in code. It is solvable. You can find in Data Structures texts. Just like the eight queens problem.
 
Mark Herschberg
Author
Posts: 6055
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Jim -
Welcome back from JavaOne !
I'm pretty sure it's a quarter...
-Bert
 
Michael Morris
Ranch Hand
Posts: 3451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 3451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[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
Posts: 3451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 4632
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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();
}
}
 
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
http://www.velucchi.it/mathchess/knight.htm

The Ultimate Knight's Tour Page of Links
 
Bert Bates
author
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
wow Robert,

You pulled this thread out of the archives
 
The moustache of a titan! The ad of a flea:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic