数独をコンピュータに解いてもらうシリーズの第一段。
DFS(深さ優先探索)は、名前の通りグラフの親ノードから子ノードがなくなるまで探索し、バックトラックする方法である。再帰かスタックを用いて実装される。c++が初めてなのもあるが、ゆっくり実装しすぎてしまった点は反省。
スタックのメンバ関数
#include<iostream> #include<stack> std::stack<int> st; // 先頭に追加 st.push(1); // 先頭への参照 std::cout << st.top(); // 1 // 先頭を削除 st.pop(); // 空ならtrue st.empty(); // 0 // サイズ(size_type)を返す std::cout << st.size(); // 1
実装
結局高々81回しか再帰しないのでスタック使う気がなくなった。使う場合は盤面をスタックもどきとして使うべきでstd::stackは必要ない。
inputはこんな感じ。
009030020 400068000 080200000 615000000 007005008 000700063 020300080 000187036 006000400
#include<iostream> #include<string> #include<vector> //#define REP(i, n) for(int i = 0; i < (n); ++i) //template <typename T> // using vv = vector<vector<T>>; using std::vector; using vint = vector<int>; class Board { private: vector<vint> board; vector<vint> isused_x, isused_y, isused_box; public: Board() { board = vector<vint>(9, vint(9)); isused_x = isused_y = isused_box = vector<vint>(9, vint(9)); } void input(); void print(); bool isempty(int x, int y) { return !board[x][y]; } void set(int x, int y, int val) { board[x][y] = val; isused_x[x][val - 1]++; isused_y[y][val - 1]++; isused_box[3 * (x / 3) + y / 3][val - 1]++; } void remove(int x, int y, int val) { board[x][y] = 0; isused_x[x][val - 1]--; isused_y[y][val - 1]--; isused_box[3 * (x / 3) + y / 3][val - 1]--; } // board[x][y]にvalを入れられることの確認(空いているかの確認はしない) bool isok(int x, int y, int val) { return !isused_x[x][val - 1] && !isused_y[y][val - 1] && !isused_box[3 * (x / 3) + y / 3][val - 1]; } }; void Board::input() { std::string line; for (int i = 0; i < 9; i++) { std::cin >> line; for (int j = 0; j < 9; j++) { //board[i][j] = static_cast<int>(line[j] - '0'); board[i][j] = (int)(line[j] - '0'); } } // 問題の設定に矛盾はないとみなす for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (!isempty(i, j)) { isused_x[i][board[i][j] - 1]++; isused_y[j][board[i][j] - 1]++; isused_box[3 * (i / 3) + j / 3][board[i][j] - 1]++; } } void Board::print() { for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) std::cout << board[i][j] << (j == 8 ? "\n" : ""); } class Sudoku { private: Board problem, answer; public: void input() { problem.input(); answer = problem; } void print_ans() { answer.print(); } void print_problem() { problem.print(); } bool solve(int cell=0) { // 全セルが埋まっている場合 if (cell == 81) { return true; } // セルが埋まっていない場合は埋める int x = cell / 9, y = cell % 9; if (answer.isempty(x, y)) { for (int val=1; val < 10; val++) { if (answer.isok(x, y, val)) { answer.set(x, y, val); if (solve(cell + 1)) return true; else answer.remove(x, y, val); } } } // セルが埋まっている場合 else return solve(cell + 1); // うまく行かない場合 return false; } }; int main(void) { Sudoku problem; problem.input(); if (problem.solve()) problem.print_ans(); else std::cout << "bad problem! has no answer." << std::endl; return 0; }
すぐ忘れるのでコンパイルオプションも。
g++ -std=c++11 sudoku.cpp -o sudoku
参考
- 深さ優先探索の説明
- wikipedia:深さ優先探索
- TopCoderから学ぶ美しいマクロや型宣言 C++
↓↑typedef vector<int> VI
とかはusing VI = vector<int>
使うべき - Template Aliases
- キャスト演算子
- topcoderにおけるC++の標準入力読み込み: 今回はあまり関係ないが
\n
が入力に入ってしまう場合の対処法