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;
        }

---

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++;
}

---

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

PEACE!!!
Shrestha