1

I am building a Sudoku solver that use the Try and Fail technique to solve any problem. My algorithm is:

1)Update (method that remove any possible value that already given as a final value to element in the same Row, column or squar)

2)Get the minimum element that has minimum number of possible values

3)start solve assuming the first possible value is the final value

4)save the current sate into a stack

5)Try to solve

5-a)If solved, return

5-b)if not solved and with invalid Sudoku, then Pop previous state

6)Repeat step 3) for all possible vaues (9)

7)Repeat step 2) until the puzzel is solved

This is my code 

Stack<Element[][]> myStack= new Stack<>();
private Element[][] mySudoku;
public void solve(){
        update();//remove all final values from all possible values for each element
        if(isSudokuSolved(mySudoku)){
                return;
        }
        //find a cell that is not confirmed and has the minimal candidates
        int celli=-1,cellj=-1, p=10;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(mySudoku[i][j].getValue()==0){
                        if(mySudoku[i][j].getPossibleValues().size()<p){
                                celli=i;
                                cellj=j;
                                p=mySudoku[i][j].getPossibleValues().size();
                        }
                }
            }
        }

        try {
            for (int c = 0; c < mySudoku[celli][cellj].getPossibleValues().size() - 1; c++) {
                //save state  
                Element[][] copy=deepCopy(mySudoku);//copy the current state
                myStack.push(copy);
                //apply candidate to cell
                mySudoku[celli][cellj].setValue(mySudoku[celli][cellj].getPossibleValues().get(c));
                update();//check is solved
                if(checkValidInputSudoku(mySudoku)){
                    solve();
                }else{
                   try {
                        mySudoku = myStack.pop();
                    } catch (EmptyStackException est) {
                        //do nothing
                    } 
                }

            }
        } catch (Exception e) {

        }

        //if we have reached here then we are at the last possible value for the candidates so confirm candidate in cell
        if(celli!=-1 && cellj!=-1 && p!=10) {//Some problems happen here "out of Boundry -1 Error"
            mySudoku[celli][cellj].setValue(mySudoku[celli][cellj].getPossibleValues().get(mySudoku[celli][cellj].getPossibleValues().size()-1));
        }
}//end of solve method

I have spent more than 6 hours trying to find out the problem. I have checked for the Update() method, deepCopy() method and checkValidInputSudoku() method. They all works fine. Thank you in Advance

4

1 回答 1

1

我可以在您的代码中看到一个问题。你有一个循环正在锯掉它所在的分支：

for(int c = 0; c < mySudoku[celli][cellj].getPossibleValues().size() - 1; c++) {
    ...
    mySudoku[celli][cellj].setValue(mySudoku[celli]cellj].getPossibleValues().get(c));
    ...
}

除此之外，您缺少其中一个值，它应该是for(c=0; c!=size; ++c)，即不是size - 1。此外，仅调用一次 getPossibleValues() 将使该代码更具可读性。最后，捕获和忽略堆栈下溢只是愚蠢的，因为据我所知，它隐藏了算法中的错误。如果你不知道如何处理错误，不要只是让它沉默。由于 java 需要你去捕捉它，所以把它放在最外面的地方，或者至少 abort 或者做一些事情，但不要忽略它！

还有一件事：您正在通过mySodokuand递归和传递上下文数据myStack。这完全忽略了递归点（或者至少是它通常使用的方式），因为函数调用堆栈是您唯一需要的堆栈。使用这些来传递参数只会使事情变得比必要的更复杂。相反，该函数应返回部分数独谜题并返回完全解决的谜题或 null。Using 比你现在使用的异常更容易区分，这是一种常规和预期的事情，并不是真正的异常。然后，当尝试不同的选择时，您依次将单元格设置为值并递归，直到调用不返回 null。如果没有任何选项返回解决方案，则清除单元格并自己返回 null。

solve(sodoku):
    if sodoku is solved:
        return true
    if sodoku is invalid:
        return false

    c = some empty cell
    for v in 1...9:
        // set to a value and recurse
        c = v
        if solve(sodoku):
            // found a solution
            return true
    // no solution found, clear cell and return failure
    c = null
    return false

顺便说一句：这种策略称为“回溯”。使用具有最少可能值的单元格称为“修剪”，它允许您从搜索树中切断整个分支。实际上确定可能的值也有助于避免一些徒劳的尝试。

于 2013-04-30T20:33:57.130 回答