Зачем решать судоку?
Разработка корпоративных приложений – это, по большей части, решение одного из этих типов проблем:
- “Позвольте мне создавать, читать, обновлять и удалять эти вещи”
- “Выполняйте эту же задачу с как можно большим количеством вещей, как можно быстрее”
- “Как лучше всего распределить ресурсы, которые у меня есть для выполнения этих задач, если все, что выполняет задачу X, не может быть использовано для выполнения задачи Y?”
Этот последний тип задач представляет собой задачу раскрашивания графа , и природа их такова, что решение одной из них во многом совпадает с решением другой.
Судоку – один из таких типов задач, но у него очень простые правила, так что это хорошая игровая площадка, чтобы попробовать различные способы решения задач раскрашивания графов. В этом посте описывается решение с использованием программирования ограничений с помощью chocolate solver .
Что такое программирование ограничений?
Программирование с ограничениями – это парадигма программирования, которая может показаться немного необычной при первом обращении к ней, поскольку она полностью отличается от императивного программирования.
Короче говоря: вы сообщаете программе, какую проблему необходимо решить, но не как решить эту проблему.
Что это означает в практическом плане, так это:
- Сначала вы определяете свои переменные.
- Это мои задачи
- Это мои работники
- Затем вы определяете домены, в которых существуют эти переменные. Например:
- Эта переменная должна иметь значение 3
- Эта переменная может иметь любое значение от 1 до 42
- Эта переменная представляет собой набор от 4 до 10 чисел, которые все взяты из домена, работающего от 1 до 99.
- Затем вы определяете ограничения для этих переменных, например:
- Если одна переменная имеет значение, то другая переменная должна иметь другое значение.
- Одна переменная должна быть суммой/max/min нескольких других переменных.
- Один набор должен быть дополнением к другому набору.
- Если вы ищете какое-либо решение, то вам конец. Если вы ищете наилучшее решение, то вам необходимо определить набор переменных затрат, которые вы стремитесь минимизировать или максимизировать. Например:
- Найдите решение, которое минимизирует переменную “стоимость ведения бизнеса”.
- Найдите решение, которое максимизирует переменную “сколько сообщений передается”.
- Наконец, вы предоставляете это фреймворку для решения, и он будет использовать различные подходы ИИ для поиска решений определенной вами проблемы.
Решение судоку в Choco Solver
Итак, чтобы сделать эти идеи более конкретными, мы будем использовать их для решения простой проблемы.
Для этого примера мы выберем самую сложную в мире задачу судоку , вы можете найти полный пример этого в Sudoku.java
Если вы не знаете Судоку , правила таковы:
- Сетка представляет собой площадь квадратов размером 9 Х 9.
- Каждый квадрат должен содержать одно число от 1 до 9.
- Одно и то же число не может появиться в одной строке дважды.
- Одно и то же число не может появиться в одном столбце дважды.
- Сетка разбита на 9 отдельных подсетей по 9 квадратов в каждой. Одно и то же число не может появиться в одной и той же подсети дважды.
Это оно. Если вам интересно, какое это имеет отношение к использованию ресурсов, вы можете представить, что цифры представляют доступные каналы в вышке сотовой связи, а квадраты представляют сообщения, которые необходимо отправить. Решение этой проблемы подскажет вам, как вы могли бы отправлять эти сообщения равномерно распределенным образом, не вызывая какой-либо конкуренции за ресурсы на каналах.
Начало работы с Choco Solver
Полный код для этого доступен здесь: Sudoku
Прежде чем мы сделаем что-нибудь еще, мы должны сначала создать пустую модель для игры, это так же просто, как:
Model model = new Model("sudoku");
В этой модели создаются новые переменные, ограничения и оптимизации.
Определение переменных и доменов
Для задачи судоку существует 81 переменная, по одной на каждый квадрат в нашей сетке.
IntVar[][] grid = new IntVar[9][9];
Они бывают одного из двух видов:
- Если значение неизвестно в начале, то нам нужно определить его с помощью области возможных значений, в нашем случае это значения от 1 до 9
grid[row][col] = model.intVar(row, col), 1, 9);
- Если значение известно в начале, то мы определяем его как простую константу, которая не может измениться. По сути, это означает, что переменная имеет область одного значения.
grid[row][col] = model.intVar(value)
Определение ограничений
Как только у нас есть переменные, нам нужно настроить их ограничения, у нас есть 9 строк, столбцов и подквадратов, где все значения должны быть разными. Для этого мы используем ограничение allDifferent .
for (int i = 0; i != 9; i++) {
model.allDifferent(getCellsInRow(grid, i)).post();
model.allDifferent(getCellsInColumn(grid, i)).post();
model.allDifferent(getCellsInSquare(grid, i)).post();
}
Решите это
Наконец, мы решаем ее следующим образом.
Solver solver = model.getSolver(); solver.solve();
Choco solver будет продолжать искать решения до тех пор, пока не сдастся, потому что он использовал их все, или потому, что он думает, что не найдет ничего лучшего, или потому, что вы сказали ему сдаться после того, как проделали достаточно работы.
Как только это будет сделано, вы можете получить значение, найденное choco solver для каждой ячейки следующим образом
grid[row][column].getValue()
И все, самое сложное судоку в мире решается менее чем за секунду.
Так что еще вы можете сделать с choco solver?
Что бы вы ни хотели, главное, чтобы вы могли превратить это в проблему ограничений комбинаторики.
Например, вот более сложная программа раскрашивания графиков: GraphColouring.java
То, что он делает, это:
- Учитывая график: представьте, что это задачи, которые не могут быть выполнены одновременно.
- Учитывая, что у вас есть N возможных цветов на выбор: представьте, что это рабочие, которые доступны для выполнения этих задач.
- Учитывая, что ни один цвет не может быть использован более M раз: представьте, что рабочий может сделать только так много вещей за день.
- Учитывая, что вы хотите использовать наименьшее количество цветов: используйте наименьшее количество рабочих, необходимых для выполнения этой работы.
- Раскрасьте график в: предложите список задач и работников, в котором задействовано наименьшее количество людей, не перегружая их работой.
Куда нам теперь идти?
Этот пост ссылается на два простых примера того, что возможно, но на самом деле большинство комбинаторных задач могут быть решены с использованием этого подхода.
- Для получения более формального и полного описания программирования ограничений ознакомьтесь с Объяснение программирования ограничений
Для получения хорошего объяснения того, как формализовать актуальные проблемы, ознакомьтесь с лекциями 7, 8 и 9 этой серии лекций по искусственному интеллекту из MIT (на самом деле, всю эту серию стоит посмотреть)
Оригинал: “https://dev.to/sonalake/constraint-programming-solving-sudoku-with-choco-solver-library-3mbj”