数独板生成器有时会出现在 StackOverflow 中

Question

我正在使用 Java 创建一个数独板，但有时它最终会出现在 StackOverflow 中。这是因为我的程序效率低下吗？

import java.lang.Math;
import java.lang.Thread;

public class CreateBoard {
    int[][] intAnswerBoard = new int[9][9];
    int[][] intPlayingBoard = new int[9][9];
    int intRuns = 0;
    int K; // Number of digits to remove

    public CreateBoard(String s, int K) {
        this.K = K;
        populateBoard();
    }

    public void populateBoard() {
        for (int i = 0; i < intAnswerBoard.length; i++) {
            for (int j = 0; j < intAnswerBoard[i].length; j++) {
                intAnswerBoard[i][j] = 0;
            }
        }
        createBoard(0, 0, (int) (Math.random() * 9) + 1, 1, 0);
        // System.out.println(toString());
        // System.out.println(intRuns);
        removeKDigits();
        // System.out.println("After removing " + K + " digits:");
        // System.out.println(toString());
    }

    public void removeKDigits() {
        int count = K;
        
        intPlayingBoard = intAnswerBoard.clone();
        while (count > 0) {
            int i = (int) (Math.random() * 9);
            int j = (int) (Math.random() * 9);
            if (intAnswerBoard[i][j] != 0) {
                intAnswerBoard[i][j] = 0;
                count--;
            }
        }
    }
    
    public boolean createBoard(int i, int j, int intR, int counter, int sum) {
        intRuns++;
        try{
            if(i==8&&j==8) {
                System.out.println(i);
                System.out.println(j);
            }
            Thread.sleep(10);
            // Check if this number is found in the row or column
            for (int k = 0; k < 9; k++) {
                if (intAnswerBoard[i][k] == intR) {
                    if (counter == 9) {
                        intAnswerBoard[i][j] = 0;
                        if(j==0) {
                            return createBoard(i-1, 8, intR, counter, sum);
                        } else {
                            return createBoard(i, j - 1, intR, counter, sum);
                        }
                    } else {
                        // Number already exists in the row
                        if((intR+1) > 9) {
                            return createBoard(i, j, 1, counter, sum);
                        } else {
                            return createBoard(i, j, intR+1, counter, sum);
                        }
                    }
                }
            }
            for(int k=0; k<9; k++) {
                if(intAnswerBoard[k][j] == intR) {
                    // Number already exists in the column
                    if (counter == 9) {
                        intAnswerBoard[i][j] = 0;
                        if(j==0) {
                            return createBoard(i-1, 8, intR, counter, sum);
                        } else {
                            return createBoard(i, j - 1, intR, counter, sum);
                        }
                        
                    } else {
                        if((intR+1) > 9) {
                            return createBoard(i, j, 1, counter+1, sum);
                        } else {
                            return createBoard(i, j, intR+1, counter+1, sum);
                        }
                    }
                }
            }
            
            // Check 3x3 matrix
            if (!check3x3Matrix(i, j, intR)) {
                if (counter == 9) {
                    intAnswerBoard[i][j] = 0;
                    if(j==0) {
                        return createBoard(i-1, 8, intR, counter, sum);
                    } else {
                        return createBoard(i, j - 1, intR, counter, sum);
                    }
                } else {
                    if((intR+1) > 9) {
                        return createBoard(i, j, 1, counter+1, sum);
                    } else {
                        return createBoard(i, j, intR+1, counter+1, sum);
                    }
                }
            }
        
            // The number can be inserted in the current position
            intAnswerBoard[i][j] = intR;
        
            if (j == 8) {
                // Move to the next row and start from the first column
                return createBoard(i + 1, 0, (int)(Math.random() * 9) + 1, 1, 0);
            } else if (i == 8 && j == 8) {
                // Board is filled successfully
                return true;
            } else {
                // Move to the next column in the same row
                return createBoard(i, j + 1, (int)(Math.random() * 9) + 1, 1, sum+intR);
            }
        }catch (Exception e) {
           
            // catching the exception
            System.out.println(e);
            return false;
        }
    }
    
    private boolean check3x3Matrix(int i, int j, int intR) {
        int startRow = i - i % 3;
        int startCol = j - j % 3;

        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {
                if (intAnswerBoard[startRow + row][startCol + col] == intR) {
                    return false; // Number already exists in the 3x3 matrix
                }
            }
        }
        return true; // Number can be inserted in the 3x3 matrix
    }
    
    @Override
   public String toString() {
       String strOutput = "";
       
        strOutput += "    ";
        for(int i=0; i<9; i++){
            if(i%3 == 0 && i!=0) {
                strOutput += "  ";
            }
            strOutput += (i+1) + " ";
        }
        strOutput += "\n   ";
        for(int i=0; i<12; i++){
            strOutput += "--";
        }
        strOutput += "\n";
        for (int i = 0; i < intAnswerBoard.length; i++) {
            
            if((i)%3 == 0 && i!=0) {
                strOutput += "    ";
                for(int k=0; k<21; k++){
                    strOutput += "-";
                }
                strOutput += "\n" + (i+1) + " | ";
            } else {
                strOutput += (i+1) + " | ";
            }
            
            
            for (int j = 0; j < intAnswerBoard[i].length; j++) {
                if((j)%3 == 0 && j!=0) {
                    strOutput += "| ";
                }
                strOutput += (intAnswerBoard[i][j] == 0 ? "●" : intAnswerBoard[i][j])  + " ";
            }
            strOutput += " |\n";
        }
        strOutput += "   ";
        for(int i=0; i<12; i++){
            strOutput += "--";
        }
        
        return strOutput;
   }

}

大多数情况下，板都会生成，但是需要很长时间，有时会遇到 StackOverflow 才能生成。我尝试添加 10 毫秒的延迟来防止这种情况，但没有成功。

Answer 1

你的代码效率很低。生成数独板时，尝试更改结构以遵循明显的模式。