Thread: Knight's Tour-Help Please!

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    1

    Knight's Tour-Help Please!

    Anyone familiar with the Knight's tour problem? Where you have to move a knight across a chess board, reaching all squares without touching any square twice.

    I've been working on this code for a week now. I'm at my limits and out of ideas. My program solves all the way up to 62 moves, but enters a never ending loop when I try and solve for the last 2 moves.

    I'm guessing I have some little bug that's throwing something off. I have no idea what it could be. If anyone could look over my code and give me any sort of hint, anything at all. I would be very happy.

    Thanks

    Code:
    #include <iostream>
    #include <vector>
    #include <iterator>
    
    using std::cout;
    using std::endl;
    using std::vector;
    
    const int rowMoves [8] = {-2,-2, 1, 1, 2, 2, 1,-1};//Possible moves knight can make
    const int colMoves [8] = {-1, 1,-2, 2, 1,-1,-2,-2};
    
    int grid [8][8];  //The size of chessboard, keeps track of where I have been
    					//I add a '1' if I've been there.
    
    vector <int> pathRow; //vectors used to record moves
    vector <int> pathCol;
    int counter = 0;
    
    bool ktour (int,int);
    int display (); //Not part of logic, just displays at end.
    
    int main (void) 
    {	
    	int row = 0;
    	int col = 0;
    
    	if (ktour (row, col));  //Calls ktour, which will run recursivly
    	{
    		cout << "done" << endl;
    	}
    	display();
    	system ("pause");
    	return 1;
    }
    
    bool ktour (int row, int col)
    {
    	pathRow.push_back (row);  //Starts off with adding move to vectors
    	pathCol.push_back (col);
    	grid [row] [col] = 1;		//adds a one to place in grid, so I can show I've been there
    	counter++;
    
    	if (pathRow.size() == 64)  //This drops the program out of the recursive, checks to see if vector is 64
    		return true;			//needs to be 64 for 8 x 8, but I can only do 62.
    
    	int possRow, possCol, moveOption;
    
    	for (moveOption = 0; moveOption < 8; moveOption++) //Cycles through the 8 possible moves
    	{
    		possRow = row + rowMoves [moveOption];
    		possCol = col + colMoves [moveOption];
    		
    		//The below if statement tries each of the 8 moves to see if its legal
    		//If it finds a good move, it call the program again, sending the move location back to the top
    		//where I can add to vector and start again.
    		if (possRow < 8 && possRow >= 0 && possCol < 8 && possCol >= 0 && grid [possRow] [possCol] != 1)
    		{
    			if (ktour (possRow, possCol))  //recursion
    				return true;
    		}
    	}
    
    	//The below lines of code will be reached if all 8 moves have been tried, and all have failed
    	//This code will attempt to back up my program, by returning false to lase stack and resetting counters
    	grid [pathRow.back()][pathCol.back()] = 0;	//Dead end, set that spot back to 0
    	pathRow.pop_back ();			//remove move history from vectors
    	pathCol.pop_back ();
    	counter--;
    	return false;
    }
    
    int display () //Displays moves after program has solved.
    {
            for (int index=0; index<(int)pathRow.size(); ++index)
    		{	
    			cout << "Move#: " << index+1 << " Square: ";
    			cout << pathRow.at(index) << ", ";
    			cout << pathCol.at(index);
    			cout << endl;
    		}
    		return 1;
    }
    Last edited by rickster11; 04-09-2010 at 06:28 PM. Reason: Added comments

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    This line:
    Code:
    const int rowMoves [8] = {-2,-2, 1, 1, 2, 2, 1,-1};//Possible moves knight can make
    lacks the symmetry you would expect out of a knight move listing.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. knight's tour!
    By Jasin14 in forum C Programming
    Replies: 13
    Last Post: 12-22-2010, 04:30 PM
  2. Knight's Tour Recursion Problem
    By thephreak6 in forum C++ Programming
    Replies: 1
    Last Post: 10-14-2003, 09:18 AM
  3. Knights Tour Trivia
    By shrestha in forum C++ Programming
    Replies: 2
    Last Post: 01-16-2003, 08:32 AM
  4. Knight's Tour Problem 2
    By Nutshell in forum C Programming
    Replies: 11
    Last Post: 01-09-2002, 09:32 PM
  5. Knight's Tour
    By Nutshell in forum C Programming
    Replies: 31
    Last Post: 01-08-2002, 10:58 PM