• 问题来源
• 问题简介

  给定一个未填满的数独，要求你把它填满。

解题思路

Code

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

struct Node {
    Node() { set(0, 0, 0, false); };
    Node(int row, int col, int num) { set(row, col, num, false); };
    void set(int r, int c, int n, bool s) {
        col = c;
        row = r;
        num = n;
        block = row / 3 * 3 + col / 3;
        seted = s;
    }
    bool seted;
    int col,
        row,
        block,
        num;
};

class Solution {
public:
    Solution(char data[9][10]) {
        init(data);
    }

    ~Solution() {
        for (int i = 0; i < 9; i++) {
            delete[] data[i];
        }
        delete[] data;
    }

    bool solve() {
        stack<Node> q;
        bool inited = false;

        q.push(Node(0, -1, 0));
        while (!q.empty()) {
            Node &cur = q.top();
            // cout << cur.row << " " << cur.col << " " << cur.num << endl;
            t_node = cur;


            if (inited) {
                if (!cur.seted) {
                    set(cur);
                }
                else {
                    unset(cur);
                    q.pop();
                    continue;
                }
            }
            else {
                q.pop();
                inited = true;
            }

            if (!next_space(t_node)) {
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++) {
                        data[i][j] = data_int[i][j] + '0';
                    }
                }
                return true;
            }

            for (int i = 1; i <= 9; i++) {
                t_node.num = i;
                if (isNotOccupied(t_node)) {
                    q.push(t_node);
                }
            }
        }
        return false;
    }

    void display() {
        for_each(data, data + 9, [&](char *t) {
            for (int i = 0; i < 9; i++) {
                cout << t[i] << " ";
            }
            cout << endl;
        });
    }

private:
    char **data;
    bool row_occupied[9][10],
        col_occupied[9][10],
        block_occupied[9][10];

    uint8_t data_int[9][10];
    Node t_node;

    void init(char t[9][10]) {
        data = new char*[9];
        for (int i = 0; i < 9; i++) {
            data[i] = new char[10];
            for (int j = 0; j < 10; j++) {
                data[i][j] = t[i][j];
            }
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                for (int num = 0; num < 10; num++) {
                    t_node.set(i, j, num, false);
                    unset(t_node);
                }

            }
        }

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (data[row][col] == '.') {
                    continue;
                }
                else {
                    t_node.set(row, col, data[row][col] - '0', false);
                    set(t_node);
                }
            }
        }
    }

    inline void set(Node &cur) {
        row_occupied[cur.row][cur.num] = true;
        col_occupied[cur.col][cur.num] = true;
        block_occupied[cur.block][cur.num] = true;
        cur.seted = true;

        data_int[cur.row][cur.col] = cur.num;
    }

    inline void unset(const Node &cur) {
        row_occupied[cur.row][cur.num] = false;
        col_occupied[cur.col][cur.num] = false;
        block_occupied[cur.block][cur.num] = false;

        data_int[cur.row][cur.col] = '.';
    }

    inline bool isNotOccupied(const Node &cur) {
        return (!row_occupied[cur.row][cur.num] && !col_occupied[cur.col][cur.num] && !block_occupied[cur.block][cur.num]);
    }

    inline bool next_space(Node &cur) {
        while (cur.row != 8 || cur.col != 8) {
            ++cur.col;
            if (cur.col == 9) {
                ++cur.row;
                cur.col = 0;
            }
            if (data[cur.row][cur.col] == '.') {
                cur.block = cur.row / 3 * 3 + cur.col / 3;
                return true;
            }
        }
        return false;
    }

};

int main() {
    char data[][10] = {
        "53..7....",
        "6..195...",
        ".98....6.",
        "8...6...3",
        "4..8.3..1",
        "7...2...6",
        ".6....28.",
        "...419..5",
        "....8..79"
    };
    Solution t(data);
    bool rs = t.solve();
    if (rs) {
        t.display();
    }
    else {
        cout << "无解" << endl;
    }

    return 0;
}

运行结果