/************************************************************************/
/* ８クイーン その１７ */
/* */
/* 対称性のチェックの準備 */
/* */
/* 盤面のクイーンの並び方で大小比較のための関数を用意 */
/* */
/* usage: queen */
/* */
/************************************************************************/
#include <stdio.h>
int answercount;
char board[8][8]; /* チェス盤 */
#define QUEEN 'Q'
#define BLANK '.'
#define TRUE 1
#define FALSE 0
void initboard( void );
void copyboard( char dest[8][8], char src[8][8] );
void rotate( char dest[8][8], char src[8][8] );
void lrmirror( char dest[8][8], char src[8][8] );
int isunique( void );
void setqueen( int x, int y );
void setblank( int x, int y );
int ison( int x, int y );
int isokleft( int x, int y );
int isokleftup( int x, int y );
int isokleftdown( int x, int y );
int isok( int x, int y );
void tryqueen( int x, int y );
void foundanswer( void );
void printboard( char b[8][8] );
int main( int argc, char **argv );
/*----------------------------------------------------------------------*/
/* チェス盤の初期化 */
/*----------------------------------------------------------------------*/
void initboard( void )
{
int x, y;
for( x=0; x<8; ++x ) {
for( y=0; y<8; ++y ) {
board[x][y] = BLANK;
}
}
}
/*----------------------------------------------------------------------*/
/* チェス盤のコピー */
/*----------------------------------------------------------------------*/
void copyboard( char dest[8][8], char src[8][8] )
{
int x, y;
for( x=0; x<8; ++x )
for( y=0; y<8; ++y )
dest[x][y] = src[x][y];
}
/*----------------------------------------------------------------------*/
/* 盤面上のコマを９０度回転する */
/*----------------------------------------------------------------------*/
void rotate( char dest[8][8], char src[8][8] )
{
char work[8][8]; /* to, from が同じ配列でもOK */
int x, y;
for( x=0; x<8; ++x )
for( y=0; y<8; ++y )
work[y][7-x] = src[x][y];
copyboard( dest, work );
}
/*----------------------------------------------------------------------*/
/* 盤面上のコマを左右反転する */
/*----------------------------------------------------------------------*/
void lrmirror( char dest[8][8], char src[8][8] )
{
char work[8][8]; /* to, from が同じ配列でもOK */
int x, y;
for( x=0; x<8; ++x )
for( y=0; y<8; ++y )
work[7-x][y] = src[x][y];
copyboard( dest, work );
}
/*----------------------------------------------------------------------*/
/* 回転・反転などによるユニーク性のチェック */
/*----------------------------------------------------------------------*/
int isunique( void )
{
char work[8][8]; /* 作業用盤面 */
printboard( board ); /* 候補 */
rotate( work, board ); printboard( work ); /* 90度回転 */
rotate( work, work ); printboard( work ); /* 180度回転 */
rotate( work, work ); printboard( work ); /* 270度回転 */
lrmirror( work, board ); printboard( work ); /* 左右裏返し */
rotate( work, work ); printboard( work ); /* 90度回転 */
rotate( work, work ); printboard( work ); /* 180度回転 */
rotate( work, work ); printboard( work ); /* 270度回転 */
}
/*----------------------------------------------------------------------*/
/* チェス盤の指定場所にクイーンをセット */
/*----------------------------------------------------------------------*/
void setqueen( int x, int y )
{
board[x][y] = QUEEN;
}
/*----------------------------------------------------------------------*/
/* チェス盤の指定場所をブランクにする */
/*----------------------------------------------------------------------*/
void setblank( int x, int y )
{
board[x][y] = BLANK;
}
/*----------------------------------------------------------------------*/
/* 指定位置(x,y)が盤上かどうかの判定 */
/*----------------------------------------------------------------------*/
int ison( int x, int y )
{
if( x<0 || x>=8 )
return FALSE;
if( y<0 || y>=8 )
return FALSE;
return TRUE;
}
/*----------------------------------------------------------------------*/
/* 同じy座標 (←) のところに他のクイーンがないことを確認 */
/*----------------------------------------------------------------------*/
int isokleft( int x, int y )
{
int i;
int stat = TRUE;
for(;;) {
--x;
if( ! ison( x, y ) )
break;
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
/*----------------------------------------------------------------------*/
/* 左上対角線上 (＼) のところに他のクイーンがないことを確認 */
/*----------------------------------------------------------------------*/
int isokleftup( int x, int y )
{
int i;
int stat = TRUE;
for(;;) {
--x;
--y;
if( ! ison( x, y ) )
break;
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
/*----------------------------------------------------------------------*/
/* 左下対角線上 (／) のところに他のクイーンがないことを確認 */
/*----------------------------------------------------------------------*/
int isokleftdown( int x, int y )
{
int i;
int stat = TRUE;
for(;;) {
--x;
++y;
if( ! ison( x, y ) )
break;
if( board[x][y] == QUEEN ) {
stat = FALSE;
break;
}
}
return stat;
}
/*----------------------------------------------------------------------*/
/* 左上対角線上 (＼) のところに他のクイーンがないことを確認 */
/*----------------------------------------------------------------------*/
int isok( int x, int y )
{
if( ! isokleft( x, y ) ) { /* 効き筋(←)にあるので置けない */
return FALSE;
}
if( ! isokleftup( x, y ) ) { /* 効き筋(＼)にあるので置けない */
return FALSE;
}
if( ! isokleftdown( x, y ) ) { /* 効き筋(／)にあるので置けない */
return FALSE;
}
return TRUE;
}
/*----------------------------------------------------------------------*/
/* チェス盤の指定場所をにクイーンを置けるか調べる */
/*----------------------------------------------------------------------*/
void tryqueen( int x, int y )
{
int z;
if( ! isok( x, y ) )
return;
setqueen( x, y ); /* 置いた */
if( x == 7 ) { /* ８個置き終えた */
foundanswer();
} else { /* 一つ右側について調べる */
for( z=0; z<8; ++z ) {
tryqueen( x+1, z );
}
}
setblank( x, y ); /* 外した */
}
/*----------------------------------------------------------------------*/
/* 解が見つかった */
/*----------------------------------------------------------------------*/
void foundanswer( void )
{
isunique(); /* ユニークかどうかの検査を行う予定 */
++answercount;
printf( "Answer %d\n", answercount );
printboard( board );
}
/*----------------------------------------------------------------------*/
/* チェス盤のプリント */
/*----------------------------------------------------------------------*/
void printboard( char b[8][8] )
{
int x, y;
for( y=0; y<8; ++y ) {
for( x=0; x<8; ++x ) {
printf( " %c", b[x][y] );
}
printf( "\n" );
}
printf( "\n" );
}
/*----------------------------------------------------------------------*/
/* メイン */
/*----------------------------------------------------------------------*/
int main( int argc, char **argv )
{
int y;
answercount = 0;
initboard();
for( y=0; y<8; ++y ) {
tryqueen( 0, y );
}
}
/************************************************************************/
/* End */
/************************************************************************/
