回溯在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求解似乎是無限循環

回答

相關問題