プログラムの出力結果は以下の通り。
Zorg: num point:62 : 0 1 2 3 4 5 6 7 8 9 10 11 12 0: . . . . . . 6 . . . . . . 1: . . . . . . 19 . . . . . . 2: . . 28 . 30 31 32 33 34 . 36 . . 3: 39 40 41 . 43 44 45 46 47 . 49 50 51 4: . . 54 55 56 57 58 59 60 61 62 . . 5: . . 67 68 69 70 71 72 73 74 75 . . 6: 78 79 80 81 82 83 84 85 86 . . . . 7: . . 93 94 95 96 97 98 99 100 101 . . 8: . . . 107 . . 110 . . 113 . . . 9: . . . 120 . . 123 . . 126 . . . 10: . . . . . . . . . . . . . 11: . . . . . . . . . . . . . 12: . . . . . . . . . . . . . Find:1 FIND_A: num point:31 : 0 1 2 3 4 5 6 7 8 9 10 11 12 0: . . . . . . 6 . . . . . . 1: . . . . . . 19 . . . . . . 2: . . 28 . 30 31 32 33 . . . . . 3: 39 40 41 . 43 44 . . . . . . . 4: . . 54 55 56 57 58 59 . . . . . 5: . . 67 68 69 . 71 . . . . . . 6: 78 79 80 . . . 84 . . . . . . 7: . . 93 94 95 . . . . . . . . 8: . . . 107 . . . . . . . . . 9: . . . 120 . . . . . . . . . 10: . . . . . . . . . . . . . 11: . . . . . . . . . . . . . 12: . . . . . . . . . . . . . FIND_B: num point:31 : 0 1 2 3 4 5 6 7 8 9 10 11 12 0: . . . . . . . . . . . . . 1: . . . . . . . . . . . . . 2: . . . . . . . . 34 . 36 . . 3: . . . . . . 45 46 47 . 49 50 51 4: . . . . . . . . 60 61 62 . . 5: . . . . . 70 . 72 73 74 75 . . 6: . . . 81 82 83 . 85 86 . . . . 7: . . . . . 96 97 98 99 100 101 . . 8: . . . . . . 110 . . 113 . . . 9: . . . . . . 123 . . 126 . . . 10: . . . . . . . . . . . . . 11: . . . . . . . . . . . . . 12: . . . . . . . . . . . . .
判りやすくすると以下の通り。
上記図形は以下のように同じ図形である。
プログラムのソースは以下の通り。結構長くなってしまった。
#include "puzutl.h"
const int M = 13; // 図形全体の大きさ,プログラムを楽にするため縦横同じ大きさとする
const byte BLK = 0xFF;// 図形内の空白
const int NUMX = 62; // 図形の矩形は全部で62個ある
const int NUMA = 31; // 全部で62なので，2つの図形の半分は31個
const int NUMD = 7; // 最初に決まっているポイントは7点,7点に隣接する点も自動的に決まる
const int NUMC = 20; // 最初の7点が決まったとき自動的に決まる点
cstring str_original_zukei[] = {
// X :図形内で点のある場所
// A-G :図形を2つに分割したとき肝となる場所
// a-g :図形を2つに分割したとき大文字の点と同じ場所に分類される
"......a......",
"......a......",
"..b.XXAXX.c..",
"bbb.XXXXX.ccc",
"..BXXXXXXXC..",
"..XXXXXXXXX..",
"ddDXXXXXX....",
"..XEXXFXGgg..",
"...e..f..g...",
"...e..f..g...",
".............", // 全体の図形は横長なので縦を拡張
".............",
".............", // ここが空でなくなる図形だとプログラムの修正が必要
};
struct Zukei { // M*Mの配列内で点がある場所
byte m_zu[M][M]; // 点のある場所はINDEX値,無い場所はBLK
Zukei() { clear(); }
void clear() { memset( m_zu, BLK, sizeof(byte)*M*M);}
};
struct Point { // 図形内の位置情報
int m_row;
int m_col;
Point() {
m_row = m_col = 0;
}
};
struct PointSub : public Point{ // 7点が決まったとき更に決まる点
int m_chr; // 7点の文字('A'=>0,'B'=>1,...)
};
struct Trans { // 変換方法
int m_numRotate90;
int m_numMirror;
int m_row_diff;
int m_col_diff;
Trans( int numRotate90, int numMirror) {
m_numRotate90 = numRotate90;
m_numMirror = numMirror;
m_row_diff = m_col_diff = 0;
}
Trans() {
m_numRotate90 = m_numMirror = m_row_diff = m_col_diff = 0;
}
};
Zukei Zorg;
PointSub point7Sub[NUMX]; // 7点が確定したとき,追加で確定する位置
int nPoint7Sub = 0; // 7点が確定したとき追加で確定する位置
set<string> findedSolution; // 同じ分割を2つ以上出力しないようにする
inline YesNo exist( int row, int col) // 図形内の位置か?
{
if( row < 0 || row >= M) return NO;
if( col < 0 || col >= M) return NO;
return YES;
}
int rowcol_to_idx( int row, int col)
{
return row*M + col;
}
void rotate90( Zukei& zukeiNew, const Zukei& zukei) // 図形を左に90度回転する
{
byte val;
for( int row=0; row< M; row++) {
for( int col=0; col< M; col++) {
zukeiNew.m_zu[M-col-1][row] = zukei.m_zu[row][col];
}
}
}
void mirror( Zukei& zukeiNew, const Zukei& zukei) // 図形を左右対象にする
{
byte c;
for( int row=0; row< M; row++) {
for( int col=0; col<= M/2; col++) {
zukeiNew.m_zu[row][col] = zukei.m_zu[row][M-col-1];
zukeiNew.m_zu[row][M-col-1] = zukei.m_zu[row][col];
}
}
}
int init_zukei( Zukei& zukei, Point* point) // 文字列で与えられた図形をプログラムで使う形式に変換する。
{
int cnt = 0; // 図形内の点の数
int npoint = 0;
for( int row=0; row< M; row++) {
for( int col=0; col< M; col++) {
char c = str_original_zukei[row][col];
zukei.m_zu[row][col] = BLK; // 点が無い
if( c != '.') zukei.m_zu[row][col] = cnt; // 点がある
if( c >= 'A' && c <= 'G') {
assert( npoint<NUMD);
point[npoint].m_row = row;
point[npoint].m_col = col;
npoint++;
}
if( c >= 'a' && c <= 'g') {
assert( nPoint7Sub < NUMC);
point7Sub[nPoint7Sub].m_row = row;
point7Sub[nPoint7Sub].m_col = col;
point7Sub[nPoint7Sub].m_chr = c-'a';
nPoint7Sub++;
}
cnt++;
}
}
assert( npoint == NUMD);
assert( nPoint7Sub == NUMC);
return npoint;
}
void assign_point_to_zukei( Zukei& A, Point Ap[], int& numAp, Zukei& B, Point Bp[], int& numBp, Point point[NUMD], int bit)
{
// 最初の7点をA,Bの図形に振り分ける。
// Ap[], Bp[] は最初の7点に付随する点で正規化する前の図形の点の位置
A.clear(); B.clear();
numAp = numBp = 0;
int ab[NUMD];
for( int i=0; i< NUMD; i++) {
int row = point[i].m_row, col = point[i].m_col;
if( bit&1) {
B.m_zu[row][col] = rowcol_to_idx( row, col);
Bp[numBp].m_row = row; Bp[numBp].m_col = col; numBp++;
ab[i] = 2; // B
}
else {
A.m_zu[row][col] = rowcol_to_idx( row, col);
Ap[numAp].m_row = row; Ap[numAp].m_col = col; numAp++;
ab[i] = 1; // A
}
bit >>= 1;
}
// 振り分けが終わったら，7点以外に振り分けできる点を振り分ける。
for( i=0; i< nPoint7Sub; i++) {
int row = point7Sub[i].m_row, col = point7Sub[i].m_col;
if( ab[point7Sub[i].m_chr] == 1) {
// Aに分類
A.m_zu[row][col] = rowcol_to_idx(row,col);
Ap[numAp].m_row = row; Ap[numAp].m_col = col; numAp++;
}
else {
// Bに分類
B.m_zu[row][col] = rowcol_to_idx(row,col);
Bp[numBp].m_row = row; Bp[numBp].m_col = col; numBp++;
}
}
}
void find_non_blank_row_col_idx( const Zukei& z, int& row, int& col)
{
for( row=0; row< M; row++) {
for( col=0; col< M; col++) {
if( z.m_zu[row][col] != BLK) {
// colはこれより小さな位置にかこれと等しい位置にあるはず。
for( int c=0; c< col; c++) {
for( int r=0; r< M; r++) {
if( z.m_zu[r][c] != BLK) {
col = c;
return;
}
}
}
col = c;
return;
}
}
}
assert(0); // 図形が空の場合は何らかのエラーがあったと予想される
}
void normalize( Zukei& z, Trans& trans)
{
// 図形を左上に配置する
int row, col;
find_non_blank_row_col_idx( z, row, col);
trans.m_row_diff = row;
trans.m_col_diff = col;
memcpy( z.m_zu, (byte*)z.m_zu+row*sizeof(byte)*M, (M-row)*sizeof(byte)*M);
memcpy( z.m_zu, (byte*)z.m_zu+col*sizeof(byte) , (M*M-col)*sizeof(byte));
// 下のrow行に空白を設定する。
memset( (byte*)z.m_zu+(M-row)*sizeof(byte)*M, BLK, (row)*sizeof(byte)*M);
// 右のcol列には自動で空白が入っているはずなので何もしなくて良い。
}
void doTrans( const Trans& T, int row, int col, int& newRow, int& newCol)
{
newRow = row;
newCol = col;
if( T.m_numMirror) {
newCol = M - newCol - 1;
}
int tmpRow, tmpCol;
for( int r=0; r< T.m_numRotate90; r++) {
tmpRow = newRow, tmpCol = newCol;
newRow = tmpCol;
newCol = M-tmpRow-1;
}
newRow -= T.m_row_diff;
newCol -= T.m_col_diff;
}
void reverseTrans( const Trans& T, int row, int col, int& newRow, int& newCol)
{
newRow = row;
newCol = col;
newRow += T.m_row_diff;
newCol += T.m_col_diff;
int tmpRow, tmpCol;
for( int r=0; r< T.m_numRotate90; r++) {
tmpRow = newRow, tmpCol = newCol;
newRow = M-tmpCol-1;
newCol = tmpRow;
}
if( T.m_numMirror) {
newCol = M - newCol - 1;
}
}
YesNo match( const Zukei& A, const Trans& transA, Point Ap[], int numApFrom, int numApTo, const Trans& transB, Zukei& mergeA, Zukei& mergeB, int mergeType)
{
int rowAdd, colAdd, rowA, colA, rowB, colB;
for( int idx=numApFrom; idx< numApTo; idx++) {
// Aに追加された点に対応する点がB上に存在するか?
rowAdd = Ap[idx].m_row; // 追加された点
colAdd = Ap[idx].m_col;
if( mergeType == 1) mergeA.m_zu[rowAdd][colAdd] = rowcol_to_idx( rowAdd, colAdd);
if( mergeType == 2) mergeB.m_zu[rowAdd][colAdd] = rowcol_to_idx( rowAdd, colAdd);
// これがAの正規化された図形のどこにMAPされるか?
doTrans( transA, rowAdd, colAdd, rowA, colA);
// これがBの元の図形のどこに相当するか?
reverseTrans( transB, rowA, colA, rowB, colB);
// この位置が元の図形に存在するか?
if( !exist(rowB,colB)) return NO;
assert( rowB >= 0 && rowB < M);
assert( colB >= 0 && colB < M);
if( Zorg.m_zu[rowB][colB] == BLK) {
return NO; // 元の図形に存在しない点である
}
if( mergeType == 1) mergeB.m_zu[rowB][colB] = rowcol_to_idx( rowB, colB);
if( mergeType == 2) mergeA.m_zu[rowB][colB] = rowcol_to_idx( rowB, colB);
}
return YES;
}
void mergeZukei( Zukei& z, const Zukei& A, const Zukei& B)
{
for( int row=0; row< M; row++) {
for( int col=0; col< M; col++) {
z.m_zu[row][col] = BLK;
assert( A.m_zu[row][col] == BLK || B.m_zu[row][col] == BLK); // 2つの図形を重ねるとき両方の図形に同じ点が使われているのは拙い
if( A.m_zu[row][col] != BLK) z.m_zu[row][col] = A.m_zu[row][col];
if( B.m_zu[row][col] != BLK) z.m_zu[row][col] = B.m_zu[row][col];
}
}
}
YesNo match( const Zukei& A, const Trans& transA, Point Ap[], int numApFrom, int numApTo,
const Zukei& B, const Trans& transB, Point Bp[], int numBpFrom, int numBpTo,
Zukei& mergeA, Point mergeAp[], int& numMergeAp, Zukei& mergeB)
{
mergeA.clear();
mergeB.clear();
Zukei x;
// ２つの図形が重なるかどうか調べる。図形全体を調べるのは手間がかかるので,調べるべき点だけを調べる。
// aに追加された図形の点がbにあるかどうか調べる。bに無くても問題ないが,bで既に使われていたら駄目。
// Bに追加された点がAに…
if( match( A, transA, Ap, numApFrom, numApTo, transB, mergeA, mergeB, 1) &&
match( B, transB, Bp, numBpFrom, numBpTo, transA, mergeA, mergeB, 2)) {
numMergeAp = 0;
for( int row=0; row< M; row++) {
for( int col=0; col< M; col++) {
if( mergeA.m_zu[row][col] != BLK) {
assert(numMergeAp<NUMX);
mergeAp[numMergeAp].m_row = row;
mergeAp[numMergeAp].m_col = col;
numMergeAp++;
}
}
}
return YES;
}
return NO;
}
void exist_and_nouse( const Zukei& A, const Zukei& B, Zukei& z, int row, int col, Point newPoint[], int& numNewPoint)
{
if( !exist(row,col)) return;
if( Zorg.m_zu[row][col] == BLK) return;
if( A.m_zu[row][col] != BLK) return; // 既に使われている
if( B.m_zu[row][col] != BLK) return;
if( z.m_zu[row][col] != BLK) return;
newPoint[numNewPoint].m_row = row;
newPoint[numNewPoint].m_col = col;
numNewPoint++;
assert( row != 0 && col != 0);
z.m_zu[row][col] = rowcol_to_idx(row,col);
}
int find_point_nouse( const Zukei& A, const Zukei& B, Point Ap[], int low, int numAp, Point newPoint[])
{
Zukei z;
int row, col;
int numNewPoint = 0;
for( int i=low; i< numAp; i++) {
// この点の周りでまだ使われていない点を探す。
// 上,下,左,右を調べる。
row = Ap[i].m_row;
col = Ap[i].m_col;
assert( (row != 0) || (col != 0));
exist_and_nouse( A, B, z, row-1, col+0, newPoint, numNewPoint);
exist_and_nouse( A, B, z, row+1, col+0, newPoint, numNewPoint);
exist_and_nouse( A, B, z, row+0, col-1, newPoint, numNewPoint);
exist_and_nouse( A, B, z, row+0, col+1, newPoint, numNewPoint);
}
return numNewPoint;
}
string zukei_to_str( const Zukei& zukei) // 同じ図形が解として見つかっても複数出力しないように判断するために利用する
{
char buf[M*M*4+1];
astring p = buf;
for( int row=0; row< M; row++) {
for( int col=0; col< M; col++) {
sprintf( p, "%3d.", zukei.m_zu[row][col]); // どんな文字列になっても図形が違えば違う文字列になれば良い
p += 4;
}
}
return buf;
}
void dump( const Zukei& z, cstring msg)
{
int row, col;
int cnt = 0;
for( row=0; row< M; row++) {
for( int col=0; col< M; col++) {
if( z.m_zu[row][col] != BLK) cnt++;
}
}
ps( "%s: num point:%d\n", msg, cnt);
ps( " : ");for( col=0; col< M; col++) ps( "%3d ", col);ps("\n");
for( row=0; row< M; row++) {
ps( "%2d: ", row);
for( int col=0; col< M; col++) {
if( z.m_zu[row][col] == BLK) ps( " . ");
else ps( "%3d ", z.m_zu[row][col]);
}
ps( "\n");
}
ps( "\n");
}
void is_zukei_delete_countinous( Zukei& zukei, int row, int col)
{
if( zukei.m_zu[row][col] != BLK) zukei.m_zu[row][col] = BLK;
if( exist( row-1, col+0) && zukei.m_zu[row-1][col+0] != BLK) is_zukei_delete_countinous( zukei, row-1, col+0);
if( exist( row+1, col+0) && zukei.m_zu[row+1][col+0] != BLK) is_zukei_delete_countinous( zukei, row+1, col+0);
if( exist( row+0, col-1) && zukei.m_zu[row+0][col-1] != BLK) is_zukei_delete_countinous( zukei, row+0, col-1);
if( exist( row+0, col+1) && zukei.m_zu[row+0][col+1] != BLK) is_zukei_delete_countinous( zukei, row+0, col+1);
}
YesNo is_zukei_continuous( const Zukei& zukei)
{
Zukei zukei_check = zukei;
int row, col;
int cnt = 0;
for( row=0; row< M; row++) {
for( int col=0; col< M; col++) {
if( zukei_check.m_zu[row][col] != BLK) {
if( cnt++ == 0) is_zukei_delete_countinous( zukei_check, row, col);
}
}
}
return (cnt==1)?YES:NO;
}
void findNext( Zukei& A, Zukei& B, Point Ap[], int numAp, const Trans& transA, const Trans& transB)
{
Point newPoint[NUMX]; // 図形Aの周りの点で，図形Aに追加できる点を探して設定する
int numNewPoint = 0;
int row, col;
if( numAp >= NUMA) { // 全部の点のうち半分を決定できたので解が見つかった
string str_zukei = zukei_to_str(A);
is_zukei_continuous(A); is_zukei_continuous(B) ;
if( findedSolution.find( str_zukei) == findedSolution.end()) {
// 同じ解を出力しないように既に出現した解を記録しておく。
ps( "Find:%d\n", findedSolution.size()+1);
dump(A,"FIND_A");
dump(B,"FIND_B");
findedSolution.insert( str_zukei);
}
return;
}
// まず新しく追加した点の周りにで拡張できる点を探す。見つからないときは既に全ての点から探す。
numNewPoint = find_point_nouse( A, B, Ap, numAp-1, numAp, newPoint); // 厳密に言うとこの部分は問題あり。main()から呼ばれるとき0にならないと他を探さない
if( numNewPoint == 0) numNewPoint = find_point_nouse( A, B, Ap, 0, numAp, newPoint);
int rowAdd, colAdd, rowA, colA, rowB, colB;
for( int i=0; i< numNewPoint; i++) {
rowAdd = newPoint[i].m_row; // 新しく図形Aに追加しようとしている点
colAdd = newPoint[i].m_col;
doTrans( transA, rowAdd, colAdd, rowA, colA); // その点がAを正規化した図形のどこに配置されるか?
assert( exist(rowA,colA)); // Aの場合必ず図形内に配置されるはず
reverseTrans( transB, rowA, colA, rowB, colB); // それが正規化する前の図形Bのどこに配置されるか?
if( !exist(rowB,colB)) continue; // その位置が図形からはみ出してしまえばこの点はAに追加できない
if( Zorg.m_zu[rowB][colB] == BLK) continue; // 元の図形に存在しない位置であるのでこの点はAに追加できない
if( A.m_zu[rowB][colB] != BLK) continue; // この点は既にAの図形が使っている
if( B.m_zu[rowB][colB] != BLK) continue; // この点は既にBの図形が使っている
assert( A.m_zu[rowAdd][colAdd] == BLK);
assert( B.m_zu[rowB][colB] == BLK); if( B.m_zu[rowB][colB] != BLK) ps( "B*[%d][%d]=%d\n", rowB, colB, B.m_zu[rowB][colB]);
A.m_zu[rowAdd][colAdd] = rowcol_to_idx(rowAdd,colAdd);
B.m_zu[rowB][colB] = rowcol_to_idx( rowB, colB);
Ap[numAp].m_row = rowAdd;
Ap[numAp].m_col = colAdd;
findNext( A, B, Ap, numAp+1, transA, transB);
B.m_zu[rowB][colB] = BLK;
A.m_zu[rowAdd][colAdd] = BLK;
}
}
int main( int argc, cstring argv[])
{
Zukei A, B, mergeA, mergeB;
Zukei A1, B1, B2, B3, B4, C1, C2, C3, C4;
Trans baseTransA1(0,0), baseTransB1(0,0), baseTransB2(1,0), baseTransB3(2,0), baseTransB4(3,0), baseTransC1(0,1), baseTransC2(1,1), baseTransC3(2,1), baseTransC4(3,1); // 正規化を記録
Point point7[NUMD]; // この7点の位置
Point Ap[NUMX], Bp[NUMX], mergeAp[NUMX]; // A,Bの図形上の点
int numAp, numBp, numMergeAp;
// 最初に決まっている7点と,矩形の位置を求める。
int n = init_zukei( Zorg, point7);
dump(Zorg,"Zorg");
ProcTime pt;pt.start();
// 7点から1点,2点,3点を選択し解を求める。
// 3点まででOK。4点になると，3点の場合と逆になるだけなので。
// 選んだ方の図形をBとする。
for( int selnum=1; selnum< 4; selnum++) {
// 選択する点を7ビットから選ぶものとする。
for( int bit=1; bit<= 0x7F; bit++) {
if( bitcount(bit) == selnum) {
// ビットがONの場所を図形Bに選択して検索する。
// 図形にポイントを設定する。
assign_point_to_zukei( A, Ap, numAp, B, Bp, numBp, point7, bit);
Trans transA1=baseTransA1;
Trans transB1=baseTransB1,transB2=baseTransB2,transB3=baseTransB3,transB4=baseTransB4;
Trans transC1=baseTransC1,transC2=baseTransC2,transC3=baseTransC3,transC4=baseTransC4;
// 図形の可能性を調べる。
A1 = A;
B1 = B;
rotate90(B2,B1);
rotate90(B3,B2);
rotate90(B4,B3);
mirror(C1,B1);
mirror(C2,B2);
mirror(C3,B3);
mirror(C4,B4);
// 比較用に図形を正規化する
normalize(A1,transA1);
normalize(B1,transB1);
normalize(B2,transB2);
normalize(B3,transB3);
normalize(B4,transB4);
normalize(C1,transC1);
normalize(C2,transC2);
normalize(C3,transC3);
normalize(C4,transC4);
// 図形が重なる可能性があるか調べ,可能性があれば更に可能性を追求する。
if( match( A1, transA1, Ap, 0, numAp, B1, transB2, Bp, 0, numBp, mergeA, mergeAp, numMergeAp, mergeB)) findNext( mergeA, mergeB, mergeAp, numMergeAp, transA1, transB1);
if( match( A1, transA1, Ap, 0, numAp, B2, transB2, Bp, 0, numBp, mergeA, mergeAp, numMergeAp, mergeB)) findNext( mergeA, mergeB, mergeAp, numMergeAp, transA1, transB2);
if( match( A1, transA1, Ap, 0, numAp, B3, transB2, Bp, 0, numBp, mergeA, mergeAp, numMergeAp, mergeB)) findNext( mergeA, mergeB, mergeAp, numMergeAp, transA1, transB3);
if( match( A1, transA1, Ap, 0, numAp, B4, transB2, Bp, 0, numBp, mergeA, mergeAp, numMergeAp, mergeB)) findNext( mergeA, mergeB, mergeAp, numMergeAp, transA1, transB4);
if( match( A1, transA1, Ap, 0, numAp, C1, transC2, Bp, 0, numBp, mergeA, mergeAp, numMergeAp, mergeB)) findNext( mergeA, mergeB, mergeAp, numMergeAp, transA1, transC1);
if( match( A1, transA1, Ap, 0, numAp, C2, transC2, Bp, 0, numBp, mergeA, mergeAp, numMergeAp, mergeB)) findNext( mergeA, mergeB, mergeAp, numMergeAp, transA1, transC2);
if( match( A1, transA1, Ap, 0, numAp, C3, transC2, Bp, 0, numBp, mergeA, mergeAp, numMergeAp, mergeB)) findNext( mergeA, mergeB, mergeAp, numMergeAp, transA1, transC3);
if( match( A1, transA1, Ap, 0, numAp, C4, transC2, Bp, 0, numBp, mergeA, mergeAp, numMergeAp, mergeB)) findNext( mergeA, mergeB, mergeAp, numMergeAp, transA1, transC4);
}
}
}
pt.end();
pe( "%g 秒\n", pt.sec());
return 0;
}