プログラムの実行結果は以下の通り。
Find Ｓ1 Ｃ4 Ｈ3 Ｄ2 Ｈ2 Ｄ3 Ｓ4 Ｃ1 Ｄ4 Ｈ1 Ｃ2 Ｓ3 Ｃ3 Ｓ2 Ｄ1 Ｈ4
これを図示すると以下のようになる。
プログラムのソースは以下の通り。
#include "puzutl.h"
int type_mask[] = { 0x000F, 0x00F0, 0x0F00, 0xF000};
#define D 0 // ダイヤ
#define H 1 // ハート
#define S 2 // スペード
#define C 3 // クラブ
int no_mask[] = { 1, 2, 4, 8};
#define N1 0 // 1
#define N2 1 // 2
#define N3 2 // 3
#define N4 3 // 4
const int M = 4;
struct mat { // structにして関数の引数に指定したときコピーが作成されるようにする
int m[M][M];
} ma;
int typeno2bit( int type, int no) // カードの種類と数字がどのビットに対応するか？
{
int bit = no_mask[no];
bit <<= type*4;
return bit;
}
int bit2type( int bit) // ビットがどの種類を示すものか？
{
for( int i=0; i< 4; i++) {
if( bit & type_mask[i]) return i;
}
pe( "Program Error\n");
return 0; // コンパイルエラーを避けるため適当な値
}
int bit2no( int bit) // ビットがどの数字を示すものか？
{
int no = bit | (bit>>4) | (bit>>8) | (bit>>12); // 1ビットしか立っていないことが大前提
for( int i=0; i< 4; i++) {
if( no & no_mask[i]) return i; // ビット位置が数字になる
}
pe( "Program Error\n");
return 0; // コンパイルエラーを避けるため適当な値
}
void mask_type( mat& m, int Row, int Col, int type) // この位置にこのカードを置けない
{
m.m[Row][Col] = m.m[Row][Col] & ~type_mask[type];
}
void mask_no( mat& m, int Row, int Col, int no) // この位置にこの数字を置けない
{
int n = no_mask[no], nomask;
nomask = (n<<0) | (n<<4) | (n<<8) | (n<<12);
m.m[Row][Col] = m.m[Row][Col] & ~nomask;
}
YesNo decide1( mat& m, int Row, int Col, int type, int no) // この位置のカードを確定する
{
int bit = typeno2bit(type,no);
if( m.m[Row][Col] & bit) { // この位置に候補としてあるので配置できる
m.m[Row][Col] = bit; // この位置のカードをこのカードで確定する,他の候補は消去される
return YES; // 配置できた
}
return NO; // 配置できない
}
YesNo decide( mat& m, int Row, int Col, int type, int no) // カードを配置する
{
// 同じ行，列に同じ種類のカード，同じ値のカードを置けなくする。
// 対角線上も同じ。
int irow, icol, i;
if( !decide1( m, Row, Col, type, no)) { // この位置のカードは確定
return NO; // この位置にカードを配置できなかった。
}
for( icol=0; icol< M; icol++) { // 同じ行に置けない
if( icol != Col) {
mask_type( m, Row, icol, type);
mask_no( m, Row, icol, no);
}
}
for( irow=0; irow< M; irow++) { // 同じ列に置けない
if( irow != Row) {
mask_type( m, irow, Col, type);
mask_no( m, irow, Col, no);
}
}
if( Row == Col) { // 対角上に置けない
for( i=0; i< M; i++) {
if( i != Row) {
mask_type( m, i, i, type);
mask_no( m, i, i, no);
}
}
}
if( Row == (M-1-Col)) { // 対角上に置けない
for( i=0; i< M; i++) {
if( i != Row) {
mask_type( m, i, M-1-i, type);
mask_no( m, i, M-1-i, no);
}
}
}
return YES;
}
void dump( const mat& m) // 結果を出力する
{
int irow, icol;
cstring str_type[] = { "Ｄ", "Ｈ", "Ｓ", "Ｃ"};
for( irow=0; irow< M; irow++) {
for( icol=0; icol< M; icol++) {
//ps( "%04x ", m.m[irow][icol]);
int type = bit2type(m.m[irow][icol]);
int no = bit2no(m.m[irow][icol]);
ps( "%s%d ", str_type[type], no+1);
}
ps( "\n");
}
}
void find( mat m, int level)
{
if( level >= M*M) {
ps( "Find\n");
dump(m);
return;
}
int irow, icol;
irow = level / M;
icol = level % M;
int v = m.m[irow][icol];
int bit = 1;
for( int i=0; i< 16; i++) { // 全てのカードをこの位置に配置できるか調べる
if( v&bit) { // カードを配置できる
mat mm = m;
int type = bit2type(bit);
int no = bit2no(bit);
if( decide( mm, irow, icol, type, no)) { // この位置にカードを配置できれば配置する
find( mm, level+1);
}
}
bit <<= 1;
}
}
int main( int argc, cstring argv[])
{
int irow, icol;
mat ma;
for( irow=0; irow< M; irow++) {
for( icol=0; icol< M; icol++) {
ma.m[irow][icol] = 0xFFFF; // 全てのカードを配置できる可能性がある。
}
}
decide( ma, 0, 0, S, N1); // [0,0]にスペードの1を配置
decide( ma, 0, 3, D, N2); // [0,3]にダイヤの2を配置
decide( ma, 2, 2, C, N2); // [2,2]にクラブの2を配置
decide( ma, 3, 0, C, N3); // [3,0]にクラブの3を配置
find( ma, 0/*探索開始位置*/);
return 0;
}