前言:
今天朋友们对“用c语言编写数独算法”可能比较着重,同学们都需要了解一些“用c语言编写数独算法”的相关知识。那么小编同时在网摘上汇集了一些关于“用c语言编写数独算法””的相关内容,希望大家能喜欢,兄弟们快快来了解一下吧!使用计算机语言解决谜题问题,对大部分编程爱好者来说都是最感兴趣的。今天来看一道数独问题。
先来讲一下数独的规则。
在一个九宫格(9x9的阵列)的每个格子都有一个数字,并且:
每一行中都包含1-9九个数字且不重复;
每一列都包含1-9九个数字且不重复;
将九宫格分成9个3x3小格子,每个小格子中,包含1-9九个数字且不重复;
在给出一个九宫格,里面已经填写了部分数字后,按照规则要求解出其他未填的空格。
虽然我们人脑做数独题时颇费脑筋,但是计算机解决起来还是很容易的。
下面这是我的解决方案,略加优化的使用递归暴力法。
/*九宫格用board存储,每个格中填写'1' - '9', 或者 '.',表示待填项.*/class Solution {public: void solveSudoku(vector<vector<char>>& board) { //首先将待解决的空格收集存放到一个列表中 vector<pair<int,int>> toBeSolved; for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { if(board[i][j]=='.') toBeSolved.push_back(pair<int,int>(i,j)); } } //从第一个开始,逐个解决每一个空格 subsolver(board,toBeSolved,0); } // 递归解决每一个空格 // currIdx是当前待解决的空格索引 bool subsolver(vector<vector<char>>& board,vector<pair<int,int>> toBeSolved,int currIdx){ pair<int,int> curr = toBeSolved[currIdx]; //根据数独规则,计算出当前空格可以填写的数字集合 set<char> available = getAvailable(board, curr); //如果没有可填写的数字,说明这条路径走不通 if(available.empty()) return false; //如果已经是最后一个空格,到这一步就胜利了, 成功返回!!! ++currIdx; if(currIdx==toBeSolved.size()) { board[curr.first][curr.second] = *available.begin(); return true; } //依次填入一个可选数字,递归调用本函数,看是否能够得到正确答案 for(auto c:available){ board[curr.first][curr.second] = c; //这个数字得到了正确结果,返回true if(subsolver(board,toBeSolved,currIdx)) return true; //这个数字不对,恢复现场,再试下一个; board[curr.first][curr.second] = '.'; } //本轮挑战失败 return false; } //按照规则计算当前空格可选的数字 set<char> getAvailable(vector<vector<char>>& board,pair<int,int>& curr){ set<char> available = {'1','2','3','4','5','6','7','8','9'}; for(int i=0;i<9;i++) { available.erase(board[curr.first][i]); available.erase(board[i][curr.second]); if(available.empty()) return available; } int sub_row = curr.first/3*3; int sub_col = curr.second/3*3; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { available.erase(board[sub_row+i][sub_col+j]); if(available.empty()) return available; } } return available; }};
算法时间复杂度较高,每个空格最多可选项9个,时间复杂度是:
程序的空间复杂度是O(1).
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #用c语言编写数独算法