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 17-Apr-2008, 14:42
harry1617 harry1617 is offline
New Member
 
Join Date: Apr 2008
Posts: 3
harry1617 is on a distinguished road

Knights tour problem (using brute force)


Hi,
I have been trying to write a program that solves the knights tour problem using brute force, as aposed to the huristic method used in the other posts i have read on the problem.
(You probably know of the basic problem, move a knight around a chess board
without visiting the same square twice. Other posts that explain it better than i can!)
Anyway, down to my specific problem, i have written a peice of code that starts the knight in the top left corner of the board and then randomly picks a moves to make untill the knight gets stuck or all 64 moves have been made and then simply prints how many moves have been attchived. (I intend to modify the program later to loop forever until all 64 moves are made.)
However when i compile and run the program somtimes it works just fine and other times it seems to freeze as though it has got stuck in an infinite loop.
I will post the code, but this is my first post so i hope it all works correctly.
Please forgive all the 'if' statments, i was worried that my boolean algebra may have been at fault.

CPP / C++ / C Code:
#include<iostream>
using std::cout;
using std::endl;

#include<cmath>
using std::srand;
using std::rand;

#include<ctime>
using std::time;

int FindNextMove(int, int); // Function used to find the next move.
bool Stuck(int, int); // Function used to see if the knight cannot move.
inline void SetBoard(); // Funtion used to 

// Array Horizontal and Vertical used to make moves
// in keeping with the knight's abilities.
static int Horizontal[8] = {2,   1, -1, -2, -2, -1, 1, 2};
static int Vertical[8] =   {-1, -2, -2, -1,  1,  2, 2, 1}; 
// Array Board used to represent the chess board. 
int Board[8][8] = {0};

int main()
{     
   srand(time(0));
   int MoveCounter = 1;
   int Move;
   int CR = 0; // Represents the Current Row the knight is on.
   int CC = 0; // Represents the Currrent Coloumn the knight is on.
   
   Board[CR][CC] = MoveCounter;   
   
   for(int j = 0; j < 64; j++)
   {
      MoveCounter++;
      
      Move = FindNextMove(CR, CC); // Randomly find the next move.
         
      CR += Horizontal[Move]; // Ajust Coloumn and Row with move found.
      CC += Vertical[Move];
         
      Board[CR][CC] = MoveCounter; // Move the knight there.

      // Check to see if the knight is stuck.
      if(Stuck(CR, CC) == true)
         break;
      else
         ;
   }
   
   cout << "1: " << MoveCounter
        << endl;
   
   system("PAUSE");
   return 0;
}

bool Stuck(int CR, int CC)
{
   int Counter = 0;
   int NR; // Represents the next possible row.
   int NC; // Represents the next possible column.
   
   // Loop through all possible moves and increment
   // a counter if that move is blocked.
   for(int k = 0; k < 8; k++)
   {  
      NR = CR;
      NC = CC;      
   
      NR += Horizontal[k];
      NC += Vertical[k];

      if(NR > 7)
      {
         Counter++;
         continue;
      }
      if(NR < 0)
      {
         Counter++;
         continue;
      }
      if(NC > 7)
      {
         Counter++;
         continue;
      }
      if(NC < 0)
      {
         Counter++;
         continue;
      }
      if(Board[NR][NC] > 0)
      {
         Counter++;
         continue;
      }
   }
   
   // If all moves are blocked...
   if(Counter == 8)
      return true;
   else
      return false;
}

int FindNextMove(int CR, int CC)
{
   int Move;
   int NR;
   int NC;

   // Loop while an invalid move is picked.
   for(;;)
   {
      Move = 0 + rand() % 7;  
      NR = CR;
      NC = CC;      
   
      NR += Horizontal[Move];
      NC += Vertical[Move];
      
      if(NR > 7)
         continue;
      if(NR < 0)
         continue;
      if(NC > 7)
         continue;
      if(NC < 0)
         continue;
      if(Board[NR][NC] > 0)
         continue;
      else 
         break;
   }   
   return Move;
}
  #2  
