Knight's Tour

Using another algorithm

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 23263 Views - Last Post: 07 October 2010 - 05:42 PM Rate Topic: -----

#1 qwert12345  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Knight's Tour

Posted 29 September 2010 - 03:35 PM

The program will display a "knight's tour" on a chess board.
knight is a chess piece which moves from a (row, col) to (nrow, ncol)
where:
nrow=row+dx, ncol=col+dy
where dx, dy pairs are given below. of course the nrow and ncol should be within
the board (and be empty)

dx dy
-2 1
-1 2
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1

thus from a typical "cell" it can move to one of upto 8 possible positions.
of course not all of these may be inside the board.

Old Algorithm:
the following "priority" rule to make
the move:

col 01234567

row
0 12222221
1 23444432
2 24566542
3 24677642
4 24677642
5 24566542
6 23444432
7 12222221
lower number means higher priority: the more close you are to
a "corner" higher the priority. if you can go to 2 cells with the same high
priority, choose any one of them.

e.g., from row=4, col=1 you would move to any one of the below:
row=6 col=0 or row=2, col=0 if they are both available because they both have
the same high priority 2

New Algorithm:

The following strategy for choosing among the possible moves.
we want to decide where to move from (i, j)
1. we find all the possible cells we could move to : say these c1 c2 ..cn
(not all 8 moves may be possible)
2. now we ask:
from c1 HOW many cells we could move to: call it m1
from c2 HOW many cells we could move to: call it m2
from c3 HOW many cells we could move to: call it m3
...
from c4 HOW many cells we could move to: call it mn
3. find the minimum of the numbers m1 m2 .. mn say it is mj
4. MOVE to cj

So, I wanted to know a way to change the small parts of the code that includes the priority rule into the new algorithm..without redoing the whole code.

I comment out the parts that are based on the priority rule in the code.

Here's the code some far:
#include <iostream>
#include <iomanip>
using namespace std;

#define SIZE 8

int board[SIZE][SIZE];
const int DX[SIZE]={-2,-1,1,2,2,1,-1,-2};
const int DY[SIZE]={1,2,2,1,-1,-2,-2,-1};
/*const int PRIORITY[SIZE][SIZE]= { 
				{1,2,2,2,2,2,2,1},
				{2,3,4,4,4,4,3,2},
				{2,4,5,6,6,5,4,2},
				{2,4,6,7,7,6,4,2},
				{2,4,6,7,7,6,4,2},
				{2,4,5,6,6,5,4,2},
				{2,3,4,4,4,4,3,2},
				{1,2,2,2,2,2,2,1},
			};
*/
struct CELL 
{  
//a cell on the board
int row; 
int col;
};
void DisplayBoard() 
{  
//display the board, 0=empty;
  for  (int i = 0; i < SIZE; i++) 
  {
        for (int j = 0; j < SIZE; j++) 
            {
               cout << setw(4) << board[i][j];
            }
    cout << endl;
  }
}
void EmptyBoard() 
{ 
//board[i][j]==0 means cell (i, j) is empty
	for (int i = 0; i < SIZE; i++)
	  for (int j = 0; j < SIZE; j++)
	    board[i][j] = 0;
}
bool ValidCell(int row, int col) 
{  //(row, col) should be inside the board and be empty
  if ( (row<0) || (col<0) || (row>=SIZE) || (col>=SIZE) ) return false;  //outside board
  if (board[row][col]>0) return false; //not empty
  return true;

}
int NextPossibleCells (CELL c, CELL nc[]) 
{ 
//store the next moves in array nc and return howmany there are
//nc[0], nc[1],  ... should contain the next possible moves
	int j; 
    int cnt = 0;
	int row0 = c.row;  
    int col0 = c.col;
 for (int i = 0; i < 8; i++) 
    {
         if ( ValidCell(row0+DX[i], col0+DY[i]) ) 
         { 
              nc[cnt].row=row0+DX[i];  
              nc[cnt].col=col0+DY[i];
              cnt++;
         }
    }
    return cnt;
}

