Knight's Tour Problem

Twan
11-06-2006, 10:08 AM
Hi there everyone. I haven't been here in awhile but I recently came across a problem in computer science that I am looking for some guide in.

Here's my problem:
One of the more interesting puzzlers for chess buffs is the Knight’s Tour problem. The question is this: Can the chess piece called the knight move around an empty chessboard and touch each of the 64 squares once and only once? We study this intriguing problem in depth here.
The knight makes L-shaped moves (over two in one direction and then over one in a perpendicular direction). Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 through 7) as shown in Fig. 4.30 .

a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight’s Tour by hand. Put a 1 in the first square you move to, a 2 in the second square, a 3 in the third, etc. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. How far did you get? Was this close to your estimate?
b) Now let us develop a program that will move the knight around a chessboard. The board is represented by an 8-by-8 double-subscripted array board. Each of the squares is initialized to zero. We describe each of the eight possible moves in terms of both their horizontal and vertical components. For example, a move of type 0, as shown in Fig. 4.30 , consists of moving two squares horizontally to the right and one square vertically upward. Move 2 consists of moving one square horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The eight moves may be described by two single-subscripted arrays, horizontal and vertical, as follows:


horizontal[ 0 ] = 2
horizontal[ 1 ] = 1
horizontal[ 2 ] = -1
horizontal[ 3 ] = -2
horizontal[ 4 ] = -2
horizontal[ 5 ] = -1
horizontal[ 6 ] = 1
horizontal[ 7 ] = 2
vertical[ 0 ] = -1
vertical[ 1 ] = -2
vertical[ 2 ] = -2
vertical[ 3 ] = -1
vertical[ 4 ] = 1
vertical[ 5 ] = 2
vertical[ 6 ] = 2
vertical[ 7 ] = 1

Let the variables currentRow and currentColumn indicate the row and column of the knight’s current position. To make a move of type moveNumber, where moveNumber is between 0 and 7, your program uses the statements

currentRow += vertical[ moveNumber ]; currentColumn += horizontal[ moveNumber ];

Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Remember to test each potential move to see if the knight has already visited that square, and, of course, test every potential move to make sure that the knight does not land off the chessboard. Now write a program to move the knight around the chessboard. Run the program. How many moves did the knight make?


/*
===================================
File: prg0342.cpp
Mod: D
Date: 9/19/2006

===================================
*/
#include <iostream.h>
#include <cstdlib.h>
#include <ctime.h>
#include <math.h>

int board [8][8] = { { 0 }, { 0 } };
int horizontal [8];
int vertical [8];
int currentRow = 3;
int currentColumn = 4;



int main ()
{
int moveNumber = 0;
horizontal[ 0 ] = 2;
horizontal[ 1 ] = 1;
horizontal[ 2 ] = -1;
horizontal[ 3 ] = -2;
horizontal[ 4 ] = -2;
horizontal[ 5 ] = -1;
horizontal[ 6 ] = 1;
horizontal[ 7 ] = 2;
vertical[ 0 ] = -1;
vertical[ 1 ] = -2;
vertical[ 2 ] = -2;
vertical[ 3 ] = -1;
vertical[ 4 ] = 1;
vertical[ 5 ] = 2;
vertical[ 6 ] = 2;
vertical[ 7 ] = 1;

for (int counter = 1; counter < 64; counter++)
{
moveNumber++;
if (moveNumber > 7)
moveNumber = 0;


currentRow += horizontal [ moveNumber ];
currentColumn += vertical [ moveNumber ];
if (board[ currentRow ][ currentColumn ] != 0 || currentRow > 7 || currentColumn > 7 || currentRow < 0 || currentColumn < 0)
{
currentRow -= horizontal [ moveNumber ];
currentColumn -= vertical [ moveNumber ];
moveNumber++;
}
else
board [ currentRow ][ currentColumn ] = counter;
cout << "The current row is " << currentRow << " and the current column is " << currentColumn << "." << endl;

}

return 0;
}


The program isn't running properly, but I'm pretty sure I'm doing everything needed. I'm not asking for code, just some direction so I can fully understand it myself.

