#include <stdio.h>
#include <stdlib.h>
int count=0;
void print(int a[30][6])
{
count++;
printf("case: %d:\n",count);
for(int i=0;i<30;i++)
for(int j=0;j<6;j++)
{
printf("%d ",a[i][j]);
j==5?printf(" %d\n",i):0;
}
}
//判斷是否可以將第i行、第j列的數設為k
int test(int a[30][6],int i,int j,int k)
{
int p,q;
p=0;
while (p<6){
if(a[i][p]==k)return 0;
else ++p;
}
int num1=1,col=0;
while(col<j){
for(q=0;q<i;q++){
if((a[q][col]==a[i][col]&&a[q][j]==k)||(a[q][col]==k&&a[q][j]==a[i][col]))
++num1;
}
if(num1>2)return 0;
else {
col++;
num1=1;
}
}
return 1;
}
void SD(int a[30][6],int n)//求解
{
int i,j;
int b[30][6];
for(i=0;i<30;i++)
for(j=0;j<6;j++)
b[i][j]=a[i][j]; //用b進行嘗試
i=n/6,j=n%6; //行列
if(n==180){
print(b);
}
if(a[i][j]!=0){
SD(b,n+1);
a[i][j]=0;
}//如果該位置固定
else
{
int k=1; //試數
while(k<=6){
if(test(b,i,j,k)) //可以
{
b[i][j]=k;
SD(b,n+1);
b[i][j]=0;
}
k++;
}
}
}
int main()
{
int a[30][6];
printf("請輸入原始資料，沒有資料用0代替。\n");
for(int i=0;i<30;i++)
for(int j=0;j<6;j++)
scanf("%d",&a[i][j]);
printf("-------------------\n\n");
SD(a,0);
if(count==0)
printf("此陣列無解!");
return 0;
}
uj5u.com熱心網友回復：
運算的時間特別長，希望高手能幫忙出出建議，簡化一下uj5u.com熱心網友回復：
你在SD里邊又呼叫SD，可能這是慢的原因吧。uj5u.com熱心網友回復：
遞回函式建議明確一下退出條件，看到你的if, else里都呼叫了自身。那么SD怎么退出呢？ if(n==180){
print(b);
return; //這樣退出是否符合你的要求，如果符合建議試一下
}
uj5u.com熱心網友回復：
你可以用記憶化搜索試試uj5u.com熱心網友回復：
我想只輸出一個結果，應該怎么跳出遞回呢？
uj5u.com熱心網友回復：
試一下了嗎？
另外，根據你的需求定義跳出的位置呢。你想什么時候就退出了？
uj5u.com熱心網友回復：
我試了，還是很慢
uj5u.com熱心網友回復：
在SD中添加times++，計算執行次數，然后分析演算法復雜度。如果確實無法優化，建議放棄。uj5u.com熱心網友回復：
if(n==180){
//print(b); // print太慢，不要
return;
}
uj5u.com熱心網友回復：
好的，謝謝
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/108739.html
標籤：C語言
上一篇：LNK2019求解答