Old 18-Apr-2008, 13:11
fakepoo fakepoo is offline
Regular Member
 
Join Date: Oct 2007
Posts: 969
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: Knights tour problem (using brute force)


That is an interesting problem. I didn't look too deeply at your code as I have a suggestion as to how I would solve it. I would represent the path of a knight as a 2D array of integers and a move number. Initially, all of the array elements will be set to -1. Then, as the knight moves to a space, the corresponding element will be changed to the move number. This will make it very easy to see the path of the knight.

Then, I would use recursion to move the knight at every possible combination until it completes the entire board.

I have completed the task and would like to share some of it with you:
CPP / C++ / C Code:
// GameBoard.h
#include <iostream>

#define NUM_ROWS 8
#define NUM_COLS 8

class GameBoard
{ public:
	GameBoard();
	~GameBoard();
    
	bool HasBeenUsed( int row, int col ); // has this space been used by the knight?
	void Move( int row, int col ); // move to that space, increment MoveNumber
	bool UsedAllPositions(); // have all positions been used?
	bool IsValidPosition( int row, int col ); // Is row/col between 0 and 7 (inclusive)?
	
	void Print();

  private:
	int Board[NUM_ROWS][NUM_COLS];  // initialize all to -1
	int MoveNumber; // initialize to 0
};

// This is the function to be called recursively
// Returns true if the move resulted in a completely filled board (which is shown in gbResult)
// Returns false if it ran into a dead end
bool MakeMove( int row, int col, GameBoard gbCurrent, GameBoard& gbResult );

I'll let you think about how you would implement this. Later, I will show the rest of the code to help with any uncertain areas. I will say that with an 8x8 board, it runs for a LONG TIME. If you chose a 5x5 board, it finishes much sooner.
  #3  
Old 18-Apr-2008, 13:29
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Knights tour problem (using brute force)


Quote:
Originally Posted by harry1617
...randomly picks a moves to make untill the knight gets stuck...somtimes it works ...and other times i...infinite loop.

You need to have some way of finding whether it is "stuck" while it is in the FindNextMove function.

Note that it is possible to get into a corner (or maybe other position) where there is no next move.

For example, from a starting position in the upper left corner, the following sequence of moves (as defined in your arrays) will get the Knight stuck:
Code:
6 0 0 6 5 0 3 6 1 3 0

After these 11 moves from the original postion, the board looks like:
Code:
1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 11 8 0 6 0 0 0 0 0 5 0 9 0 0 0 12 0 10 7 0 0 0 0

Now the Knight is in the lower left corner with no way out. (Therefore your FindNextMove() function is, indeed, in an infinite loop.)

So: the loop inside FindNextMove() should, somehow, know when to quit when it has tried all possible moves. Then FindNextMove() can return a negative value if it has tried them all without finding a valid move, and the main program will know it is stuck without calling another function.

Maybe something like:

CPP / C++ / C Code:

int main()
.
.
.
        Move = FindNextMove(CR, CC);    // Randomly find the next move.
        if (Move < 0) {
            // It's stuck. Abandon all hope.
            // print error message or whatever
            break; 
        }
        else {
            // Adjust row and column and store move number at that position
        }
.
.
.

                    
bool tried_them_all(int *c, int n);

int FindNextMove(int CR, int CC)
{
    int Move;
    int NR;
    int NC;
    int counter[8] = {0};
    bool success = false;

  
    // Loop while an invalid move is picked.
    while (!tried_them_all(counter, 8 )) {
.
.
        //all of your tests that will reject this move
.
.
            else {// this is the good move
                success = true;
                break;
            }
        }
    }
    if (!success) {// left the loop because it had tried them all
        Move = -1;
    }
    return Move;
}
.
.
.
bool tried_them_all(int *c, int n)
{
    // loop through c[i]
    // If all values are non-zero, then return true
    // if there is (at least) one that is zero, return false
}


[edit]Instead of changing it the way that I showed, maybe you could just put your Stuck() test before you call FindNextMove()---I haven't tested it, but this could, maybe, solve it with no significant changes to your code.[[/edit]

