锐客网

  1. 首页 > it技术 > >

C++实现数独快速求解

什么是数独 数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
解决思路 1、遍历数独表，找出数字为空（以0填充）的表格；
2、找出每个数据中空的表格中可以填充的数字；
3、找到其中可以填充的数字个数最少的表格；
4、将每个数字分别填充到该表格中；
5、递归重复步骤1-4，直到表格中不再有数字为0的表格

#include #include 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(totalres; pos->row = i; pos->col = j; pos->res = res; minum = total; }elsedelete []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:"<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<
【C++实现数独快速求解】C++实现数独快速求解
文章图片

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。

    推荐阅读


    上一篇：图文详解Mysql索引的最左前缀原则

    下一篇：android实现数独游戏机器人