Sudoku Solver-Optimierung

  • Ich arbeite gerade an einem Sudoku-Solver, der ein 25 x 25-Gitter lösen kann. Ich habe jedoch Probleme mit der Optimierung, um schnell genug zu laufen, um tatsächlich ein Ergebnis mit einem Raster größer als 9 x 9 zu erzielen. Ich habe mich gefragt, ob jemand meinen Code betrachten und mir ein paar Ideen zur Optimierung geben kann.

     public class SudokuGrid {
        private String[][] grid;
    
        /**
         * Constructs an empty 9x9 Sudoku Grid.
         */
        public SudokuGrid() {
            this(16);
        }
    
        /**
         * Constructs an empty, square Sudoku grid.
         * @param boardSize the length of each row & column
         */
        public SudokuGrid(int gridSize) {
            this.grid = new String[gridSize][gridSize];
            for (int r = 0; r < this.grid.length; r++) {
                for (int c = 0; c < this.grid.length; c++) {
                    this.grid[r][c] = "-";
                }
            }
        }
    
        /**
         * Constructs a partially filled Sudoku grid.
         * @param str the contents of the grid (using '-' for blank)
         */
        public SudokuGrid(String str) {
            String[] contents = str.split("\\s+");
            int gridSize = (int)Math.sqrt(contents.length);
    
            this.grid = new String[gridSize][gridSize];
            for (int i = 0; i < contents.length; i++) {
                this.grid[i/gridSize][i%gridSize] = contents[i];
            }
        }
    
        /**
         * Fills the Sudoku grid with numbers using recursive backtracking.
         * @return whether the grid was successfully filled
         */
    
        public boolean fillGrid(){
            return fillGrid(0,0);
        }
    
        private boolean fillGrid(int row, int col){
            if (col >= this.grid.length) {
                col = 0;
                if (++row >= this.grid.length)
                    return true;
            }
            if (!this.grid[row][col].equals("-")){
                return fillGrid(row , col + 1);
            }
            for (int i = 1; i <= this.grid.length; i++) {
                String temp = ""+i;
                if (isValidValue(row, col, temp)) {
                    this.grid[row][col] = temp;
                    if (fillGrid(row, col + 1)){
                        return true;
                    }
                }
            }
            grid[row][col] = "-";
            return false;
        }
    
    
        private boolean isValidValue(int row, int col, String val) {
            for (int i = 0; i < this.grid.length; i++){
                if (val.equals(this.grid[i][col])){
                    return false;
                }
            }
    
            for (int j = 0; j < this.grid.length; j++){
                if (val.equals(this.grid[row][j])){
                    return false;
                }
            }
    
            double squareRootVal = Math.sqrt(this.grid.length);
            int rowOffset = (row / (int)squareRootVal) * (int)squareRootVal;
            int colOffset = (col / (int)squareRootVal) * (int)squareRootVal;
            for (int i = 0; i < squareRootVal; i++) {
                for (int j = 0; j < squareRootVal; j++){
                    if (val.equals(this.grid[rowOffset + i][colOffset + j])){
                        return false;
                    }
                }
            }
            return true;
        }
    
        /**
         * Constructs a String representation of the grid.
         * @return the grid in a displayable row/column format
         */
        @Override
        public String toString() {
            String output = "";
            for (int r = 0; r < this.grid.length; r++) {
                for (int c = 0; c < this.grid.length; c++) {
                    output += grid[r][c] + " ";
                }
                if (r < this.grid.length-1) {
                    output += "\n";
                }
            }
            return output;
        }
    }
     
    27 May 2015
    Jamal
1 answer
  • isValidValue() ist unnötig einfach - Sie prüfen immer alle 9 Werte für jedes Feld. Versuchen Sie stattdessen, "Bleistiftzeichen" zu implementieren, die Menschen beim Lösen von Sudoku verwenden. Für jedes Feld ohne Wert sollten Sie explizit speichern, welche Werte noch in dieses Feld eingegeben werden können. (Sagen Sie in a boolean[rows][cols][value].).

    Wenn Sie eine Zahl platzieren, entfernen Sie sie als Kandidatenwert aus den anderen Feldern in der Zeile / Spalte / Feld und fügen Sie hinzu Wenn Sie aus diesem Versuch zurückkehren, können Sie es erneut ausführen.

    Andere Techniken, die von Menschen verwendet werden, können auch in Software implementiert werden. Wenn Sie Bleistiftmarken nachverfolgt haben, sollte Hidden Single recht unkompliziert sein. (In der Tat ist es vielleicht besser, dies vor einer Backtracking-Suche zu versuchen.) Sie können auch versuchen, die Suche zu beschleunigen, indem Sie zuerst die Felder mit den wenigsten möglichen Kandidaten ausfüllen und die Ziffern ausprobieren, die Sie bereits zuerst platziert haben . (Ich bin weniger sicher, dass diese einem Softwarelöser helfen werden, aber es könnte zu einem Konflikt kommen, der früher zu einem Backtrack führt.)

    10 December 2011
    millimoose