所以我有此程序,應該解決用C 至極一個futoshiki拼圖是由具有此格式的文本文件加載:FutoshikiÇ遞歸求解器
5 0 | 0 | 0 | 0 | 0 - - - - v - - - - 0 > 0 | 0 | 0 | 3 - - - - - - - - - 0 | 0 < 2 | 0 | 0 - - - - v - - - - 0 | 0 | 0 | 0 | 4 ^ - v - - - - - - 0 | 0 | 0 | 0 | 0
其中5是矩陣的大小,以及數字adjcent給運營商<
,>
,^
,v
必須滿足它們所規定的條件,從文件的行中的所有字符都用空格分開 如0 |
... 所以,我已經成功地加載該文件,以檢查它是否滿足數學運算符的條件,但我卡在recu上rsive功能
我想知道些什麼:
我有沒有選擇正確的方式來存儲矩陣或者我應該從邏輯運算符整除的數?
如何在矩陣上執行遞歸擴展,以及如何在特定步驟中跟蹤使用的數字(以防止我必須回溯)?
例如。比方說,我在index[j][j]
到哪j<n
(矩陣的大小),從那裏開始,我將不得不遞減j
(「接觸」),只有數字,並檢查子矩陣滿足條件
這裏就是我管理到目前爲止的代碼。
其中:
char **readmat(int *n);
//從該文件讀取消除
void print(char **mat,int n);
字符之間的空間矩陣//打印所存儲的矩陣
int check(char **mat,int n);
//檢查是否大小的矩陣的項n滿足數學運算符
int expand (char **mat,int n,int i);
//這應該是遞歸函數,它一次獲取一個元素並檢查是否有任何condi重刑得到滿足,如果是的話,增加它的例子
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char **readmat(int *n);
void print(char **mat,int n);
int check(char **mat,int n);
int expand (char **mat,int n,int i);
int main(int argc, char *argv[])
{
char **mat;
int n, j;
mat=readmat(&n);
if(mat == NULL)
return 1;
if(check(mat,n)){
print(mat,n);
}
else if(expand(mat,n,0)==1){
print(mat,n);
}
else {
printf("Nessuna soluzione trovata.\n");
}
for(j=0; j<=n;j++)
free(mat[j]);
free(mat);
system("PAUSE");
return 0;
}
char **readmat(int *n){
FILE *fp;
char *line,nome[100];
int i,j,k;
char **mat;
printf("Inserire il nome del file: ");
scanf("%s",nome);
fp=fopen(nome,"r");
if(fp==NULL){
printf("Errore apertura file");
return NULL;
}
if(fgets(nome,100,fp)==NULL){
printf("Formato file non valido\n");
fclose(fp);
return NULL;
}
if(sscanf(nome,"%d",n)!=1){
printf("Errore nei parametri del file\n");
fclose(fp);
return NULL;
}
(*n)=(((*n)*2)-1);
mat=(char**)malloc((*n)*sizeof(char*));
for(i=0;i<=(*n);i++)
mat[i]=(char*)malloc((*n)*sizeof(char));
line=(char*)malloc(2*(*n)*sizeof(char));
i=0;
while(i<=2*(*n) && fgets(line,2*(*n)+2,fp)!=NULL){
j=0;
k=0;
while(j<=2*(*n)){
if(line[j]!=' '){
mat[i][k]=line[j];
k++;
}
j++;
}
i++;
}
return mat;
//print(mat, (*n));
}
void print(char **mat,int n){
int i=0,j=0;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
printf("%c", mat[i][j]);
}
printf("\n");
}
}
int check(char **mat,int n) {
int i,j;
int k=1;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(mat[i][j]=='<'){
if(mat[i][j-1] >= mat[i][j+1])
k=0;
}
else if(mat[i][j]=='>'){
if(mat[i][j-1] <= mat[i][j+1])
k=0;
}
else if(mat[i][j]=='^'){
if(mat[i-1][j] >= mat[i+1][j])
k=0;
}
else if(mat[i][j]=='v'){
if(mat[i-1][j] <= mat[i+1][j])
k=0;
}
}
}
return k;
}
int expand (char **mat,int n,int i){
int j=i/n;
int k=i%n;
int p;
if(i>=n*n){
return 1;
}
else{
if((mat[j][k]>47)&&(mat[j][k]<58)){
if(mat[j][k]=='0'){
expand(mat,n,i+2);
}
for (p=(mat[j][k]-48); p<(10-(mat[j][k]-48)); p++) {
mat[j][k]=48+p;
if (check(mat,i)) {
if (expand(mat, n, i+2)) {
return 1;
}
}
}
i-=2;
mat[j][k]='0';
}
}
return 0;
}
解決方案:正如你所看到的邏輯條件方面顯然很滿意
0 | 0 | 1 | 0 | 0
- - - - v - - - -
1 > 0 | 0 | 0 | 3
- - - - - - - - -
0 | 0 < 2 | 0 | 0
- - - - v - - - -
0 | 1 | 0 | 0 | 4
^ - v - - - - - -
1 | 0 | 0 | 0 | 0
我會保持號碼和運營商分開。 (我也會保持水平和垂直運算符分離。)畢竟,你只想在解決問題時更新數字,而不是操作員。 – 2012-02-09 13:54:32
您確定您發佈的示例拼圖有解決方案嗎?用手工完成,我從下面第二排繼續得到兩個1。 – Kevin 2012-02-09 14:14:46
@kevin當然是的,你肯定錯過了一些東西。 – 2012-02-09 14:30:10