Posted on 2008-10-17 17:37
kainster 阅读(140)
评论(0) 编辑 收藏 所属分类:
《C&Pointer》笔记
八皇后
#define NUM 8
enum status 
{
NORMAL = 0,//没棋子
CAPTURED = 1,//后在的位置
INFLUENCED = 2//能被后打到
};
//第一维是step
//第二维是x
//第三维是y
status matrix[NUM][NUM][NUM];
void printMatrix(int step);
void printMatrix(int step)
{
if(step >= NUM)
return;
for(int i = 0; i<NUM; i++ )
{
for(int j=0; j<NUM; j++ )
{
printf("%d",matrix[step][i][j]);
}
printf("\n");
}
}
void doPutDown(int x,int y)
{
for( int i = 0 ; i < NUM; i++ )
for( int j = 0; j < NUM; j++ )
{
if( x>0 )
{
matrix[x][i][j] = matrix[x-1][i][j];
}
else
matrix[x][i][j] = NORMAL;
if( i == x || j == y)
{
matrix[x][i][j] = INFLUENCED;
}
}
matrix[x][x][y] = CAPTURED;
}
//尝试把皇后摆在某个位置上
bool tryputdownchessman(int step,int x, int y)
{
if(step == 0)
return true;
int i,j;
if( NORMAL != matrix[step-1][x][y] )
return false;
for( i = 0 ; i < NUM; i++ )
for( int j = 0; j < NUM; j++ )
if( i == x || j == y)
{
if( CAPTURED == matrix[step-1][i][j] )
return false;
}
i = x; j = y;
while(i<NUM && j<NUM)
{
i++;j++;
if( CAPTURED == matrix[step-1][i][j] )
return false;
}
i = x; j = y;
while(i>=0 && j>=0)
{
i--;j--;
if( CAPTURED == matrix[step-1][i][j] )
return false;
}
i = x; j = y;
while(i>=0 && j<NUM)
{
i--;j++;
if( CAPTURED == matrix[step-1][i][j] )
return false;
}
i = x; j = y;
while(i<NUM && j>=0)
{
i++;j--;
if( CAPTURED == matrix[step-1][i][j] )
return false;
}
return true;
}
bool putdown( int step)
{
if(step == NUM -1 )
{
int i = 0 ;
for( i=0; i<NUM; i++ )
{
if( true == tryputdownchessman(step,step,i))
{
doPutDown( step, i );
return true;
}
}
return false;
}
else
{
int i = 0;
while( i < NUM )
{
if( true == tryputdownchessman(step,step,i))
{
doPutDown( step , i );
if( true == putdown( step+1 ) )
return true;
}
i++;
}
return false;
}
}
void eightQueens()
{
int i; // loop variable
//initialize the matrix
for(int i1 =0; i1<NUM; i1++)
for(int i2 =0; i2<NUM; i2++)
for(int i3 =0; i3<NUM; i3++)
{
matrix[ i1][ i2 ][ i3] = NORMAL;
}
putdown(0);
printMatrix(NUM - 1);
}