C++如何实现数独快速求解

这篇文章主要介绍“c++如何实现数独快速求解”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“C++如何实现数独快速求解”文章能帮助大家解决问题。

什么是数独

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

解决思路

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

#include <iOStream>#include <ctime>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(total<minum)            {                delete []pos->res;                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:"<<clock()/1e6<<endl;        printResult(board);        return;    }    for(int i=0;i<9;++i)    {        if(pos->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<<start/1e6<<endl;    int board[][9] =        {            0, 0, 0, 0, 0, 0, 0, 1, 0,            4, 0, 0, 0, 0, 0, 0, 0, 0,            0, 2, 0, 0, 0, 0, 0, 0, 0,            0, 0, 0, 0, 5, 0, 4, 0, 7,            0, 0, 8, 0, 0, 0, 3, 0, 0,            0, 0, 1, 0, 9, 0, 0, 0, 0,            3, 0, 0, 4, 0, 0, 2, 0, 0,            0, 5, 0, 1, 0, 0, 0, 0, 0,            0, 0, 0, 8, 0, 6, 0, 0, 0        };    printResult(board);    sudoku(board);    int end = clock();    cout <<"time:" << (end - start)/1e6 << endl;    return 0;}

关于“C++如何实现数独快速求解”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注编程网其他教程频道，小编每天都会为大家更新不同的知识点。