Решение головоломок судоку
В данном примере продемонстрировано, как найти решение головоломки судоку, используя методы смешанного целочисленного линейного программирования (англ. Mixed Integer Linear Programming, MILP) и программирования в ограничениях (англ. Constraint Programming, CP).
Мы решим эту задачу с помощью рабочего процесса проблемно-ориентированной оптимизации.
Установка библиотек
Если в вашем окружении не установлена последняя версия пакета JuMP, раскомментируйте и запустите ячейку ниже:
Pkg.add(["JuMP", "HiGHS"])
Описание задачи
Судоку — это логическая комбинаторная головоломка с размещением чисел. Цель состоит в том, чтобы заполнить сетку 9x9 цифрами так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3x3 содержали все цифры от 1 до 9.
Правила:
- Каждая строка должна содержать цифры от 1 до 9 без повторений.
- Каждый столбец должен содержать цифры от 1 до 9 без повторений.
- Каждая подсетка 3х3 должна содержать цифры от 1 до 9 без повторений.
Для того чтобы решение головоломки было возможно, предоставлены первоначальные подсказки:
.png)
Пример решенного судоку:
.png)
Головоломки судоку варьируются от простых до чрезвычайно сложных, причем сложность часто определяется количеством предоставленных первоначальных подсказок и сложностью стратегий, необходимых для их решения. Правильно составленная головоломка судоку должна иметь только одно решение.
Подключение библиотек
Подключите библиотеку JuMP:
using JuMP;
Подключите библиотеку решателя HiGHS:
using HiGHS;
Подключите библиотеку построения графиков Plots:
using Plots;
Подключите библиотеку генерации случайных чисел Random:
using Random;
Создание функции визуализации судоку
Создайте функцию plot_sudoku(), визуализирующую судоку:
function plot_sudoku(grid)
p = plot(aspect_ratio=:equal, legend=false, axis=false, ticks=false)
for i in 0:9
plot!(p, [i, i], [0, 9], color=:black, linewidth=(i % 3 == 0 ? 2 : 1))
plot!(p, [0, 9], [i, i], color=:black, linewidth=(i % 3 == 0 ? 2 : 1))
end
for i in 1:9, j in 1:9
if grid[i,j] != 0
annotate!(p, j-0.5, 9.5-i, text(string(grid[i,j]), 14))
end
end
return p
end
Мы будем использовать данную функцию для визуализации судоку в этом примере.
Генерация головоломок судоку
В данном разделе мы напишем программу, которая будет генерировать головоломки судоку для решения.
Создайте функцию generate_full_grid(), отвечающую за построение сетки судоку:
function generate_full_grid()
grid = zeros(Int, 9, 9)
fill_grid!(grid, 1)
return grid
end
Создайте рекурсивную функцию fill_grid!(), заполняющую сетку судоку числами:
function fill_grid!(grid, pos)
if pos > 81
return true
end
row, col = divrem(pos - 1, 9) .+ 1
nums = shuffle(1:9)
for num in nums
if is_valid(grid, row, col, num)
grid[row, col] = num
if fill_grid!(grid, pos + 1)
return true
end
grid[row, col] = 0
end
end
return false
end
Данная функция реализует алгоритм обратного отслеживания для заполнения сетки судоку допустимыми числами.
Создайте функцию is_valid(), проверяющую допустимо ли размещение заданного числа (num) в определенной ячейке (строке, столбце) сетки судоку:
function is_valid(grid, row, col, num)
for i in 1:9
if grid[row, i] == num || grid[i, col] == num
return false
end
end
box_row, box_col = 3 * ((row - 1) ÷ 3) + 1, 3 * ((col - 1) ÷ 3) + 1
for i in 0:2, j in 0:2
if grid[box_row + i, box_col + j] == num
return false
end
end
return true
end
Эта функция имеет решающее значение для соблюдения всех трех правил в процессе заполнения сетки судоку.
Создайте функцию remove_numbers!(), отвечающую за удаление чисел из заполненной сетки судоку, для создания головоломки:
function remove_numbers!(grid, num_to_remove)
positions = [(i, j) for i in 1:9 for j in 1:9]
shuffle!(positions)
for _ in 1:num_to_remove
for (row, col) in positions
if grid[row, col] != 0
temp = grid[row, col]
grid[row, col] = 0
solution_count = count_solutions(grid)
if solution_count != 1
grid[row, col] = temp
else
break
end
end
end
end
end
Это ключевая часть создания головоломок судоку разного уровня сложности, поскольку количество удаленных ячеек может повлиять на сложность головоломки.
Создайте рекурсивную функцию count_solutions(), подсчитывающую количество допустимых решений для заданной сетки судоку:
function count_solutions(grid, limit=2)
empty_cell = findfirst(iszero, grid)
if empty_cell === nothing
return 1
end
row, col = Tuple(empty_cell)
count = 0
for num in 1:9
if is_valid(grid, row, col, num)
grid[row, col] = num
count += count_solutions(grid, limit - count)
grid[row, col] = 0
if count >= limit
return count
end
end
end
return count
end
Эта функция имеет решающее значение для обеспечения того, чтобы удаление чисел из сетки (в функции remove_numbers!) не приводило к появлению множественных решений.
Создайте функцию generate_sudoku_puzzle(), генерирующую судоку с заданным количеством подсказок:
function generate_sudoku_puzzle(num_clues)
full_grid = generate_full_grid()
num_to_remove = 81 - num_clues
remove_numbers!(full_grid, num_to_remove)
return full_grid
end
Теоретическое минимальное количество подсказок для головоломки судоку с единственным решением — 17.
Написанная нами программа может стабильно генерировать судоку с единственным решением, где минимальное количество подсказок составляет где-то между 20 и 30, что является более чем достаточным для данного примера.
Сгенерируйте судоку с 25 подсказками:
sudoku_puzzle = generate_sudoku_puzzle(25);
Визуализируйте судоку с подсказками:
plot_sudoku(sudoku_puzzle)
Формулировка задачи смешанного целочисленного линейного программирования
Решим задачу с использованием смешанного целочисленного линейного программирования. Цель состоит в том, чтобы смоделировать головоломку как задачу осуществимости, где каждая ячейка должна удовлетворять определенным ограничениям.
Создайте оптимизационную задачу с помощью функции Model() и укажите название решателя в скобках:
sudoku_milp = Model(HiGHS.Optimizer)
Создайте переменную x, представляющую собой трехмерный массив , где i, j и k находятся в диапазоне от 1 до 9. Аргумент Bin указывает на то, что переменная x является двоичной.
@variable(sudoku_milp, x[i = 1:9, j = 1:9, k = 1:9], Bin);
Массив x состоит из:
i(индекс строки): представляет номер строки в сетке судоку в диапазоне от 1 до 9j(индекс столбца): представляет номер столбца в сетке судоку, также в диапазоне от 1 до 9k(индекс цифры): представляет потенциальную цифру (от 1 до 9), которую можно поместить в ячейку (i,j)
Таким образом, двоичное представление x означает что:
-
— цифра 8 помещена в ячейку, расположенную в строке 3, столбце 3
-
= 0 — цифра 8 не помещена в эту ячейку
Используя циклы for для перебора строк i и столбцов j, создайте следующее условие для оптимизационной задачи:
Данное условие гарантирует, что каждая из ячеек в сетке судоку содержит ровно одно число от 1 до 9.
for i in 1:9
for j in 1:9
@constraint(sudoku_milp, sum(x[i, j, k] for k in 1:9) == 1)
end
end
Используя циклы for для перебора строк i и столбцов j, создайте следующие условия для оптимизационной задачи:
Это ограничение гарантирует, что каждая цифра k появляется ровно один раз в каждой строке ind.
Это ограничение гарантирует, что каждая цифра k появляется ровно один раз в каждом столбце ind.
for ind in 1:9
for k in 1:9
@constraint(sudoku_milp, sum(x[ind, j, k] for j in 1:9) == 1)
@constraint(sudoku_milp, sum(x[i, ind, k] for i in 1:9) == 1)
end
end
Код в вышестоящей ячейке добавляет в модель 162 ограничения:
- 81 ограничение для строк (9 строк × 9 цифр)
- 81 ограничение для столбцов (9 столбцов × 9 цифр)
С помощью этих двух условий мы выполнили соблюдение первых двух правил судоку:
- Каждая строка должна содержать цифры от 1 до 9 без повторений
- Каждый столбец должен содержать цифры от 1 до 9 без повторений
Используя циклы for, создайте следующее условие для оптимизационной задачи:
Самый внешний цикл для i в 1:3:7 перебирает строки 1, 4 и 7, являющиеся начальными строками каждой подсетки 3x3.
Средний цикл для j в 1:3:7 перебирает столбцы 1, 4 и 7, которые являющиеся начальными столбцами каждой подсетки 3x3.
Самый внутренний цикл для k в 1:9 перебирает все возможные цифры (от 1 до 9).
Переменные r и c позволяют определить ограничения для каждой подсетки 3x3 в судоку.
r- представляет индексы строк в подсетке 3x3 и принимает значения отiдоi+2c- представляет индексы столбцов в подсетке 3x3 и принимает значения отjдоj+2
for i in 1:3:7
for j in 1:3:7
for k in 1:9
@constraint(sudoku_milp, sum(x[r, c, k] for r in i:(i+2), c in j:(j+2)) == 1)
end
end
end
Код в вышестоящей ячейке добавляет в модель 81 ограничение (9 цифр для каждой из 9 подсеток), гарантируя, что каждая подсетка 3х3 содержит все цифры от 1 до 9 без повторений. Так мы выполняем третье правило головоломок судоку.
Используя циклы for для перебора ячеек, проставьте значения 1 (true) в двоичной переменной x в ячейках, где есть первоначальные подсказки (sudoku_puzzle), с помощью функции fix():
for i in 1:9
for j in 1:9
if sudoku_puzzle[i, j] != 0
fix(x[i, j, sudoku_puzzle[i, j]], 1; force = true)
end
end
end
Вы создали условия выполнения всех трех правил решения головоломок и внесли подсказки в переменную x. Теперь вы можете решить оптимизационную задачу:
optimize!(sudoku_milp)
Выведите статус результата работы решателя:
game_status = termination_status(sudoku_milp)
println("Статус: ", game_status)
if game_status == MOI.OPTIMAL || game_status == MOI.FEASIBLE_POINT
println("Оптимальное решение найдено")
else
println("Оптимальное решение не найдено")
end
Статус OPTIMAL означает, что решатель нашел глобальное оптимальное решение задачи.
Сохраните значения двоичной переменной x в переменной x_val:
x_val = value.(x)
Вы можете убедиться в том, что каждому значению k из решения была присвоена позиция в сетке переменной x_val.
Создайте новую матрицу 9x9, заполненную нулями, которая будет использована для преобразования результатов из двоичного формата в стандартный формат сетки судоку. Аргумент Int указывает на то, что значения матрицы целые числа.
sol_milp = zeros(Int, 9, 9);
Используя циклы for для перебора всех ячейк и возможных цифр в сетке судоку, преобразуйте значения трехмерного массива x_val в двухмерный массив целых чисел sol_milp.
sol_milp = zeros(Int, 9, 9)
for i in 1:9
for j in 1:9
for k in 1:9
if round(Int, x_val[i, j, k]) == 1
sol_milp[i, j] = k
end
end
end
end
Теперь переменная sol_milp содержит фактическое решение головоломки в формате двухмерного массива целых чисел.
Визуализируйте результаты:
plot_sudoku(sol_milp)
Мы продемонстрировали решение задачи с помощью смешанного целочисленного линейного программирования. Решатель находит возможную конфигурацию чисел, которая соответствует правилам решения судоку, сформулированным как ограничения по строкам, столбцам и подсеткам.
Формулировка задачи программирования в ограничениях
Вы также можете смоделировать данную задачу, используя программирование с ограничениями. Применим условие AllDifferent()(«все разные»), которое гласит, что никакие два элемента вектора не могут принимать одно и то же значение.
Создайте оптимизационную задачу с помощью функции Model() и укажите название решателя в скобках:
sudoku_cp = Model(HiGHS.Optimizer)
Создайте переменную sudoku_cp, содержащую двухмерный массив . Каждая переменная находится в диапазоне от 1 до 9. Аргумент Int указывает, что значения переменных являются целыми числами.
@variable(sudoku_cp , 1 <= x[1:9, 1:9] <= 9, Int);
Задайте условие, применимое к каждой строке i сетки судоку. MOI.AllDifferent(9) гарантирует, что все элементы в строке i различны.
Это означает, что каждое число от 1 до 9 появляется ровно один раз в каждой строке.
@constraint(sudoku_cp , [i = 1:9], x[i, :] in MOI.AllDifferent(9));
Задайте условие, применимое к каждому столбцу j сетки судоку. MOI.AllDifferent(9) гарантирует, что все элементы в столбце j различны.
Это означает, что каждое число от 1 до 9 появляется ровно один раз в каждом столбце.
@constraint(sudoku_cp, [j = 1:9], x[:, j] in MOI.AllDifferent(9));
Задайте условие, применимое к каждой подсетке 3x3 в судоку. MOI.AllDifferent(9) гарантирует, что все элементы в каждой из подсеток различны. Это означает, что каждое число от 1 до 9 появляется ровно один раз в каждой подсетке 3x3.
for i in 1:3:7, j in 1:3:7
@constraint(sudoku_cp, vec(x[i:i+2, j:j+2]) in MOI.AllDifferent(9))
end
Для каждой из ячеек [i, j] перенесите изначальные подсказки из sudoku_puzzle в переменную x с помощью функции fix:
for i in 1:9, j in 1:9
if sudoku_puzzle[i, j] != 0
fix(x[i, j], sudoku_puzzle[i, j]; force = true)
end
end
Вы создали условия выполнения всех трех правил решения головоломок и внесли подсказки в переменную x. Теперь вы можете решить оптимизационную задачу:
optimize!(sudoku_cp)
Выведите статус результата работы решателя:
game_status = termination_status(sudoku_cp)
println("Статус: ", game_status)
if game_status == MOI.OPTIMAL || game_status == MOI.FEASIBLE_POINT
println("Оптимальное решение найдено")
else
println("Оптимальное решение не найдено")
end
Статус OPTIMAL означает, что решатель нашел глобальное оптимальное решение задачи.
Сохраните результаты в переменной. Полученные значения имеют тип Float64. Вы можете использовать функцию round вместе с аргументом Int, чтобы конвертировать значения в целые числа.
sol_cp = round.(Int, value.(x));
Визуализируйте полученное решение судоку:
plot_sudoku(sol_cp)
Вы можете сравнить решения полученные путем использования смешанного целочисленного линейного программирования и путем программирования в ограничениях:
sol_milp == sol_cp
Результаты обоих методов решения головоломки совпадают.
Заключение
В данном примере мы решили головоломку судоку с помощью двух разных подходов — смешанного целочисленного линейного программирования (англ. Mixed Integer Linear Programming, MILP) и программирования в ограничениях (англ. Constraint Programming, CP). Оба подхода могут решить головоломку, но они формулируют и решают задачу принципиально по-разному, демонстрируя различные характеристики в моделировании и решении задач. В рамках решения задачи продемонстрированной в данном примере мы можем выделить некоторые отличия между этими подходами.
Смешанное целочисленное линейное программирование:
- Использует двоичные переменные
@variable(sudoku_milp, x[i = 1:9, j = 1:9, k = 1:9], Bin)
- Использует линейные ограничения для обеспечения соблюдения правил судоку
@constraint(sudoku_milp, sum(x[i, j, k] для k в 1:9) == 1)
- Более крупная модель с большим количеством переменных, но с более простыми ограничениями
- Как правило, более устойчиво к небольшим изменениям модели и лучше масштабируется с увеличением размера задачи
Программирование в ограничениях:
- Использует целочисленные переменные
@variable(sudoku_cp, 1 <= x[1:9, 1:9] <= 9, Int)
- Использует глобальные ограничения, такие как
AllDifferent, для обеспечения соблюдения правил судоку
@constraint(sudoku_cp, [i = 1:9], x[i, :] в MOI.AllDifferent(9))
- Меньшая модель с меньшим количеством переменных, но с более сложными ограничениями
- Может быть более чувствительно к размеру и структуре задачи
На практике выбор между смешанным целочисленным линейным программированием и программированием в ограничениях часто зависит от конкретных характеристик задачи, причем для некоторых задач один метод лучше подходит, чем другой. В некоторых случаях эффективными могут оказаться гибридные подходы, сочетающие оба метода.