Knight tour (arrays help needed)

dilmv · #1 08-Oct-2004, 19:51

Ok I have started work on a "knight's tour" project. I am sure many of you have heard of this or have had to solve it. I need to develope a program that will start the night at the upper left corner of a chess "board" and it has to move around the board using "legal" knight moves. I have programed the knight's possible moves into two arrays. I understand pretty much how arrays work but I know I need to use quite a few in this program and I am having trouble dealing with all the arrays and getting them to do what I want them to.
Here is my current code. I am kinda lost as to what to do next.. I know I need to use my moves array to test a move on my board and then make sure it is a vaid move. Then make sure the square has not been visited already. I am supposed to just use a "brute force" method of doing this. If anyone could point me in the right direct I would greatly appreciate it:

CPP / C++ / C Code:

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
	int horizontal[8] = {2,1,-1,-2,-2,-1,1,2};
	int vertical[8] = {-1,-2,-2,-1,1,2,2,1};
	int chessBoard[8][8];

	int currentRow = 0, currentColumn= 0, move_count = 0;
	
	for(int i=0; i<8; i++)
		for(int j=0; j<8; j++)
			chessBoard[i][j]=0;

	for(int i=0; i<64; i++)
		for(int j=0; i<8; i++)
			chessBoard[vertical[i]][horizontal[i]] = 1;

		for(int i=0; i<8; i++)
			for(int j=0; j<8; j++)
				cout << setw(2) << chessBoard[i][j];
	return 0;	
}

dsmith · #2 09-Oct-2004, 08:31

Hello dilmv. Welcome to GIDForums.

It appears that you have a great start on this. You seem to be on the right track. Question: when do you stop moving? When there are no more valid moves that go to unvisited squares?

If so then I would set up a do while as the main loop with an inner loop of a for statement that breaks when a valid move is hit. I just wrote this off the top of my head, so there are no guarantees that it won't break

But it should give you an idea of how to approach this I hope.

CPP / C++ / C Code:

do{
  for(move=0;move<8;move++){
    //set position
    new_vert = currentRow + vertical[move];
    new_horz = currentCol + horizontal[move];
    //Is this a valid move
    if ( (new_vert>=0) && (new_vert < 8) )
      if( (new_horz>=0) && (new_horz < 8) )
         if( !chessBoard[new_horz][new_vert] ){
            chessBoard[new_horz][new_vert] = 1;
            move_count++;
            currentRow = new_vert;
            currentCol = new_horz;
            break;
          }
  }
  if(move<8){
    //Print new location
  }
while(move<8);

Good luck!

davekw7x · #3 09-Oct-2004, 08:47

Quote:

Originally Posted by dilmv

Ok I have started work on a "knight's tour" project. I am sure many of you have heard of this or have had to solve it. I need to develope a program that will start the night at the upper left corner of a chess "board" and it has to move around the board using "legal" knight moves. I have programed the knight's possible moves into two arrays. I understand pretty much how arrays work but I know I need to use quite a few in this program and I am having trouble dealing with all the arrays and getting them to do what I want them to.
Here is my current code. I am kinda lost as to what to do next.. I know I need to use my moves array to test a move on my board and then make sure it is a vaid move. Then make sure the square has not been visited already. I am supposed to just use a "brute force" method of doing this. If anyone could point me in the right direct I would greatly appreciate it:
[

Well, I really won't have time to try help you on your chess problem, but I have a couple of suggestions about programming in general.

First of all, before you get too involved in solving the problem, I think it's important to make sure you are starting out with a correct setup.

I have added some output statements to show you what I usually do.

CPP / C++ / C Code:

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
  int horizontal[8] = {2, 1, -1, -2, -2, -1, 1, 2};
  int vertical[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
  int chessBoard[8][8];

  int currentRow = 0, currentColumn = 0, move_count = 0;
  
  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      chessBoard[i][j] = 0;
    }
  }

  for(int i = 0; i < 64; i++) {
    cout << "Debug1: i = " << i << endl;
    for(int j = 0; i < 8; i++) {
      cout << "Debug2: vertical["<<i <<"] = " << vertical[i] 
           << ", horizontal[" << i <<  "] = " << horizontal[i] 
           << endl << endl;
      chessBoard[vertical[i]][horizontal[i]] = 1;
    }
  }

  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      cout << setw(2) << chessBoard[i][j];
    }
    cout << endl;
  }
  return 0;  
}

Notice that I always use {} after the for() (I also always use them after if() and else() conditionals). That lets me know at a glance which statements are included in the blocks. It wasn't necessary for your program to have them, but if you want to put in debug statements, as I did, it's easy to forget to add the braces. Simply using braces every time saved me lots of debug time.

I also find the code to be more readable if I include spaces around operators, as you see here. Maybe you think that's just a matter of taste, but it's important to me to have things set apart visually. It doesn't make the code run any better, but it makes it easier to read through more quickly when I'm debugging.

Now these opinions about spacing and use of braces are really about style rather than substance. If you put in the debug statement as I have shown, I think you will see a substantial error.

