GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 03-Apr-2006, 20:31
earachefl earachefl is offline
Member
 
Join Date: Feb 2006
Posts: 178
earachefl is on a distinguished road

"Knight's Tour" problem (from Euler)


An assignment from my textbook. 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?

The code I've written seems pretty good until the very end of the run, where illegal row and column values start showing up. I'm guessing I have some sort of logic error in my inner loop, which runs through each of eight possible moves until a legal one is found. This seems to happen at the point where the program can find no more legal moves - yet it doesn't exit the loop as I had planned.

Any help would be appreciated.
CPP / C++ / C Code:
//Knight's Tour problem (from Euler)
#include <iostream>
#include <ctime>
#include <stdlib.h>
#include <iomanip>
using namespace std;

void printTour(int[][8]);

int main () 
{
   srand(time(NULL));                                         //seed random                                     
   
   int board [8][8] = {};                                     //declare 8x8 board array, initialized to 0s
   const int horizontal[8] = {2, 1, -1, -2, -2, -1, 1, 2};    //declare legal horizontal moves
   const int vertical[8] = {-1, -2, -2, -1, 1, 2, 2, 1};      //declare corresponding vertical moves
   int currentRow, currentColumn;                             //where the Knight currently stands
   int moveNumber;                                            //for switching between legal moves 0 - 7
   int tempR = 0, tempC = 0;                                  //temporary storage of new row and column values
   int counter = 0;                                           //counter variable
   
   //Randomize starting point
   currentRow = rand() % 8;
   currentColumn = rand() % 8;
   
   //Show starting point values - for debugging
   cout << "Starting row: " << currentRow << ", column: " << currentColumn
		   << ", counter: " << counter << ", board: " << board[currentColumn][currentRow] << endl;

   //outer counter controlled loop - cycle through all 64 moves
   for (counter = 1; counter <= 64; counter++)
   {
      cout << "Counter " << counter << endl;                  //for debugging
	  moveNumber = 0;                                         //initialize possible legal move to 0
	  tempR = currentRow + horizontal[moveNumber];            //store temporary values after move 0
	  tempC = currentColumn + vertical[moveNumber];           //
	  
	  //display current values for debugging
	  cout << "Move number " << moveNumber << ", tempR: " << tempR << ", tempC:" << tempC << endl;
	  
	  //inner loop - while the board value at the new position is not equal to 0 (because it has been visited)
	  //or the new temp values are out of range, and the moveNumber is less than 7, keep looping until a valid
	  //move is found
      while ((board[tempC][tempR] != 0 || tempR < 0 || tempR > 7 || tempC < 0 || tempC > 7) && moveNumber < 7)
	  {
	  
	     ++moveNumber;                                        //increment possible legal move
		 tempR = currentRow + horizontal[moveNumber];         //reset temporary row and column positions
	     tempC = currentColumn + vertical[moveNumber];
		 
		 //for debugging
		 cout << "Move number " << moveNumber << ", tempR: " << tempR << ", tempC:" << tempC << endl;
	  }  //end inner loop - valid move has been found
                                                              	   
      currentRow = tempR;                                     //set current row position to the temporary value
	  currentColumn = tempC;                                  //set current column position to the temporary value
	  board[currentColumn][currentRow] = counter;             //set the value of the board at the current position
	                                                          //to equal the counter number
	  //for debugging														  
	  cout << "Current row: " << currentRow << ", column: " << currentColumn
		   << ", counter: " << counter << ", board: " << board[currentColumn][currentRow] << endl;
   }  //end outer loop - all 64 moves finished
   
   printTour(board);	                                      //call print function			
     
   return 0;
}
void printTour (int board[][8])                                     //pretty much self-explanatory
{
   cout << "_________________________________________" << endl;     //nested for loop which prints the
   for (int i = 0; i < 8; i++)
   {
      cout << "|    |    |    |    |    |    |    |    |" << endl;  //Knight's path
      for (int j = 0; j < 8; j++)
	  {
	     cout << "| " << setw(2) << board[i][j] << " ";             //showing the counter value at each board location
      }
	  cout << "|" << endl
	       << "|____|____|____|____|____|____|____|____|" << endl;
   }
}
      
