Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

The knight's tour problem in c++

Posted on 2002-11-25
12
Medium Priority
?
3,886 Views
Last Modified: 2012-08-13
hi
i need some help in the knight's tour problem..if anyone did this problem befor in c++ and have a possible solution for me  i will be more than  thankful  


 Problem Description
One of the more interesting puzzlers for chess buffs is the Knight's Tour problem, originally proposed by the mathematician Euler.  The question is this:  Can the chess piece called the knight move around an empty chessboard and touch each of the 64 squares once and only once?
The knight makes L-shaped moves (over two in one direction and then over one in a perpendicular direction.  Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 through 7) as shown in the following figure:
         
             0 1 2 3 4 5 6 7
            0
            1      2   1
            2    3      0
            3        k
            4    4      7
            5     5    6
            6
            7  

Trial Solution
Develop a program that will move the knight around a chessboard.  The board is represented by an 8-by-8 double-subscripted array board.  Each of the squares is initialized to zero.  We describe each of the eight possible moves in terms of both their horizontal and vertical components.  For example, a move of type 0 as shown above consists of moving two squares horizontally to the right and one square vertically upward.  Move 2 consists of moving one square horizontally to the left and two squares vertically upward.  Horizontal moves to the left and vertical moves upward are indicated with negative numbers.  The eight moves may be described by two single-subscripted arrays, horizontal and vertical, as follows:
horizontal[0] = 2
horizontal[1] = 1
horizontal[2] = -1
horizontal[3] = -2
horizontal[4] = -2
horizontal[5] = -1
horizontal[6] = 1
horizontal[7] = 2vertical[0] = -1
vertical[1] = -2
vertical[2] = -2
vertical[3] = -1
vertical[4] = 1
vertical[5] = 2
vertical[6] = 2
vertical[7] = 1Let the variables currentRow and currentColumn indicate the row and column of the knight's current position.  To make a move of type moveNumber, where moveNumber is between 0 and 7, your program uses the statements
currentRow += vertical[moveNumber];
currentColumn += horizontal[moveNumber];Keep a counter that varies from 1 to 64.  Record the latest count in each square the knight moves to.  Remember to test each potential move to see if the knight has already visited that square.  And, of course, test every potential move to make sure that the knight does not land off the chessboard.  now write a program to move the knight around the chessboard.  Run the program.  How many moves did the knight make?
0
Comment
Question by:hm025
12 Comments
 
LVL 5

Expert Comment

by:EOL
ID: 7495587
I am not familiar with the problem, could you please post the problem text so I can profit by this thread too?
0
 
LVL 5

Expert Comment

by:Kimpan
ID: 7495703
I can give you the solution right away, no it is impossible
0
 
LVL 5

Accepted Solution

