Оптимизация алгоритма обратного отслеживания решений Sudoku

Ответ 1

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

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

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

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

Ответ 2

долгое время я написал решение Sudoku (несколько лет назад, но я сохраняю весь код, который пишу). Он не был обобщен для решения "большего" размера, чем обычный судоку, но он довольно быстро.

Он решает следующее в 103 мс (на Core 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();

}

Ответ 3

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

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

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

Ответ 4

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

Вы можете посмотреть на wikpedia, как работают Dancing Links, и адаптировать его к Sudoku самостоятельно. Или вы посмотрите на "Судоку Solver в Java, реализующий алгоритм Knuths Dancing Links" .

PS: Алгоритм X является алгоритмом обратного слежения.

Ответ 5

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

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

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

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

Вот мой код psuedo:

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

Ответ 6

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

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

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

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

Ответ 7

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

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

Ответ 8

Ниже приведены результаты моей оптимизации алгоритма обратного слежения для судоку. Вы можете загрузить код из http://yikes.com/~bear/suds.c. Это чисто основано на принципе ямы голубя, и я нашел его, как правило, быстрее, чем решение, основанное на правилах.

Используя значения из другого сообщения в этом потоке, я получаю результат 7ms на core2 duo @2.2 ghz или 3ms на ядре i5. Это сопоставимо с результатом плаката 100 мс, хотя это, возможно, было измерено по-другому. Сроки добавлены в http://yikes.com/~bear/suds2.c.

Я написал это 10 лет назад и, безусловно, буду оптимизироваться по-другому, если бы я повторно сделал эту проблему.

$ ./a.out 000070940070090005300005070087400100463000000000007080800700000700000028050268000
[----------------------- Input  Data ------------------------]

*,*,*   *,7,*   9,4,*   
*,7,*   *,9,*   *,*,5   
3,*,*   *,*,5   *,7,*   

*,8,7   4,*,*   1,*,*   
4,6,3   *,*,*   *,*,*   
*,*,*   *,*,7   *,8,*   

8,*,*   7,*,*   *,*,*   
7,*,*   *,*,*   *,2,8   
*,5,*   2,6,8   *,*,*   

[------------------ Solution 01 -------------------]

2,1,5   8,7,6   9,4,3   
6,7,8   3,9,4   2,1,5   
3,4,9   1,2,5   8,7,6   

5,8,7   4,3,2   1,6,9   
4,6,3   9,8,1   7,5,2   
1,9,2   6,5,7   3,8,4   

8,2,6   7,4,3   5,9,1   
7,3,4   5,1,9   6,2,8   
9,5,1   2,6,8   4,3,7   

Time: 0.003s Cyles: 8619081 

Ответ 9

Недавно я написал программу на Python, которая может решить головоломку Sudoku. Это в основном алгоритм обратного отслеживания, который перетаскивает поисковое пространство. Я опубликовал более подробную информацию о фактическом алгоритме в этом потоке.

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

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

Затем я сел и попытался придумать разные методы для вышеупомянутых двух вариантов. Вот что я придумал.

Следующая пустая ячейка может быть выбрана следующими способами:

• A - первая ячейка слева направо, сверху вниз
• B - первая ячейка справа налево, снизу вверх
• C - случайно выбранная ячейка
• D - ближайшая ячейка к центру сетки
• E - ячейка, которая в настоящее время имеет наименьшее количество доступных вариантов (выбор здесь означает цифру от 1 до 9)
• F - ячейка, которая в настоящее время имеет большинство доступных вариантов
• G - ячейка, у которой есть наименьшие пустые связанные ячейки (связанные ячейки является одним из того же ряда, из того же столбца или из того же 3x3 квадрант)
• H - ячейка, которая имеет самые пустые связанные ячейки.
• я - ячейка, ближайшая ко всем заполненным ячейкам (измеренная от центр ячейки указывает на центральную точку ячейки)
• J - ячейка, наиболее удаленная от всех заполненных ячеек.
• K - ячейка, чьи связанные пустые ячейки имеют наименьшее количество доступных выбор
• L - ячейка, чьи связанные пустые ячейки имеют наиболее доступную выбор

И следующую цифру можно выбрать следующими способами:

• 0 - самая низкая цифра
• 1 - наивысшая цифра
• 2 - случайно выбранная цифра
• 3 - эвристически, наименее используемая цифра по доске
• 4 - эвристически, самая используемая цифра по доске
• 5 - цифра, которая приведет к тому, что связанные пустые ячейки будут иметь наименьший количество доступных вариантов
• 6 - цифра, которая приведет к тому, что связанные пустые ячейки будут иметь наибольшее значение количество доступных вариантов
• 7 - цифра, которая является наименее распространенным доступным выбором среди связанных пустые ячейки
• 8 - цифра, которая является наиболее распространенным пустые ячейки
• 9 - цифра, которая является наименее общим доступным выбором в доска
• a - цифра, которая является наиболее распространенным доска