int BestMove(CELL nc[], int cnt) 
{ 
//return the index of the best move
//out of the possible moves this picks the best one
//if there is more than 1 best move, choose any of them (here the first one is chosen)
//return the index of the best move
	int row0;
    int col0;
    int row; 
    int col;
    int p0;
    int p;
    int bestmove_ndx; 
    if (cnt==0) 
       return -1; //there si no move at all
    row0 = nc[0].row; 
    col0 = nc[0].col; 
   // p0 = PRIORITY[row0][col0];
    bestmove_ndx = 0;
            for (int i = 1; i < cnt; i++) 
              {  //go thru all possible moves
                      row = nc[i].row; 
                      col= nc[i].col; 
                      //p = PRIORITY[row][col];
                       if (/* p < p0 */) 
                       {
                          bestmove_ndx = i; 
                          //p0 = p;
                       }
              }
    return bestmove_ndx;
}



int main() 
{
  int num; 
  int cnt;
  int bestndx;
  CELL cc, nc[SIZE];        //cc=current cell; nc=next cell array
  for (int i=0; i<SIZE; i++) 
     {
	      for (int j=0; j<SIZE; j++) 
             {  
              //go thru all start positions (i, j)
	            EmptyBoard();
	            cc.row = i; 
                cc.col = j; 
                num = 1;
                board[cc.row][cc.col] = num; 
                 num++;
                      while (1) 
                           { 
                              //keep going as long as you can go
	                         //find next cells; if none, break out of this loop
	                        //find the best move of all these
                           //put the number on the board and reset current cell to be this new cell and loop back
	                          int cnt = NextPossibleCells(cc, nc);
	                          int bestmove_ndx = BestMove(nc, cnt);
	                                     if (bestmove_ndx == -1) 
                                             {  //no move possible; break out of loop
	                                             break;
                                             } 
                                         else 
                                             {
                                                board[nc[bestmove_ndx].row][nc[bestmove_ndx].col]= num; 
                                                num++;
                                                cc.row = nc[bestmove_ndx].row;
                                                cc.col = nc[bestmove_ndx].col;
                                             }
                    	    }
       DisplayBoard();
	      if (num < 64) 
            { 
             cout << i <<" " << j << " FAILED. MAX ENTRY = " << num << "\n"; 
	        }
	      else 
             cout << "SUCCESS!! made all 64 moves from " << i << " " << j << endl;
            	}
  }
  
 
  system("pause");
  return 0;
}





Is This A Good Question/Topic? 0
  • +

Replies To: Knight's Tour

#2 Alex6788  Icon User is offline

  • kitties == adorable


Reputation: 144
  • View blog
  • Posts: 1,667
  • Joined: 15-July 10

Re: Knight's Tour

Posted 29 September 2010 - 03:39 PM

I don't know if you know this or not but a better alternative to system("pause"); is cin.get(); and sometimes that doesn't work if there is already input in the buffer then use

cin.ignore();
cin.get();

Hope that was useful. :-)
Was This Post Helpful? 0
  • +
  • -

#3 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 991
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Knight's Tour

Posted 29 September 2010 - 03:52 PM

View Postqwert12345, on 30 September 2010 - 07:35 AM, said:

So, I wanted to know a way to change the small parts of the code that includes the priority rule into the new algorithm..without redoing the whole code.


Well if your code has been properly written then either decision should be fully contained within the bestMove() function.
Is that how you wrote your original code for the first algorithm?
If you did, then the only part that needs changing is that function.
If you didn't then you should re-write your code to achieve that anyway.

Is that what you are asking?
It is unclear to me what you are asking.

If you are asking us to change the code for you that's not going to be happening.
Or are you asking for an algorithm to implement the new "best move" criteria?

