数独ソルバ

topcoder等のプログラミングコンテスト用の練習をしていると、数独のようなパズルは、それ自体がパズルなのでは無くて、それを解くプログラムを書くというパズルに思えてくる。という訳で、書いてみた。何も考えてない、単なる深さ優先探索。

ソース

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>


using namespace std;


class SudokuSolver{

private:
  vector<vector<int> > cell;
  vector<vector<bool> > given;
  const int n;
  const int n_rt;

  bool check_row(const int i, const int val){
    for(int j = 0; j < n; j++){
      if(cell[i][j] == val) return false;
    }
    return true;
  }
  bool check_col(const int j, const int val){
    for(int i = 0; i < n; i++){
      if(cell[i][j] == val) return false;
    }
    return true;
  }
  bool check_room(const int r, const int val){
    for(int i = 0; i < n_rt; i++){
      for(int j = 0; j < n_rt; j++){
	if(cell[i + (r / n_rt) * n_rt][j + (r % n_rt) * n_rt] == val) return false;
      }
    }
    return true;
  }
  int index2room(const int i, const int j){
    const int ii = i / n_rt;
    const int jj = j / n_rt;
    return ii * n_rt + jj;
  }
  bool dfs(const int i, const int j){
    if((i == n - 1) && (j == n - 1)){
      for(int k = 0; k < n; k++){
	if(check_row(i, k)){
	  cell[i][j] = k;
	  break;
	}
      }
      return true;
    }

    int ii, jj;
    if(j == n - 1){
      ii = i + 1;
      jj = 0;
    }
    else{
      ii = i;
      jj = j + 1;
    }

    if(!given[i][j]){
      for(int k = 0; k < n; k++){
	if(check_row(i, k) && check_col(j, k) && check_room(index2room(i, j), k)){
	  cell[i][j] = k;
	  if(dfs(ii, jj)) return true;
	  cell[i][j] = -1;
	}
      }
      return false;
    }
    else{
      return dfs(ii, jj);
    }
  }

public:
  SudokuSolver(int n_, int n_rt_) :
    n(n_), n_rt(n_rt_)
  {
    cell.clear();
    cell.resize(n, vector<int>(n, -1));
    given.clear();
    given.resize(n, vector<bool>(n, false));
  }
  void readProblem(istream& ist){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
	ist >> cell[i][j];
	cell[i][j]--;
	if(cell[i][j] >= 0){
	  given[i][j] = true;
	}
      }
    }
  }
  void print(ostream& ost){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
	ost << cell[i][j] + 1 << " ";
      }
      ost << endl;
    }
  }
  void run(){
    dfs(0, 0);
  }
};

istream& operator>>(istream& ist, SudokuSolver& s){
  s.readProblem(ist);
  return ist;
}

ostream& operator<<(ostream& ost, SudokuSolver& s){
  s.print(ost);
  return ost;
}  


int main(int argc, char* argv[]){
  int n, n_rt;
  cin >> n >> n_rt;

  SudokuSolver solver(n, n_rt);
  cin >> solver;
  solver.run();
  cout << solver;

  return 0;
}

入力ファイル

9 3
0 0 5 3 0 0 0 0 0
8 0 0 0 0 0 0 2 0
0 7 0 0 1 0 5 0 0
4 0 0 0 0 5 3 0 0 
0 1 0 0 7 0 0 0 6
0 0 3 2 0 0 0 8 0
0 6 0 5 0 0 0 0 9
0 0 4 0 0 0 0 3 0
0 0 0 0 0 9 7 0 0

• 最初の1行に、問題のサイズ。
  • 行の数( = 列の数 = 数字の種類数)と、その平方根
• 残りに、問題。空欄には0を入れる。

実行方法

./a.out < inupt.txt

次なるパズルは、このアルゴリズムで最も時間がかかる入力を考えること。