Оптимизация алгоритма отслеживания в обратном порядке, решая Судоку

Делайте некоторое распространение ограничений перед каждым недетерминированным шагом .

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

Большинство головоломок судоку для людей являются спроектированы таким образом, что они вообще не нуждаются в возврате.

Некоторое время назад я реализовал Танцующие ссылки Дональда Кнута и его алгоритм X для судоку в Ruby (язык, который, как известно, не слишком эффективен). Для нескольких примеров, которые я проверил, на моем ноутбуке с частотой 1,5 ГГц потребовалось несколько миллисекунд.

Вы можете посмотреть в викпедии, как работают Dancing Links, и самостоятельно адаптировать ее к судоку. Или вы можете взглянуть на «Решатель судоку на Java, реализующий алгоритм танцующих связей Кнута» .

PS: Алгоритм X - это алгоритм поиска с возвратом.

Вы можете посмотреть в викпедии, как работают Dancing Links, и самостоятельно адаптировать ее к судоку. Или вы можете взглянуть на «Решатель судоку на Java, реализующий алгоритм танцующих связей Кнута» .

PS: Алгоритм X - это алгоритм поиска с возвратом.

Вы можете посмотреть в викпедии, как работают Dancing Links, и самостоятельно адаптировать ее к судоку. Или вы можете взглянуть на «Решатель судоку на Java, реализующий алгоритм танцующих связей Кнута» .

PS: Алгоритм X - это алгоритм поиска с возвратом.

Я думаю, что большой оптимизацией было бы сохранение не только состояния доски, но и для каждой строки / столбца / квадрата, если он содержит каждое из чисел 1-9. Теперь, чтобы проверить, может ли позиция иметь число, вам просто нужно проверить, не содержит ли строка / столбец / квадрат, в котором находится позиция, это число (это всего лишь 3 поиска по массиву).

Также большая потеря скорости имеет создавать новый массив для каждого рекурсивного вызова. Вместо этого внесите изменение в массив перед рекурсивным вызовом, а затем отмените его после рекурсивного вызова. В основном добавьте инвариант, что Solve будет менять слоты во время выполнения, но когда он вернется, он оставит его таким, каким он был при вызове функции.

Также каждый раз при возврате решения вы должны проверять, решена ли доска или нет. Если решение не находит решения, оно должно просто вернуть null, если он найдет решение, он должен его вернуть. Таким образом, вы можете быстро проверить, нашел ли ваш рекурсивный вызов решения решение или нет.

Помогает ли размещение числа в квадрате с наименьшим количеством вариантов? Без этого код будет намного проще (вам не нужно сохранять что-либо в связанных списках и т. Д.)

Вот мой псевдокод:

for(square on the board)
      for(possible value)
           if(this square can hold this value){
                place value on the board
                update that this row/col/square now contains this value

                recursive call
                if recursive call succeeded return the value from that call

                update that this row/col/square does not contain this value
                undo placing value on board
           }
if (no empty squares)
    return solved

Вот мой код (я его не тестировал):

public int[][] solve(int[][] board, boolean[][] row, boolean[][] col, boolean[][] square){
    boolean noEmpty = true;
    for(int i = 0; i < 9;i++){
        for(int j = 0; j < 9;j++){
            if(board[i][j] == 0){
                noEmpty = false;
                for(int v = 1; v <= 9; v++){
                    int sq = (i/3)*3+(j/3);
                    if(row[i][v-1] == false && col[j][v-1] == false && square[sq][v-1] == false){
                        board[i][j] = v;
                        row[i][v-1] = true;
                        col[j][v-1] = true;
                        square[sq][v-1] = true;
                        int[][] ans = solve(board,row,col,square);
                        if(ans != null)
                            return ans;
                        square[sq][v-1] = false;
                        col[j][v-1] = false;
                        row[i][v-1] = false;
                        board[i][j] = 9;
                    }
                }
            }
        }
    }
    if(noEmpty){
        int[][] ans = new int[9][9];
        for(int i = 0; i < 9;i++)
            for(int j = 0; j < 9;j++)
                ans[i][j] = board[i][j];
        return ans;
    }else{
        return null;
    }       
}

Вероятно, вам следует использовать профилировщик, чтобы увидеть, какой оператор занимает больше всего времени, а затем подумать о том, как его оптимизировать.