If you are then:
You test the possible moves from the current location. (That should be in a function of its own if it isn't already.)
Store the number of moves and the end of move locations.
Now loop through each of the end of move locations and test for possible moves from that location.
Store the number of moves possible from each end move location.
Find the end of move location with the greatest number of possible subsequent moves.
Return that as the best move.
Was This Post Helpful? 0
  • +
  • -

#4 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon

Reputation: 2965
  • View blog
  • Posts: 11,222
  • Joined: 15-July 08

Re: Knight's Tour

Posted 29 September 2010 - 04:08 PM

I just want to put it out there that I wrote a knight's tour snippet for Python, but using that snippet, it was easy to convert it to C++ and Java (both I did). My version runs very quickly in only ~.5 seconds. I hope it helps:
http://www.dreaminco...snippet5177.htm

Mine uses the "choose path of least resistance" method, where it selects those possible moves that have the least number of next moves.
Was This Post Helpful? 0
  • +
  • -

#5 qwert12345  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Re: Knight's Tour

Posted 29 September 2010 - 05:28 PM

View Postjanotte, on 29 September 2010 - 02:52 PM, said:

View Postqwert12345, on 30 September 2010 - 07:35 AM, said:

So, I wanted to know a way to change the small parts of the code that includes the priority rule into the new algorithm..without redoing the whole code.


Well if your code has been properly written then either decision should be fully contained within the bestMove() function.
Is that how you wrote your original code for the first algorithm?
If you did, then the only part that needs changing is that function.
If you didn't then you should re-write your code to achieve that anyway.


No, I don't want the code written for me. And you answered my question..Thanks.

View PostAlex6788, on 29 September 2010 - 02:39 PM, said:

I don't know if you know this or not but a better alternative to system("pause"); is cin.get(); and sometimes that doesn't work if there is already input in the buffer then use

cin.ignore();
cin.get();

Hope that was useful. :-)

Yeah, but why is cin.get() a better alternative to system("pause")??
Was This Post Helpful? 0
  • +
  • -

#6 Alex6788  Icon User is offline

  • kitties == adorable


Reputation: 144
  • View blog
  • Posts: 1,667
  • Joined: 15-July 10

Re: Knight's Tour

Posted 29 September 2010 - 06:09 PM

View Postqwert12345, on 29 September 2010 - 06:28 PM, said:

View Postjanotte, on 29 September 2010 - 02:52 PM, said:

View Postqwert12345, on 30 September 2010 - 07:35 AM, said:

So, I wanted to know a way to change the small parts of the code that includes the priority rule into the new algorithm..without redoing the whole code.


Well if your code has been properly written then either decision should be fully contained within the bestMove() function.
Is that how you wrote your original code for the first algorithm?
If you did, then the only part that needs changing is that function.
If you didn't then you should re-write your code to achieve that anyway.


No, I don't want the code written for me. And you answered my question..Thanks.

View PostAlex6788, on 29 September 2010 - 02:39 PM, said:

I don't know if you know this or not but a better alternative to system("pause"); is cin.get(); and sometimes that doesn't work if there is already input in the buffer then use

cin.ignore();
cin.get();

Hope that was useful. :-)

Yeah, but why is cin.get() a better alternative to system("pause")??

Well for many reasons one is that it's a system command so it has to call the os, it prints "Press any key to continue", and I've even heard that anti virus programs think your program is a virus when you use system("pause"); Those are just a few of the many reasons. I'll try to find a article about why it's bad.

It's cin.get(); not cin.get()

This post has been edited by Alex6788: 29 September 2010 - 06:10 PM

Was This Post Helpful? 0
  • +
  • -

#7 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 991
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Knight's Tour

Posted 29 September 2010 - 06:13 PM

View Postqwert12345, on 30 September 2010 - 09:28 AM, said:

Yeah, but why is cin.get() a better alternative to system("pause")??


Read this:
http://www.gidnetwork.com/b-61.html
Was This Post Helpful? 0
  • +
  • -

#8 Alex6788  Icon User is offline

  • kitties == adorable


Reputation: 144
  • View blog
  • Posts: 1,667
  • Joined: 15-July 10

Re: Knight's Tour

Posted 29 September 2010 - 06:16 PM

View Postjanotte, on 29 September 2010 - 07:13 PM, said:

View Postqwert12345, on 30 September 2010 - 09:28 AM, said:

Yeah, but why is cin.get() a better alternative to system("pause")??


Read this:
http://www.gidnetwork.com/b-61.html

Ah that's the article i was looking for thanks.
Was This Post Helpful? 0
  • +
  • -

#9 qwert12345  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Re: Knight's Tour

Posted 02 October 2010 - 02:24 PM

Now the program is running...but the max entry is always less than 64. The problem is in the BestMove function.

Output:.......

15 8 19 40 0 38 0 50

18 11 16 37 26 41 0 0

7 14 9 20 39 0 49 0

10 17 12 25 36 27 42 0

13 6 21 28 43 48 0 0

22 29 24 35 32 45 2 0

5 34 31 44 3 0 47 0

30 23 4 33 46 0 0 1

7 7 FAILED. MAX ENTRY = 51

#include <iostream>
#include <iomanip>
using namespace std;

#define SIZE 8