by:
kooheji earned 500 total points
ID: 7496239
There are several solutions to the knight's tour. However your assignment isn't just to give a solution, you need to write the code that will find the solution. (For s solution -- not code -- go here http://www.borderschess.org/KnightTour.htm)

Now I'll help you out with writing your program. This brings back great memories from college.. just whatever you do, DON'T get the complete program written from somewhere else. Do it yourself, you will benifit, and nothing beats that feeling when your program finally works.

First of all, make sure you understood the problem completely.

Next make sure you are familiar with the concepts of loops and arrays in C++, in addition to functions. If you understand recursion that will be a plus to solving the problem, but not completely necessary. Stacks is another option for a solution.

First you need to initialize certain variables:


int chessBoard[8][8]; // 8 by 8 gives 64 squares. Initialze them to 0 .. if a sqaure has been visited, make it 1 so you don't go there again

int currentRow;      // Which row is the knight on
int currentColumn;   // Which column is the knight on

int moveCount = 0;  //Count how many moves have been made so far.. if you made 64 moves, you solved the problem.

Now we will start our knight always at row 0 colum 0.

currentRow = 0;
currentColumn = 0;
chessBoard[0][0] = 1; //visited by the knight

From there on it's up to you to choose which moves to make. Think of this as an initial trial where we'll just move in sequence. I will use the move numbers from your solution description. Make sure the horizontal and vertical arrays are already initialized as such.

  For( int moveNumber = 0 ; moveNumber <=7 ; moveNumber++ )

What does this do? We try each one of the 8 moves to see if we find a valid move. As soon as we find one, we make it.

  if (currentRow + vertical[moveNumber] >= 0) && 
     (currentRow + vertical[moveNumber] <= 7) &&
     (currentColumn + horizontal[moveNumber] >= 0) &&
     (currentColumn + horizontal[moveNumber] <= 7)

What does the above line do? Makes sure the move we choose is within the bounds of the board.
       
         if ( board[currentRow + vertical[moveNumber]][currentColumn + horizontal[moveNumber]] != 1 )

The above line makes sure the square we are moving to is NOT already visited.


If the above two conditions are met, change current row and current column, and then restart moveNumber from 0, also increment moveCount.. you are on a new sqaure and you will check all 8 moves again.

If none of the 8 moves worked and your for loop ended that means there are no more valid moves.. Output movecount and find how many moves you were able to make..



I hope you got a fairly good idea of what's going on. The best way is to head for the compiler and start coding. Come back here if you face any problems, post your code if it's not working, and we'll help you out until this thing is done.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 3

Expert Comment

by:RJSoft
ID: 7497017
Semi-Pseudo code

int  LastRow;
int  LastCol;
char TrackMoves[HIGHVAL][3];
int Board[8][8];


int NextMoveWorks(int Row,int Col)
{
int flag=0;
// Now calculate all possible positions knight
// can move from spot Row,Col and detect if all spots
// already taken. If so return zero.

// If more than one spot is OK. Then choose randomly between all of them. USE rand() to do your decision

// If NextMoveWorks


return flag;
}//endfunc

void RemoveLastMove()
{
// get TrackMoves[MoveCount][] values atoi them
// for Row and Col
// Example    
//      Temp[0]=TrackMoves[MoveCount][0];//8
//      Temp[1]='\0';
//      int Row = atoi(Temp);
//      TrackMoves[MoveCount][1]=='1'
//      etc...
// adjust Board[Row][Col]=0;
}

void SaveSpot(int WhatMove, int Row, int Col)
{
char Temp1[10];
char Temp2[10];
Board[Row][Col]=1;
itoa(Row,Temp1,10);
itoa(Col,Temp2,10);
strcat(Temp1,Temp2);
strcpy(TrackMoves[WhatMove],Temp1);
}//endfunc

void main()
{
int  KeepIt=0;
long MoveCount=0;
srand(...); // IMPORTANT ONLY CALL SRAND ONCE!

// Do this loop untill answer is found
while(1)
{
  while(1)
  {
  //pick starting spot
  if(MoveCount==0)
  {
  Row=rand()%9;
  Col=rand()%9;
  }
  if(MoveCount<64)
  {
  if(NextMoveWorks(Row,Col)
  {
  SaveSpot(MoveCount,Row,Col);
  MoveCount++;
  }//endifnext
  else
  {
  MoveCount--;
  if(MoveCount<0)
  {
  MoveCount=0;
  continue;
  }//endif<0
  RemoveLastMove();
  }//endelse
  }//endelse MoveCount!=0%%64

  if(MoveCount==64)
  {
  KeepIt=1;
  break;
  }
  }//endinnerwhileloop

if(KeepIt)break;
}//endouterwhileloop

// Save to file
FILE *fptr=NULL;
fptr=fopen("result.txt","wb");
int x=0;
while(1)
{
fprintf("%s\n",TrackMoves[x],fptr)
x++;if(x==HIGHVAL)break;
}

}// end main

0
 
LVL 5

Expert Comment

by:Kimpan
ID: 7497592
I mean it's not so quite impossible with knowledge of graph theory :)
0
 
LVL 3

Expert Comment

by:RJSoft
ID: 7501823
I have been trying to picture how to do the NextMove logic.

But the only thing I could come up with is that you will have to make a table of all possible moves from each square that is the current square.

Example.

// This is just a partial visual for positions
01,02,03,04,05,06,07,08
09,10,11,12,13,14,15,16
17,18,19,20,21,22,23,24
25,26,27,28,29,30,31,32
33,34,35,36,37,38,39,40
41,42,43,44,45,46,47,48
etc....

The visual shows that 01 position can move to
11 and 18. Where position 20 can move to
3,5,14,30,37,35,26,10 (8 possible moves as u said)

So you could HARD CODE a table of values that a
current position would be able to choose.

struct POSSIBLE
{
int Move[8];
};
struct TABLE
{
struct POSSIBLE Possible;
}Table[64];


Then load it

//Position 0 possible moves
//Each is given 8, but can be flagged with a 0
//to not allow

// first spot   first move
// shows only two moves
Table[0].Possible[0]=11;
Table[0].Possible[1]=18;
Table[0].Possible[2]=0; //zero is no move
Table[0].Possible[3]=0;
Table[0].Possible[4]=0;
Table[0].Possible[5]=0;
Table[0].Possible[6]=0;
Table[0].Possible[7]=0;

Next would be Table[1] and so on...



Then reffering to the table would give you
the ability to pick possible moves from your
current position.

Since I would use rand() like my previous posting
suggest I would force my rand() to pick a valid spot

int x=0;
int result=0;
while(!result)
{
x=rand()%9;
result=Table[CurrentSpot].Possible[x];
}



This also allows you to create your board
as a single array
int Board[64];
that would simplify entering in 1 or 0 for if (spot used)


If you get done with this thing post it back
I would like to see what you come up with

Richard





0
 
LVL 49

Expert Comment

by:DanRollins
ID: 7504925
Always move to the square that has the fewest exits.  My son did that and got an A++

But he had to write some lines of program code....

-- Dan
0
 

Author Comment

by:hm025
ID: 7580050
ok guys i have coded this code

telll me what u think about it.....and i need now to let it do 64 tours....each tour starts from each squar on the board....like first tour starts from board[0][0] second tour board[0][1] and so on and i have to tell how many tours did it complete out of 64 tours ....i ve tried to do that but it didnt work for me any solution ?? here is my code..

#include<iostream>
#include <iomanip>
#include<conio.h>
using namespace std;


int nextmove(int chess [][8],int table[][8],int hmoves[],int vmoves[],
                  int frow, int fcol);


void knightmove(int chess[][8],int hmoves[],int vmoves[],int choice,
                    int knight,int *frow,int *fcol);

void printboard(int chess[][8]);


int main()
{
     int choice;
     int firstrow=1;
     int firstcol=6;
     int board[8][8]={0};
     int accboard[8][8] ={
          {2,3,4,4,4,4,3,2},
          {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},
     };
     
     int moves =0;
     int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
     int vertical[8]={-1,-2,-2,-1,1,2,2,1};
         
     for(int i =0; i<63; i++){
          choice=nextmove(board,accboard,horizontal,vertical
                              ,firstrow,firstcol);
          moves++;
          knightmove(board,horizontal,vertical,choice
               ,moves,&firstrow,&firstcol);}
     printboard(board);
     
     return 0;
}





int nextmove(int chess [][8],int table[][8],int hmoves[],int vmoves[],
                 int frow,int fcol)
{
     
     int startval=100;
     int choice=-1;
     int row,col;
     
     for(int i=0;i<8;i++){
          row = frow;
          col = fcol;
          row +=hmoves[i];
          col +=vmoves[i];
          if(row >=0 && row < 8 && col>=0 && col<8 && chess[row][col]==0)
          {
               if(table[row][col] < startval && table[row][col]!=0)
               {
                    startval=table[row][col];
                    choice=i;
               }
          }
     }return choice;
     
}





void knightmove(int chess[][8],int hmoves[],int vmoves[],int choice,
                    int knight,int *frow,int *fcol)
{
     if(choice !=-1)
     {
         
          chess[*frow][*fcol]=+knight;
          *frow +=hmoves[choice];
          *fcol +=vmoves[choice];
          if(knight==63)
          {
               knight++;
               chess[*frow][*fcol]=64;
          }
     
     
     }
     
}

     
void printboard(int chess[][8])
{
     for(int i=0;i<8;i++){
          cout <<endl;
          for(int j=0;j<8;j++)
               cout <<setw(6)<< chess[i][j]; }
cout << endl;}



 
0
 
LVL 3

Expert Comment

by:RJSoft
ID: 7584296
First of all what I would do, and what you do could be different and may only add to your confusion and mine.

@@
>
~

BUT!

It seems you need two loops in your main function to get your logic right.

It's simple, you use a loop to do a process. Make a knight move 64 times across a board.

Now you need to run that process 64 times.

void main()
{
int CompletedTours[64];
.....your initialization
....
int x=0;
int y=0;
while(1)
{
      x=0;
      while(1)
      {
      DoNextMoveOrWhatever();
      x++;
      if(x==64)break;
      }//endinnerwhile

CompletedTours[y]=DidWeComplete();

y++;
if(y==64)break;
}//endouterwhile

// show results
x=0;
while(1)
{
if(CompletedTours[x])printf("\nTour %d completed",x+1);
else printf("\nTour %d failed",x+1);
x++;
if(x==64)break;
}//endwhile

0
 
LVL 11

Expert Comment

by:griessh
ID: 7662491
This question didn't show any activity for more than 21 days. I will ask Community Support to close it unless you finalize it yourself within 7 days.
You can always request to keep this question open. But remember, experts can only help if you provide feedback to their comments.
Unless there is objection or further activity,  I will suggest to split between  

    "kooheij & RJSoft"


PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
========
Werner
0
 
LVL 6

Expert Comment

by:Mindphaser
ID: 7735586
Force accepted

** Mindphaser - Community Support Moderator **

RJSoft, there is a separate question with points for your help in http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_20458481.html
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

971 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question