Hello everyone, I'm having a bit of an issue here. I'm doing a Knight's Tour program for class, and thought I just about had it until this problem popped up.

While I was writing my code, I had some simple cout test statements after some of the function calls just to be able to mark my progress as I went along. Later, my program finally was displaying the proper filled solution arrays, with the test statements in between. When I went to get rid of these statements, the program no longer worked properly.

//find next possible moves; 
	      cnt = next_valid_cells(cc, nc);
	      
	      cout << "TEST" << endl;
     
	    //find the best move out of all these valid moves
	      bestndx = bestmove(nc, cnt);

I narrowed it down to the above "TEST" statement I used between these two function calls. When I run the program with the statement there like above, it works...but with "TEST" between all the solution arrays 60 or so times depending on the particular solution its testing. When I comment it out, the program hangs and doesn't do anything.

I don't understand why I can't just remove that cout statement, which would leave my program running just right. I've never had a problem like this before, so I thought I'd come to the pros. Any help would be appreciated.

Recommended Answers

All 5 Replies

There's a memory overwrite bug in your code somewhere (most likely anyway).

Without seeing the whole code, we're not going to figure anything out staring at those 3 lines.

Sorry about that, I didn't know if I should post the whole code or not or if there was just some obvious answer that was eluding me.
Here's all the code.

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

#define SIZE 8

int board[SIZE][SIZE];                     //board, DX, DY, PRIORITY
const int DX[SIZE] = {-2,-1, 1,2, 2,  1,-1,-2};  //are all global variables
const int DY[SIZE] = { 1, 2, 2,1,-1, -2,-2,-1};
const int PRIORITY[SIZE][SIZE] = { 
				{1,2,2,2,2,2,2,1},
				{2,3,4,4,4,4,3,2},
				{2,4,5,6,6,5,4,2},
				{2,4,6,7,7,6,4,2},
				{2,4,6,7,7,6,4,2},
				{2,4,5,6,6,5,4,2},
				{2,3,4,4,4,4,3,2},
				{1,2,2,2,2,2,2,1},
			};
struct CELL {  //a cell on the board
  int row, col;
};
void display_board() {  //display the board, 0=empty; >0 means occupied
  int i, j;
  for  (i = 0; i < SIZE; i++) 
  {
    for (j = 0; j < SIZE; j++) 
    {
      cout << setw(4) << board[i][j];
    }
    cout << endl;
  }
}
void init() { //board[i][j]==0 means cell (i, j) is empty
  int i, j;
  for  (i = 0; i < SIZE; i++) 
  {
    for (j = 0; j < SIZE; j++) 
    {
      board[i][j] = 0;
    }
  }	
}
bool valid_cell(int row, int col) {  //(row, col) is "valid" if it is inside the board and is empty
     //to be valid row and col should be >=0 and < SIZE
     //also: board[row][col]should be ==0
     //write this code
    
     if ( row < 0 || row >= SIZE )   //checks for row inside the board
     {
        return false;
     }
     
     if ( col < 0 || col >= SIZE )   //checks for column inside the board
     {
        return false;
     }
        
     if ( board[row][col] != 0 )     //checks if cell is empty
     {
        return false; 
     }
     
     else
     {
        return true;             //returns true for valid cells
     } 
}
int next_valid_cells (CELL c, CELL nc[]) { //store the next valid cells in nc array and return the count 
    //go thru all cells: (c.row+DX[i], c.col+DY[i]) i=0 to SIZE-1
    //if it is valid cell put it in nc array
    //and keep trackof how many are there: cnt and return this value
    
    int count = 0;
    
    for ( int i = 0; i < SIZE; i++ )     //loop cycles through the 8 possible moves
       //write the code
    {    
        if ( valid_cell( c.row+DX[i], c.col+DY[i] ) )   //if cell is valid
        {
             nc[count].row = c.row+DX[i];           //assigns valid cell row to nc array
             nc[count].col = c.col+DY[i];           //assigns valid cell column to nc array
             count++;                                //counts number of valid moves
        }
    }
    
    return count;      // returns valid move count
}

int bestmove(CELL nc[], int cnt) { //return the index of the best move
	//you know nc[0], nc[1],  nc[cnt-1] hold the valid cells
	//find the cell which has the least priority number
	//and return this index
    
    //complete this code
    
    int best_index, smallest;
    
    if ( cnt == 0 )   //if count is zero, there were no valid moves found
    {
         best_index = -1;
    }
    
    else
    {
        smallest = PRIORITY[nc[0].row][nc[0].col];
        
        for ( int i = 1; i < cnt; i++ )
        {
            if ( PRIORITY[nc[i].row][nc[i].col] < smallest )
            {
                 smallest = PRIORITY[nc[i].row][nc[i].col];
                 best_index = i;
            }
        }
    }
            
    return best_index;
}



int main() {
  int i, j, num, cnt, bestndx;
  CELL cc, nc[SIZE];       //cc=current cell; nc=next cell array
  for ( i = 0; i < SIZE; i++) 
  {
	for (j = 0; j < SIZE; j++) 
    {  //go thru all start positions (i, j)
	  init();  //make board all 0. (all empty)
	  cc.row = i; 
      cc.col = j; 
      num = 1; 
      board[cc.row][cc.col] = num; //put 1 on the start cell
      num++; //increment and keep ready to put the next number
      
      
      while (1) 
      { //keep going as long as you can go or this starting point (i, j)
	    //find next possible moves; 
	      cnt = next_valid_cells(cc, nc);
	      
	      cout << "TEST" << endl;
     
	    //find the best move out of all these valid moves
	      bestndx = bestmove(nc, cnt);
	    
	      if ( bestndx == -1 )
          {
             break;
          }  //no valid moves; break out of while loop
	    //else put the number on the board and reset current cell to be this new cell and loop back	  
          else 
          {
             board[nc[bestndx].row][nc[bestndx].col] = num; 
             num++;
             cc.row = nc[bestndx].row; cc.col = nc[bestndx].col;
          }
        
	  } //completed for one start position (i, j)
      display_board();
	  if (num < 65) { 
		cout << i <<" " << j << " failed. max entry= " << num - 1 << endl; 
	  }
	  else cout << "SUCCESS!! made all 64 moves from " << i << " " << j << endl;
	}
  }
  
 
  system("pause");
  return 0;
}
smallest = PRIORITY[nc[0].row][nc[0].col];
    
    for ( int i = 1; i < cnt; i++ )

If count is 1, bestindex is garbage.

smallest = PRIORITY[nc[0].row][nc[0].col];
    
    for ( int i = 1; i < cnt; i++ )

If count is 1, bestindex is garbage.

Thanks for spotting that! I initialized best_index to zero, and the everything was fixed when I removed the test statement.

So how did the garbage data that I had when count was 1 cause the program to not run correctly with that test statement? I would have thought that it would messed up the actual solutions, which it didn't appear to do. Just trying to understand how the two relate.

Thanks again. :-)

Pure dumb luck is all.

Your cout statement basically filled that part of the stack with a value which was harmless enough (maybe even the right answer).

Taking out the cout statement, that part of memory had different garbage, and a different result.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.