int board[SIZE][SIZE];
const int DX[SIZE]={-2,-1,1,2,2,1,-1,-2};
const int DY[SIZE]={1,2,2,1,-1,-2,-2,-1};
/*const int PRIORITY[SIZE][SIZE]= { 
				{1,2,2,2,2,2,2,1},
				{2,3,4,4,4,4,3,2},
				{2,4,5,6,6,5,4,2},
				{2,4,6,7,7,6,4,2},
				{2,4,6,7,7,6,4,2},
				{2,4,5,6,6,5,4,2},
				{2,3,4,4,4,4,3,2},
				{1,2,2,2,2,2,2,1},
			};
*/
struct CELL 
{  
//a cell on the board
int row; 
int col;
};
void DisplayBoard() 
{  
//display the board, 0=empty;
  for  (int i = 0; i < SIZE; i++) 
  {
        for (int j = 0; j < SIZE; j++) 
            {
               cout << setw(4) << board[i][j];
            }
    cout << endl;
  }
}
void EmptyBoard() 
{ 
//board[i][j]==0 means cell (i, j) is empty
	for (int i = 0; i < SIZE; i++)
	  for (int j = 0; j < SIZE; j++)
	    board[i][j] = 0;
}
bool ValidCell(int row, int col) 
{  //(row, col) should be inside the board and be empty
  if ( (row<0) || (col<0) || (row>=SIZE) || (col>=SIZE) ) return false;  //outside board
  if (board[row][col]>0) return false; //not empty
  return true;

}
int NextPossibleCells (CELL c, CELL nc[]) 
{ 
//store the next moves in array nc and return howmany there are
//nc[0], nc[1],  ... should contain the next possible moves
	int j; 
    int cnt = 0;
	int row0 = c.row;  
    int col0 = c.col;
 for (int i = 0; i < 8; i++) 
    {
         if ( ValidCell(row0+DX[i], col0+DY[i]) ) 
         { 
              nc[cnt].row=row0+DX[i];  
              nc[cnt].col=col0+DY[i];
              cnt++;
         }
    }
    return cnt;
}

int BestMove(CELL nc[], int cnt) 
{ 
//return the index of the best move
//out of the possible moves this picks the best one
//if there is more than 1 best move, choose any of them (here the first one is chosen)
//return the index of the best move
	int row0;
    int col0;
    int row; 
    int col;
    int m;
    int c;
    //int p0;
    //int p;
    int bestmove_ndx; 
    
/*   in this case we'll use the following strategy for choosing among the possible moves.
we want to decide where to move from (i, j)
1. we find all the possible cells we could move to : say these c1 c2 ..cn
   (not all 8 moves may be possible)
2. now we ask: 
       from c1 HOW many cells we could move to: call it m1
       from c2 HOW many cells we could move to: call it m2
       from c3 HOW many cells we could move to: call it m3
       ...
       from c4 HOW many cells we could move to: call it mn   
3. find thwe minimum of the numbers m1 m2 .. mn say it is mj
4. MOVE to cj    
*/
 
    if (cnt==0) 
       return -1; //there si no move at all
    row0 = nc[0].row; 
    col0 = nc[0].col; 
   // p0 = PRIORITY[row0][col0];
    bestmove_ndx = 0;
            for (int i = 1; i < cnt; i++) 
              {  //go thru all possible moves
                      row = nc[i].row; 
                      col= nc[i].col; 
                      //p = PRIORITY[row][col];
                       if (row < row0) 
                       {
                          bestmove_ndx = i; 
                          //p0 = p;
                          row0 = row;
                         
                       }
                       if (col < col0) 
                       {
                          bestmove_ndx = i; 
                          //p0 = p;
                         
                          col0 = col;
                       }
              }
    return bestmove_ndx;
}



