回溯——生成数独数组

Question

我想使用回溯生成一个简单的数独生成器。我卡住了/不知道我是否正确使用了回溯。 zahlIstGueltigAufPosition returns 如果数字 zahl 有效（如果 zahl 在 row/column 或 9 个框之一中出现一次).

public static boolean fuelleArray(int y, int x, int zahl){

    sudokuArray[y][x]=zahl;


    if(zahlIstGueltigAufPosition(y,x,zahl)){

        if(x==8 && y<=7 && fuelleArray(y+1,0,1)){
            return true;

        }else if(x==8 && y==8 && fuelleArray(y,x,zahl)) {
            return true;

        }else if(x<=7 && y<=8){
            if(fuelleArray(y,x+1,1)) {
                return true;
            }
       }
    }else{
        if(zahl<9 && x<=8 && y<=8 ){fuelleArray(y,x,zahl+1);}
    }

    return false;
}

程序给出：

 1 2 3 4 5 6 7 8 9
 4 5 6 1 2 3 9 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0

感谢您的帮助

Answer 1

所以这是我的解决方案，有更好的方法可以使用回溯生成数独，比如调用 fuelleArray(fieldIndex, numberInField)。这样，代码中的回溯将更加明显和清晰，您不必像我一样处理行末尾的情况。

public static boolean fuelleArray(int y, int x, int zahl){

    sudokuArray[y][x]=zahl;

    if(zahlIstGueltigAufPosition(y,x,zahl)){
                                       //#1
        if(x==8 && y<=7){              //if you aren't at the end
            if(fuelleArray(y+1,0,1)){  //look if the the next field
                return true;           //is correct
            }
                                       //#2
        }else if(x==8 && y==8){        //if I am at the end 
            return true;               //return true, cause at 
                                       //zahlIstGueltigAufPosition
                                       //we know its correctly plassed               
                                       //by the SudokuRules


        }else if(x<=7 && y<=8){        //Just like #1, but there it
            if(fuelleArray(y,x+1,1)){  //was to handle the end of a 
                return true;           //row

            }
        }
    }

    if(zahl<9 && x<=8 && y<=8 ){      //if we are not correct we
        if(fuelleArray(y,x,zahl+1)){  //increase the number in that
            return true;              //field

        }
    }else {                           //if we are at number 9 we put 
        sudokuArray[y][x]=0;          //put it back to zero
                                      //
    }                                 //
    return false;                     //and return false

}

回溯——生成数独数组

Backtracking - Generate Sudokuarray

java

recursion

backtracking

sudoku

generate