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;
}
