C++如何實現數獨快速求解

這篇文章主要介紹“C++如何實現數獨快速求解”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C++如何實現數獨快速求解”文章能幫助大家解決問題。

什么是數獨

數獨是源自18世紀瑞士的一種數學游戲。是一種運用紙、筆進行演算的邏輯游戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個粗線宮（3*3）內的數字均含1-9，不重復。
數獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都只出現一次，所以又稱“九宮格”。

解決思路

1、遍歷數獨表，找出數字為空（以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++如何實現數獨快速求解”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。