C++实现数独快速求解
来源:脚本之家    时间:2022-03-24 15:25:43

什么是数独

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。
数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。

解决思路

1、遍历数独表,找出数字为空(以0填充)的表格;
2、找出每个数据中空的表格中可以填充的数字;
3、找到其中可以填充的数字个数最少的表格;
4、将每个数字分别填充到该表格中;
5、递归重复步骤1-4,直到表格中不再有数字为0的表格

#include 
#include 
using namespace std;
struct Position
{
    int row;
    int col;
    int *res;
};
Position* findMinBlank(int board[][9])
{
    int *validNums(int board[][9], int row, int col);
    Position *pos = new Position();
    pos->res = 0;
    int *res;
    int total=0, minum = 10;
    for(int i=0; i<9; ++i)
        for(int j=0; j<9; ++j)
        {
            if(board[i][j]!=0)
                continue;
            res = validNums(board, i, j);
            total = 0;
            for(int p=0; p<9; ++p)
            {
                if(res[p]!=0)
                {
                    ++ total;
                }
            }
            if(totalres;
                pos->row = i;
                pos->col = j;
                pos->res = res;
                minum = total;
            }
            else
                delete []res;
        }
    return pos;
}
int *validNums(int board[][9], int row, int col)
{
    int *res = new int[9] {1,2,3,4,5,6,7,8,9};
    for (int i = 0; i < 9; i++)
    {
        res[board[row][i]-1] = 0;
        res[board[i][col]-1] = 0;
    }
    int p = row / 3 * 3;
    int q = col / 3 * 3;
    for (int x = p; x < p + 3; x++)
        for (int y = q; y < q + 3; y++) 
        {
            res[board[x][y]-1] = 0;
        }
    return res;
}
void printResult(int result[][9] )
{
    for (int i = 0; i < 9; i++) 
    {
        for (int j = 0; j < 9; j++) 
        {
            cout << result[i][j] << "  ";
        }
        cout << endl;
    }
    cout << endl;
}
void sudoku(int board[][9])
{
    Position *pos = findMinBlank(board);
    if(!pos->res)
    {
        cout<<"time:"<res[i]==0)
            continue;
        board[pos->row][pos->col] = pos->res[i];
        sudoku(board);
    }
    board[pos->row][pos->col] = 0;
    delete pos->res;
    delete pos;
}
int main()
{
    int start = clock();
    cout<

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

关键词: 希望大家 八十一格

X 关闭

X 关闭