求解数独 改自超级用户 侵删

明天自然醒

求解使用状态压缩+回溯。
状态压缩

• 使用 bitset<9> 来压缩存储每一行、每一列、每一个 3x3 宫格中 1-9 是否出现
• 这样每一个格子就可以计算出所有不能填的数字，然后得到所有能填的数字 getPossibleStatus()
• 填入数字和回溯时，只需要更新存储信息
• 每个格子在使用时，会根据存储信息重新计算能填的数字
  

回溯

• 每次都使用 getNext() 选择能填的数字最少的格子开始填，这样填错的概率最小，回溯次数也会变少
• 使用 fillNum() 在填入和回溯时负责更新存储信息
• 一旦全部填写成功，一路返回 true ，结束递归
  

[C++] 纯文本查看 复制代码

class Solution {

private:
    bitset<9> getPossibleStatus(int x, int y)
    {
        return ~(rows[x] | cols[y] | cells[x / 3][y / 3]);
    }

    vector<int> getNext(vector<vector<char>>& board)
    {
        vector<int> ret;
        int minCnt = 10;
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board.size(); j++)
            {
                if (board[j] != '.') continue;
                auto cur = getPossibleStatus(i, j);
                if (cur.count() >= minCnt) continue;
                ret = { i, j };
                minCnt = cur.count();
            }
        }
        return ret;
    }

    void fillNum(int x, int y, int n, bool fillFlag)
    {
        rows[x][n] = (fillFlag) ? 1 : 0;
        cols[y][n] = (fillFlag) ? 1 : 0;
        cells[x / 3][y / 3][n] = (fillFlag) ? 1 : 0;
    }

    bool dfs(vector<vector<char>>& board, int cnt)
    {
        if (cnt == 0) return true;

        auto next = getNext(board);
        auto bits = getPossibleStatus(next[0], next[1]);
        for (int n = 0; n < bits.size(); n++)
        {
            if (!bits.test(n)) continue;
            fillNum(next[0], next[1], n, true);
            board[next[0]][next[1]] = n + '1';
            if (dfs(board, cnt - 1)) return true;
            board[next[0]][next[1]] = '.';
            fillNum(next[0], next[1], n, false);
        }
        return false;
    }

    vector<bitset<9>> rows;
    vector<bitset<9>> cols;
    vector<vector<bitset<9>>> cells;

public:

    void solve(vector<vector<char>>& board)
    {
        rows = vector<bitset<9>>(9, bitset<9>());
        cols = vector<bitset<9>>(9, bitset<9>());
        cells = vector<vector<bitset<9>>>(3, vector<bitset<9>>(3, bitset<9>()));

        int cnt = 0;
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board.size(); j++)
            {
                cnt += (board[j] == '.');
                if (board[j] == '.') continue;
                int n = board[j] - '1';
                rows |= (1 << n);
                cols[j] |= (1 << n);
                cells[i / 3][j / 3] |= (1 << n);
            }
        }
        dfs(board, cnt);
    }
};

秒出结果

数独.zip (228.31 KB, 下载次数: 55)

2023-4-9 00:22 上传

点击文件名下载附件

原贴
易语言数独，当前论坛最完美的数独哦！！（为作业No.94的源码）
https://bbs.125.la/forum.php?mod=viewthread&tid=14191541
(出处: 精易论坛)

469207978

DLL 易语言源码有吗

469207978

不能解其他答案？

lm88818

支持开源~！感谢分享

我喜欢学习

好,太好了

精易论坛龙

牛，

sanclyj

求解数独 改自超级用户

喵芣可言

已经顶贴，感谢您对论坛的支持！

xxx159357

好,太好了

灵感吖

支持一下，学习看看~~~

Conquer

谢谢分享学习一下