tak0kadaの何でもノート

発声練習、生存確認用。

医学関連は 医学ノート へ

数独 :: DFS

アルゴリズム 数独 C、C++

数独をコンピュータに解いてもらうシリーズの第一段。

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

参考