/********************************************************************* * C MAGAZINE 2001 4 電脳クラブ(121回) 隣差魔方陣 * * * * Vid Forn ( vid@geocities.co.jp ) * ********************************************************************/ /*-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/ /* インクルードファイル *********************************************/ #include #include /*-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/ /* マクロ ***********************************************************/ /* マスの位置 * A B C * D E F * G H I * と置く。 * 一次元配列に数値はセットするため、その添字 */ #define A 0 #define B 1 #define C 2 #define D 3 #define E 4 #define F 5 #define G 6 #define H 7 #define I 8 /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* マス自体添字付きで */ #define MA mbox[0] #define MB mbox[1] #define MC mbox[2] #define MD mbox[3] #define ME mbox[4] #define MF mbox[5] #define MG mbox[6] #define MH mbox[7] #define MI mbox[8] /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 隣差を計算する */ #define nsub(n,m) abs(mbox[n]-mbox[m]) /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 関数の戻り値 成功／失敗 */ #define SUCCEED 0 #define FAILE -1 /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 魔方陣の値，隣差の値を入れる時の変数 */ #define MAGIC int /* unsigned char より int の方が早いので…… */ /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 数値の大小のチェックのため */ #define ifbig( a , b ) (((a)>(b))?1:(((b)>(a))?-1:0)) /* 参照が二回起るため、インクリメント／デクリメントの * 副作用に注意。よーするに使えない。 */ /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* フラグが上がっているかどうかを調べる */ #define USE(n) ( chkflg&(0x01<<(n)) ) /* 0: 上がっていない ／ not 0 フラグは上がっている */ #ifdef NDEBUG /* フラグ操作(マクロ) */ #define check(n) ( chkflg |= ( 0x01 << (n) ) ) #define uncheck(n) ( chkflg &= (~( 0x01<<(n))) ) #endif /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 答え表示用(デバグ時以外は出力しない) */ #ifdef NDEBUG #define printans() ; #endif /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 数値候補が 4 つある場合の計算 */ #define fourcheck(v,w,x,y,z) \ if( (v=mbox[(w)]+(x))==(mbox[(y)]+(z)) ){}else \ if( (v=mbox[(w)]+(x))==(mbox[(y)]+(z)) ){}else \ if( (v=mbox[(w)]+(x))==(mbox[(y)]+(z)) ){}else \ if( (v=mbox[(w)]+(x))==(mbox[(y)]+(z)) ){}else \ { continue; }; \ if( i < 1 ){ continue; } /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* for LOOP の中の条件 */ #define LOOP(n) for( n = 1 ; n <= 12 ; n++ ){ UseCheck(n); #define LOOPEND } #define LOOP2(n,m) for(n=1;n<=12;n++){ UseCheck(n);\ for(m=1;m<=12;m++){ UseCheck(m); #define LOOP2END }} /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* USE チェック→ for 繰り返し */ #define UseCheck(n) if( USE(n) ){ continue; } /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* sign による数値の上下 */ #define SIGNLOOP {int sign;\ for( sign = -1 ; sign <= 1 ; sign += 2 ){ #define SIGNLOOPEND }} /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 数字が重なっているかどうかを調べる */ #ifdef NDEBUG #define checkover() ((MA!=MB)&&(MA!=MC)&&(MA!=MD)&& \ (MA!=ME)&&(MA!=MF)&&(MA!=MG)&& \ (MA!=MH)&&(MA!=MI)&&(MB!=MC)&& \ (MB!=MD)&&(MB!=ME)&&(MB!=MF)&& \ (MB!=MG)&&(MB!=MH)&&(MB!=MI)&& \ (MC!=MD)&&(MC!=ME)&&(MC!=MF)&& \ (MC!=MG)&&(MC!=MH)&&(MC!=MI)&& \ (MD!=ME)&&(MD!=MF)&&(MD!=MG)&& \ (MD!=MH)&&(MD!=MI)&&(ME!=MF)&& \ (ME!=MG)&&(ME!=MH)&&(ME!=MI)&& \ (MF!=MG)&&(MF!=MH)&&(MF!=MI)&& \ (MG!=MH)&&(MG!=MI)&&(MH!=MI)) #endif /*-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/ /* 関数宣言 *********************************************************/ int main( int argc , char *argv[] ); /* メイン関数 */ int clear(); /* セットされた魔方陣の数値のクリア */ #ifndef NDEBUG /* フラグ操作(関数) */ int check( int num ); /* 隣差として使用した値のチェック */ int uncheck( int num ); /* 同、チェックを外す */ #endif int calc1(); /* 計算１ A=1 の時 */ int calc1_sub1(); /* 関数が長くなったのでその対策 */ int calc2(); /* 計算２ B=1 の時 */ int calc2_sub1(); int calc3(); /* 計算３ E=1 の時 */ int calc3_sub1( int be ); #ifndef NDEBUG int printans(); /* 答えの表示 */ int checkover(); /* 数字が重なってないかのチェック */ #endif /*-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/ /* グローバル変数 ***************************************************/ MAGIC mbox[9]; /* 魔方陣 */ unsigned short int chkflg; /* 使用された隣差のチェックフラグ */ char *message[] = { "Pattern 1 ( A=1 / AB < AD )\n", "Pattern 2 ( B=1 / AB < BC )\n", "Pattern 3 ( E=1 / BE < EH / BE < DE < EF )\n", "Answer: %d\n", }; enum message_num { PAT1 = 0 , PAT2 , PAT3 , ANSWER }; /*-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/ /* 関数 *************************************************************/ /* main +---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ int main( int argc , char *argv[] ) { int ans,old; /* 答えの数 */ /* 初期化 */ ans = 0; chkflg = 0; /* 計算１ A=1 */ ans = calc1(); #ifndef NDEBUG printf( "FLAG: %d\n" , chkflg ); #endif printf("Ans: %d\n" , ans ); /* 計算２ B=1 */ ans += ( old = calc2()); #ifndef NDEBUG printf( "FLAG: %d\n" , chkflg ); #endif printf("Ans: %d\n" , old ); /* 計算３ E=1 */ ans += (old = calc3()); #ifndef NDEBUG printf( "FLAG: %d\n" , chkflg ); #endif printf("Ans: %d\n" , old ); /* 答えの数の表示 */ printf( message[ANSWER] , ans ); return SUCCEED; } #ifndef NDEBUG /* printans +---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 答えを表示する */ int printans() { static int count = 0; static unsigned char hash[6]; if( !checkover() ){ return FAILE; } /* */ count++; printf("\n>>%d\n" " %2d [%2d] %2d [%2d] %2d\n" "[%2d] [%2d] [%2d]\n" " %2d [%2d] %2d [%2d] %2d\n" "[%2d] [%2d] [%2d]\n" " %2d [%2d] %2d [%2d] %2d\n", count , MA , nsub(A,B), MB , nsub(B,C) , MC, nsub(A,D) , nsub(B,E) ,nsub(C,F), MD , nsub(D,E), ME , nsub(E,F) , MF, nsub(D,G) , nsub(E,H) , nsub(F,I), MG , nsub(G,H), MH , nsub(H,I) , MI ); hash[0] = (( nsub(A,B) & 0x0F )<< 4) | ( nsub(B,C) & 0x0F ); hash[1] = (( nsub(D,E) & 0x0F )<< 4) | ( nsub(E,F) & 0x0F ); hash[2] = (( nsub(G,H) & 0x0F )<< 4) | ( nsub(H,I) & 0x0F ); hash[3] = (( nsub(A,D) & 0x0F )<< 4) | ( nsub(D,G) & 0x0F ); hash[4] = (( nsub(B,E) & 0x0F )<< 4) | ( nsub(E,H) & 0x0F ); hash[5] = (( nsub(C,F) & 0x0F )<< 4) | ( nsub(F,I) & 0x0F ); printf(":%c%02X%02X%02X%02X%02X%02X\n", ((MA==1)?'A':((MB==1)?'B':((ME==1)?'E':'X'))), hash[0] , hash[1] , hash[2] , hash[3] , hash[4] , hash[5] ); return SUCCEED; } /* check +---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* フラグチェック */ /* 戻り値 * SUCCEED 成功(値はチェックされる) * FAILE 失敗(値はチェックされている＝使用されている) */ /* FAILE の場合、フラグ操作は行われない */ int check( int num ) { if( (chkflg&(0x01< ab /*条件２*/; ad-- ){ MD = 1 /*MA*/ + ad; check( ad ); /* E の決定 */ LOOP2(be,de){ /* E 決定時の時には４つのパターンが考えられる */ /* (+be,+de) , (+be,-de) , (-be,+de) , (-be,-de) */ /* これらのどれかで E が成立した場合、他の組み合わせは 成り立たない */ fourcheck( i , B , be , D , de ); /* */ /* ここに来た時点で E が成立している */ /* E の候補値は i に代入されている */ /* 成立した場合は次の計算に移るのだが、 * 関数が長くなったので次の関数へ移す */ ME = i; check(be); check(de); ans += calc1_sub1(); uncheck(be); uncheck(de); }LOOP2END/* END LOOP: be,de */ uncheck( ad ); } /* END for : ad = 12 ; ad > ab ; ad-- */ uncheck( ab ); /* 使用した値の解放 */ } /* End for : ab = 1 ; ab < ad ; ab++ */ return ans; } /* calc1_sub +---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 長くなったので関数分割 */ int calc1_sub1() { MAGIC cf , bc , dg , ef , eh , fi , gh , hi; int ans = 0 , i; /* ABDE が決定されている／回転・鏡像解は既に考慮済み */ /* F の決定 */ LOOP(ef){ check( ef ); SIGNLOOP; MF = ME + (ef*sign); /* C の決定 */ LOOP2(bc,cf){ fourcheck( i , B , bc , F , cf ); MC = i; check(bc); check(cf); /* H の決定 */ LOOP(eh){ check(eh); SIGNLOOP; MH = ME + (eh*sign); /* G の決定 */ LOOP2(dg,gh){ fourcheck( i , D , dg , H , gh ); MG = i; check(dg); check(gh); /* I の決定 */ LOOP2(fi,hi){ fourcheck( i , F , fi , H , hi ); MI = i; ans += checkover(); /* 答えが求まった */ /* checkover は、同じ数字がマスに無ければ 1 を返すようにしている。あれば 0 が返る */ /* つまり、相違であれば答えが +1 される */ printans(); /* 答えの簡易表示 */ /* ……やっぱり長く深くなってるのは これ以上は気にしない事にしよう */ }LOOP2END; /* END LOOP : fi , hi */ uncheck(dg); uncheck(gh); }LOOP2END; /* END LOOP: dg,gh */ SIGNLOOPEND; uncheck(eh); }LOOPEND;/* END LOOP: eh */ uncheck(cf); uncheck(bc); }LOOP2END; /* END LOOP : bc,cf */ SIGNLOOPEND; uncheck( ef ); }LOOPEND; /* END LOOP : ef */ return ans; } /* calc2 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* パターン２／条件 B = 1 : AB < BC */ int calc2() { int ans = 0 ; /* 答えの数 */ int i; MAGIC ab, be , ad , de , bc; /* 計算時のテンポラリ */ /* 条件表示など */ printf( "%s" , message[PAT2] ); /* 計算開始 */ MB = 1; /* 条件１ */ /* A の決定 */ for( ab = 1 ; ab <= 11 ; ab++ ){ /* AB < BC より、 AB=12 は存在しない */ MA = 1 + ab; check( ab ); /* E の決定 */ LOOP(be){ check(be); ME = 1 + be; /* D の決定 */ LOOP2(ad,de){ fourcheck( i , A , ad , E , de ); MD = i; check( ad ); check( de ); /* C の決定 */ for( bc = 12 ; bc > ab ; bc-- ){ /* ab < bc (条件２) */ UseCheck(bc); check( bc ); MC = 1 + bc; ans += calc2_sub1(); uncheck( bc ); } /* END for: bc = 12 ; bc > ab ; bc-- */ uncheck( ad ); uncheck( de ); }LOOP2END; /* END LOOP : ad , de */ uncheck(be); }LOOPEND /* END LOOP : be */ uncheck( ab ); } /* END for : ab = 1 ; ab <= 11 ; ab++ */ return ans; } /* calc2_sub1 +---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 長くなったので関数分割 */ int calc2_sub1() { int ans=0,i; MAGIC cf , ef , fi , eh , dg , gh , hi; /* ここに来た時点で回転・鏡像解の重複チェックは行われている */ /* ABCDE が決定している */ /* F の決定 */ LOOP2(cf,ef){ fourcheck( i , C , cf , E , ef ); check( cf ); check( ef ); MF = i; /* H の決定 */ LOOP(eh){ check(eh); SIGNLOOP; MH = ME + (eh*sign); /* G の決定 */ LOOP2(dg,gh){ fourcheck( i , D , dg , H , gh ); MG = i; check(dg); check(gh); /* I の決定 */ LOOP2(fi,hi){ fourcheck( i , F , fi , H , hi ); MI = i; ans += checkover(); /* 答えのチェック */ printans(); /* 答えの簡易表示 */ }LOOP2END; /* END LOOP : fi , hi */ uncheck(dg); uncheck(gh); }LOOP2END; /* END LOOP: dg,gh */ SIGNLOOPEND; uncheck(eh); }LOOPEND; /* END LOOP : eh */ uncheck( cf ); uncheck( ef ); }LOOP2END; /* END LOOP: cf,ef */ return ans; } /* calc3 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* パターン３／条件 E = 1 : BE < EH : BE < DE < EF */ int calc3() { int ans = 0; /* 答えの数 */ int i; MAGIC be , de , ab , ad , ef; /* 条件表示など */ printf( "%s" , message[PAT3] ); ME = 1; /* 条件１ */ /* B の決定 */ for( be = 1 ; be <= 9 ; be++ ){ /* be < (de,ef,eh) より、 be は 9 以下 */ check(be); MB = 1+be; /* D の決定 */ for( de = 11 ; de > be ; de-- ){ /* be < de < ef より、 de は 11 以下、 be より上 */ check(de); MD = 1 +de; /* A の決定 */ LOOP2(ab,ad){ fourcheck( i , B , ab , D , ad ); MA = i; check( ab ); check( ad ); /* F の決定 */ for( ef = 12 ; ef > de ; ef-- ){ UseCheck(ef); check(ef); MF = 1 + ef; ans += calc3_sub1( be ); uncheck(ef); } /* END for: ef = 12 ; ef > de ; ef-- */ uncheck( ad ); uncheck( ab ); }LOOP2END;/* END LOOP: ab,ad */ uncheck(de); } /* END for : de = 11 ; de > be ; de-- */ uncheck(be); } /* END for : be = 1 ; be <= 9 ; be++ */ return ans; } /* calc3_sub1 +---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /* 長くなったので関数分割 */ int calc3_sub1( int be ) { int ans = 0,i; MAGIC eh , bc , cf , dg , gh , hi , fi; /* ABDEF 決定済み */ /* C 決定 */ LOOP2(bc,cf){ fourcheck( i , B , bc , F , cf ); check( bc ); check( cf ); MC = i; /* H 決定 */ for( eh = 12 ; eh > be ; eh-- ){ /* 回転・鏡像解排除条件より eh > be */ UseCheck(eh); check( eh ); MH = 1 + eh; /* G 決定 */ LOOP2(dg,gh){ fourcheck( i , D , dg , H , gh ); MG = i; check(dg); check(gh); /* I 決定 */ LOOP2(fi,hi){ fourcheck( i , F , fi , H , hi ); MI = i; ans += checkover(); /* 答えのチェック */ printans(); /* 答えの簡易表示 */ }LOOP2END; /* END LOOP : fi , hi */ uncheck(dg); uncheck(gh); }LOOP2END; /* END LOOP: dg,gh */ uncheck( eh ); } /* END for : eh = 12 ; eh > be ; eh -- */ uncheck( cf ); uncheck( bc ); }LOOP2END; /* bc,cf */ return ans; } /*+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+*/ /*-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/ /********************************************************************/ /********************************************************************/ /*-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/ /* メモ ************************************************************** * マスの位置 * A B C * D E F * G H I * １：数値の１を絶対に使用すること。 * ２：回転・鏡像解の排除 * この２点より、計算は * 1) A = 1 : AB < AD * 2) B = 1 : AB < BC * 3) E = 1 : BE < EH : BE < DE < EF * 三種類を計算し、この合計が答えになると考えられる。 * 計算の順番 * 求める箱の順番 () の中は隣差として決定する値 * 一意に決められない場合はそこで計算を一つ前に戻す(枝刈り) * 計算の順番は何通りも考えられるが、 * 私は以下の順番でマスの値を求めた * 1) A * (AB)B * (AD)D * (BE:DE)E * (EF)F * (BC:CF)C * (EH)H * (DG:GH)G * (FI:HI)I * 2) B * (AB)A * (BE)E * (AD:DE)D * (BC)C * (CF:EF)F * (EH)H * (DG:GH)G * (FI:HI)I * 3) E * (BE)B * (AB)A * (AD:DE)D * (EF)F * (BC:CF)C * (EH)H * (DG:GH)G * (FI:HI)I ******************************************************************** * プログラムとしては、グローバル関数に頼っているところなど * 非常に見苦しいけど、そこはご勘弁です。 * 変数、全部、内側に持ち込むことも考えましたが…… * どっちがよかったでしょ？ 私としては、関数に引数を渡す * 必要がないので、こちらの方が楽でしたが。それに、マクロを使って * ある程度隠蔽してるので、結局はどっちもどっちだと思うのですが…… ********************************************************************/ /********************************************************************/ /* Copyright (c) Vid Forn / FUKUMORI Akihiro , 2001 */ /* vid@geocities.co.jp */ /* http://www.geocities.co.jp/SiliconValley-PaloAlto/2293/ */ /********************************************************************/ /* EOF **************************************************************/