#include<iostream>
#include <vector>
#include <fstream>
using namespace std;
bool isValid(std::vector<std::vector<int>> &chess,
int x,int y,int val){
bool ret=true;
for(int j=0;j<9;j++){
if(j==y) continue;
if(val==chess.at(x).at(j)){
ret=false;
return ret;
}
}
for(int i=0;i<9;i++){
if(i==x) continue;
if(val==chess.at(i).at(y)){
ret=false;
return ret;
}
}
int new_x=x/3,new_y=y/3;
int tl_x=new_x*3,tl_y=new_y*3;
for(int i=tl_x;i<tl_x+3;i++){
for(int j=tl_y;j<tl_y+3;j++){
if(i==x&&j==y){
continue;
}
if(val==chess.at(i).at(j)){
ret=false;
return ret;
}
}
}
return true;
}
struct Pos{
Pos(int i,int j):x(i),y(j),val(0){}
int x;
int y;
int val;
};
class Solution{
public:
bool backTracking(std::vector<std::vector<int>> &matrix,
std::vector<Pos>& pos,int n){
bool ret=false;
if(n==pos.size()){
return true;
}
for(int i=1;i<=9;i++){
pos.at(n).val=i;
if(isValid(matrix,pos.at(n).x,pos.at(n).y,i)){
matrix.at(pos.at(n).x).at(pos.at(n).y)=i;
ret=backTracking(matrix,pos,n+1);
if(ret){
break;
}else{
matrix.at(pos.at(n).x).at(pos.at(n).y)=0;
}
}
}
return ret;
}
void findSolution(std::vector<std::vector<int>> &matrix,
std::vector<Pos>& pos){
bool ret=false;
for(int i=1;i<=9;i++){
pos.at(0).val=i;
if(isValid(matrix,pos.at(0).x,pos.at(0).y,i)){
matrix.at(pos.at(0).x).at(pos.at(0).y)=i;
ret=backTracking(matrix,pos,1);
if(ret){
break;
}else{
matrix.at(pos.at(0).x).at(pos.at(0).y)=0;
}
}
}
if(ret){
int len=pos.size();
for(int i=0;i<len;i++){
matrix.at(pos.at(i).x).at(pos.at(i).y)
=pos.at(i).val;
}
}
}
};
int main(){
//std::ifstream in("data.txt");
//std::streambuf *cinbackup;
//cinbackup=cin.rdbuf(in.rdbuf());
std::vector<std::vector<int>> matrix;
matrix.resize(9,std::vector<int>());
std::vector<Pos> zero_pos;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
int num;
std::cin>>num;
matrix.at(i).push_back(num);
if(0==num){
zero_pos.push_back(Pos(i,j));
}
}
}
Solution so;
so.findSolution(matrix,zero_pos);
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(8==j){
std::cout<<matrix.at(i).at(j)<<std::endl;
}else{
std::cout<<matrix.at(i).at(j)<<" ";
}
}
}
return 0;
}
數(shù)獨(dú)-Sudoku
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。
相關(guān)閱讀更多精彩內(nèi)容
- 閑來(lái)有了用python解數(shù)獨(dú)的想法,但由于對(duì)復(fù)雜些的算法仍是一竅不通,最終算是用簡(jiǎn)單算法實(shí)現(xiàn)了出來(lái)。 相關(guān)簡(jiǎn)介: ...
- 數(shù)獨(dú)是一種小游戲。規(guī)則是在一個(gè)9*9或者其他型號(hào)的板子上填數(shù)字,必須滿足三個(gè)要求:1.每一個(gè)橫排的9個(gè)空格必須是1...
- 關(guān)于我的 Leetcode 題目解答,代碼前往 Github:https://github.com/chenxia...
- LeetCode上有一道數(shù)獨(dú)題,https://leetcode.com/problems/sudoku-solv...
- 37. 解數(shù)獨(dú) 編寫一個(gè)程序,通過(guò)已填充的空格來(lái)解決數(shù)獨(dú)問(wèn)題。 一個(gè)數(shù)獨(dú)的解法需遵循如下規(guī)則: 數(shù)字 1-9 在每...