Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

The knight's tour problem in c++

Posted on 2002-11-25
12
3,655 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 125 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
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
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 14

Expert Comment

by:AlexVirochovsky
ID: 7498639
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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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 learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

809 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