Thread: Knights Tour Trivia

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    2

    Question Knights Tour Trivia

    Hi all....
    I've been makin the Knight's tour program...basically...it is finding the number of possible ways in which the knight in a chess board can move and fill all the spaces in the board without visiting the same space twice......well...I have used a two dimensional array to form the board used recursion to track every move.....according to my program...the knight tries all the possible moves...and recurses the move function......but for some erason, while using a 5X5 board, my moves dont go to more than 16 moves...and on a 8X8 board, the moves dont go further than 48 moves.......I just couldnt figure out why it is doing this....can somebody please help me with this!!!!

    Here is a copy of my code:

    Code:
    #include <iostream.h>
    #include <cctype>
    #include <cstdlib>
    
    //To Change the size of the board, Simply change this:
    const int max_num=8;
    
    const int dispnum=1;//change this to change num of free holes
    int numove=max_num*max_num;
    int mover=1;
    int count=0;
    int count1=0;
    
    
    struct chess
    	{
    	int board[9][9];
    	int x;
    	int y;
    	int move;
    	};
    
    void draw(chess board);
    bool movepossible(chess board);
    void moving(chess board);
    
    void main()
    	{
    	chess board;
    	
    	 
    	 board.x=0;
    	 board.y=0;  
    	 board.move=0;
      
    
    		for (int i=0; i<max_num+1; i++)
    		   {
    		   for (int j=0; j<max_num; j++)
    			board.board[i][j]=0;
    		   }
    //Test For Convergence
    	 board.board[0][0]=1;
    	 board.x=0;
    	 board.y=0;
    draw(board);
    moving(board);
    cout<<"Final Count is: "<<count<<endl;
    
    	}
    void draw(chess board)
    	{
    
    	for (int i=0; i<max_num;i++)
             cout<<"-----";
    		cout<<endl;
    
    	 for (i=0; i<max_num; i++)	  
    		{
    		cout<<"|";
    
    			for (int j=0;j<max_num; j++)
    			{
    		cout<<" ";
    			if (board.board[i][j] ==0)
    				cout<<"  ";
    			else
    			{
    				cout<<board.board[i][j];
    				if (board.board[i][j]<10)
    						cout<<" ";
    			}
    				cout<<" |";
    			}
    		cout<<endl;
    		for(int i=0; i<max_num; i++)
    			cout<<"-----";
    		cout<<endl;
    		}
    	 
    	}
    
    void moving(chess board)
    	{
    
    
    
    /*
    //USE THIS TO TRACK THE NUMBER MF MOVES 
    
    	if (mover>47)
    	{
    	draw(board);
    	cout<<"MOVE NO: "<<mover<<endl;
    	}
    */
      //Case #1
    
    	if((board.x-2)>0 && (board.y+1)<max_num && board.board[board.x-2][board.y+1]==0)
    		{
    		 board.x=board.x-2;
    		 board.y=board.y+1;
    		 
    		 board.move++;
    		 mover++;
    		board.board[board.x][board.y]=mover;
    	
    		if(mover<numove)
    			{
    			moving(board);
    			}
    			board.board[board.x][board.y]=0;
    
    			board.x=board.x+2;
    			board.y=board.y-1;
    			mover--;
       		}
    
    	//Case #2	
    	if((board.x-1)>0 && (board.y+2)<max_num && board.board[board.x-1][board.y+2]==0)
    		{
    		 board.x=board.x-1;
    		 board.y=board.y+2;
    		 
    		 board.move++;
    		 mover++;
    		board.board[board.x][board.y]=mover;
    	
    		if(mover<numove)
    			{
    			moving(board);
    			}
    			board.board[board.x][board.y]=0;
    
    			board.x=board.x+1;
    			board.y=board.y-2;
    			mover--;
       		}
    
    //Case #3
    	if((board.x+1)<max_num && (board.y+2)<max_num && board.board[board.x+1][board.y+2]==0)
    		{
    		 board.x=board.x+1;
    		 board.y=board.y+2;
    		 
    		 board.move++;
    		 mover++;
    		board.board[board.x][board.y]=mover;
    	
    		if(mover<numove)
    			{
    			moving(board);
    			}
    			board.board[board.x][board.y]=0;
    
    			board.x=board.x-1;
    			board.y=board.y-2;
    			mover--;
       		}
    
    	//Case #4
    	if((board.x+2)<max_num && (board.y+1)<max_num && board.board[board.x+2][board.y+1]==0)
    		{
    		 board.x=board.x+2;
    		 board.y=board.y+1;
    		 
    		 board.move++;
    		 mover++;
    		board.board[board.x][board.y]=mover;
    	
    		if(mover<numove)
    			{
    			moving(board);
    			}
    			board.board[board.x][board.y]=0;
    
    			board.x=board.x-2;
    			board.y=board.y-1;
    			mover--;
       		}
    
    	//Case #5
    	if((board.x+2)<max_num && (board.y-1)>0 && board.board[board.x+2][board.y-1]==0)
    		{
    		 board.x=board.x+2;
    		 board.y=board.y-1;
    		 
    		 board.move++;
    		 mover++;
    		board.board[board.x][board.y]=mover;
    	
    		if(mover<numove)
    			{
    			moving(board);
    			}
    			board.board[board.x][board.y]=0;
    
    			board.x=board.x-2;
    			board.y=board.y+1;
    			mover--;
       		}
    
    	//Case #6
    	if((board.x+1)<max_num && (board.y-2)>0 && board.board[board.x+1][board.y-2]==0)
    		{
    		 board.x=board.x+1;
    		 board.y=board.y-2;
    		 
    		 board.move++;
    		 mover++;
    		board.board[board.x][board.y]=mover;
    	
    		if(mover<numove)
    			{
    			moving(board);
    			}
    			board.board[board.x][board.y]=0;
    
    			board.x=board.x-1;
    			board.y=board.y+2;
    			mover--;
       		}
    
    	//Case #7
    	if((board.x-1)>0 && (board.y-2)>0 && board.board[board.x-1][board.y-2]==0)
    		{
    		 board.x=board.x-1;
    		 board.y=board.y-2;
    		 
    		 board.move++;
    		 mover++;
    		board.board[board.x][board.y]=mover;
    
    		if(mover<numove)
    			{
    			moving(board);
    			}
    			board.board[board.x][board.y]=0;
    
    			board.x=board.x+1;
    			board.y=board.y+2;
    			mover--;
       		}
    
    	//Case #8
    	if((board.x-2)>0 && (board.y-1)>0 && board.board[board.x-2][board.y-1]==0)
    		{
    		 board.x=board.x-2;
    		 board.y=board.y-1;
    		 
    		 board.move++;
    		 mover++;
    		board.board[board.x][board.y]=mover;
    		
    	
    		if(mover<numove)
    			{
    			moving(board);
    			}
    			board.board[board.x][board.y]=0;
    
    			board.x=board.x+2;
    			board.y=board.y+1;
    			mover--;
       		}
    	
    	if (mover==numove)
    	{
    		draw(board);
    		count++;
    		cout<<"Total Count is: "<<count <<endl;
    	}

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Two problems with your code that should clear it up. First off, your board starts at (0,0) but you constantly check to make sure that the knight's position is GREATER than zero. Change all of your
    Code:
    if((board.x-1)>0 && (board.y-2)>0 && etc etc....)
    to
    Code:
    if((board.x-1)>=0 && (board.y-2)>=0 && etc etc...)
    Now your knight can actually hit the top and the left edges!

    Second of all, you don't check to see if the knight's tour is done until AFTER you subtract the last spot and move on with the rest of the recursion. This makes it so when it finally reaches the check at the end, the count is NEVER the amount you are looking for. You need to check to see if the knight has finished after every move like so:
    Code:
    if(mover<numove)
    {
       moving(board);
    }
    else
    {
       cout<<"Whoohoo, I finished the tour!!!";
       draw(board);  // just to proove to you that he did it!
       count++;
    }

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    2

    Thanks!!!!

    Thanks a lot.....The program works now!!!! Thanks to your sharpe eye!!!!

    PEACE!!!
    Shrestha

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: couting problems
    By Sektor in forum C++ Programming
    Replies: 3
    Last Post: 01-19-2004, 12:46 PM
  3. Knight's Tour Recursion Problem
    By thephreak6 in forum C++ Programming
    Replies: 1
    Last Post: 10-14-2003, 09:18 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