AOJ : 2058 - Moduic Squares
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2058
問題文の図のように, 1から10の数字をそれぞれ, 3*3のマス目 or 右側の1つのマス目に埋めます.
このとき, 3*3のマス目において, (縦の3つの数字の合計 % 右側のマスの数字) == (横の3つの数字の合計 % 右側のマスの数字) == (斜めの3つの数字の合計 % 右側のマスの数字) となるようなパターンをModuic Squareと呼ぶこととします.
この問題では, 四角形の一部のマスが空いている入力が与えられるので, そのマスを全て埋めたとき, Moduic Squareになるようなパターン数がいくらあるかを答える必要があります.
アルゴリズム
全探索で解きます( O(10!) ).
空いてるマスに, まだ使用していない数字をあてはめて, 全パターンを調べれば解けます.
プログラム
#include <iostream> #include <cstring> using namespace std; int t[9],d; //問題に一致した魔法陣であるかの判定 bool isModuicSquare(void){ int rem = (t[0] + t[1] + t[2]) % t[9]; return ((t[3] + t[4] + t[5]) % t[9] == rem && (t[6] + t[7] + t[8]) % t[9] == rem && (t[0] + t[3] + t[6]) % t[9] == rem && (t[1] + t[4] + t[7]) % t[9] == rem && (t[2] + t[5] + t[8]) % t[9] == rem && (t[0] + t[4] + t[8]) % t[9] == rem && (t[2] + t[4] + t[6]) % t[9] == rem); } int solve(int idx,bool *used){ if(idx == 10) return isModuicSquare() ? 1 : 0; if(t[idx] != 0) return solve(idx+1,used); int res = 0; for(int i=1;i<=10;i++){ if(!used[i]){ t[idx] = i; used[i] = true; res += solve(idx+1,used); used[i] = false; t[idx] = 0; } } return res; } int main(void){ while(1){ bool used[11]; memset(used,0,sizeof(used)); for(int i=0;i<10;i++){ cin>>t[i]; if(t[i] > 0) used[t[i]] = true; } if(t[0] == -1) break; cout<<solve(0,used)<<endl; } return 0; }