Я предлагаю вам, не используя профилировщик, каждый раз создавая новый PuzzleGenerator с нуля и передавая слоты в качестве аргумента в метод possibleValuesInGrid. Я думаю, это означает, что PuzzleGenerator пересчитывает все заново каждый раз, для каждой позиции и для каждой конфигурации слотов; тогда как вместо этого он мог бы быть [намного] более эффективным, если бы запомнил предыдущие результаты и постепенно изменялся.

Нахождение слота с наименьшей возможными решениями невероятно дорого, а для традиционной головоломки судоку, вероятно, не стоит накладных расходов.

Упрощенная оптимизация состоит в том, чтобы отслеживать количество из каждой цифры, и когда вы «попробуйте» разместить цифру в слот, начните с того, что использовалось наименее (редактировать: убедитесь, что включают те, с высеванными головоломками). Это сделает ваш алгоритм, скорее всего, начнет успешный путь, а не неудачный.

Кроме того, проверьте искусственный интеллект: современный подход , как предложено IMSASU. Это фантастическая книга и охватывает рекурсивные отступления в хорошую деталь.

P.S. Мне любопытно, что касается выработки производительности (если таковые имеются), предоставленные вашим «шагом 1» оптимизацией. У вас есть фигура?

Долгое время я написал Sudoku Solver (несколько лет назад, но я держу весь код, который я пишу). Это не было обобщено, чтобы решить «больший» размер, чем обычный судоку, но это довольно быстро.

Это решает следующее в 103 мс (на сердечке 2 Duo 1,86 ГГц) и действительно не было оптимизировано:

        {0,0,0,0,7,0,9,4,0},
        {0,7,0,0,9,0,0,0,5},
        {3,0,0,0,0,5,0,7,0},
        {0,8,7,4,0,0,1,0,0},
        {4,6,3,0,0,0,0,0,0},
        {0,0,0,0,0,7,0,8,0},
        {8,0,0,7,0,0,0,0,0},
        {7,0,0,0,0,0,0,2,8},
        {0,5,0,2,6,8,0,0,0},            

Как быстро ваше и на какую плату это медленно? Вы уверены, что вы не постоянно пересматриваете путь, который не должен быть пересматриваться?

Вот мясо алгоса:

private static void solveRec( final IPlatform p ) {
    if (p.fullBoardSolved()) {
        solved = p;
        return;
    }
    boolean newWayTaken = false;
    for (int i = 0; i < 9 && !newWayTaken; i++) {
        for (int j = 0; j < 9 && !newWayTaken; j++) {
            if (p.getByteAt(i, j) == 0) {
                newWayTaken = true;
                final Set<Byte> s = p.avail(i / 3, j /3);
                for (Iterator<Byte> it = s.iterator(); it.hasNext();) {
                    final Byte b = it.next();
                    if (!p.columnContains(j, b) && !p.lineContains(i, b)) {
                        final IPlatform ptemp = duplicateChangeOne(p, b, i, j);
                        solveRec(ptemp);
                        if (solved != null) {
                            return;
                        }
                    }
                }
            }
        }
    }
}

и абстракция iPlatform (пожалуйста, будь хорошая, это было написано много лет назад, прежде чем я Знал, что в Java добавляю «я» перед именами интерфейсов был не все ярость):

public interface IPlatform {

    byte getByteAt(int i, int j);

    boolean lineContains(int line, int value);

    boolean columnContains(int column, int value);

    Set<Byte> avail(int i, int j);

    boolean fullBoardSolved();

}

У меня было задание сделать именно это: создать самый быстрый решатель судоку на Java. В итоге я выиграл конкурс со временем 0,3 миллисекунды.

Я не использовал алгоритм танцевальных ссылок и не сравнивал с ним, но некоторые участники, должно быть, пробовали его, а у моего ближайшего конкурента потребовалось около 15 миллисекунд.

Я просто использовал рекурсивный алгоритм поиска с возвратом, дополнил его четырьмя «правилами» (что сделало обратное отслеживание ненужным почти для каждой головоломки) и сохранил битовое поле как список допустимых значений для каждой позиции.

Я написал об этом в блоге и разместил код здесь: http://www.byteauthor.com/2010/08/sudoku-solver/