Can anyone check this?

[tchriss]

I'm trying to write a knights tour prog with iterations.
Basically the knight has a starting point on the chess board and has to visit all the squares only once!

This is the starting code basically but it seems it doesn't work!
(Surprise surprise!)


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

int main()
{
srand(time(NULL));
// Initialise the board array
int board[8][8]={0};

// Initialise the array that holds all the possible movements
int ran_move[8][2]={1,2, -1,-2, 1,-2, -1,2, 2,1, -2,-1, 2,-1, -2,1};

// Integer that holds the number of moves
int move = 0;

// Random integer
int ran;
// Integers that hold the coordinates of the moves
int x_pos, y_pos ;
int x_pos_temp, y_pos_temp;

do
{
cout << &quot;\n Enter the starting position coordinates: &quot;;
cin >> x_pos >> y_pos;
}
while ((x_pos < 0) || (y_pos < 0) || (x_pos >= 8) || (y_pos >= 8));

while (x_pos > 0 && y_pos > 0 && move < 63)
{

ran = (0 + rand() % 7);
x_pos = x_pos + ran_move[ran][1];
y_pos = y_pos + ran_move[ran][2];


if (x_pos > 8 || y_pos > 8)
{
cout << &quot;End of journey. Number of moves:&quot; << move << endl;
for (int i; i <= 8; i++){
for (int j; j <=8; j++){
cout << setw(3) << board[j];
}
}
}
else if (board[x_pos][y_pos] = 0)
{
move = move++;
board[x_pos][y_pos] = move;
}
else if (board[x_pos][y_pos] != 0)

cout << &quot;End of journey. Number of moves:&quot; << move << endl;
for (int i; i <= 8; i++)
for (int j; j <=8; j++)
cout << board[j];
}
return 0;
}

 

[djones7936]

Hi,

The program's not perfect, but it runs. When you access arrays, remember to start with 0 and not 1. If you make an array of size 2, then you access the elements 0 and 1.

int testarray[2] = {16, 25};

testarray[0] is 16;
testarray[1] is 25;
testarray[2] is out of bounds (error).

There are a lot of little modifications. When you display the board, the j needs to be in the first for loop because the inside for loop is &quot;nested&quot;. The board was probably printing differently than you intended before (with the x axis down the screen and the y axis across the screen). I also the newline (endl) at the end of each row.

You can comment out the cout lines with the Debug comments all around them. The first ones just show how data is pulled from arrays.

The program is a pretty cool idea. Tracking each move of the knight across a chess board. You might have to run the program a couple times to get good results because of the seed random feature.

Here ya go!
--------------------------

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

int main()
{
    srand(time(NULL));
    // Initialise the board array
    int board[8][8]={0};
    
    // Initialise the array that holds all the possible movements
    int ran_move[8][2]={1,2, -1,-2, 1,-2, -1,2, 2,1, -2,-1, 2,-1, -2,1};
    
    // Integer that holds the number of moves
    int move = 0, x,y;
    
    // Random integer
    int ran;
    // Integers that hold the coordinates of the moves
    int x_pos, y_pos ;
    //int x_pos_temp, y_pos_temp;

	cout << setw(3);

	cout << &quot;Debugging: Look at the code that produces this&quot; << endl << &quot; to see how to access and display arrays.&quot; << endl;
	//Debugging
	for(y=0;y<8;y++)
	{
		for(x=0;x<8;x++)
			cout << board[x][y] << &quot; &quot;;
		cout << endl;
	}

	//Debugging
	for(x=0;x<8;x++)
			cout << &quot;(&quot; << ran_move[x][0] << &quot;, &quot; << ran_move[x][1] << &quot;) &quot; << endl;

	cout << endl << endl << endl;

    do
    {
        cout << &quot;\n Enter the starting position coordinates: &quot;;
        cin >> x_pos >> y_pos;
    }
    while ((x_pos < 0) || (y_pos < 0) || (x_pos >= 8) || (y_pos >= 8));

    
    while (x_pos >= 0 && y_pos >= 0 && move < 63)
    {
        
        ran = (0 + rand() % 7);
        x_pos = x_pos + ran_move[ran][0];
        y_pos = y_pos + ran_move[ran][1];
     
		if (x_pos > 8 || y_pos > 8)
		{
			cout << &quot;End of journey. Number of moves:&quot; << move << endl;
			for (int j=0; j < 8; j++)
			{
				for (int i=0; i <8; i++)
				{
					cout << board[ i ][j];
				}
				cout << endl;
			}
			break;
		}
		else if(board[x_pos][y_pos] == 0)
		{
			move++;
			board[x_pos][y_pos] = move;     
		}
		else if (board[x_pos][y_pos] != 0)
		{
			cout << &quot;End of journey. Number of moves:&quot; << move << endl;

			for (int j=0; j < 8; j++)
			{
				for (int i=0; i <8; i++)
					cout << board[ i ][j];
				cout << endl;
			}
			break;
		}
	}

	//Debugging
	cout << &quot;End of game. Number of moves: &quot; << move << endl;

     return 0;
}