reboot
11-06-2006, 10:10 AM
What's the question?

Twan
11-06-2006, 10:11 AM
What's the question?
What am I doing wrong? Is my logic correct, just not the code?

Zumwalt
11-06-2006, 10:28 AM
Have you solved this on paper yet at all?

Twan
11-06-2006, 10:38 AM
I tried it on paper, but did not manage to get a solution. I guess I can keep retrying, and then view the move order like that.

Zumwalt
11-06-2006, 12:00 PM
For fun I did it on paper, although I have little time to devote to it at the moment, I discovered the start point and end point to find the solution itself. You will have this data if you figure out 1/4 of the puzzle.

The only way you are going to be able to figure this thing out is if you have the physical solution on paper infront of you to see what needs to happen, otherwise, no matter what code you use, you won't know how to test its authenticity for the solution.

This is one of those type of problems where you solve it on paper before you write it in code.

Edit: (don't get to excited)
This zip file contains a PSD file that you can use instead of paper. Its simply a checkers board with a green box around the 4 center spots, and an S in one of the 4 to use as a starting point of reference.

What you do is simply use the paintbrush in photoshop to draw your moves, create a new layer for every try, you keep moving until you get stuck and need to start over then create a new layer, hide the previous move sets, but this is faster than paper and easier.

Deadalus
11-06-2006, 01:13 PM
Excuse me, but Zumwalt is talking nonsense. The whole purpose of the exercise is first to see how difficult it is to figure this out on paper with a hit-and-miss approach, and then to construct a simple algorithm that will let the computer find a solution by systematically trying out possible moves. This problem is a classical application of back-tracking, because a successful algorithm will roughly have this form:

- check all moves until you find a free square
- if successful, repeat from that square
- if not (no square that can be reached from here), go back and make different choice on previous square

From the description it seems that you don't need to implement the backtracking part yet, meaning that your knight will simply stop when none of the eight moves is possible.
The main problem with your code is that you also increase the counter when no possible move is found. Plus, since you're not using back-tracking and thus finding a move will most likely fail before you make 64 moves, you need an end condition. Namely, if all moves from a square have been found impossible, the program should stop and show the number of valid moves made.
(Also, you're increasing moveNumber in two places.)

Zumwalt
11-06-2006, 01:32 PM
No offense, Deadalus, but I am giving one of many solutions to the problem, not talking nonsense, and I take offense to you attacking my method to approaching a simple way to help someone new to figuring out the algorithim.

There is more than 1 way to skin a cat, and to put down someone for giving a way to take care of the problem is demeaning and a direct attack on that persons knowledge.

FYI using my method I have found a solution, haven't coded it, didn't plan on coding it, but I have on paper (photoshop) the answer to the first part of the equation, is it possible or not.

The second part of the problem is can he create a program to simulate what he has done on paper, which is part of his assignment, to do it on paper first, find out if it is possible, then give a program that is capibile of solving the problem in question using arrays and loops.

I would appreciate it if you do not attack me again.

Deadalus
11-06-2006, 02:55 PM
I certainly didn't mean to attack you. I might have come over a bit fierce, because this is such a common problem (see Google (http://www.google.be/search?q=Knight's+Tour+Problem&ie=utf-8&oe=utf-8&rls=org.mozilla:en-US:official&client=firefox-a)) that to me it is self-evident that there are indeed solutions.

And this being a programming forum, I assume that the purpose of the exercise is to learn something about programming, or in a more general sense, about using a computer to solve a problem. Trying to solve the knight's tour problem by hand might be challenging, pleasant and even good brain exercise, but it doesn't teach you anything about those things.

By the way, there are billions of 'solutions' to the problem.

Twan
11-06-2006, 07:39 PM
Thanks!

After a few modifications, I came up with this:


/*
===================================
File: prg0342.cpp
Mod: D
Date: 9/19/2006

===================================
*/
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int board [8][8] = { { 0 }, { 0 } };
int horizontal [8];
int vertical [8];
int currentRow = 3;
int currentColumn = 4;
int stop = 0;



