1

(免責事項:SOにはおそらく20の異なるバージョンのこの質問がありますが、それらのほとんどを読んでもまだ私の問題は解決していません)

こんにちは、(比較的) 初心者のプログラマーです。そこで、未完成のパズルを埋める数独バックトラッカーを作ろうとしました。1〜3行が完全に空の場合(つまり、0で埋められた場合)でも完全に機能するようですが、より多くのボックスが空になり始めると(具体的には、数字で書くのをやめた4行目の7〜8列あたり)、私はスタック オーバーフロー エラーを取得します。コードは次のとおりです。

import java.util.ArrayList;
import java.util.HashSet;

public class Sudoku
{
    public static int[][] puzzle = new int[9][9];
    public static int filledIn = 0;
    public static ArrayList<Integer> blankBoxes = new ArrayList<Integer>(); 
    public static int currentIndex = 0;
    public static int runs = 0;

    /**
     * Main method.
     */
    public static void main(String args[])
    {

        //Manual input of the numbers
        int[] completedNumbers = {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,3,4,
                8,9,1,2,3,4,5,6,7,
                3,4,5,6,7,8,9,1,2,
                6,7,8,9,1,2,3,4,5,
                9,1,2,3,4,5,6,7,8};


        //Adds the numbers manually to the puzzle array
        ArrayList<Integer> completeArray = new ArrayList<>();
        for(Integer number : completedNumbers) {
            completeArray.add(number);
        }
        int counter = 0;
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                puzzle[i][j] = completeArray.get(counter);
                counter++;
            }
        }

        //Adds all the blank boxes to an ArrayList.
        //The index is stored as 10*i + j, which can be retrieved
        // via modulo and integer division.
        boolean containsEmpty = false;
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(puzzle[i][j] == 0) {
                    blankBoxes.add(10*i + j);
                    containsEmpty = true;
                }
            }
        }
        filler(blankBoxes.get(currentIndex));
    }

    /**
     * A general method for testing whether an array contains a
     * duplicate, via a (relatively inefficient) sort.
     * @param testArray The int[] that is being tested for duplicates
     * @return True if there are NO duplicate, false if there
     * are ANY duplicates.
     */

    public static boolean checkDupl(int[] testArray) {
        for(int i = 0; i < 8; i++) {
            int num = testArray[i];
            for(int j = i + 1; j < 9; j++) {
                if(num == testArray[j] && num != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * If the puzzle is not full, the filler will be run. The filler is my attempt at a backtracker.
     * It stores every (i,j) for which puzzle[i][j] == 0. It then adds 1 to it's value. If the value
     * is already somewhere else, it adds another 1. If it is 9, and that's already there, it loops to 
     * 0, and the index beforehand is rechecked.
     */
    public static void filler(int indexOfBlank) {
        //If the current index is equal to the size of blankBoxes, meaning that we
        //went through every index of blankBoxes, meaning the puzzle is full and correct.
        runs++;
        if(currentIndex == blankBoxes.size()) {
            System.out.println("The puzzle is full!" + "\n");
            for(int i = 0; i < 9; i++) {
                System.out.println();
                for(int j = 0; j < 9; j++) {
                    System.out.print(puzzle[i][j]);                 
                }
            }
            System.out.println("\n" + "The filler method was run " + runs + " times");
            return;
        }

        //Assuming the puzzle isn't full, find the row/column of the blankBoxes index.
        int row = blankBoxes.get(currentIndex) / 10;
        int column = blankBoxes.get(currentIndex) % 10;
        //Adds one to the value of that box.
        puzzle[row][column] =  (puzzle[row][column] + 1);

        //Just used as a breakpoint for a debugger.
        if(row == 4 && column == 4){
            int x  = 0;
        }

        //If the value is 10, meaning it went through all the possible values:
        if(puzzle[row][column] == 10) {
            //Do filler() on the previous box
            puzzle[row][column] = 0;
            currentIndex--;
            filler(currentIndex);
        }
        //If the number is 1-9, but there are duplicates:
        else if(!(checkSingleRow(row) && checkSingleColumn(column) && checkSingleBox(row, column))) {
            //Do filler() on the same box.
            filler(currentIndex);
        }
        //If the number is 1-9, and there is no duplicate:
        else {
            currentIndex++;
            filler(currentIndex);
        }       
    }

    /**
     * Used to check if a single row has any duplicates or not. This is called by the 
     * filler method.
     * @param row
     * @return
     */
    public static boolean checkSingleRow(int row) {
        return checkDupl(puzzle[row]);
    }

    /**
     * Used to check if a single column has any duplicates or not. 
     * filler method, as well as the checkColumns of the checker.
     * @param column
     * @return
     */
    public static boolean checkSingleColumn(int column) {
        int[] singleColumn = new int[9];
        for(int i = 0; i < 9; i++) {
            singleColumn[i] = puzzle[i][column];
        }
        return checkDupl(singleColumn);         
    }

    public static boolean checkSingleBox(int row, int column) {
        //Makes row and column be the first row and the first column of the box in which
        //this specific cell appears. So, for example, the box at puzzle[3][7] will iterate
        //through a box from rows 3-6 and columns 6-9 (exclusive).
        row = (row / 3) * 3;
        column = (column / 3) * 3;

        //Iterates through the box
        int[] newBox = new int[9];
        int counter = 0;
        for(int i = row; i < row + 3; i++) {
            for(int j = row; j < row + 3; j++) {
                newBox[counter] = puzzle[i][j];
                counter++;
            }
        }
        return checkDupl(newBox);
    }
}

なぜ私はそれを奇妙なエラーと呼んでいるのですか? いくつかの理由:

  1. エラーが発生するボックスはランダムに変化します(ボックスを与えるか取るか)。
  2. エラーが発生する実際のコード行はランダムに変化します (通常はフィラー メソッドで発生するようですが、それはおそらくそれが最大のものだからです。
  3. コンパイラが異なれば、ボックスごとに異なるエラーが発生します (おそらく 1 に関連しています)。

私が想定しているのは、非効率的なコードを書いただけなので、実際の無限再帰ではありませんが、スタック オーバーフロー エラーを呼び出すには十分です。しかし、明白な問題を見ている人がいれば、私はそれを聞きたい. ありがとう!

4

1 に答える 1

1

あなたのコードはバックトラックしていません。バックトラッキングは、失敗時に戻ることを意味します。

 if(puzzle[row][column] == 10) {
        puzzle[row][column] = 0;
        currentIndex--;
        filler(currentIndex);// but every fail you go deeper
    }

次のようなものが必要です。

public boolean backtrack(int currentIndex) {
    if (NoBlankBoxes())
        return true;
    for (int i = 1; i <= 9; ++i) {
        if (NoDuplicates()) {
            puzzle[row][column] = i;
            ++currentIndex;
            if (backtrack(currentIndex) == true) {
                return true;
            }
            puzzle[row][column] = 0;
        }
    }
    return false;
}
于 2013-09-01T05:38:15.540 に答える