Futoshiki C 递归求解器

Question

所以我有这个程序应该解决 C 中的 futoshiki 难题 wich 从具有以下格式的文本文件加载：

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 是矩阵的大小，以及与运算符 <、>、 相邻的数字^, v 必须满足它们强加的条件，从文件中所有行上的字符都被空格分隔 例如 0 |... 所以我设法加载文件，检查它是否满足数学运算符条件，但我陷入了递归函数

我想知道的是：

我是否选择了正确的方式来存储矩阵或我' ve 应该将数字与逻辑运算符相除吗？

如何对矩阵执行递归扩展以及如何跟踪某个步骤中使用的数字（以防我必须回溯）？

例如。假设我到达 index[j][j] 其中 j （矩阵大小），从那里开始我必须递减 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); //这应该是递归函数一次获取一个元素并检查是否满足任何条件，如果满足，则递增

#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

Answer 1

存储矩阵的方式应该不会太重要。你可以随心所欲地存储它，只要你能方便地获取/设置每个点的数值，并评估操作人员是否满意。

广泛地说，您可以通过使用如下算法来解决此类问题：

//returns true if this function solved the puzzle, false otherwise.
//gameData will be changed to the solved form of the puzzle if a solution exists, or remain unchanged if no solution exists.
//(so, whatever language you're using, ensure gameData is passed by reference here)
bool solve(gameData){
    if (!isValid(gameData)){return false;}  //oops, puzzle is unsolvable!
    if (isComplete(gameData)){return true;} //puzzle is already solved; no further modification needed.

    //choose a spot on the game board that hasn't been filled in yet.
    int x;
    int y;
    getEmptySpot(gameData, &x, &y);

    //iterate through all the possible values that could go into the empty spot.
    //you don't need anything fancy here to generate legal values for i;
    //if you accidentally supply an invalid value, then isValid()
    //will notice in the next solve() call.
    for (int i = 1; i <= 5; i++){
        //try putting i in the empty spot.
        setValue(gameData, x, y, i);
        if (solve(gameData)){ //putting i in the spot led to a solution!
            return true;
        }
    }
    //didn't find a solution :(
    //return gameData to its original state.
    setValue(gameData, x, y, 0);
    return false;
}

该算法进行强力递归搜索，尝试每个点的每个可能值，如果进入非法状态则回溯。在最坏的情况下，它以指数时间运行，但实际上，开始时的 isValid() 调用会短路任何明显不可行的分支，因此对于 5x5 来说它应该相当快地完成输入。

isValid、isComplete、getEmptySpot 和 setValue 的实现将取决于您定义 gameData 的方式。

isValid 应该检查游戏数据是否处于非法状态 - 在您的情况下，它应该检查所有大于比较是否正确，并检查每个数字是否只出现一次每行和每列。这些检查应该忽略值为 0 的点，因为它们只是一个占位符，意思是“尚未填写”。

isComplete 应检查是否没有任何位置带有“尚未填写”占位符。 (isValid(gameData) && isComplete(gameData)) 意味着 gameData 已解决。

getEmptySpot 应该找到尚未填充的位置。如果您担心速度，它应该找到可以合法输入的数值最少的位置。这将大大减少搜索树的宽度。

最后，setValue 应该将给定点设置为给定值。

Answer 2

我会

1. 删除矩阵大小。很明显，通过读取矩阵本身
2. 删除管道和其他字符，只留下空格
3. 在矩阵后面添加运算符，在特殊的“编码”格式中，
4. 单个函数可以采用规则并尝试求解矩阵

矩阵示例：

0 0 0 0 0
0 0 0 0 3
0 0 2 0 0
0 0 0 0 4
0 0 0 0 0 
--
1,3>2,3
2,1>2,2
3,2<3,3
3,3>4,3
4,1<5,1
4,2>5,2

在<之后code>-- 启动规则，含义很明确（至少对我来说）：
第 1 行、第 3 列的值必须大于第 2 行、第 3 列的值

。等等。

关于求解器，我将按如下方式开始：

1. 在矩阵中搜索是否存在涉及 2 必须大于的单元格的规则另一个细胞。如果是，您可以立即在整个矩阵的另一个单元格重复点 1 中插入 1
2. ，这样您将得到一个新的、部分求解的矩阵作为起始点
3. 与上面的 4 相同，规则为“小于” 。您可以在相关单元格中输入 5
4. 现在搜索是否有一行（或一列）填充了 4 个数字。如果是这样，第五个数字就很明显了。

完成上述步骤后，您将获得部分（如果幸运的话可能是完全）求解的矩阵，然后您必须编写一个核心函数来尝试每种组合，但考虑动态规则（文件中的规则）和静态规则（那些制作游戏的人）。