int main ()
{
int moveNumber = 0;
horizontal[ 0 ] = 2;
horizontal[ 1 ] = 1;
horizontal[ 2 ] = -1;
horizontal[ 3 ] = -2;
horizontal[ 4 ] = -2;
horizontal[ 5 ] = -1;
horizontal[ 6 ] = 1;
horizontal[ 7 ] = 2;
vertical[ 0 ] = -1;
vertical[ 1 ] = -2;
vertical[ 2 ] = -2;
vertical[ 3 ] = -1;
vertical[ 4 ] = 1;
vertical[ 5 ] = 2;
vertical[ 6 ] = 2;
vertical[ 7 ] = 1;

for (int counter = 1; counter < 64; counter++)
{

if (moveNumber > 7)
moveNumber = 0;


currentRow += horizontal [ moveNumber ];
currentColumn += vertical [ moveNumber ];
if (board[ currentRow ][ currentColumn ] != 0 || currentRow > 7 || currentColumn > 7 || currentRow < 0 || currentColumn < 0)
{
currentRow -= horizontal [ moveNumber ];
currentColumn -= vertical [ moveNumber ];
moveNumber++;
counter--;
stop++;
if (stop == 100)
break;

}
else {
board [ currentRow ][ currentColumn ] = counter;
cout << "The current row is " << currentRow + 1 << " and the current column is " << currentColumn + 1 << "." << endl;
}

}
for (int j = 0; j <= 7; j++){
for (int q = 0; q <= 7; q++)
cout << board[j][q] << endl;
}
return 0;
}



I don't think it completes, but it works pretty well.

One problem I found though is that on those nested for loops, I don't get numbers printed out like they should. I mean, if I have a 42, I should have a 1-41, but I'm not seeing that.

Zumwalt
11-07-2006, 08:12 AM
The idea of solving it on paper first would give you the 'logic' idea of how to solve the problem, seeing how you need to 'go back' and find a new path when the first path was not valid.

Deadalus is correct that there are thousands of answers to this problem, all depending on where you start and how large the board is, there are rules to what would make sense for the problem and what wouldn't (odd number board vs even number since odd would never solve)

For every square you move into, there are 8 possible moves, when you move, you will need to ilimate the previous square from the solution as a possible move on a forward link, but it needs to be stored somewhere for a 'move back' in simple terms.

This leaves you 7 logical steps remaining, then you simply check those 7 to see if you have already moved into that square. You will want to store your list of moves in the order you did them in, so you can iliminate those from your search equation.

First, what you are working on is your steps forward, and all you have to do is determine if any of the squares have already been visited. Move into one that has not, and repeat.

You can't leave the board and do a 're-enterant' move, and you can't double up on a square, on top of that you need only make 64 moves.

To me, it was easier to understand how it works by drawing it out on paper without 'google'ing the problem, then I understood the visual logic. If you google it up, you will find tons of websites that talk about the solution.

You have a board with a number from 1 - 64, you start in one of the 4 center squares of the board (there are tons of other places to start to solve this), in my photoshop file, I am starting on square 28, so 28 is taken in my move array as the begining point. Then when I move, lets say to square 13 (upper left is square 1, lower right is 64), I store 13 as used in the arrays next entry, so array element [0] is 28, array element [1] is 13, from 13 there are only 7 possible moves since square 28 is taken.

This was the foundation to the loop checking against my array list of moves.
Probably not logical to the more advanced programmers though.

Twan
11-07-2006, 09:37 AM
I actually went the brute force method:


/*
===================================
File: prg0342.cpp
Mod: D
Date: 9/19/2006

===================================
*/
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>


bool done = false;
int board [8][8] = { { 0 }, { 0 } };
int horizontal [8];
int vertical [8];
int currentRow = 0;
int currentColumn = 0;
int stop = 0;

