歡迎吹毛求疵?? QQ：1423173783??? 郵箱：1423173783@qq.com

這個代碼是我做事時腦中突然遞歸到這里，才貼出來的。我認(rèn)為有必要把調(diào)試遇到的錯誤的特例貼出來。?? 代碼沒做啥美觀修飾，抱歉，本來就是遞歸到這

我想馬上，返回那里還有一些問題沒解決。?

#include <iostream>
#include <cstdlib>
#include <ctime>
#include<time.h>
#include<cstdlib>
#define? K?? 4
using namespace std;
int table[K*K][K*K];
void shuffle(int arr[])
{
??? int tmp, rd;
??? for(int i = 0; i < K*K; i++)
?{
??????? rd = rand() % (K*K);
??????? tmp = arr[rd];
??????? arr[rd] = arr[i];
??????? arr[i] = tmp;
??? }
}
bool test(int x, int y, int v)
{
???
??? int _x = x / K * K;
??? int _y = y / K * K;
?//測試3 * 3矩陣內(nèi)是否有重復(fù)的數(shù)
??? for(int i = _x; i <=x-1; i++)
??????? for(int j = _y; j <= _y + K-1; j++)
??????????? if(table[i][j] == v)?? return false;
??? //測試橫向、縱向是否有重復(fù)的數(shù)
??? for(int j = 0; j <=y-1; j++)
??????? if(table[x][j] == v )????? return false;
??? for(int i=0;i<=x-1;i++)
??if(table[i][y]==v) return (false);
??? return true;
}
int main()
{
??? long time1=clock();
?int b[K*K];
?for(int i=0;i<=K*K-1;i++)
??b[i]=i+1;
?//int num=0;
?//do
?//{
?for(int i=0;i<=K*K-1;i++)
??table[0][i]=i+1;
??? srand((unsigned int)time(NULL));
??? shuffle(table[0]);
??? for (int x=1;x<=K*K-1;x++)????????????????? //這是核心? 這兩個for循環(huán)中的代碼是實踐調(diào)試改出來的，調(diào)試圖片下面會附上
???? {
??? for (int y=0;y<=K*K-1;y++)
??????? {
???????????? int i;
??? shuffle(b);
???????????? for( i=0;i<=K*K-1;i++)
??? {
???????????????? if(test(x,y,b[i]))
???? { table[x][y]=b[i];? break;}
??? }
??????????? if(i==K*K && y>0)
???{
????for(int m=0;m<=y-1;m++)
???????? table[x][m]=0;
????y=-1;
????if(x>=2)
????{
?????for(int i=0;i<=K*K-1;i++)
??????table[x-1][i]=0;
?????x-=2;
?????break;
????}
???}
???else if(i==K*K && y==0)
???{
????for(int i=0;i<=K*K-1;i++)
?????table[x-1][i]=0;
????x-=2;
????break;
???}
?????? }
??? }
?/*for(int i=0;i<=8;i++)
??for(int j=0;j<=8;j++)
???table[i][j]=0;*/
?//num++;
?//}while(num<1000);
??? for(int x=0;x<=K*K-1;x++)
?{
??????? for(int y = 0; y <=K*K-1; y++)
??????????? cout << table[x][y] << " ";
??????? cout << endl;
??? }
?time1=clock()-time1;
?cout<<"use time "<<time1/1000<<"s"<<time1%1000<<"ms"<<endl;
??? system("pause");
}

?

?

?

?

//這個算法生成的的是一系列本質(zhì)一樣的終盤，其實只生成一個，

//???? 代碼后面舉兩個生成的終盤

#include <stdio.h>???????????????????????????????????????????????????????????????????????????????????????????????????????????????
#include<cstdlib>
#include<time.h>
//using namespace std;
int Initial(int i, int j, int start);
int b[9]={1,2,3,4,5,6,7,8,9};
int data[9][9];
int line[9][9], column[9][9], block[9][9],data1[9][9];
void shuffle(int arr[])
{
??? int tmp, rd;
??? for(int i = 0; i <=8 ; i++)
?{
??????? rd = rand() % 9;
??????? tmp = arr[rd];
??????? arr[rd] = arr[i];
??????? arr[i] = tmp;
??? }
}

int main()
{
??? int i, j;
?long time1;
?? /* for (i = 0; i < 9; i++)
??????? for (j = 0; j< 9; j++)
??????? {
??????????? data[i][j] = 0;??????????? //數(shù)獨陣線初始化為零
??????????? line[i][j] = 0;??????????? //行標(biāo)記數(shù)組初始化
??????????? column[i][j] = 0;??????? //列標(biāo)記數(shù)組初始化
??????????? block[i][j] = 0;??????? //塊標(biāo)記數(shù)組初始化
??????? }*/
??? time1=clock();
?srand(time(0));
?shuffle(b);
??? Initial(0, 0, 8);??????????????? //賦值函數(shù)
?printf("%ums\n",clock()-time1);
??? for (i = 0; i < 9; i++)??????????? //打印數(shù)獨陣
??? {
??????? for (j = 0; j < 9; j++)
??????????? printf("%i ", data[i][j]);
??????? printf("\n");
??? }
??? system("pause");
?return 0;
}

