プログラムの実行結果は以下の通り。
Find S1 C4 H3 D2 H2 D3 S4 C1 D4 H1 C2 S3 C3 S2 D1 H4
これを図示すると以下のようになる。
プログラムのソースは以下の通り。
#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[] = { "D", "H", "S", "C"}; 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; }