这篇文章主要介绍“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++如何实现数独快速求解”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注编程网行业资讯频道，小编每天都会为大家更新不同的知识点。