int Initial(int i, int j, int start)
{
??? int k;
??? for (k = start;k>=0;k--)??????? //從1至9依次試驗
??? {
??????? if (!line[i][b[k]-1] && !column[j][b[k]-1] && !block[i/3*3+j/3][b[k]-1])
??????? {
??????????? data[i][j] = b[k];
???data1[i][j]=k;
??????????? line[i][b[k]-1] = 1;
??????????? column[j][b[k]-1] = 1;
??????????? block[i/3*3+j/3][b[k]-1] = 1;

??????????? if (i == 8 && j == 8)??????? //初始化完畢退出
??????????????? return 1;

??????????? if (j == 8)??????????????????? //定位下一位置???????????????????
??????????? {
??????????????? j = 0;
??????????????? i++;
??????????? }
??????????? else
??????????????? j++;
??????????? Initial(i, j, 8);??????????? //初始化下一位置
??????????? return 1;
??????? }
???????
??????? if (k == 0)??????????????????????? //1至9均無合適值，回溯
??????? {
??????????? do
??????????? {
??????????????? if (j == 0)??????????????? //定位前一位置
??????????????? {
??????????????????? j = 8;
??????????????????? i--;
??????????????? }
??????????????? else
??????????????????? j--;
??????????????? line[i][data[i][j]-1] = 0;
??????????????? column[j][data[i][j]-1] = 0;
??????????????? block[i/3*3+j/3][data[i][j]-1] = 0;
??????????? }while (data[i][j] == b[0]);

??????????? //回溯到一可以繼續(xù)的位置,從這一位置開始遞歸賦值
??????????? Initial(i, j, data1[i][j] -1);
??????????? return 1;??????????????????? //遞歸結(jié)束返回后立即退出
??????? }
??? }
?? // return 1;
}

?

?

?

?

下面是另一種生成器，時間復(fù)雜度不如上面兩種算法。

?

#include <iostream>
#include <cstdlib>
#include <ctime>
#include<time.h>
#include<cstdlib>
#define? K?? 3
using namespace std;
int table[K*K][K*K];
void shuffle(int arr[],int m,int n)//小標(biāo)為m--小標(biāo)為n打亂順序
{
??? int tmp, rd;
??? for(int i =m ; i <=n; i++)
?{
??????? rd = m+rand() % (n-m+1);
??????? tmp = arr[rd];
??????? arr[rd] = arr[i];
??????? arr[i] = tmp;
??? }
}
bool test(int x, int y, int v)
{
???
??? int _x = x / K * K;
??? int _y = y / K * K;
?//測試3 * 3矩陣內(nèi)是否有重復(fù)的數(shù)
??? for(int i = _x; i <=x-1; i++)
??????? for(int j = _y; j <= _y + K-1; j++)
??????????? if(table[i][j] == v)?? return false;
??? //測試橫向、縱向是否有重復(fù)的數(shù)
??? for(int j = 0; j <=y-1; j++)
??????? if(table[x][j] == v )????? return false;
??? for(int i=0;i<=x-1;i++)
??if(table[i][y]==v) return (false);
??? return true;
}
int check(int y,int x,int *mark)? //求probable[y][x]
{
?int i,j,is,js,count=0;
?for(i=1;i<=K*K;++i)
? mark[i]=0;
?for(i=0;i<K*K;++i)
? mark[table[y][i]]=1;
?for(i=0;i<K*K;++i)
? mark[table[i][x]]=1;
?is=y/K*K;
?js=x/K*K;
?for(i=0;i<K;++i)
?{
? for(j=0;j<K;++j)
?? mark[table[is+i][js+j]]=1;
?}
?for(i=1;i<=K*K;++i)
? if(mark[i]==0)
? {? count++; mark[i]=i;}
? else mark[i]=0;
? shuffle(mark,1,K*K);
?return count;
}
int main()
{
??? long time1=clock();
?int b[K*K+1];
?for(int i=0;i<=K*K-1;i++)
??table[0][i]=i+1;
??? srand((unsigned int)time(NULL));
??? shuffle(table[0],0,K*K-1);
??? for (int x=1;x<=K*K-1;x++)
???? {
??? for (int y=0;y<=K*K-1;y++)
??????? {
???????????? int i;
???????????? check(x,y,b);
??? for( i=1;i<=K*K;i++)
??? {
???????????????? if(b[i]!=0)
???? { table[x][y]=b[i];? break;}
??? }
??????????? if(i==K*K+1 && y>0)
???{
????for(int m=0;m<=y-1;m++)
???????? table[x][m]=0;
????y=-1;
????if(x>=2)
????{
?????for(int i=0;i<=K*K-1;i++)
??????table[x-1][i]=0;
?????x-=2;
?????break;
????}
???}
???else if(i==K*K+1 && y==0)
???{
????for(int i=0;i<=K*K-1;i++)
?????table[x-1][i]=0;
????x-=2;
????break;
???}
?????? }
??? }
??? for(int x=0;x<=K*K-1;x++)
?{
??????? for(int y = 0; y <=K*K-1; y++)
??????????? cout << table[x][y] << " ";
??????? cout << endl;
??? }
?time1=clock()-time1;
?cout<<"use time "<<time1/1000<<"s"<<time1%1000<<"ms"<<endl;
??? system("pause");
}

?

?

?

?

?

?

下面也是一種思路，不過耗時太長

?

?

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include<time.h>
#include<cstdlib>
using namespace std;
int sudoku[9][9],avail[9]={1,2,3,4,5,6,7,8,9};//定義數(shù)獨數(shù)組和可選數(shù)字?jǐn)?shù)組
void remove(int t[],int);//聲明移除前置函數(shù)
void restore(void);//聲明重置函數(shù)
void print(void);//聲明打印數(shù)獨函數(shù)
void init(void);//聲明初始化函數(shù)
int search(int t[],int);//聲明搜索下標(biāo)函數(shù)
int en=9;//可選avail下標(biāo)
void init() //初始化
{
??? int x,y;
??? srand(time(NULL));
??? for (y=0;y<=8;y++)
???? {
?????? for (x=0;x<=8;x++)
??????? {
????????? sudoku[y][x]=0;
??????? }
???? }//初始化數(shù)組
}
void remove(int t[],int n) //n為下標(biāo)，移除排除下標(biāo)，項前移
{
??? int i;
??? for (i=n;i<=7;i++)
???? {
?????? t[i]=t[i+1];
???? }
??? en--;//可選數(shù)字在原有基礎(chǔ)上減
}
int search(int t[],int n) //n為搜索的數(shù)字，返回下標(biāo)，如果沒有則返回-1
{
??? int i;
??? for (i=0;i<=en-1;i++)
??? if (t[i]==n)
?????? return i;
??? return -1;
}
void restore() //初始化en,avail
{
?? int i;
?? en=9;
?? for (i=0;i<=8;i++)
???? avail[i]=i+1;
}
void print(void)
{
?? int i,j;
?? for (i=0;i<=8;i++)
??? {
????? for (j=0;j<=8;j++)
?????? {
????????? cout << sudoku[i][j] << " ";
?????? }
???? cout << endl;
??? }
}
int main()
{
??? int x=0,y=0;
??? int kill;//已存在的數(shù)的小標(biāo)
??? long time;
??? time=clock();
??? init();
??? cout << "正在生成一個數(shù)獨..." << endl;
??? //restore();
??? for (y=0;y<=8;y++)
??? {
???? for (x=0;x<=8;x++)
??????? {
???????????????????????????????
???????????? int i,j;
???????????? for (i=0;i<=x;i++)//排除橫行
????????????????? {
??????????????????????? kill=search(avail,sudoku[y][i]);
??????????????????????? if (kill!=-1)
???????????????????????????? remove(avail,kill);
?????????????????? }
?????????????? for (i=0;i<=y;i++)//排除縱行
????????????????? {
??????????????????????? kill=search(avail,sudoku[i][x]);
??????????????????????? if (kill!=-1)
??????????????????????????? remove(avail,kill);
?????????????????? }
????????????? for (i=0;i<=2;i++) //排除九宮
????????????????? {
?????????????????????? for (j=0;j<=2;j++)
???????????????????????????? {
???????????????????????????????? kill=search(avail,sudoku[(y/3)*3+i][(x/3)*3+j]);
???????????????????????????????? if (kill!=-1)
???????????????????????????????????? remove(avail,kill);
????????????????????????????? }
??????????????????? }
??????????? if (en==0 && y>0) //排除無解
?????????????? {
?????????????????? y-=2;
?????????????????? break;
?????????????? }
?????????? else if (en==0 && y==0)
?????????????? {
??????????????????? init();
??????????????????? y=-1;
??????????????????? break;
??????????????? }
???????????? sudoku[y][x]=avail[rand()%en];
???????????? restore();
?????? }
???? restore();
??? }
print();//打印數(shù)獨
time=clock()-time;
cout<<"時間"<<time/1000<<"秒"<<time%1000<<"毫秒"<<endl;
system("pause");
}

?

?

總結(jié)

以上是生活随笔為你收集整理的数独终盘生成器（调试成果）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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