int main() 
{
  int num; 
  int cnt;
  int bestndx;
  CELL cc, nc[SIZE];        //cc=current cell; nc=next cell array
  for (int i=0; i<SIZE; i++) 
     {
	      for (int j=0; j<SIZE; j++) 
             {  
              //go thru all start positions (i, j)
	            EmptyBoard();
	            cc.row = i; 
                cc.col = j; 
                num = 1;
                board[cc.row][cc.col] = num; 
                 num++;
                      while (1) 
                           { 
                              //keep going as long as you can go
	                         //find next cells; if none, break out of this loop
	                        //find the best move of all these
                           //put the number on the board and reset current cell to be this new cell and loop back
	                          int cnt = NextPossibleCells(cc, nc);
	                          int bestmove_ndx = BestMove(nc, cnt);
	                                     if (bestmove_ndx == -1) 
                                             {  //no move possible; break out of loop
	                                             break;
                                             } 
                                         else 
                                             {
                                                board[nc[bestmove_ndx].row][nc[bestmove_ndx].col]= num; 
                                                num++;
                                                cc.row = nc[bestmove_ndx].row;
                                                cc.col = nc[bestmove_ndx].col;
                                             }
                    	    }
       DisplayBoard();
	      if (num < 64) 
            { 
             cout << i <<" " << j << " FAILED. MAX ENTRY = " << num << "\n"; 
	        }
	      else 
             cout << "SUCCESS!! made all 64 moves from " << i << " " << j << endl;
            	}
  }
  

  //system("pause");
 // return 0;
 cin.ignore();
cin.get();
 
}


Was This Post Helpful? 0
  • +
  • -

#10 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 991
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Knight's Tour

Posted 03 October 2010 - 06:37 AM

You seem to know which function your problem lies in.
How have you reached that conclusion?
What have you tried already?

I am unclear how your algorithm works because you code has turned into such a mess in the process of appearing on the board.

You seem to only have one try from each starting position.
Is that the case?
So do you assume that from any given position you will find the right pattern on the first try?
That's a brave assumption (if indeed you are making it).

Can I suggest you put 30 minutes into cleaning your code up. Make sure your brace alignment and indentation is top notch and that you have discarded all the commented out code and all that good stuff. The mess you have in there will definitely be making it harder for you to see your code properly.
Was This Post Helpful? 0
  • +
  • -

#11 qwert12345  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Re: Knight's Tour

Posted 03 October 2010 - 04:24 PM

#include <iostream>
#include <iomanip>
using namespace std;

#define SIZE 8

int board[SIZE][SIZE];
const int DX[SIZE]={-2,-1,1,2,2,1,-1,-2};
const int DY[SIZE]={1,2,2,1,-1,-2,-2,-1};
struct CELL 
{  
//a cell on the board
int row; 
int col;
};
void DisplayBoard() 
{  
//display the board, 0=empty;
  for  (int i = 0; i < SIZE; i++) 
  {
     for (int j = 0; j < SIZE; j++) 
        {
         cout << setw(4) << board[i][j];
        }
    cout << endl;
  }
}
void EmptyBoard() 
{ 
//board[i][j]==0 means cell (i, j) is empty
	for (int i = 0; i < SIZE; i++)
	  for (int j = 0; j < SIZE; j++)
	    board[i][j] = 0;
}

bool ValidCell(int row, int col) 
{  //(row, col) should be inside the board and be empty
  if ( (row<0) || (col<0) || (row>=SIZE) || (col>=SIZE) ) return false;  //outside board
  if (board[row][col]>0) return false; //not empty
  return true;

}
int NextPossibleCells (CELL c, CELL nc[]) 
{ 
//store the next moves in array nc and return howmany there are
//nc[0], nc[1],  ... should contain the next possible moves
int j; 
int cnt = 0;
int row0 = c.row;  
int col0 = c.col;
   for (int i = 0; i < 8; i++) 
     {
       if ( ValidCell(row0+DX[i], col0+DY[i]) ) 
         { 
           nc[cnt].row=row0+DX[i];  
           nc[cnt].col=col0+DY[i];
           cnt++;
         }
     }
  return cnt;
}

int BestMove(CELL nc[], int cnt) 
{ 
//return the index of the best move
//out of the possible moves this picks the best one
//if there is more than 1 best move, choose any of 
//them (here the first one is chosen)
//return the index of the best move
int row0;
int col0;
int row; 
int col;
int bestmove_ndx;   
 if (cnt==0) 
    return -1; //there si no move at all
row0 = nc[0].row; 
col0 = nc[0].col; 
   
bestmove_ndx = 0;
         for (int i = 1; i < cnt; i++) 
            {  //go thru all possible moves
              row = nc[i].row; 
              col= nc[i].col;
                 if (row < row0) 
                    {
                      bestmove_ndx = i; 
                      row0 = row;
                    }
                 if (col < col0) 
                    {
                      bestmove_ndx = i; 
                      col0 = col;
              }
     }
             
return bestmove_ndx;
}

