SRM 315 Div1 Medium SillySudoku

問題

4x4の数独があり、ところどころは数字で埋められている。この状態での正解パターン数を求めよ。

やりかた

深さ優先探索で通る。1～4の順列を生成して各行を試していき、マスが全部埋まったところで正解かどうか調べればいい。マスが小さいので枝刈りは必要なかった。

class SillySudoku {
public:
  int ans;
  vector<vector<int>> f;
  void rec(vector<vector<int>> a, int idx){
    if(idx == 4){
      if(check(a[0][0], a[0][1], a[1][0], a[1][1]) && 
	 check(a[0][2], a[0][3], a[1][2], a[1][3]) && 
	 check(a[2][0], a[2][1], a[3][0], a[3][1]) && 
	 check(a[2][2], a[2][3], a[3][2], a[3][3]) && 
	 check(a[0][0], a[1][0], a[2][0], a[3][0]) && 
	 check(a[0][1], a[1][1], a[2][1], a[3][1]) && 
	 check(a[0][2], a[1][2], a[2][2], a[3][2]) && 
	 check(a[0][3], a[1][3], a[2][3], a[3][3])) ans++;
      return;
    }

    int num[4] = {1, 2, 3, 4};
    do{//各行ですべての順列をためす
      vector<vector<int>> t = a;
      bool good = true;
      for(int i = 0; i < 4; i++){
	if(t[idx][i] == 0 || t[idx][i] == num[i]) t[idx][i] = num[i];
	else good = false;
      }
      if(good) rec(t, idx + 1);
    }while(next_permutation(num, num + 4));

    return;
  }

  bool check(int a, int b, int c, int d){
    int s[4] = {a, b, c, d};
    sort(s, s + 4);
    return s[0] == 1 && s[1] == 2 && s[2] == 3 && s[3] == 4;
  }

  int countWays(vector <string> board){
    ans = 0;
    int N = board.size();
    f.clear();
    f.resize(N);
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	f[i].push_back(board[i][j] == '-' ? 0 : board[i][j]- '0');

    rec(f, 0);
    return ans;
  }
};