Оптимизация Судоку Решатель


В настоящее время я работаю на решатель судоку, которые должен уметь решать 25 х 25 сетки. Однако, у меня возникли проблемы с оптимизацией, чтобы бежать достаточно быстро, чтобы действительно получить результат с любой сетки больше, чем 9 х 9. Мне было интересно, если кто-то может взглянуть на мой код и дать мне некоторые идеи о том, как оптимизировать его.

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;
    }
}


1567
4
задан 10 декабря 2011 в 02:12 Источник Поделиться
Комментарии
1 ответ

метод isvalidvalue() является излишне простой – вы проверьте все 9 значений для каждого поля всегда. Вместо этого, попробуйте реализации "карандаш", которые люди используют при решении судоку. Для каждого поле без значения, вы должны явно магазин, какие значения все еще могут быть введены в это поле. (В сказать логическое[строк][перевалы][значение]).

Затем, когда вы делаете большое количество, удалить его как ценность кандидата из других полей в строку/столбец/поле, и добавить его снова, как вы возвратиться из этого попробовать.

Другие методы используют люди также могут быть реализованы в программном обеспечении. После того, как вы отслеживать карандашом, скрытых один должен быть довольно простым. (На самом деле это может быть лучше попробовать что никто до поиска с возвратом.) Вы также можете попробовать ускорить поиск, заполнив квадраты с наименьшими возможными кандидатами во-первых, и цифры, которые вы уже разместили, самый первый. (Я менее уверен, что это поможет решатель программного обеспечения, но они могли выйти на конфликт, который повлечет возвратиться раньше.)

8
ответ дан 10 декабря 2011 в 03:12 Источник Поделиться