int main() 
{
int num; 
int cnt;
int bestndx;
CELL cc, nc[SIZE];        //cc=current cell; nc=next cell array
  for (int i=0; i<SIZE; i++) 
     {
     for (int j=0; j<SIZE; j++) 
       {  
 //go thru all start positions (i, j)
         EmptyBoard();
         cc.row = i; 
         cc.col = j; 
         num = 1;
         board[cc.row][cc.col] = num; 
         num++;
           while (1) 
             { 
//keep going as long as you can go
//find next cells; if none, break out of this loop
//find the best move of all these
//put the number on the board and reset current 
//cell to be this new cell and loop back
            int cnt = NextPossibleCells(cc, nc);
            int bestmove_ndx = BestMove(nc, cnt);
               if (bestmove_ndx  == -1) 
                 { 
//no move possible; break out of loop
                   break;
                 } 
               else 
                 {
 board[nc[bestmove_ndx].row][nc[bestmove_ndx].col]= num; 
                   num++;
                   cc.row = nc[bestmove_ndx].row;
                   cc.col = nc[bestmove_ndx].col;
               }
   	    }
 DisplayBoard();
	      if (num < 64) 
            { 
cout << i <<" " << j << " FAILED. MAX ENTRY = " << num << "\n"; 
	        }
	      else 
cout << "SUCCESS!! made all 64 moves from " << i << " " << j << endl;
      	}
  }
cin.ignore();
cin.get();
 
}



This post has been edited by qwert12345: 03 October 2010 - 04:26 PM

Was This Post Helpful? 0
  • +
  • -

#12 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 379
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Knight's Tour

Posted 03 October 2010 - 05:48 PM

I'd like to reiterate janotte's point about cleaning up your code.

Here are two style of indentation:

C++:
#include <iostream>
using std::cout;

int main()
{
  int a = 10;

  if(a == 10)
  {
    cout << "A is 10" << endl;
  }
  
  return 0;
}


K&R C:
#include <iostream>
using std::cout;

int main() {
  int a = 10;

  if(a == 10) {
    cout << "A is 10" << endl;
  }
  
  return 0;
}


Please use one of the two styles and your enter key. That code is not readable by any means. Note how I spaced out separate ideas. Do the same, it makes code so much easier to look at.

As for the actual problem:

1) What errors are you receiving?
2) If there are no errors, is the program behaving weirdly?

You need to describe the problem.

People help others here at their own free will. Clean code and a nice description of the problem will encourage more people to help you.

If someone posts a wall of text, their code looks like crap, and there is no description of the problem, I won't think twice before hitting the 'back' button.

This post has been edited by eker676: 03 October 2010 - 05:50 PM

Was This Post Helpful? 0
  • +
  • -

#13 qwert12345  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Re: Knight's Tour

Posted 03 October 2010 - 09:38 PM

View Posteker676, on 03 October 2010 - 04:48 PM, said:

As for the actual problem:

1) What errors are you receiving?
2) If there are no errors, is the program behaving weirdly?

You need to describe the problem.

People help others here at their own free will. Clean code and a nice description of the problem will encourage more people to help you.

If someone posts a wall of text, their code looks like crap, and there is no description of the problem, I won't think twice before hitting the 'back' button.


If you read this post, you would know that I have already described the problem...for the second time, the problem with my problem is that the max entry is always less than 64 when i run the program and I think the problem is in the BestMove function.

#include <iostream>

#include <iomanip>

using namespace std;

#define SIZE 8

int board[SIZE][SIZE];

const int DX[SIZE]={-2,-1,1,2,2,1,-1,-2};

const int DY[SIZE]={1,2,2,1,-1,-2,-2,-1};

struct CELL 
{  

// a cell on the board

int row;
 
int col;

};

void DisplayBoard() 
{
  
//display the board, 0=empty;
  
 for  (int i = 0; i < SIZE; i++) 
  {
     for (int j = 0; j < SIZE; j++) 
        {
        
          cout << setw(4) << board[i][j];
        }
          cout << endl;
  }
}

void EmptyBoard() 
{ 
//board[i][j]==0 means cell (i, j) is empty
	
        for (int i = 0; i < SIZE; i++)
	     
             for (int j = 0; j < SIZE; j++)
	            
                      board[i][j] = 0;
}

