回溯算法最佳實(shí)踐：解數(shù)獨(dú)

///數(shù)獨(dú)
1.3*3的判斷
2.很多if-------怎么回溯二維棋盤(pán)+有預(yù)設(shè)，不填
3.這個(gè)沒(méi)設(shè)初始值，要設(shè)就加個(gè)輸入給res

#include <iostream> #include<bits/stdc++.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std;#define maxn 10000 int sum=0; int fin =9;int res[maxn][maxn]={0}; ///panduan int isvalid(int m,int n,int num) {for(int i=1;i<=fin;i++)///列內(nèi)是否重復(fù) {if(res[m][i]==num){return 0;}}for(int i=1;i<=fin;i++){if(res[i][n]==num){return 0;}}for(int i=1;i<=fin;i++)///3*3方格 {///3*3非常惡心，但也有意思 if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)這個(gè)是0，0開(kāi)始的，下面是1，1開(kāi)始的 if(res[ ((m-1)/3)*3 + (i-1)/3 + 1 ][ ((n-1)/3)*3 +(i-1)%3 +1 ]==num){return 0;}}return 1;}void backtrack(int m,int n) {if(m==fin&&n>fin){for(int i=1;i<=fin;i++){for(int j=1;j<=fin;j++){cout<<res[i][j]<<" ";}cout<<endl;}sum++;cout<<"sum="<<sum;cout<<endl;return ;}if(n>fin)///一行填完，下一行 {backtrack(m+1,0);return ;}if(res[m][n]!=0)///有預(yù)設(shè)，不填 {backtrack(m,n+1);return ;}for(int i=1;i<=fin;i++){if(!isvalid(m,n,i)){continue;}res[m][n]=i;backtrack(m,n+1);res[m][n]=0; }} int main(int argc, char** argv) {res[3][3]=1; backtrack(1,1);return 0; }

2021.3.9復(fù)習(xí)

重點(diǎn)在于怎么遍歷（換行）

第28-33行非常重要，不是硬置，而是開(kāi)新遍歷

另外跳過(guò)已知條件，應(yīng)放在遍歷可行解之前，并在if內(nèi)遞歸

只找一個(gè)可行解的話(huà)：可以利用return true 找到可行解直接結(jié)束，具體看gitbook

中間有if判斷，阻斷繼續(xù)遍歷，很重要

#include <iostream> #include<bits/stdc++.h> using namespace std; typedef long long ll; #define maxn 1000005 int res[10][10]; int isvalid(int x,y,a) {} int neednum(int x,y) {} int fin=9;///重點(diǎn)在于怎么遍歷（換行）void traceback() {if(x>fin){//存儲(chǔ)或輸出return ;}if(y>fin){ // y=1; // x+=1; ///非常重要，不是硬置，而是開(kāi)新遍歷traceback(x+1,1);}if(res[x][y]!=0)///有數(shù)了,跳過(guò)的應(yīng)該放在遍歷之前{traceback(x,y+1);}for(int i=1;i<=fin;i++){//if(neednum(x,y)&&!isvalid(x,y,a))continue;//////這里寫(xiě)的也有問(wèn)題，那碰上不能填的，就直接完結(jié)了///跳過(guò)的應(yīng)該放在遍歷之前if(!isvalid(x,y,a))continue;res[x][y]=i;traceback(x,y+1);///重點(diǎn)res[x][y]=0;}}///另外只找一個(gè)可行解，可以利用return true 找到可行解直接結(jié)束，具體看gitbook ///（中間有if判斷，阻斷繼續(xù)遍歷，很重要）int main() {return 0; }

總結(jié)

以上是生活随笔為你收集整理的回溯算法-解数独的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。