contoh program backtracking "langkah catur kuda " C++

#include
#include
#include
const int DIM = 8 ;
const int MAX = DIM * DIM -1 ;
int v[DIM][DIM], row[MAX], col[MAX], rp,cp, index, MIN,p;
int A[DIM][DIM] =
{
{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 dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 },
dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 } ;
void direction()
{
int i ;
int C0_dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 }, // better for col 0
C0_dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 } ;
int C7_dx[] = { -2, -1, 1, 2, 2, 1, -1, -2 }, // better for col 7
C7_dy[] = { -1, -2,-2, -1, 1, 2, 2, 1 } ;
int R0_dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 }, // better for row 0
R0_dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 } ;
int R7_dx[] = { -2, -2, -1, 1, 2, 2, 1, -1 }, // better for row 7
R7_dy[] = { 1, -1, -2, -2, -1, 1, 2, 2 } ;
if ( cp < rp && cp < 4 )
for ( i = 0 ; i < 8 ; i++ )
{
dx[i] = C0_dx[i] ;
dy[i] = C0_dy[i] ;
}
if ( cp > rp && cp > 3 )
for ( i = 0 ; i < 8 ; i++ )
{
dx[i] = C7_dx[i] ;
dy[i] = C7_dy[i] ;
}
if ( rp < cp && rp < 4 )
for ( i = 0 ; i < 8 ; i++ )
{
dx[i] = R0_dx[i] ;
dy[i] = R0_dy[i] ;
}
if ( rp > cp && rp > 3 )
for ( i = 0 ; i < 8 ; i++ )
{
dx[i] = R7_dx[i] ;
dy[i] = R7_dy[i] ;
}
}
int valid( int a,int b ) {
if ( a < 0 || a >= DIM || b < 0 || b >= DIM )
return 0 ;
//if( a == rp && b == cp ) return 0 ;
return 1 ;
}
void Try(int r,int c,int pos ) {
int i,j,nr,nc ;
int *a ;
a = new int[8] ;
if( pos == MAX )
{
r = row[62] ;
c = col[62] ;
for ( i = 1 ; i < 8 ; i++ )
{
nr = r + dx[i] ;
nc = c + dy[i] ;
if ( valid( nr,nc ) && !v[nr][nc] )
break ;
}
if ( i == 8 ) return ;
r = nr ;
c = nc ;
for ( i = 0 ; i < 8 ; i++ )
{
nr = r + dx[i] ;
nc = c + dy[i] ;
if ( valid( nr,nc ) && nr == 5 && nc == 7 )
break ;
}
if ( i == 8 ) return ;
for ( i = 0 ; i < MAX ; i++ )
{ v[ row[i] ][ col[i] ] = i+1 ; }
for ( i = 0 ; i < 8 ; i++ )
{
for ( j = 0 ; j < 8 ; j++ )
{
if ( v[i][j] == 0 ) v[i][j] = 64 ;
printf("%-4d ",v[i][j] ) ;

}
printf("\n\n");
}
exit(0);
}
v[r][c] = pos + 1 ;
for ( i = 0 ; i < 8 ; i++ )
{
nr = r + dx[i] ;
nc = c + dy[i] ;
if( nr < 8 && nr >= 0 && nc < 8 && nc >= 0 && v[nr][nc] == 0 )
a[i] = --A[nr][nc] ;
else a[i] = 10 ;
}
for ( i = 0 ; i < 8 ; i++ )
{
MIN = 10 ;
for ( j = 0 ; j < 8 ; j++ )
{
if ( a[j] < MIN )
{
MIN = a[j] ;
p = j ;
}
}
a[p] = 10 ;
if ( MIN == 10 ) break ;
nr = r + dx[p] ;
nc = c + dy[p] ;
index++ ;
row[index] = nr ;
col[index] = nc ;
Try( nr,nc, pos+1 ) ;
index-- ;
v[nr][nc] = 0 ;
}
delete [] a ;
}
int main() {
int i,j ;
index = 0 ;
for ( i = 0 ; i < DIM ; i++ )
for ( j = 0 ; j < DIM ; j++ )
v[i][j] = 0 ;
/* printf("Enter Starting Row and Column : ");
scanf("%d%d",&rp,&cp ) ;
printf("\n");
rp-- ;
cp-- ; */
rp = 5 ;
cp = 7 ;
direction();
row[0] = rp ; col[0] = cp ;
v[rp][cp] = 1 ;
Try( rp,cp,0 ) ;
return 0 ;
getch();
}