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