回溯在nonogram求解似乎是无限循环

我试着写Ønonogram求解器在Java中学校的功课。它适用于除一个之外的所有提供的输入。我的代码是在github https://github.com/farkadav/Nonogram-solver 回溯在nonogram求解似乎是无限循环

在CSPSolver我解决nonogram。我对所有能排/给出其在GitHub上的文本文件，然后我检查弧一致性，然后我试着通过回溯找到解决办法的约束的cols组合。我也有输出它应该看起来如何解决。当我尝试解决dino.txt时，我的回溯函数似乎进入了解决第11行和第15列的无限循环。这是该方法的代码。

public void backtracking(){ 

    if(orderedVars.isEmpty()){ 

     String[] solString = new String[rowDim]; 
     for(Line line : rowSolution){ 

      solString[line.position] = new String(); 
      for(int j=0; j<colDim; j++){ 
       solString[line.position] +=line.value[j]; 
      } 

     } 
     String solution = new String(); 
     for(String sol : solString){ 
      solution += sol +"\n"; 
     } 
     solutions.add(solution); 
     return; 
    } 
    CSPVariable cspVar = orderedVars.poll(); 


    for(char[] var : cspVar.storage){ 
     if(consistent(var,cspVar)){ 

      if(cspVar.Row){     
       rowSolution[helpX++] = new Line(var,cspVar.position,cspVar.Row);      
       backtracking(); 
       rowSolution[--helpX] = null; 
      } else{ 
       colSolution[helpY++] = new Line(var,cspVar.position,cspVar.Row);      
       backtracking(); 
       colSolution[--helpY] = null; 
      } 
     } 
    } 
    orderedVars.add(cspVar); 

}

我不知道究竟是什么原因导致它，任何帮助将不胜感激。如果有什么不清楚的地方是链接到作业http://cw.fel.cvut.cz/wiki/courses/a4b33zui/task2-malovane-krizovky-en

来源

2017-04-08 lobito

调用backtracking（）中间操纵helpX和helpY看起来有问题。如果从算法的定义中没有必要尝试以这种方式重新排序，那么在调用backtracking（）之前修改这样的helpX和helpY。

来源

2017-04-08 16:12:12 Kriegel

恐怕有必要从算法的定义。但是，我可能是错的我不是csp的大师。无论如何......无论如何我都试过了，它使整个程序崩溃。谢谢你的建议：） – lobito

回溯在nonogram求解似乎是无限循环

回答

相关问题