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 09-Apr-2006, 10:19
earachefl earachefl is offline
Member
 
Join Date: Feb 2006
Posts: 178
earachefl is on a distinguished road

Knight's Tour - now with heuristics


OK, thanks to WaltP for his help with my beginning attempts at this. Here is my newest version, which actually works, yay! I still have to implement a version which looks ahead to the following move. In the meantime, any comments would be appreciated.

I don't know what's going on with my indenting. In my compiler, I have everything lined up perfectly, yet when I post it here, it goes haywire. I don't use tab, either - I indent three spaces each time. Perhaps there's a preference in my compiler (XCode 2.2) that is affecting this - will have to check.

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

//function prototypes
void startPoint(int&, int&);
void legalMove(const int, const int, const int[], const int[], const int[][8], bool[]);
int firstBest(const bool[], const int, const int, const int[], const int[], const int [][8]);
void modifyAccess(const int, const bool[], const int, const int, const int[], const int[], int[][8]);
void printTour(int[][8]);

int main () 
{
   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
   bool legal[8] = {false};                                   //array to store possible legal moves
   int startRow = 0, startColumn = 0;                         //declare and initialize starting point
   int currentRow, currentColumn;                             //where the Knight currently stands
   int firstBestMove;                                         //for storage of first best legal move
   int counter;                                               //for inner loop counter

   //outer counter controlled loop - cycle through 64 iterations, starting at each of the 64 possible start points   
   for (int s = 1; s <= 64; s++)
   { 
      int access[8][8] = {{2,3,4,4,4,4,3,2},                  //declare 8x8 accessibility heuristic
                          {3,4,6,6,6,6,4,3},
					      {4,6,8,8,8,8,6,4},
					      {4,6,8,8,8,8,6,4},
					      {4,6,8,8,8,8,6,4},
					      {4,6,8,8,8,8,6,4},
					      {3,4,6,6,6,6,4,3},
					      {2,3,4,4,4,4,3,2}};
     
      //set starting point
      currentRow = startRow;
      currentColumn = startColumn;
	  
	  //initialize board to 0s
	  for (int i = 0; i < 8; i++)
	  {
	     for (int j = 0; j < 8; j++)
		 {
		    board[i][j] = 0;
		 }
	  }
   
      board[currentRow][currentColumn] = 1;                    //initialize board to first move
   
      //inner counter controlled loop - cycle through all 64 moves
      for (counter = 2; counter <= 64; counter++)
      {
	     //function call - check all legal moves and update legal array
	     legalMove(currentRow, currentColumn, vertical, horizontal, board, legal);
		 
		 //function call - check all legal moves and find the first move with the lowest heuristic
		 firstBestMove = firstBest(legal, currentRow, currentColumn, vertical, horizontal, access);
		 
         if (firstBestMove == -1)                              //if no legal moves available, break out of inner loop
	     {
	        break;
	     }
		 
		 //function call - Modify accessibility heuristic for remaining legal moves
		 modifyAccess(firstBestMove, legal, currentRow, currentColumn, vertical, horizontal, access);
        	    	  
         //Move Knight
         currentRow += vertical[firstBestMove];                //set current row position to the next move
	     currentColumn += horizontal[firstBestMove];           //set current column position to the next move
	     board[currentRow][currentColumn] = counter;           //set the value of the board at the current position
	                                                           //to equal the counter number
	    }  //end inner loop
   
   //call print function
   printTour(board);	                                      
   
   if (counter == 65)                                
   {
      cout << endl << "Knight finished tour" << endl;
   }
   
   //function call - increment starting point
   startPoint (startRow, startColumn);
   
   }// end outer loop
        
   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;
   }
}

//increment starting point
void startPoint (int& row, int& column)
{
   ++column;
   if (column >= 8)
   {
      column = 0;
	  ++row;
   }
}

//determine which of eight moves are legal
void legalMove(const int cRow, const int cColumn, const int vert[], const int horiz[], const int board[][8], bool legal[])
{ 
   int moveNumber = 0;                                             //initialize possible legal move to 0
   while (moveNumber < 8)
   {
      int tempR = cRow + vert[moveNumber];                         //store temporary values after move 0
      int tempC = cColumn + horiz[moveNumber];           
		 
      if (tempR >= 0 && tempR <= 7 && tempC >= 0 && tempC <= 7)    //Checks for legal bounds
      {  
         if (board[tempR][tempC] == 0)                             //Checks for non-visited square
         {                                                         //if not visited and in bounds
            legal[moveNumber] = true;                              //stores true in legal moves array at current move #
         }
         else
		 {
            legal[moveNumber] = false;                             //stores false in legal moves array at current move #
         }
      }
      else
         {
            legal[moveNumber] = false;
         }
      ++moveNumber;                                                //increment possible legal move
   }  
}

 //Find lowest accessibility heuristic
int firstBest(const bool legal[], const int cRow, const int cColumn, const int vert[], const int horiz[], const int access[][8])
{
   int minAccess = 8;                                             //variable to store best accessibility heuristic - initialize to highest level
   int firstBestMove = -1;                                        //initialize to false value
   for (int moveNumber = 0; moveNumber < 8; moveNumber++)         //cycle through all 8 possible moves
   {
      if (legal[moveNumber] == false)                             //If move is illegal, skip remaining statements in inner loop
      {
         continue;
      }
      int tempR = cRow + vert[moveNumber];                        //store temporary values at current legal move
      int tempC = cColumn + horiz[moveNumber];                    //
	
      if (access[tempR][tempC] < minAccess)                       //
      {
         minAccess = access[tempR][tempC];
         firstBestMove = moveNumber;                              //Store first legal move with lowest accessibility
      }
   } //end for loop
	  
   return firstBestMove;
}

//Modify accessibility heuristic array for remaining legal moves
void modifyAccess(const int firstBest, const bool legal[], const int cRow, const int cColumn, const int vert[], const int horiz[], int access[][8])
{ 
   for (int moveNumber = firstBest + 1; moveNumber < 8; moveNumber++)
   {
      if (legal[moveNumber] == false)                            //If move is illegal, skip remaining statements in for loop
	  {
         continue;
      }
 
      int tempR = cRow + vert[moveNumber];                       //store temporary values at current legal move
      int tempC = cColumn + horiz[moveNumber];                   //

      --access[tempR][tempC];                                    //Decrement accessibility heuristic array at remaining legal moves
   }
}
 


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
Knights Tour - Reloaded . kobi_hikri C Programming Language 12 03-Oct-2005 12:15
knight tour (chess program) kai85 C++ Forum 10 25-Mar-2005 07:12
Knight tour (arrays help needed) dilmv C++ Forum 7 18-Oct-2004 14:31
Robs World Tour jrobbio Open Discussion Forum 3 29-Mar-2004 23:04

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

All times are GMT -6. The time now is 23:08.


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