From a sample run (can't seem to get it to show up properly here):
Quote:
_________________________________________
| | | | | | | | |
| 5 | 40 | 25 | 10 | 3 | 8 | 15 | 20 |
|____|____|____|____|____|____|____|____|
| | | | | | | | |
| 26 | 11 | 4 | 41 | 14 | 19 | 2 | 17 |
|____|____|____|____|____|____|____|____|
| | | | | | | | |
| 39 | 6 | 13 | 24 | 9 | 16 | 21 | 34 |
|____|____|____|____|____|____|____|____|
| | | | | | | | |
| 12 | 27 | 42 | 37 | 22 | 33 | 18 | 1 |
|____|____|____|____|____|____|____|____|
| | | | | | | | |
| 43 | 38 | 23 | 54 | 49 | 46 | 35 | 32 |
|____|____|____|____|____|____|____|____|
| | | | | | | | |
| 28 | 53 | 50 | 45 | 36 | 31 | 48 | 61 |
|____|____|____|____|____|____|____|____|
| | | | | | | | |
| 51 | 44 | 55 | 30 | 47 | 62 | 59 | 0 |
|____|____|____|____|____|____|____|____|
| | | | | | | | |
| 56 | 29 | 52 | 63 | 58 | 0 | 0 | 0 |
|____|____|____|____|____|____|____|____|

and the corresponding debugging printouts from the run. Notice that the row and column values start to go out of range at the 57th move:
Quote:
[Session started at 2006-04-03 22:14:05 -0400.]
Starting row: 5, column: 4, counter: 0, board: 0
Counter 1
Move number 0, tempR: 7, tempC:3
Current row: 7, column: 3, counter: 1, board: 1
Counter 2
Move number 0, tempR: 9, tempC:2
Move number 1, tempR: 8, tempC:1
Move number 2, tempR: 6, tempC:1
Current row: 6, column: 1, counter: 2, board: 2
Counter 3
Move number 0, tempR: 8, tempC:0
Move number 1, tempR: 7, tempC:-1
Move number 2, tempR: 5, tempC:-1
Move number 3, tempR: 4, tempC:0
Current row: 4, column: 0, counter: 3, board: 3
Counter 4
Move number 0, tempR: 6, tempC:-1
Move number 1, tempR: 5, tempC:-2
Move number 2, tempR: 3, tempC:-2
Move number 3, tempR: 2, tempC:-1
Move number 4, tempR: 2, tempC:1
Current row: 2, column: 1, counter: 4, board: 4
Counter 5
Move number 0, tempR: 4, tempC:0
Move number 1, tempR: 3, tempC:-1
Move number 2, tempR: 1, tempC:-1
Move number 3, tempR: 0, tempC:0
Current row: 0, column: 0, counter: 5, board: 5
Counter 6
Move number 0, tempR: 2, tempC:-1
Move number 1, tempR: 1, tempC:-2
Move number 2, tempR: -1, tempC:-2
Move number 3, tempR: -2, tempC:-1
Move number 4, tempR: -2, tempC:1
Move number 5, tempR: -1, tempC:2
Move number 6, tempR: 1, tempC:2
Current row: 1, column: 2, counter: 6, board: 6
Counter 7
Move number 0, tempR: 3, tempC:1
Current row: 3, column: 1, counter: 7, board: 7
Counter 8
Move number 0, tempR: 5, tempC:0
Current row: 5, column: 0, counter: 8, board: 8
Counter 9
Move number 0, tempR: 7, tempC:-1
Move number 1, tempR: 6, tempC:-2
Move number 2, tempR: 4, tempC:-2
Move number 3, tempR: 3, tempC:-1
Move number 4, tempR: 3, tempC:1
Move number 5, tempR: 4, tempC:2
Current row: 4, column: 2, counter: 9, board: 9
Counter 10
Move number 0, tempR: 6, tempC:1
Move number 1, tempR: 5, tempC:0
Move number 2, tempR: 3, tempC:0
Current row: 3, column: 0, counter: 10, board: 10
Counter 11
Move number 0, tempR: 5, tempC:-1
Move number 1, tempR: 4, tempC:-2
Move number 2, tempR: 2, tempC:-2
Move number 3, tempR: 1, tempC:-1
Move number 4, tempR: 1, tempC:1
Current row: 1, column: 1, counter: 11, board: 11
Counter 12
Move number 0, tempR: 3, tempC:0
Move number 1, tempR: 2, tempC:-1
Move number 2, tempR: 0, tempC:-1
Move number 3, tempR: -1, tempC:0
Move number 4, tempR: -1, tempC:2
Move number 5, tempR: 0, tempC:3
Current row: 0, column: 3, counter: 12, board: 12
Counter 13
Move number 0, tempR: 2, tempC:2
Current row: 2, column: 2, counter: 13, board: 13
Counter 14
Move number 0, tempR: 4, tempC:1
Current row: 4, column: 1, counter: 14, board: 14
Counter 15
Move number 0, tempR: 6, tempC:0
Current row: 6, column: 0, counter: 15, board: 15
Counter 16
Move number 0, tempR: 8, tempC:-1
Move number 1, tempR: 7, tempC:-2
Move number 2, tempR: 5, tempC:-2
Move number 3, tempR: 4, tempC:-1
Move number 4, tempR: 4, tempC:1
Move number 5, tempR: 5, tempC:2
Current row: 5, column: 2, counter: 16, board: 16
Counter 17
Move number 0, tempR: 7, tempC:1
Current row: 7, column: 1, counter: 17, board: 17
Counter 18
Move number 0, tempR: 9, tempC:0
Move number 1, tempR: 8, tempC:-1
Move number 2, tempR: 6, tempC:-1
Move number 3, tempR: 5, tempC:0
Move number 4, tempR: 5, tempC:2
Move number 5, tempR: 6, tempC:3
Current row: 6, column: 3, counter: 18, board: 18
Counter 19
Move number 0, tempR: 8, tempC:2
Move number 1, tempR: 7, tempC:1
Move number 2, tempR: 5, tempC:1
Current row: 5, column: 1, counter: 19, board: 19
Counter 20
Move number 0, tempR: 7, tempC:0
Current row: 7, column: 0, counter: 20, board: 20
Counter 21
Move number 0, tempR: 9, tempC:-1
Move number 1, tempR: 8, tempC:-2
Move number 2, tempR: 6, tempC:-2
Move number 3, tempR: 5, tempC:-1
Move number 4, tempR: 5, tempC:1
Move number 5, tempR: 6, tempC:2
Current row: 6, column: 2, counter: 21, board: 21
Counter 22
Move number 0, tempR: 8, tempC:1
Move number 1, tempR: 7, tempC:0
Move number 2, tempR: 5, tempC:0
Move number 3, tempR: 4, tempC:1
Move number 4, tempR: 4, tempC:3
Current row: 4, column: 3, counter: 22, board: 22
Counter 23
Move number 0, tempR: 6, tempC:2
Move number 1, tempR: 5, tempC:1
Move number 2, tempR: 3, tempC:1
Move number 3, tempR: 2, tempC:2
Move number 4, tempR: 2, tempC:4
Current row: 2, column: 4, counter: 23, board: 23
Counter 24
Move number 0, tempR: 4, tempC:3
Move number 1, tempR: 3, tempC:2
Current row: 3, column: 2, counter: 24, board: 24
Counter 25
Move number 0, tempR: 5, tempC:1
Move number 1, tempR: 4, tempC:0
Move number 2, tempR: 2, tempC:0
Current row: 2, column: 0, counter: 25, board: 25
Counter 26
Move number 0, tempR: 4, tempC:-1
Move number 1, tempR: 3, tempC:-2
Move number 2, tempR: 1, tempC:-2
Move number 3, tempR: 0, tempC:-1
Move number 4, tempR: 0, tempC:1
Current row: 0, column: 1, counter: 26, board: 26
Counter 27
Move number 0, tempR: 2, tempC:0
Move number 1, tempR: 1, tempC:-1
Move number 2, tempR: -1, tempC:-1
Move number 3, tempR: -2, tempC:0
Move number 4, tempR: -2, tempC:2
Move number 5, tempR: -1, tempC:3
Move number 6, tempR: 1, tempC:3
Current row: 1, column: 3, counter: 27, board: 27
Counter 28
Move number 0, tempR: 3, tempC:2
Move number 1, tempR: 2, tempC:1
Move number 2, tempR: 0, tempC:1
Move number 3, tempR: -1, tempC:2
Move number 4, tempR: -1, tempC:4
Move number 5, tempR: 0, tempC:5
Current row: 0, column: 5, counter: 28, board: 28
Counter 29
Move number 0, tempR: 2, tempC:4
Move number 1, tempR: 1, tempC:3
Move number 2, tempR: -1, tempC:3
Move number 3, tempR: -2, tempC:4
Move number 4, tempR: -2, tempC:6
Move number 5, tempR: -1, tempC:7
Move number 6, tempR: 1, tempC:7
Current row: 1, column: 7, counter: 29, board: 29
Counter 30
Move number 0, tempR: 3, tempC:6
Current row: 3, column: 6, counter: 30, board: 30
Counter 31
Move number 0, tempR: 5, tempC:5
Current row: 5, column: 5, counter: 31, board: 31
Counter 32
Move number 0, tempR: 7, tempC:4
Current row: 7, column: 4, counter: 32, board: 32
Counter 33
Move number 0, tempR: 9, tempC:3
Move number 1, tempR: 8, tempC:2
Move number 2, tempR: 6, tempC:2
Move number 3, tempR: 5, tempC:3
Current row: 5, column: 3, counter: 33, board: 33
Counter 34
Move number 0, tempR: 7, tempC:2
Current row: 7, column: 2, counter: 34, board: 34
Counter 35
Move number 0, tempR: 9, tempC:1
Move number 1, tempR: 8, tempC:0
Move number 2, tempR: 6, tempC:0
Move number 3, tempR: 5, tempC:1
Move number 4, tempR: 5, tempC:3
Move number 5, tempR: 6, tempC:4
Current row: 6, column: 4, counter: 35, board: 35
Counter 36
Move number 0, tempR: 8, tempC:3
Move number 1, tempR: 7, tempC:2
Move number 2, tempR: 5, tempC:2
Move number 3, tempR: 4, tempC:3
Move number 4, tempR: 4, tempC:5
Current row: 4, column: 5, counter: 36, board: 36
Counter 37
Move number 0, tempR: 6, tempC:4
Move number 1, tempR: 5, tempC:3
Move number 2, tempR: 3, tempC:3
Current row: 3, column: 3, counter: 37, board: 37
Counter 38
Move number 0, tempR: 5, tempC:2
Move number 1, tempR: 4, tempC:1
Move number 2, tempR: 2, tempC:1
Move number 3, tempR: 1, tempC:2
Move number 4, tempR: 1, tempC:4
Current row: 1, column: 4, counter: 38, board: 38
Counter 39
Move number 0, tempR: 3, tempC:3
Move number 1, tempR: 2, tempC:2
Move number 2, tempR: 0, tempC:2
Current row: 0, column: 2, counter: 39, board: 39
Counter 40
Move number 0, tempR: 2, tempC:1
Move number 1, tempR: 1, tempC:0
Current row: 1, column: 0, counter: 40, board: 40
Counter 41
Move number 0, tempR: 3, tempC:-1
Move number 1, tempR: 2, tempC:-2
Move number 2, tempR: 0, tempC:-2
Move number 3, tempR: -1, tempC:-1
Move number 4, tempR: -1, tempC:1
Move number 5, tempR: 0, tempC:2
Move number 6, tempR: 2, tempC:2
Move number 7, tempR: 3, tempC:1
Current row: 3, column: 1, counter: 41, board: 41
Counter 42
Move number 0, tempR: 5, tempC:0
Move number 1, tempR: 4, tempC:-1
Move number 2, tempR: 2, tempC:-1
Move number 3, tempR: 1, tempC:0
Move number 4, tempR: 1, tempC:2
Move number 5, tempR: 2, tempC:3
Current row: 2, column: 3, counter: 42, board: 42
Counter 43
Move number 0, tempR: 4, tempC:2
Move number 1, tempR: 3, tempC:1
Move number 2, tempR: 1, tempC:1
Move number 3, tempR: 0, tempC:2
Move number 4, tempR: 0, tempC:4
Current row: 0, column: 4, counter: 43, board: 43
Counter 44
Move number 0, tempR: 2, tempC:3
Move number 1, tempR: 1, tempC:2
Move number 2, tempR: -1, tempC:2
Move number 3, tempR: -2, tempC:3
Move number 4, tempR: -2, tempC:5
Move number 5, tempR: -1, tempC:6
Move number 6, tempR: 1, tempC:6
Current row: 1, column: 6, counter: 44, board: 44
Counter 45
Move number 0, tempR: 3, tempC:5
Current row: 3, column: 5, counter: 45, board: 45
Counter 46
Move number 0, tempR: 5, tempC:4
Current row: 5, column: 4, counter: 46, board: 46
Counter 47
Move number 0, tempR: 7, tempC:3
Move number 1, tempR: 6, tempC:2
Move number 2, tempR: 4, tempC:2
Move number 3, tempR: 3, tempC:3
Move number 4, tempR: 3, tempC:5
Move number 5, tempR: 4, tempC:6
Current row: 4, column: 6, counter: 47, board: 47
Counter 48
Move number 0, tempR: 6, tempC:5
Current row: 6, column: 5, counter: 48, board: 48
Counter 49
Move number 0, tempR: 8, tempC:4
Move number 1, tempR: 7, tempC:3
Move number 2, tempR: 5, tempC:3
Move number 3, tempR: 4, tempC:4
Current row: 4, column: 4, counter: 49, board: 49
Counter 50
Move number 0, tempR: 6, tempC:3
Move number 1, tempR: 5, tempC:2
Move number 2, tempR: 3, tempC:2
Move number 3, tempR: 2, tempC:3
Move number 4, tempR: 2, tempC:5
Current row: 2, column: 5, counter: 50, board: 50
Counter 51
Move number 0, tempR: 4, tempC:4
Move number 1, tempR: 3, tempC:3
Move number 2, tempR: 1, tempC:3
Move number 3, tempR: 0, tempC:4
Move number 4, tempR: 0, tempC:6
Current row: 0, column: 6, counter: 51, board: 51
Counter 52
Move number 0, tempR: 2, tempC:5
Move number 1, tempR: 1, tempC:4
Move number 2, tempR: -1, tempC:4
Move number 3, tempR: -2, tempC:5
Move number 4, tempR: -2, tempC:7
Move number 5, tempR: -1, tempC:8
Move number 6, tempR: 1, tempC:8
Move number 7, tempR: 2, tempC:7
Current row: 2, column: 7, counter: 52, board: 52
Counter 53
Move number 0, tempR: 4, tempC:6
Move number 1, tempR: 3, tempC:5
Move number 2, tempR: 1, tempC:5
Current row: 1, column: 5, counter: 53, board: 53
Counter 54
Move number 0, tempR: 3, tempC:4
Current row: 3, column: 4, counter: 54, board: 54
Counter 55
Move number 0, tempR: 5, tempC:3
Move number 1, tempR: 4, tempC:2
Move number 2, tempR: 2, tempC:2
Move number 3, tempR: 1, tempC:3
Move number 4, tempR: 1, tempC:5
Move number 5, tempR: 2, tempC:6
Current row: 2, column: 6, counter: 55, board: 55
Counter 56
Move number 0, tempR: 4, tempC:5
Move number 1, tempR: 3, tempC:4
Move number 2, tempR: 1, tempC:4
Move number 3, tempR: 0, tempC:5
Move number 4, tempR: 0, tempC:7
Current row: 0, column: 7, counter: 56, board: 56
Counter 57
Move number 0, tempR: 2, tempC:6
Move number 1, tempR: 1, tempC:5
Move number 2, tempR: -1, tempC:5
Move number 3, tempR: -2, tempC:6
Move number 4, tempR: -2, tempC:8
Move number 5, tempR: -1, tempC:9
Move number 6, tempR: 1, tempC:9
Move number 7, tempR: 2, tempC:8
Current row: 2, column: 8, counter: 57, board: 57
Counter 58
Move number 0, tempR: 4, tempC:7
Current row: 4, column: 7, counter: 58, board: 58
Counter 59
Move number 0, tempR: 6, tempC:6
Current row: 6, column: 6, counter: 59, board: 59
Counter 60
Move number 0, tempR: 8, tempC:5
Move number 1, tempR: 7, tempC:4
Move number 2, tempR: 5, tempC:4
Move number 3, tempR: 4, tempC:5
Move number 4, tempR: 4, tempC:7
Move number 5, tempR: 5, tempC:8
Move number 6, tempR: 7, tempC:8
Move number 7, tempR: 8, tempC:7
Current row: 8, column: 7, counter: 60, board: 60
Counter 61
Move number 0, tempR: 10, tempC:6
Move number 1, tempR: 9, tempC:5
Move number 2, tempR: 7, tempC:5
Current row: 7, column: 5, counter: 61, board: 61
Counter 62
Move number 0, tempR: 9, tempC:4
Move number 1, tempR: 8, tempC:3
Move number 2, tempR: 6, tempC:3
Move number 3, tempR: 5, tempC:4
Move number 4, tempR: 5, tempC:6
Current row: 5, column: 6, counter: 62, board: 62
Counter 63
Move number 0, tempR: 7, tempC:5
Move number 1, tempR: 6, tempC:4
Move number 2, tempR: 4, tempC:4
Move number 3, tempR: 3, tempC:5
Move number 4, tempR: 3, tempC:7
Current row: 3, column: 7, counter: 63, board: 63
Counter 64
Move number 0, tempR: 5, tempC:6
Move number 1, tempR: 4, tempC:5
Move number 2, tempR: 2, tempC:5
Move number 3, tempR: 1, tempC:6
Move number 4, tempR: 1, tempC:8
Move number 5, tempR: 2, tempC:9
Move number 6, tempR: 4, tempC:9
Move number 7, tempR: 5, tempC:8
Current row: 5, column: 8, counter: 64, board: 64
  #2  
Old 03-Apr-2006, 22:28
earachefl earachefl is offline
Member
 
Join Date: Feb 2006
Posts: 178
earachefl is on a distinguished road

Re: "Knight's Tour" problem (from Euler)


Slightly revised code, but with the same problem...
CPP / C++ / C Code:
//Knight's Tour problem (from Euler)
#include <iostream>
#include <ctime>
#include <stdlib.h>
#include <iomanip>
using namespace std;

void printTour(int[][8]);

int main () 
{
   srand(time(NULL));                                         //seed random                                     
   
   int board [8][8] = {};                                     //declare 8x8 board array, initialized to 0s
   const int horizontal[8] = {2, 1, -1, -2, -2, -1, 1, 2};    //declare legal horizontal moves
   const int vertical[8] = {-1, -2, -2, -1, 1, 2, 2, 1};      //declare corresponding vertical moves
   int currentRow, currentColumn;                             //where the Knight currently stands
   int moveNumber;                                            //for switching between legal moves 0 - 7
   int tempR = 0, tempC = 0;                                  //temporary storage of new row and column values
   int counter = 1;                                           //counter variable
   
   //Randomize starting point
   currentRow = rand() % 8;
   currentColumn = rand() % 8;
   board[currentRow][currentColumn] = counter;
   
   //Show starting point values - for debugging
   cout << "Starting row: " << currentRow << ", column: " << currentColumn
		   << ", counter: " << counter << ", board: " << board[currentRow][currentColumn] << endl;

   //outer counter controlled loop - cycle through all 64 moves
   for (counter = 2; counter <= 64; counter++)
   {
      cout << "Counter " << counter << endl;                  //for debugging
	  moveNumber = 0;                                         //initialize possible legal move to 0
	  tempR = currentRow + vertical[moveNumber];            //store temporary values after move 0
	  tempC = currentColumn + horizontal[moveNumber];           //
	  
	  //display current values for debugging
	  cout << "Move number " << moveNumber << ", tempR: " << tempR << ", tempC:" << tempC << endl;
	  
	  //inner loop - while the board value at the new position is not equal to 0 (because it has been visited)
	  //or the new temp values are out of range, and the moveNumber is less than 7, keep looping until a valid
	  //move is found
      while ((board[tempR][tempC] != 0 || tempR < 0 || tempR > 7 || tempC < 0 || tempC > 7) && moveNumber < 7)
	  {
	  
	     ++moveNumber;                                      //increment possible legal move
		 tempR = currentRow + vertical[moveNumber];         //reset temporary row and column positions
	     tempC = currentColumn + horizontal[moveNumber];
		 
		 //for debugging
		 cout << "Move number " << moveNumber << ", tempR: " << tempR << ", tempC:" << tempC << endl;
	  }  //end inner loop - valid move has been found
                                                              	   
      currentRow = tempR;                                     //set current row position to the temporary value
	  currentColumn = tempC;                                  //set current column position to the temporary value
	  board[currentRow][currentColumn] = counter;             //set the value of the board at the current position
	                                                          //to equal the counter number
	  //for debugging														  
	  cout << "Current row: " << currentRow << ", column: " << currentColumn
		   << ", counter: " << counter << ", board: " << board[currentRow][currentColumn] << endl;
   }  //end outer loop - all 64 moves finished
   
   printTour(board);	                                      //call print function			
     
   return 0;
}
void printTour (int board[][8])                                     //pretty much self-explanatory
{
   cout << "_________________________________________" << endl;     //nested for loop which prints the
   for (int i = 0; i < 8; i++)
   {
      cout << "|    |    |    |    |    |    |    |    |" << endl;  //Knight's path
      for (int j = 0; j < 8; j++)
	  {
	     cout << "| " << setw(2) << board[i][j] << " ";             //showing the counter value at each board location
      }
	  cout << "|" << endl
	       << "|____|____|____|____|____|____|____|____|" << endl;
   }
}
      
  #3  
Old 04-Apr-2006, 01:05
WaltP's Avatar
WaltP WaltP is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Midwest US
Posts: 3,435
WaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to all

Re: "Knight's Tour" problem (from Euler)


To display your board, use code tags. Sounds strange, but:
Code:
_________________________________________ | | | | | | | | | |____|____|____|____|____|____|____|____|

Some things I see.

1st, comment out the randomization (srand()) for now. Stick to one starting location until you get the program running. rand() will return the same values. Then you can tweak knowing what should be happening at each step. Randomizing at this stage is confusing. You're trying to hit a moving target.

2nd is your sloppy use of your board array. Your for and while loops calculate the new position of every possible position, whether on the board or not. For example, if you are at 7,0 (bottom left corner) you calculate new positions:
Code:
tempR tempC from 7,0: 9 -1 8 -2 6 -2 5 -1 5 1 6 2 8 2 9 1
Then in your while loop you simply use those values:
CPP / C++ / C Code:
while ((board[tempR][tempC] != 0 || ...
causing your program to test values that are not even on the board.

Move all your row/col calculations into the while loop and break out if you get a good location.
The only thing in your while statement itself should be the test for movenumber. Then within the loop
-- Calculate the next row/col
-- Then do your limit tests (<0 >7) in an if
-- Finally if the row/col are ok test your board value

Finally, how do you handle the situation where on the 48th move there are no more valid moves?
__________________

Definition: Politics
Latin, from
poly meaning many and
tics meaning blood sucking parasites
-- Tom Smothers
  #4  
Old 04-Apr-2006, 10:14
earachefl earachefl is offline
Member
 
Join Date: Feb 2006
Posts: 178
earachefl is on a distinguished road

Re: "Knight's Tour" problem (from Euler)


Quote:
Originally Posted by WaltP

Move all your row/col calculations into the while loop and break out if you get a good location.
The only thing in your while statement itself should be the test for movenumber. Then within the loop
-- Calculate the next row/col
-- Then do your limit tests (<0 >7) in an if
-- Finally if the row/col are ok test your board value

Like this?
CPP / C++ / C Code:
 while (moveNumber < 7)
	  {
	     tempR = currentRow + vertical[moveNumber];            //store temporary values after move 0
	     tempC = currentColumn + horizontal[moveNumber];           //
         if (tempR > 0 && tempR < 7 && tempC > 0 && tempC < 7)
		    if (board[tempR][tempC] == 0)
		       break;
	  
	     ++moveNumber;                                      //increment possible legal move
		 
		
	  }  //end inner loop - valid move has been found
Quote:


Finally, how do you handle the situation where on the 48th move there are no more valid moves?
Would this work?
CPP / C++ / C Code:
if (moveNumber == 8)
	     break;
I'm not that familiar with using the break statement, except in switch structures. From what I read, some programmers consider it bad practice? That's why I originally had the test conditions in the while() statement.

I must confess, I'm stumped by this one. My new revised code causes the debugger window to open, which has never happened for me before, and at the line
CPP / C++ / C Code:
	  board[currentRow][currentColumn] = counter;   
there is a message
Quote:
GD8: Program received signal: "EXC_BAD_ACCESS".
No other error messages. The run log ends with
Quote:
CH2P4.24 (Knight's Tour) has exited with status -1.
Unfortunately, I have no clue how to use the debugger.

Revised code:
CPP / C++ / C Code:
//Knight's Tour problem (from Euler)
#include <iostream>
#include <ctime>
#include <stdlib.h>
#include <iomanip>
using namespace std;

void printTour(int[][8]);

int main () 
{
   //srand(time(NULL));                                         //seed random                                     
   
   int board [8][8] = {};                                     //declare 8x8 board array, initialized to 0s
   const int horizontal[8] = {2, 1, -1, -2, -2, -1, 1, 2};    //declare legal horizontal moves
   const int vertical[8] = {-1, -2, -2, -1, 1, 2, 2, 1};      //declare corresponding vertical moves
   int currentRow, currentColumn;                             //where the Knight currently stands
   int moveNumber;                                            //for switching between legal moves 0 - 7
   int tempR = 0, tempC = 0;                                  //temporary storage of new row and column values
   int counter = 1;                                           //counter variable
   
   //Randomize starting point
   currentRow = rand() % 8;
   currentColumn = rand() % 8;
   board[currentRow][currentColumn] = counter;
   
   //Show starting point values - for debugging
   cout << "Starting row: " << currentRow << ", column: " << currentColumn
		   << ", counter: " << counter << ", board: " << board[currentRow][currentColumn] << endl;

   //outer counter controlled loop - cycle through all 64 moves
   for (counter = 1; counter <= 64; counter++)
   {
      cout << "Counter " << counter << endl;                  //for debugging
	  moveNumber = 0;                                         //initialize possible legal move to 0
	  	  
	  //display current values for debugging
	  //cout << "Move number " << moveNumber << ", tempR: " << tempR << ", tempC:" << tempC << endl;
	  
	  //inner loop - while the board value at the new position is not equal to 0 (because it has been visited)
	  //or the new temp values are out of range, and the moveNumber is less than 7, keep looping until a valid
	  //move is found
      while (moveNumber < 7)
	  {
	     tempR = currentRow + vertical[moveNumber];            //store temporary values after move 0
	     tempC = currentColumn + horizontal[moveNumber];           //
         if (tempR > 0 && tempR < 7 && tempC > 0 && tempC < 7)
		    if (board[tempR][tempC] == 0)
		       break;
	  
	     ++moveNumber;                                      //increment possible legal move
		 
		 //for debugging
		 //cout << "Move number " << moveNumber << ", tempR: " << tempR << ", tempC:" << tempC << endl;
	  }  //end inner loop - valid move has been found
	  
	  if (moveNumber == 8)
	     break;
                                                              	   
      currentRow = tempR;                                     //set current row position to the temporary value
	  currentColumn = tempC;                                  //set current column position to the temporary value
	  board[currentRow][currentColumn] = counter;             //set the value of the board at the current position
	                                                          //to equal the counter number
	  //for debugging														  
	  cout << "Current row: " << currentRow << ", column: " << currentColumn
		   << ", counter: " << counter << ", board: " << board[currentRow][currentColumn] << endl;
   }  //end outer loop - all 64 moves finished
   
   printTour(board);	                                      //call print function			
     
   return 0;
}
void printTour (int board[][8])                                     //pretty much self-explanatory
{
   cout << "_________________________________________" << endl;     //nested for loop which prints the
   for (int i = 0; i < 8; i++)
   {
      cout << "|    |    |    |    |    |    |    |    |" << endl;  //Knight's path
      for (int j = 0; j < 8; j++)
	  {
	     cout << "| " << setw(2) << board[i][j] << " ";             //showing the counter value at each board location
      }
	  cout << "|" << endl
	       << "|____|____|____|____|____|____|____|____|" << endl;
   }
}
      
  #5  
Old 04-Apr-2006, 13:00
WaltP's Avatar
WaltP WaltP is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Midwest US
Posts: 3,435
WaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to allWaltP is a name known to all

Re: "Knight's Tour" problem (from Euler)


Quote:
Originally Posted by earachefl
Like this?
CPP / C++ / C Code:
 
while (moveNumber < 7)
	  {
	     tempR = currentRow + vertical[moveNumber];            //store temporary values after move 0
	     tempC = currentColumn + horizontal[moveNumber];           //
         if (tempR > 0 && tempR < 7 && tempC > 0 && tempC < 7)
		    if (board[tempR][tempC] == 0)
		       break;
	  
	     ++moveNumber;                                      //increment possible legal move
		 
		
	  }  //end inner loop - valid move has been found
Almost. First, formatting!!!!! Line up your indents consistantly.
CPP / C++ / C Code:
while (moveNumber < 7)
{
    tempR = currentRow + vertical[moveNumber];    
    tempC = currentColumn + horizontal[moveNumber];

    // parentheses and braces in IF for readability
    if ((tempR > 0) && (tempR < 7) && (tempC > 0) && (tempC < 7))
    {
        if (board[tempR][tempC] == 0)
        {
            break;
        }
    }
    moveNumber++;     // post-increment is more standard -- style issue only
}  //end inner loop - valid move has been found

In your main if you are only valid if 1-6. Don't you want 0-7 to be valid? Need >= and <=


Quote:
Originally Posted by earachefl
Would this work?
CPP / C++ / C Code:
if (moveNumber == 8)
    break;
I'm not that familiar with using the break statement, except in switch structures. From what I read, some programmers consider it bad practice? That's why I originally had the test conditions in the while() statement.
Yes. If you don't find a valid location, you are done. For safety, I'd use >= just to be paranoid about it...

As for it being bad, no. It's normal to break out of a loop. It's how we avoid goto which is look upon by many (most?) as being a bad thing.


Quote:
Originally Posted by earachefl
I must confess, I'm stumped by this one. My new revised code causes the debugger window to open, which has never happened for me before, and at the line
CPP / C++ / C Code:
board[currentRow][currentColumn] = counter;   
there is a message No other error messages. The run log ends with Unfortunately, I have no clue how to use the debugger.
What are the values of currentRow and currentColumn? They are probably <0 or >7 would be my guess.


Now, one thing you will have to consider at some point (like maybe now) is how to actually deal with no valid location. What you have now is based on the first good move, get the next good first move. You will rarely solve the puzzle this way because the solution requires at a blocked board you back up and try a new position from the previous move. So you need to back up a step and look for new alternatives. This will actually cause you a total rewrite.

In a nutshell,
Code:
1) Find the first valid move. 2) Store each move you make in an array. 3) When you get to a stopped board (open squares and no valid moves) a) Back up a move b) Look for the next valid move c) continue at 2
This means your for loop will be changed drastically.
__________________

Definition: Politics
Latin, from
poly meaning many and
tics meaning blood sucking parasites
-- Tom Smothers
 


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Buffer problem with CD-RWriter KieranC Computer Software Forum - Windows 2 07-Jan-2006 02:45
Graphic problem in Unreal Tournament 2004 zerox Computer Software Forum - Games 10 09-Oct-2005 12:31
Runtime Problem involving "printf" in C Program supamakia C Programming Language 2 09-Oct-2005 10:09
a significant problem after installing Xp mohammad Computer Software Forum - Windows 10 09-Aug-2005 07:03

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 22:33.


vBulletin, Copyright © 2000 - 2017, Jelsoft Enterprises Ltd.