int main ()
{
int moveNumber = 0;
horizontal[ 0 ] = 2;
horizontal[ 1 ] = 1;
horizontal[ 2 ] = -1;
horizontal[ 3 ] = -2;
horizontal[ 4 ] = -2;
horizontal[ 5 ] = -1;
horizontal[ 6 ] = 1;
horizontal[ 7 ] = 2;
vertical[ 0 ] = -1;
vertical[ 1 ] = -2;
vertical[ 2 ] = -2;
vertical[ 3 ] = -1;
vertical[ 4 ] = 1;
vertical[ 5 ] = 2;
vertical[ 6 ] = 2;
vertical[ 7 ] = 1;
do
{
for (int y = 0; y < 8; y++)
{
for (int x = 0; x < 8; x++)
{
board[y][x] = 0;
}

}
currentRow = 0;
currentColumn = 0;
stop = 0;
moveNumber = 0;

for (int counter = 1; counter < 64; counter++)
{


currentRow += horizontal [ moveNumber ];
currentColumn += vertical [ moveNumber ];
if (board[ currentRow ][ currentColumn ] != 0 || currentRow > 7 || currentColumn > 7 || currentRow < 0 || currentColumn < 0)
{
currentRow -= horizontal [ moveNumber ];
currentColumn -= vertical [ moveNumber ];
moveNumber = rand() % 8;
counter--;
stop++;
if (stop == 1000000)
break;

}
else {
board [ currentRow ][ currentColumn ] = counter;
if (counter == 64)
{
done = true;
}
cout << "The current row is " << currentRow + 1 << " and the current column is " << currentColumn + 1 << "." << endl;
}

}



} while (done == false);




for (int j = 0; j <= 7; j++){
for (int q = 0; q <= 7; q++)
{ cout << board[j][q] << endl;
}
}

return 0;
}


Will that work?

Deadalus
11-07-2006, 01:09 PM
If that reaches 64 in a reasonable time period, you should play the lottery immediately. :)

It certainly is a good set-up to see how far attempts without back-tracking tend to get. Add some counters and messages to see for yourself.

Next, try to use back-tracking and keep track of how far the knight gets each time before it needs to go back one or more moves. See this page to get an idea of how many calculations are still required even with such an approach:
http://web.telia.com/~u85905224/knight/eknight.htm

Twan
11-08-2006, 10:30 AM
I can't backtrack. I'm having trouble figuring it out. Any guidance?

bassmaster52
11-08-2006, 11:15 AM
Another good site for this problem, it has many solutions for this puzzle.

http://mathworld.wolfram.com/KnightsTour.html

ossan041700
11-08-2006, 10:28 PM
I did this problem years ago as part of my grade 10 computer science class. I don't have the solution lying around, but i can tell you the fastest method for doing it (the time your code took to solve the problem was measured and whoever solved it quickest won, and I won that year). What you need to do is assign each square a point value. The point value is kind of the odds you have of being able to hit that square, the outer squares being harder to hit than the inside of the board, have a higher value. You need to tell your code to take whichever square has the highest value that it can. In the case of a tie in point value, you have it take the square that is closest to the edge of the board. I think i may be being a bit vague with my description, so sorry if that is the case, I can draw up a bitmap later if anyone would like to see the point assignment of the board.

ElderKnight
11-09-2006, 08:13 AM
Glad you mentioned the square point value. One algorithm I remember assigned weights to the squares, something like 1 for the central four, more for center-peripheral squares, more for the edges, on down to maybe 8 or 16 for the corners. The idea was to hit the corners and edges early, mainly to avoid getting stuck on a square from which there were fewer unused escape squares.

Deadalus
11-10-2006, 03:39 AM
In fact, an easy algorithm without back-tracking for this, Warnsdorff's rule, works with square points, but somewhat differently than what you guys are describing. It is mentioned in my link above. It's not guaranteed to work, but for an 8x8 square it will.

Twan
11-10-2006, 09:42 PM
Yea, my book said about implementing heuristically or something, and it was talking about giving squares point values. How can I make an array and assign 64 different values easily?

ossan041700
11-12-2006, 08:40 PM
Yea, my book said about implementing heuristically or something, and it was talking about giving squares point values. How can I make an array and assign 64 different values easily?

Yeah it was called heruistic something i can't recall, but the way i did it was
using DATA and READ, but that was in QBASIC :D, not sure what language you are using, but would stand to reason you can make a simple text file with the values and then just populate an array with the file.