-Dave

http://home.attbi.com/~djones7936/index.htm

 

[tchriss]

Thanks Dave ...

How else can I do the iterations ?

I mean I have to have loops inside loops because if the whole rout ends after 4 moves I want it to start over until it does 63 moves around the board!

Anyway thanks a lot !

Terry

 

[djones7936]

I would probably have one main while loop.

while(move<63)

then use if statements to check to see if the piece is within the boundaries, and if the next space is available.

Where each statement says break (the knight can't move to the given position), instead of exiting the while loop, you could do 2 things. Either reset your &quot;move&quot; variable and &quot;board&quot; array (zero them out), or pick another location to move to instead (without incrementing the move variable).

If you used the first option, (completely starting over after a failed move attempt) your program would probably never stop running. How many combinations of moves can the knight make over a 63 move period? It would have to guess the only right combination (probably a bunch) out of all the possible combination which is over 10^50. The program would probably not find the right result in a timely manner.

With the second option, you want to check to see if a move is available, without actually moving there. Instead of

x_pos = x_pos + ran_move[ran][0];
y_pos = y_pos + ran_move[ran][1];

you would want to use the x_pos_temp and y_pos_temp variables (You will need to uncomment the lines where they are created at the top) and change it to

x_pos_temp = x_pos+ ran_move[ran][0];
y_pos_temp = y_pos+ ran_move[ran][1];

the pos_temp variable would then store the next position that the knight wants to go. You could then check the pos_temp variables in the if statements to see if the move is possible (make sure it is within the boundaries, and it's not trying to move to a square it has already been to).
After it passes all the conditions, then you move the actual piece to the particular position and increment the move variable.

x_pos = x_pos_temp;
y_pos = y_pos_temp;
move++;

If the condition failed, then you the knight would not move, the &quot;move&quot; variable would not increment, the pos_temp variable would be discarded and the loop would start over (starting the whole process over again of finding another potential position).

The while loop would keep looking for possible moves. When the loop finds a potential move, moves the knight, increments the &quot;move&quot; variable, then continues search for more potential moves (providing the the knight hasn't moved more than 63 times). If the loop doesn't find a potential move, then it keeps looking.

Unfortunately, with option 2, it is possible that, the knight could get stuck, (out of squares that it can move to). If all of the if statement conditions continually failed (there are no available squares for the knight to move to), then the program would be stuck in an infinite loop.

You could add a variable that adds the amount of failed move attempts. When the knight doesn't move from it's spot, the variable is incremented. When the knight does make a successful move, the variable would be zeroed out. If the knight didn't make any moves for, say 100 iterations in a row, then you can guess the knight is stuck. At that point, the program should either: exit the while loop, or reset the board and try again from scratch.

You could implement that check by adding an if statement.

if(failedmoves < 100)
{
  // reset the board, and the move variable
}

I hope I explained the ideas clearly. Ask if you have any questions.

-Dave

http://home.attbi.com/~djones7936/index.htm

 

[BoulderBum]

Do you have the Deitel & Deitel text? I'm on page 700 something, and I did this problem many chapters ago.

I didn't read all of your code (I'm lazy and pressed for time) but I can give you a few tips.

If you're going to do a brute force algorithm, I suggest you have a function that clears the board matrix back to all zeros. That way you can call it after each tour attempt.

A &quot;bool isInBounds(...)&quot; function which takes the coordinates of the current knight position and the coordinates of a desired move is also handy for making sure a certain move doens't go off the board.

With a brute force approach, you might also consider having a moveIsPossible() function to see if there are any possible moves available (remember that just because a single random move is unavailable doesn't mean that another different move can't be made).

Finally, what will help dramatically with your success is a some sort of heuristic. The Deitels' text suggested an accessability matrix, which allows the knight to jump to the square with the most available moves. It looks like this if I'm not mistaken:

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

A knight on the rim is grim, as they say, and, for example, one in the corner has only 2 moves available.

By utilizing this matrix, you can have your code jump to the square with the most mobility, then decrement the mobility numbers of the squares it can jump to (because the square the knight just jumped to is no longer available).

This will give your code a fairly high success rate.

............

You can do something similar for the 8 queens problem (8 queens on a single board without threatening each other). Write a note here if you want to know more.