快捷導(dǎo)航

C++實現(xiàn)數(shù)獨快速求解

更新時間：2022年03月24日 14:00:17 作者：h578272581

這篇文章主要為大家詳細介紹了C++實現(xiàn)數(shù)獨快速求解的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

什么是數(shù)獨

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

解決思路

1、遍歷數(shù)獨表，找出數(shù)字為空（以0填充）的表格；
2、找出每個數(shù)據(jù)中空的表格中可以填充的數(shù)字；
3、找到其中可以填充的數(shù)字個數(shù)最少的表格；
4、將每個數(shù)字分別填充到該表格中；
5、遞歸重復(fù)步驟1-4，直到表格中不再有數(shù)字為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;
}