Knight movement.... " how to output all possible moves. "
- by josh kant
hi tried the following code and is still not working. it is having problem on backtracking. it just fills the squares of a board with numbers but not in expected order. The code is as follows :
include
include
using namespace std;
int i=0;
int permuteno = 0;
bool move(int *p[], int *used[] ,int x, int y,int n, int count);
bool knights (int *p[], int *used[],int x,int y,int n, int count);
void output(int *p[],int n);
int main(char argc, char *argv[])
{
int count = 1;
int n; //for size of board
int x,y; // starting pos
int **p; // to hold no. of combinations
int **used; // to keep track of used squares on the board
if ( argc != 5)
{
cout << "Very few arguments. Please try again.";
cout << endl;
return 0;
}
n = atoi(argv[2]);
if( argv[1] <= 0 )
{
cout << " Invalid board size. ";
return 0;
}
x = atoi(argv[4]);
y = atoi(argv[4]);
cout << "board size: " << n << ", "<< n << endl;
cout << "starting pos: " << x << ", " << y << endl;
//dynamic allocation of arrays to hold permutation
p = new int *[n];
for (int i = 0; i < n; i++)
p[i] = new int [n];
//dynamic allocation of used arrays
used = new int*[n];
for (int i = 0; i < n; i++)
used[i] = new int [n];
//initializing board
int i, j;
for (i=0; i
output(p,n);
if (knights(p,used,x, y, n, count))
{
cout << "solution found: " << endl <
int i, j;
for (i=0; i
else
{
cout << "Solution not found" << endl;
output (p, n);
}
knights (p,used, x, y, n, 1);
//knights (p,used,x, y, n, count);
cout << "no. perm " << permuteno << endl;
return 0;
}
void output(int *p[],int n)
{
int i = 0,j;
while ( i !=n)
{
for ( j=0; j
bool move(int *p[], int *used[] ,int x, int y,int n,int count)
{
if (x < 0 || x = n)
{
return false;
}
if ( y < 0 || y = n)
{
return false;
}
if( used[x][y] != 0)
{
return false;
}
if( p[x][y] != 0)
{
return false;
}
count++;
return true;
}
bool knights (int *p[], int *used[], int x,int y,int n ,int count)
{
//used[x][y] = 1;
if (!move(p,used,x,y,n, count))
{
return false;
}
if (move(p,used,x,y,n, count))
{
i++;
}
p[x][y] = count;
used[x][y] = 1;
cout << "knight moved " << x << ", " << y << " " << count << endl;
if(n*n == count)
{
return true;
}
//move 1
if (!knights (p,used, x-1, y-2, n, count+1))
{
used[x][y] = 0;
//p[x][y] = 0;
}
//move 2
if (!knights (p,used, x+1, y-2, n, count+1))
{
used[x][y] = 0;
//p[x][y] = 0;
}
//move 3
if (!knights (p,used, x+2, y-1, n, count+1))
{
used[x][y] = 0;
//p[x][y] = 0;
}
//move 4
if (!knights (p,used, x+2, y+1, n, count+1))
{
used[x][y] = 0;
//p[x][y] = 0;
}
//move 5
if (!knights (p,used, x+1, y+2, n, count+1))
{
used[x][y] = 0;
//p[x][y] = 0;
}
//move 6
if (!knights (p,used, x-1, y+2, n, count+1))
{
used[x][y] = 0;
//p[x][y] = 0;
}
//move 7
if (!knights (p,used, x-2, y+1, n, count+1))
{
used[x][y] = 0;
//p[x][y] = 0;
}
//move 8
if (!knights (p,used, x-2, y-1, n, count+1))
{
used[x][y] = 0;
//p[x][y] = 0;
}
permuteno++;
//return true;
//}while ( x*y != n*n );
return false;
}
I has to output all the possible combinations of the knight in a nXn board..
any help would be appreciated...