Итак, я запрограммировал вышеуказанные методы в программе. Предыдущие цифры и буквы могут быть переданы в качестве параметров программе, и он будет использовать соответствующий метод оптимизации. Что еще, потому что иногда две и более ячейки могут иметь одинаковый балл, есть возможность предоставить второй параметр сортировки. Например, параметр "EC" означает выбор случайной ячейки из всех ячеек, у которых есть наименьшее количество доступных вариантов.

Первая функция будет присваивать весам, умноженным на 1000, а вторая функция добавит новые веса, умноженные на 1. Таким образом, если, например, из первой функции три ячейки имеют одинаковый вес, например. 3000, 3000 3000, то вторая функция добавит свои собственные веса. например 3111, 3256, 3025. Сортировка всегда будет выбирать самый низкий вес. И если требуется противоположное, то весовые функции вызывают с -1000 amd -1, но сортировка по-прежнему выбирает самый низкий вес.

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

Имея вышеизложенное, я решил запустить программу с любой возможной комбинацией параметров и посмотреть, что происходит, какие из них работают лучше всего - в основном для грубой силы грубой силы:) Существует 12 методов выбора ячеек и 11 методов для выбора цифр, поэтому теоретически существует 17,424 комбинаций, но я удалил некоторые ненужные (например, "AA", "BB" и т.д., а также исключил случайные методы, поскольку все они ужасно неэффективны), поэтому число из комбинаций в конце было 12 100. Каждый прогон был выполнен на той же головоломке Sudoku, которая проста:

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

... и поисковое пространство - 36 691 771 392. Это просто простой продукт из числа вариантов для каждой пустой ячейки данной головоломки. Это преувеличение, потому что, как только заполняется одна ячейка, это уменьшает количество вариантов для других ячеек, но это самый быстрый и легкий счет, который я мог бы придумать.

Я написал короткий script (в Python, конечно), который автоматизировал весь процесс тестирования - он запускал решатель для каждого набора параметров, записывал время завершения и выгружал все в файл. Кроме того, я решил выполнить 20 прогонов, потому что я получал 0 раз от функции time.time() для одиночных прогонов. А также, если какая-либо комбинация заняла более 10 секунд, script остановится и перейдет к следующему.

script завершен в 13:04:31 часов на ноутбуке с Intel Core i7-4712MQ 2,30 ГГц, использовалось не более 2 из 8 ядер, а средняя загрузка процессора составляла около 12%. 8 652 из 12 100 комбинаций, выполненных менее чем за 10 секунд.

И победители: (* цифры скорректированы назад для одиночного времени выполнения/итераций)

1) Самое быстрое время 1,55 мс: "A0" и "A1" с 84 итерациями и 46 повторениями итераций и "B0", "B01", "B1", "B10", "BA01", "BA1", "BD01", "BD1" и "BD10" с 65 итерациями и 27 итерациями обратного хода Самые быстрые методы - самые простые, такие как A, B и D. Другой метод не появляется до позиции 308 позиции, а это "E0".

2) Наименьшие итерации 38 и 0 итераций обратного следа: Неожиданно было достигнуто множество способов, самыми быстрыми из которых были "B17", "B6", "B7", "BA16", "BA60", "BA7", "BD17" и "BD70" со временем 2,3 мс и самыми медленными являются "IK91", "JK91", "KI91", "KJ91", "KJ9a", "IK9a", "JK9a" и "KI9a" со временем около 107 мс. Также удивительно, что способ F имеет здесь несколько хороших позиций, таких как "FB6" с 7 мс (?)

В целом A, B, D, E, G и K, как представляется, выполняются значительно лучше, чем C, F, H и L, а я и J находятся между ними. Кроме того, выбор цифры, казалось, не имеет большого значения.

И, наконец, посмотрим, как эти методы-победители обрабатывают самую сложную в мире головоломку Sudoku, как утверждается в этой статье http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html * Имея в виду, что алгоритмы не универсальны, возможно, некоторые алгоритмы лучше подходят для некоторых головоломок Судоку, но не для других... Головоломка:

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

... и поисковое пространство составляет 95,865,912,019,648,512 x 10 ^ 20.

Победителем является "A0" , заканчивающийся в 1092 мс с 49,559 итерациями и 49 498 итерациями с возвратом. Большинство других не очень хорошо. "A0" , "A1", "B0", "B01", "B1", "B10", "BA01", "BA1", "BD01", "BD1" и "BD10" закончились примерно 2500 мс и 91k итераций, а остальные 30+ секунд, итераций 400k +.

Но этого недостаточно, поэтому я провел полный тест всех параметров для самого сложного судоку. На этот раз сделать один прогон не 20, а также время отсечки 2,5 секунды. script завершено в 8:23:30. 149 из 12 100 комбинаций, выполненных менее чем за 2,5 секунды. Победителями в обеих категориях являются "E36", "E37", "EA36" и "EA37" со временем 109 мс, 362 итерации и 301 итерации обратного следа. Кроме того, на первых 38 позициях преобладало начало "E".

В целом E вершины диаграмм, без сомнения, просто просмотрев итоговую таблицу. A, B, я и J имеют несколько ранжировок, но ничего особенного, а остальные даже не сделали это менее чем за 2,5 секунды.

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

Надеюсь, что это поможет:)