/************************************************************************/
/* ペントミノ その１４ */
/* */
/* 10×6の盤面に詰め込む */
/* */
/* usage: pentomino */
/************************************************************************/
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define CN 5 /* セル数 */
#define PN 12 /* ピース数 */
#define WIDTH 10 /* 盤面の幅 */
#define HEIGHT 6 /* 盤面の高さ */
#define BLANK '.' /* ブランク */
char board[WIDTH][HEIGHT]; /* 盤面 */
int used[PN]; /* 使用済み状態 */
int usedcount; /* 使用済みピース数 */
typedef struct {
int x;
int y;
} Pos;
typedef struct {
char name; /* 名称 */
Pos form[CN]; /* 配置 */
} PieceForm;
PieceForm AllPieces[] = {
{ 'F', {{ 0, 0},{ 0, 1},{ 1, 1},{ 1, 2},{ 2, 1}} },
{ 'F', {{ 0, 0},{ 1, 0},{ 1, 1},{ 1, 2},{ 2, 1}} },
{ 'F', {{ 0, 0},{ 1, 0},{ 1, 1},{ 2,-1},{ 2, 0}} },
{ 'F', {{ 0, 0},{ 1,-1},{ 1, 0},{ 1, 1},{ 2,-1}} },
{ 'F', {{ 0, 0},{ 0, 1},{ 1,-1},{ 1, 0},{ 2, 0}} },
{ 'F', {{ 0, 0},{ 1,-2},{ 1,-1},{ 1, 0},{ 2,-1}} },
{ 'F', {{ 0, 0},{ 1,-1},{ 1, 0},{ 2, 0},{ 2, 1}} },
{ 'F', {{ 0, 0},{ 1,-1},{ 1, 0},{ 1, 1},{ 2, 1}} },
{ 'I', {{ 0, 0},{ 0, 1},{ 0, 2},{ 0, 3},{ 0, 4}} },
{ 'I', {{ 0, 0},{ 1, 0},{ 2, 0},{ 3, 0},{ 4, 0}} },
{ 'L', {{ 0, 0},{ 0, 1},{ 0, 2},{ 0, 3},{ 1, 0}} },
{ 'L', {{ 0, 0},{ 0, 1},{ 1, 0},{ 2, 0},{ 3, 0}} },
{ 'L', {{ 0, 0},{ 1, 0},{ 1, 1},{ 1, 2},{ 1, 3}} },
{ 'L', {{ 0, 0},{ 1, 0},{ 2, 0},{ 3, 0},{ 3, 1}} },
{ 'L', {{ 0, 0},{ 0, 1},{ 0, 2},{ 0, 3},{ 1, 3}} },
{ 'L', {{ 0, 0},{ 0, 1},{ 1, 1},{ 2, 1},{ 3, 1}} },
{ 'L', {{ 0, 0},{ 1,-3},{ 1,-2},{ 1,-1},{ 1, 0}} },
{ 'L', {{ 0, 0},{ 1, 0},{ 2, 0},{ 3,-1},{ 3, 0}} },
{ 'N', {{ 0, 0},{ 0, 1},{ 1, 1},{ 1, 2},{ 1, 3}} },
{ 'N', {{ 0, 0},{ 1, 0},{ 1, 1},{ 2, 1},{ 3, 1}} },
{ 'N', {{ 0, 0},{ 0, 1},{ 0, 2},{ 1,-1},{ 1, 0}} },
{ 'N', {{ 0, 0},{ 1, 0},{ 2,-1},{ 2, 0},{ 3,-1}} },
{ 'N', {{ 0, 0},{ 0, 1},{ 1,-2},{ 1,-1},{ 1, 0}} },
{ 'N', {{ 0, 0},{ 1,-1},{ 1, 0},{ 2,-1},{ 3,-1}} },
{ 'N', {{ 0, 0},{ 0, 1},{ 0, 2},{ 1, 2},{ 1, 3}} },
{ 'N', {{ 0, 0},{ 1, 0},{ 2, 0},{ 2, 1},{ 3, 1}} },
{ 'P', {{ 0, 0},{ 0, 1},{ 1, 0},{ 1, 1},{ 2, 0}} },
{ 'P', {{ 0, 0},{ 0, 1},{ 0, 2},{ 1, 0},{ 1, 1}} },
{ 'P', {{ 0, 0},{ 1, 0},{ 1, 1},{ 2, 0},{ 2, 1}} },
{ 'P', {{ 0, 0},{ 0, 1},{ 1, 0},{ 1, 1},{ 1, 2}} },
{ 'P', {{ 0, 0},{ 0, 1},{ 1, 0},{ 1, 1},{ 2, 1}} },
{ 'P', {{ 0, 0},{ 0, 1},{ 0, 2},{ 1, 1},{ 1, 2}} },
{ 'P', {{ 0, 0},{ 1,-1},{ 1, 0},{ 2,-1},{ 2, 0}} },
{ 'P', {{ 0, 0},{ 0, 1},{ 1,-1},{ 1, 0},{ 1, 1}} },
{ 'T', {{ 0, 0},{ 0, 1},{ 0, 2},{ 1, 1},{ 2, 1}} },
{ 'T', {{ 0, 0},{ 1, 0},{ 1, 1},{ 1, 2},{ 2, 0}} },
{ 'T', {{ 0, 0},{ 1, 0},{ 2,-1},{ 2, 0},{ 2, 1}} },
{ 'T', {{ 0, 0},{ 1,-2},{ 1,-1},{ 1, 0},{ 2, 0}} },
{ 'U', {{ 0, 0},{ 0, 2},{ 1, 0},{ 1, 1},{ 1, 2}} },
{ 'U', {{ 0, 0},{ 0, 1},{ 1, 1},{ 2, 0},{ 2, 1}} },
{ 'U', {{ 0, 0},{ 0, 1},{ 0, 2},{ 1, 0},{ 1, 2}} },
{ 'U', {{ 0, 0},{ 0, 1},{ 1, 0},{ 2, 0},{ 2, 1}} },
{ 'V', {{ 0, 0},{ 0, 1},{ 0, 2},{ 1, 0},{ 2, 0}} },
{ 'V', {{ 0, 0},{ 1, 0},{ 2, 0},{ 2, 1},{ 2, 2}} },
{ 'V', {{ 0, 0},{ 0, 1},{ 0, 2},{ 1, 2},{ 2, 2}} },
{ 'V', {{ 0, 0},{ 1, 0},{ 2,-2},{ 2,-1},{ 2, 0}} },
{ 'W', {{ 0, 0},{ 0, 1},{ 1, 1},{ 1, 2},{ 2, 2}} },
{ 'W', {{ 0, 0},{ 1, 0},{ 1, 1},{ 2, 1},{ 2, 2}} },
{ 'W', {{ 0, 0},{ 1,-1},{ 1, 0},{ 2,-2},{ 2,-1}} },
{ 'W', {{ 0, 0},{ 0, 1},{ 1,-1},{ 1, 0},{ 2,-1}} },
{ 'X', {{ 0, 0},{ 1,-1},{ 1, 0},{ 1, 1},{ 2, 0}} },
{ 'Y', {{ 0, 0},{ 0, 1},{ 0, 2},{ 0, 3},{ 1, 1}} },
{ 'Y', {{ 0, 0},{ 1, 0},{ 1, 1},{ 2, 0},{ 3, 0}} },
{ 'Y', {{ 0, 0},{ 1,-1},{ 1, 0},{ 1, 1},{ 1, 2}} },
{ 'Y', {{ 0, 0},{ 1, 0},{ 2, 0},{ 2, 1},{ 3, 0}} },
{ 'Y', {{ 0, 0},{ 0, 1},{ 0, 2},{ 0, 3},{ 1, 2}} },
{ 'Y', {{ 0, 0},{ 1,-1},{ 1, 0},{ 2, 0},{ 3, 0}} },
{ 'Y', {{ 0, 0},{ 1,-2},{ 1,-1},{ 1, 0},{ 1, 1}} },
{ 'Y', {{ 0, 0},{ 1, 0},{ 2,-1},{ 2, 0},{ 3, 0}} },
{ 'Z', {{ 0, 0},{ 0, 1},{ 1, 1},{ 2, 1},{ 2, 2}} },
{ 'Z', {{ 0, 0},{ 1, 0},{ 1, 1},{ 1, 2},{ 2, 2}} },
{ 'Z', {{ 0, 0},{ 0, 1},{ 1, 0},{ 2,-1},{ 2, 0}} },
{ 'Z', {{ 0, 0},{ 1,-2},{ 1,-1},{ 1, 0},{ 2,-2}} },
{ '\0', } /* ←番犬 */
};
/* F I L N P T U V W X Y Z */
const int base[PN] = { 0, 8,10,18,26,34,38,42,46,50,51,59 };
Pos nextblank( int x, int y );
int ison( int x, int y );
int ispieceok( int x, int y, PieceForm *pf );
void pieceset( int x, int y, PieceForm *pf );
void pieceunset( int x, int y, PieceForm *pf );
void initboard( void );
void printboard( void );
void foundanswer( void );
void trypiece( int x, int y );
int main(int argc, char **argv);
/*----------------------------------------------------------------------*/
/* 次の空き位置を見付ける */
/*----------------------------------------------------------------------*/
Pos nextblank( int x, int y )
{
Pos q;
for(;;) {
if( board[x][y] == BLANK ) {
q.x = x;
q.y = y;
return q;
}
if( ++y >= HEIGHT ) {
++x;
y = 0;
}
}
}
/*----------------------------------------------------------------------*/
/* 指定位置(x,y)が盤上かどうかの判定 */
/*----------------------------------------------------------------------*/
int ison( int x, int y )
{
if( x<0 || x>=WIDTH )
return FALSE;
if( y<0 || y>=HEIGHT )
return FALSE;
return TRUE;
}
/*----------------------------------------------------------------------*/
/* 指定位置(x,y)を基準に指定向きのピースを置けるかの判定 */
/*----------------------------------------------------------------------*/
int ispieceok( int x, int y, PieceForm *pf )
{
int i;
int u, v;
for( i=0; i<CN; ++i ) {
u = x + pf->form[i].x;
v = y + pf->form[i].y;
if( ! ison(u,v) )
return FALSE;
if( board[u][v] != BLANK )
return FALSE;
}
return TRUE;
}
/*----------------------------------------------------------------------*/
/* 指定位置(x,y)の指定のピース(含む方向)をセットする */
/*----------------------------------------------------------------------*/
void pieceset( int x, int y, PieceForm *pf )
{
int i;
int u, v;
for( i=0; i<CN; ++i ) {
u = x + pf->form[i].x;
v = y + pf->form[i].y;
board[u][v] = pf->name;
}
}
/*----------------------------------------------------------------------*/
/* 指定位置(x,y)の指定のピース(含む方向)を取り除く */
/*----------------------------------------------------------------------*/
void pieceunset( int x, int y, PieceForm *pf )
{
int i;
int u, v;
for( i=0; i<CN; ++i ) {
u = x + pf->form[i].x;
v = y + pf->form[i].y;
board[u][v] = BLANK;
}
}
/*----------------------------------------------------------------------*/
/* 盤面の初期化 */
/*----------------------------------------------------------------------*/
void initboard( void )
{
int x, y;
for( x=0; x<WIDTH; ++x ) {
for( y=0; y<HEIGHT; ++y ) {
board[x][y] = BLANK;
}
}
}
/*----------------------------------------------------------------------*/
/* 盤面の初期化 */
/*----------------------------------------------------------------------*/
void printboard( void )
{
int x, y;
for( y=0; y<HEIGHT; ++y ) {
for( x=0; x<WIDTH; ++x ) {
printf( " %c", board[x][y] );
}
printf( "\n" );
}
printf( "\n" );
}
/*----------------------------------------------------------------------*/
/* 解を見付けた */
/*----------------------------------------------------------------------*/
void foundanswer( void )
{
printf( "Answer\n" );
printboard();
}
/*----------------------------------------------------------------------*/
/* 試す */
/*----------------------------------------------------------------------*/
void trypiece( int x, int y )
{
int i;
Pos bp;
PieceForm *p;
char name;
if( usedcount == PN ) {
foundanswer();
return;
}
bp = nextblank( x, y );
x = bp.x;
y = bp.y;
for( i=0; i<PN; ++i ) {
if( used[i] ) /* 使用済チェック */
continue;
p = &AllPieces[base[i]];
name = p->name;
for( ; p->name == name; ++p ) {
if( !ispieceok( x, y, p ) )
continue;
pieceset( x, y, p );
used[i] = TRUE;
++usedcount;
trypiece( x, y ); /* 再帰 */
pieceunset( x, y, p );
used[i] = FALSE;
--usedcount;
}
}
}
/*----------------------------------------------------------------------*/
/* main */
/*----------------------------------------------------------------------*/
int main(int argc, char **argv)
{
int i;
initboard();
for( i=0; i<PN; ++i )
used[i] = FALSE;
usedcount = 0;
trypiece(0,0);
}
/************************************************************************/
/* End of Pentomino */
/************************************************************************/