Twan
11-17-2006, 09:37 AM
Well, I finished it.

I hope I did it right, I can't even tell, but it runs tours of 59 moves so....


#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>


int horizontal [8];
int board [8][8] = { { 0 }, { 0 } };
int vertical [8];
int currentRow = 4;
int currentColumn = 3;
int oRow, oColumn;
int accessibility[8][8];

int howmany ( int, int );
void change ( int, int );
int main ()
{

int moves = 0;
board[0][0] = 1;
horizontal[ 0 ] = 2;
horizontal[ 1 ] = 1;
horizontal[ 2 ] = -1;
horizontal[ 3 ] = -2;
horizontal[ 4 ] = -2;
horizontal[ 5 ] = -1;
horizontal[ 6 ] = 1;
horizontal[ 7 ] = 2;
vertical[ 0 ] = -1;
vertical[ 1 ] = -2;
vertical[ 2 ] = -2;
vertical[ 3 ] = -1;
vertical[ 4 ] = 1;
vertical[ 5 ] = 2;
vertical[ 6 ] = 2;
vertical[ 7 ] = 1;
int highest [5] = { 0, 0, 0, 0 };
int bestMove = 8;


for (int j = 0; j < 8; j++)
{
for (int i = 0; i < 8; i++)
accessibility[i][j] = howmany (i, j);

}
for (int counter = 1; counter < 64; counter++)
{
// check all 8 moves around knight
bestMove = 9;

for (int j = 0; j < 8; j++)
{
// check all 8 moves accesibility, find lowest int that is > 0
if (accessibility[currentRow + horizontal[j]][currentColumn + vertical[j]] < bestMove )
{
if ( currentRow + horizontal[j] >= 0 && currentColumn + vertical[j] >= 0 && board[currentRow + horizontal[j]][currentColumn + vertical[j]] == 0) // if is on board
if (currentRow + horizontal[j] < 8 && currentColumn + vertical[j] < 8 )
bestMove = j;

}
}
if (bestMove == 9)
{
for (int j = 0; j < 8; j++)
{
if (0 < currentColumn + vertical [ j ] < 8 && 0 < currentRow + horizontal [ j ] < 8 && board [currentRow + horizontal [ j ]][currentColumn + vertical [ j ]] == 0)
{
bestMove = j;

}
}
}
currentRow += horizontal [ bestMove ];
currentColumn += vertical [ bestMove ];
moves++;


board[currentRow][currentColumn] = counter;
if (currentRow < 0 || currentColumn < 0)
break;
cout << currentRow + 1 << ", " << currentColumn + 1 << " and the best move was " << bestMove << "." << endl;



}


cout << "There were " << moves << " valid moves made." << endl;









return 0;

}
int howmany ( int i, int j )
{
//determine number of moves that can be made to square i, j
int num = 0;

if (i == 0 && j == 0 || i == 0 && j == 7 || i == 7 && j == 0 || i == 7 && j == 7)
num = 2;
else if (i == 1 && j == 0 || i == 0 && j == 1 || i == 7 && j == 6 || i == 6 && j == 7 || i == 0 && j == 6 || j == 0 && i == 6 || i == 7 && j == 1 || j == 7 && i == 1)
num = 3;
else if (1 < i < 6 && j == 0 || 1 < j < 6 && i == 0 || i == 7 && 1 < j < 6 || j == 7 && 1 < i < 6)
num = 4;
else if (i == 1 && j == 1 || i == 6 && j == 6 || i == 1 && j == 6 || j == 1 && i == 6)
num = 4;
else if (i == 1 && 1 < j < 6 || j == 1 && 1 < i < 6 || i == 6 && 1 < j < 6 || j == 6 && 1 < i < 6)
num = 6;
else if (i == 1 && 1 < j < 6 || i == 6 && 1 < j < 6 || j == 1 && 1 < i < 6 && j == 6 && 1 < i < 6 )
num = 6;
else
num = 8;

return num;
}


Does that all look ok?

EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum