得到這個矩陣後，經過簡單的隨機挖空，一道數獨題目就隨機生成了。
ps：我把這些隨機生成的題目塞回解數獨器求解，發現解法並不唯一，若要解法唯一則效率 ...
程式人生>>1.數獨題目生成程式（搜尋演算法）
1.數獨題目生成程式（搜尋演算法）
阿新••發佈：2019-02-16
前幾天在玩數獨遊戲的時候，產生了一個大膽的想法：
數獨app上的題目都是現成的，乾脆自己寫一個可以隨機生成數獨的程式算了
一、需求提出：
1.隨機生成數獨題目，要求該題目有解；
2.當填數違反數獨操作（填到題目原本的數字去了，填數違規等）時，禁止操作，彈出提示;
3.當81格都填滿時，判斷對錯;
二、需求分析
總：
需求2,3相對簡單，尤其是需求3，都禁止違規操作了，填滿81格不就贏了嗎？也許是當初沒有給自己再次組織語言的機會，提出了這麼傻缺的需求，核心問題就是需求1。
需求1
首先得到一個9*9，符合數獨規則的矩陣，然後隨機挖空不就行了嗎？所以需求1的問題轉化為如何得到一個隨機9*9數獨矩陣。
第一個想出來的方法是用搜索演算法，在每一個格子隨機生成1-9的數字，然後判斷符不符合規則，再下一個。
這個演算法的缺點是效率感人，81個格子，每個格子的數字都要判斷，每個格子的數字還都是隨機生成的，效率能不感人嗎？
優點是還沒付諸行動就被否定了，給程式編寫省下了不少時間
第二個想法就相對可靠了，先在隨機在若干個格子上生成隨機數（這些隨機數也要符合數獨規則），這樣就變成了一道題目，然後讓電腦用搜索演算法求解，只要能解出一種，就停止解題，並且選取這種解答作為隨機9*9數獨矩陣以及本題的答案。
解不出也沒有關係重新生成隨機數再重新解過就得了。
這個方法可行度很高，優點很多，其中最重要的優點是我在刷藍橋杯時曾經寫過一個解數獨的程式
經過除錯，我把隨機數個數設定在了15，既不會因為太少而使得隨機數在矩陣上分佈不均勻，又保證不會因為數字太多，答案太少而影響生成效率。
得到這個矩陣後，經過簡單的隨機挖空，一道數獨題目就隨機生成了。
ps：我把這些隨機生成的題目塞回解數獨器求解，發現解法並不唯一，若要解法唯一則效率低下。
在除錯後把挖空個數控制在了46~51個。
使得挖空不會太少，影響遊戲性；挖空不會太多，讓題目有成千上萬種解
經過n（n>=30）次測試，在挖空46個的情況下，求解法個數m
199的情況則瓜分了剩下的10%
雖然達不到只有一個解的嚴格標準，但是，嗯，解比較少，也還湊合吧
需求2
我採取三位數輸入的方法
百位是橫標，十位是豎標，個位是填數，除個位外不得含9，個位不得為0，判斷方法直接用解數獨器現成的就行了
輸入999表示棄權
程式執行結果：
開始
操作
棄權：
四.程式碼：
#include
#include
#include
#include
#definebig7//大方格邊界顏色
#definemid2//中方格邊界顏色
#definesmall8//小方格邊界顏色
#definecol2//題目原資料顏色
intflag=1,total=0;
voidgotoxy(intx,inty){
++x,++y;
COORDpos;//表示一個字元在控制檯螢幕上的座標
pos.X=x;
pos.Y=y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),pos);//是API中定位游標位置的函式。
}//游標控制模組
voidcolor(intb){
HANDLEhConsole=GetStdHandle((STD_OUTPUT_HANDLE));
SetConsoleTextAttribute(hConsole,b);//顏色控制
}//顏色控制模組
voidBoundary(){
gotoxy(3,1);
color(big);
printf("+---+---+---+---+---+---+---+---+---+");
color(small);
for(inti=1;i<10;++i){
color(small);
gotoxy(3,i*2+1);
if(i==3||i==6){
color(mid);
}
printf("+---+---+---+---+---+---+---+---+---+");
for(intj=0;j<10;++j){
gotoxy(3+j*4,i*2);
if(j==3||j==6){
color(mid);
}
if(j==0||j==9){
color(big);
}
printf("|");
color(7);
gotoxy(3+j*4,i*2+1);
if(i%3!=0||j%3!=0){
color(small);
}
if(j==0||j==9){
color(big);
}
if((i%3==0||j%3==0)&&j!=0&&j!=9){
color(mid);
}
printf("+");
color(small);
}
}
color(big);
gotoxy(3,19);
printf("+---+---+---+---+---+---+---+---+---+");
color(7);
gotoxy(60,1);
printf("數獨遊戲");
gotoxy(45,3);
printf("哈蒙森軟體工業公司1875年出品");
gotoxy(45,5);
printf("解法:0種");
gotoxy(45,7);
printf("操作中輸入'678',表示對6行8列標記為8;輸入'999'表示放棄遊戲");
for(inti=0;i<9;++i){
gotoxy(4*i+5,0);
printf("%d",i);
gotoxy(4*i+5,20);
printf("%d",i);
gotoxy(1,2*i+2);
printf("%d",i);
gotoxy(41,2*i+2);
printf("%d",i);
}
}
boolFlag(intm,intn,intb,intboard[9][9]){
inta[9];
for(inti=0;i<9;++i){
if(board[i][m]==b){
returnfalse;
}
if(board[n][i]==b){
returnfalse;
}
}
for(inti=0;i<9;++i){
a[i]=0;
}
a[0]=b;
gotoxy(50,15);
intq=(n/3)*3,p=(m/3)*3,r=1;
for(inti=p;i0&&board[j][i]<10){
a[r]=board[j][i];++r;
}
}
}
for(inti=0;i<9;++i){
for(intj=i+1;j<9;++j){
if(a[i]==a[j]&&i!=j&&a[i]!=0){
returnfalse;
}
}
}
returntrue;
}
voidSudoku(intboard[9][9]){
time_tseed;
srand(time(&seed));
intnumber=15,p=0,q=0,i=0;
while(i1){
return0;
}
}
return1;
}
intJudge(intx,inty,intn,intboard[9][9]){
intt=0;
for(inti=0;i<9;++i){
if(board[y][i]==n){
++t;
if(t>1){
return1;
}
}
}
t=0;
for(inti=0;i<9;++i){
if(board[i][x]==n){
++t;
if(t>1){
return1;
}
}
}
intnu,m;
if(bfs(1+(x/3)*3,1+(y/3)*3,n,board)==0){
return1;
}
}
voidShow(intinput,intboard[9][9],intsudoku[9][9][2]){//30<=input<=55
time_tseed;
srand(time(&seed));
inti=0;
color(col);
for(inti=0;i<9;++i){
for(intj=0;j<9;++j){
gotoxy(5+j*4,i*2+2);
printf("");
board[i][j]=0;
}
}
while(i9){
for(inti=1;i<=9;++i){
board[y][x]=i;
intk=Judge(x,y,i,board);
if(k==0){
Sel(x+1,y,kind,board,sudoku,total);
}
board[y][x]=0;
}
}else{
Sel(x+1,y,kind,board,sudoku,total);
}
}else{
Sel(0,y+1,kind,board,sudoku,total);
}
}else{
++total;
flag=0;
if(kind==0){
for(inti=0;i<9;++i){
for(intj=0;j<9;++j){
sudoku[i][j][0]=board[i][j];
}
}
}
}
}
intmain(){
intboard[9][9],sudoku[9][9][2];
intleve,op,input=35;
for(inti=0;i<9;++i){
for(intj=0;j<9;++j){
board[i][j];
sudoku[i][j][1]=0;
}
}
Boundary();
while(input>34&&input<56){
total=0,flag=1;
while(total==0){
Sudoku(board);
Sel(0,0,0,board,sudoku,total);
gotoxy(50,22);
}//生成符合數獨規則的矩陣
Show(input,board,sudoku);//隨機挖空
Sel(0,0,1,board,sudoku,total);
gotoxy(45,5);
color(7);
printf("解法:%d種",total-1);
gotoxy(54,9);
intkey=1;
while(key==1){
inth=0;
gotoxy(45,9);
printf("操作輸入3位數:");
scanf("%d",&op);
gotoxy(5+(op/100%10)*4,(op/10%10)*2+2);
if(sudoku[op/10%10][op/100%10][1]==0&&op%10!=0&&op<999&&op/10%10!=9&&op/100%10!=9){
board[op/10%10][op/100%10]=0;
if(Flag(op/100%10,op/10%10,op%10,board)==true){
board[op/10%10][op/100%10]=op%10;
gotoxy(5+(op/100%10)*4,(op/10%10)*2+2);
printf("%d",op%10);
for(inti=0;i<9;++i){
for(intj=0;j<9;++j){
if(board[i][j]!=0){
++h;
}
}
}
if(h==81){
key=0;
gotoxy(45,9);
printf("你贏了！");
Sleep(3000);
}
}else{
color(12);
gotoxy(45,11);
printf("輸入錯誤！");
Sleep(500);
}
}else{
if(op<999){
color(7);
gotoxy(45,11);
printf("操作非法！");
Sleep(500);
}
}
if(op==999){
key=0;
gotoxy(45,9);
printf("你輸了！現在顯示其中一種解法！");
for(inti=0;i<9;++i){
for(intj=0;j<9;++j){
if(sudoku[i][j][1]==0){
Sleep(100);
gotoxy(5+j*4,i*2+2);
printf("%d",sudoku[i][j][0]);
}
board[i][j]=0;
sudoku[i][j][0]=0;
sudoku[i][j][1]=0;
}
}
}
color(7);
gotoxy(45,9);
printf("操作:");
gotoxy(45,11);
printf("");
}
gotoxy(45,11);
printf("輸入35~55之間的數字開始新遊戲，或按其他鍵退出：");
scanf("%d",&input);
gotoxy(45,11);
printf("");
}
gotoxy(0,20);
return0;
}
ubuntu如何強制關閉qq和啟動qq
«上一篇
jquery中刪除元素detach()和remove()不同之處下一篇»
相關推薦
1.數獨題目生成程式（搜尋演算法）
前幾天在玩數獨遊戲的時候，產生了一個大膽的想法：
數獨app上的題目都是現成的，乾脆自己寫一個可以隨機生成數獨的程式算了
...
有一組數字，從1到n，從中減少了3個數，順序也被打亂，放在一個n-3的數組裡,請找出丟失的數字，最好能有程式，最好演算法比較快
staticvoidMain()
{
GetRemoveNumbe...
有一組數字，從1到n，從中減少了3個數，順序也被打亂，放在一個n-3的數組裡,請找出丟失的數字，最好能有程式，最好演算法比較快...
staticvoidMain()
...
N數碼問題的啟發式搜尋演算法--A*演算法python實現
一、啟發式搜尋：A演算法
1）評價函式的一般形式:f(n)=g(n)+h(n)
g(n):從S0到Sn的實際代價(搜尋的橫向因子)
h(n):從...
啟發式搜尋演算法求解八數碼問題（C）
下午看一個遊戲的演算法時看了一下啟發式搜尋演算法，心血來潮跑了一遍很久很久以前寫八數碼的程式（C語言），發現各種問題，後來...
運動目標跟蹤（一）--搜尋演算法預測模型之KF,EKF,UKF
這裡先總體介紹下，原文轉自：
任何感測器，鐳射也好，視覺也好，整個SLAM系統也好，要解決的問題只有一個：如何通過資料來估...
個人作業1——四則運算題目生成程序（基於控制臺）
debniobodymin此外listevespani++一、需求分析
生成四則運算題目
控制生成題目個...
第1次作業------四則運算題目生成程序（基於控制臺）
參數clstab信息panreport範圍gpo式表https://git.coding.net/YelC...
個人作業1——四則運算題目生成程序
pos要求數量需求markarray不為log運算表達式一、題目描述
1.隨機生成指定數量的不重復的四則運...
個人作業1——四則運算題目生成程序（基於安卓）
基於istviewgui已提交mdiepp實現自動生成一周一、題目描述：
實踐能力的提高當然...
搜尋
基礎教學
Mysql入門
Sql入門
Android入門
Docker入門
Go語言入門
Ruby程式入門
Python入門
Python進階
Django入門
Python爬蟲入門
最近訪問
1.數獨題目生成程式（搜尋演算法）
oracle使用regexp_substr函式將字串拆分成集合
影象識別與處理之Opencv——高斯濾波GaussianBlur()+++11月2日暫存
一個簡單的ftp+get檔案以及put檔案
802.11中的幀間間隔（SIFS/PIFS/DIFS）
servlet的使用講解
PHP讀取csv檔案的內容詳解
【C語言】輸入任意多個整數的小技巧
列舉的單例構造方法
linux下的CSV檔案操作