Now look at the Debug: outputs. Is that what you intended to do?

Regards,

Dave

dilmv · #4 09-Oct-2004, 20:00

thanks for the help to both of you! I greatly appreciate it. I have taken your suggestions, but am still having some problems.
Assuming the code is processing the moves correctly, I am having trouble outputing the board as a 8 x 8 output.
Any suggestions on this? I have been playing with the code for the last few hours and I think I am stuck.
Thanks again
Dillon

CPP / C++ / C Code:

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
	int horizontal[8] = {2,1,-1,-2,-2,-1,1,2};
	int vertical[8] = {-1,-2,-2,-1,1,2,2,1};
	int chessBoard[8][8];

	int move, currentRow = 0, currentCol= 0, move_count = 0, new_vert, new_horz;
	
for(int i=0; i<8; i++)
	for(int j =0; j<8; j++)
		chessBoard[i][j] = 0;
	
	
do
{
  for(move=0;move<8;move++)
  {
    //set position
    new_vert = currentRow + vertical[move];
    new_horz = currentCol + horizontal[move];
    //Is this a valid move
    if ( (new_vert>=0) && (new_vert < 8) )
      if( (new_horz>=0) && (new_horz < 8) )
         if( !chessBoard[new_horz][new_vert] )
		 {
            chessBoard[new_horz][new_vert] = 1;
            move_count++;
            currentRow = new_vert;
            currentCol = new_horz;
            break;
          }

		 //print the chess board	 
	 for(int i=0; i<8; i++)
		 for(int j=0; j<8; j++)
			cout << chessBoard[i][j];
  }
}
while(move<8);
	return 0;	
}

dabigmooish · #5 10-Oct-2004, 01:54

I don't think your code is "moving" correctly. When I compiled what you have it seemed to just jump around and not work. Anyway to print it you've got a good start, but you need to start a new line after every 8 iterations. Try using some stratigically placed if statements (and about a dozen {'s).
Also when you place code put it inside [c] and [ / c](no spaces) tags

dsmith · #6 10-Oct-2004, 08:03

Hi Dillon. Your code isn't that far off.

Here are the things that I think that you should do:

Move your printout to only printout when a new move occurs
Put some spacing in your printout to make it more readable like dab suggested.
Set the starting position to 1 as it has been visited.
It would be nice to see the most recent move in your printout.

This is what I came up with.

CPP / C++ / C Code:

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
	int horizontal[8] = {2,1,-1,-2,-2,-1,1,2};
	int vertical[8] = {-1,-2,-2,-1,1,2,2,1};
	int chessBoard[8][8];

	int move, currentRow = 0, currentCol= 0, move_count = 0, new_vert, new_horz;
	
for(int i=0; i<8; i++)
	for(int j =0; j<8; j++)
		chessBoard[i][j] = 0;
	
chessBoard[0][0] = 1; //Set the first point to being visited
do
{
  for(move=0;move<8;move++)
  {
    //set position
    new_vert = currentRow + vertical[move];
    new_horz = currentCol + horizontal[move];
    //Is this a valid move
    if ( (new_vert>=0) && (new_vert < 8) )
      if( (new_horz>=0) && (new_horz < 8) )
         if( !chessBoard[new_horz][new_vert] )
		 {
            chessBoard[new_horz][new_vert] = 1;
            move_count++;
            currentRow = new_vert;
            currentCol = new_horz;
            //The printout should only occur when a move is valid
            //Also, I added some basic formatting to the prinout
            for(int i=0; i<8; i++){
               for(int j=0; j<8; j++){
                  if( (j== currentRow) && (i == currentCol) )
                      cout << "X" << " "
                  else
                      cout << chessBoard[i][j] << " ";
                }
                cout << "\n";
            }
            cout << "\n";
            break;
          }
}
while(move<8);
	return 0;	
}

Unfortunately, this will give the same results everytime. It would be cool to allow the user to enter a number that would give which move to analyze first...

dilmv · #7 10-Oct-2004, 11:05

ok, I see what I did wrong! Thanks for the help! I am actually starting on some code to use a random number generator to pick a starting position and to pick a next move instead of going in the same sequence every time. Also like you said, I'll allow the user to input a starting place and possibly what move to choose. Might make it kinda cool :-)

mikhail · #8 18-Oct-2004, 15:31

Quote:

Originally Posted by dilmv

ok, I see what I did wrong! Thanks for the help! I am actually starting on some code to use a random number generator to pick a starting position and to pick a next move instead of going in the same sequence every time. Also like you said, I'll allow the user to input a starting place and possibly what move to choose. Might make it kinda cool :-)

Ever get this working? As a regular player, I'd love to have a look at it.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
need help with passing 3 arrays into a function	tommy69	C Programming Language	14	07-Apr-2004 01:22
Free 1st month / Free setup / No credit card needed...Plans start at 4.95	LarryIsaac	Web Hosting Advertisements & Offers	0	11-Oct-2003 15:03