bool ValidCell(int row, int col) 
{  
//(row, col) should be inside the board and be empty
  if ( (row<0) || (col<0) || (row>=SIZE) || (col>=SIZE) )
            return false; 
 //outside board
  if (board[row][col]>0)
                return false; //not empty
                 return true;

}

int NextPossibleCells (CELL c, CELL nc[]) 
{ 
//store the next moves in array nc and return howmany there are
//nc[0], nc[1],  ... should contain the next possible moves

int j; 

int cnt = 0;

int row0 = c.row;  

int col0 = c.col;

   for (int i = 0; i < 8; i++) 
     {
       if ( ValidCell(row0+DX[i], col0+DY[i]) ) 
         { 
           nc[cnt].row=row0+DX[i];  

           nc[cnt].col=col0+DY[i];

           cnt++;
         }
     }
  return cnt;
}

int BestMove(CELL nc[], int cnt) 
{ 
//return the index of the best move
//out of the possible moves this picks the best one
//if there is more than 1 best move, choose any of 
//them (here the first one is chosen)
//return the index of the best move
int row0;

int col0;

int row; 

int col;

int bestmove_ndx;   

 if (cnt==0) 
    return -1; //there si no move at all

row0 = nc[0].row; 

col0 = nc[0].col; 
   
bestmove_ndx = 0;
         for (int i = 1; i < cnt; i++) 
            {  
               //go thru all possible moves
             
              row = nc[i].row; 

              col= nc[i].col;

                 if (row < row0) 
                    {
                      bestmove_ndx = i; 

                      row0 = row;
                    }
                 if (col < col0) 
                    {
                      bestmove_ndx = i; 

                      col0 = col;

              }
     }
             
return bestmove_ndx;
}

int main() 
{
int num;
 
int cnt;

int bestndx;

CELL cc, nc[SIZE];        

//cc=current cell; nc=next cell array
  
 for (int i=0; i<SIZE; i++) 
     {
        for (int j=0; j<SIZE; j++) 
           {  
 //go thru all start positions (i, j)
              EmptyBoard();
 
              cc.row = i; 

              cc.col = j;
 
               num = 1;

            board[cc.row][cc.col] = num; 

             num++;

        while (1) 
             { 
//keep going as long as you can go
//find next cells; if none, break out of this loop
//find the best move of all these
//put the number on the board and reset current 
//cell to be this new cell and loop back
            int cnt = NextPossibleCells(cc, nc);

         int bestmove_ndx = BestMove(nc, cnt);
              
                 if (bestmove_ndx  == -1) 
                 { 
//no move possible; break out of loop
                   break;
                 } 
               else 
                 {
 board[nc[bestmove_ndx].row]
[nc[bestmove_ndx].col]= num; 
                  
                   num++;

                   cc.row = nc[bestmove_ndx].row;

                   cc.col = nc[bestmove_ndx].col;
               }
   	    }
 DisplayBoard();

	      if (num < 64) 
            { 
cout << i <<" " << j << " FAILED. MAX ENTRY = " << num << "\n"; 
	        }
	      else 
cout << "SUCCESS!! made all 64 moves from " << i << " " << j << endl;
      	}
  }
cin.ignore();
cin.get();
 
}




Was This Post Helpful? 0
  • +
  • -

#14 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 991
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Knight's Tour

Posted 03 October 2010 - 09:58 PM

View Postqwert12345, on 04 October 2010 - 01:38 PM, said:

If you read this post,


And if you re-read my post above you'll see that I asked you some very specific questions.

Please answer them so we can move forward.

Just getting grumpy and making the same, broad, unclear statements over and over again won't get you from where you are to where you want to be.

We need to look at specific details now and that's up to you.
The ball is in your court.
Was This Post Helpful? 0
  • +
  • -

#15 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3700
  • View blog
  • Posts: 13,372
  • Joined: 08-August 08

Re: Knight's Tour

Posted 04 October 2010 - 07:32 AM

View Postqwert12345, on 03 October 2010 - 11:38 PM, said:

If you read this post, you would know that I have already described the problem...for the second time, the problem with my problem is that the max entry is always less than 64 when i run the program and I think the problem is in the BestMove function.

That is a symptom of the problem along with a guess as to where it lies. As Janotte has pointed out, your biggest problem right now is that your code isn't readable. Because it's not readable you can't track down the source of the problem.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2