Hmmm. I wonder if there are fewer than 11 moves that get you stuck??? I mean, I just doodled around until I came up with those (and I'm not a chess player). If it hasn't been done already, maybe someone could do an "inverse knight's tour" search to find the fewest moves that trap the knight. Just a thought.

Regards,

Dave

Footnote: Since you have eight possible moves (and eight values in the Vertical and Horizontal arrays), you should let the move number be rand()%8, not rand()%7
Last edited by davekw7x : 18-Apr-2008 at 14:58.
  #4  
Old 18-Apr-2008, 15:20
harry1617 harry1617 is offline
New Member
 
Join Date: Apr 2008
Posts: 3
harry1617 is on a distinguished road

Re: Knights tour problem (using brute force)


Thanks Dave for looking into the problem and i have made use of your suggestions, it seems that the silly mistake of using ran() % 7 and not rand() % 8 was a big part of the problem. Anyway, it may take hours to find out if it works!
Im up to just over 13millilon attempts at finding a route so far.
Fakepoo's program looks like it would solve the problem faster, because at the moment my program doesn't garrentee every possible combination of moves is made, however your program looks to be beyond my capabilities.

Anyway, thanks again.
  #5  
Old 21-Apr-2008, 08:02
fakepoo fakepoo is offline
Regular Member
 
Join Date: Oct 2007
Posts: 969
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: Knights tour problem (using brute force)


Here is all of the code for the solution that I came up with:

CPP / C++ / C Code:
//GameBoard.h
#include <iostream>

#define NUM_ROWS 8
#define NUM_COLS 8

class GameBoard
{ public:
	GameBoard();
	~GameBoard();
    
	bool HasBeenUsed( int row, int col ); // has this space been used by the knight?
	void Move( int row, int col ); // move to that space, increment MoveNumber
	bool UsedAllPositions(); // have all positions been used?
	bool IsValidPosition( int row, int col ); // Is row/col between 0 and 7 (inclusive)?
	
	void Print();

  private:
	int Board[NUM_ROWS][NUM_COLS];  // initialize all to -1
	int MoveNumber; // initialize to 0
};

bool MakeMove( int row, int col, GameBoard gbCurrent, GameBoard& gbResult );
CPP / C++ / C Code:
//GameBoard.cpp
#include "GameBoard.h"
using namespace std;

GameBoard::GameBoard()
{	
	int i,j;

	MoveNumber = 0;
	for(i=0;i<NUM_ROWS;++i)
	{
		for(j=0;j<NUM_COLS;++j)
		{
			Board[i][j] = -1;
		}
	}
}


//GameBoard::GameBoard( GameBoard* gb ); // copy constructor
GameBoard::~GameBoard()
{	
	// Delete any memory
}
    
bool GameBoard::HasBeenUsed( int row, int col )
{	
	if(!IsValidPosition( row, col )) return false;
	return Board[row][col] >= 0;
}
    
void GameBoard::Move( int row, int col )
{	
	if(IsValidPosition(row,col))
		Board[row][col] = MoveNumber++;
}

bool GameBoard::UsedAllPositions()
{
	int i,j;

	for(i=0;i<NUM_ROWS;++i)
	{
		for(j=0;j<NUM_COLS;++j)
		{
			if(Board[i][j] < 0) return false;
		}
	}
	return true;
}
    
bool GameBoard::IsValidPosition( int row, int col )
{	
	return	row >= 0 &&
			row < NUM_ROWS &&
			col >= 0 &&
			col < NUM_COLS;
}

void GameBoard::Print()
{	int i,j,width;
	char fill;
	
	width = cout.width(2);
	fill = cout.fill('_');
	for(i=NUM_ROWS-1;i>=0;--i)
	{	
		for(j=0;j<NUM_COLS;++j)
		{	
			//cout << Board[i][j] << " ";
			printf("%2d ",Board[i][j]);
		}
		//cout << endl;
		printf("\n");
	}
	cout.width(width);
	cout.fill(fill);
}



bool MakeMove( int row, int col, GameBoard gbCurrent, GameBoard& gbResult )
{
	cout << row << " " << col << endl;
	gbCurrent.Move( row, col );
	gbCurrent.Print();
	//cin.get();
  
	// Have we hit all of the positions?
	if( gbCurrent.UsedAllPositions() ) 
	{	
		gbResult = gbCurrent;
		return true;
	}

	// UP 2, RIGHT 1
	if( gbCurrent.IsValidPosition( row+2, col+1 ) && !gbCurrent.HasBeenUsed( row+2, col+1 ))
	{ 
		if(MakeMove(row+2,col+1,gbCurrent,gbResult)) return true;
	}
	// UP 2, LEFT 1
	if( gbCurrent.IsValidPosition( row+2, col-1 ) && !gbCurrent.HasBeenUsed( row+2, col-1 ))
	{ 
		if(MakeMove(row+2,col-1,gbCurrent,gbResult)) return true;
	}
	// UP 1, RIGHT 2
	if( gbCurrent.IsValidPosition( row+1, col+2 ) && !gbCurrent.HasBeenUsed( row+1, col+2 ))
	{ 
		if(MakeMove(row+1,col+2,gbCurrent,gbResult)) return true;
	}
	// UP 1, LEFT 2
	if( gbCurrent.IsValidPosition( row+1, col-2 ) && !gbCurrent.HasBeenUsed( row+1, col-2 ))
	{ 
		if(MakeMove(row+1,col-2,gbCurrent,gbResult)) return true;
	}
	// DOWN 2, RIGHT 1
	if( gbCurrent.IsValidPosition( row-2, col+1 ) && !gbCurrent.HasBeenUsed( row-2, col+1 ))
	{ 
		if(MakeMove(row-2,col+1,gbCurrent,gbResult)) return true;
	}
	// DOWN 2, LEFT 1
	if( gbCurrent.IsValidPosition( row-2, col-1 ) && !gbCurrent.HasBeenUsed( row-2, col-1 ))
	{ 
		if(MakeMove(row-2,col-1,gbCurrent,gbResult)) return true;
	}
	// DOWN 1, RIGHT 2
	if( gbCurrent.IsValidPosition( row-1, col+2 ) && !gbCurrent.HasBeenUsed( row-1, col+2 ))
	{ 
		if(MakeMove(row-1,col+2,gbCurrent,gbResult)) return true;
	}
	// DOWN 1, LEFT 2
	if( gbCurrent.IsValidPosition( row-1, col-2 ) && !gbCurrent.HasBeenUsed( row-1, col-2 ))
	{ 
		if(MakeMove(row-1,col-2,gbCurrent,gbResult)) return true;
	}
	return false;
}
  #6  
Old 21-Apr-2008, 15:11
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Knights tour problem (using brute force)


Quote:
Originally Posted by fakepoo
Here is all of the code...
Thanks. Maybe I'll give it a shot.

For the Original Poster: I think the best part of trying the "brute force" method is that you may be able to get a feel for the actual complexity of the problem (computational complexity from a Big-O point of view, not from a programming difficulty point of view.)

Take the basic Big-O complexity of the fundamental task, and add the uncertainty and non-organized approach of trying random sequences of random moves, and I would say that you would have to be lucky, indeed, to find a solution before our sun goes nova (or before your computer expires or before your grandchildren have grandchildren, whichever comes first).

On the other hand using pseudo-random number sequences (some form of Monte Carlo method) for certain classes of problems has been used extensively and successfully in lots of disciplines where the problem is not particularly amenable to mathematical or physical analysis.

Regards,

Dave
 


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
Problem with getting multiple solutions from Knight's Tour... amarufox C++ Forum 3 22-Apr-2006 13:08
Knight's Tour - now with heuristics earachefl C++ Forum 0 09-Apr-2006 10:19
Knights Tour - Reloaded . kobi_hikri C Programming Language 12 03-Oct-2005 12:15

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

All times are GMT -6. The time now is 01:32.


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