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;
}