Engee Community
/
Примеры и проекты
/
Решение головоломок судоку

Решение головоломок судоку

Автор
avatar-mikhailchupmikhailchup
Notebook

Решение головоломок судоку

В данном примере продемонстрировано, как найти решение головоломки судоку, используя методы смешанного целочисленного линейного программирования (англ. Mixed Integer Linear Programming, MILP) и программирования в ограничениях (англ. Constraint Programming, CP).

Мы решим эту задачу с помощью рабочего процесса проблемно-ориентированной оптимизации.

В этом примере мы воспользуемся функциями библиотеки JuMP.jl для формулировки оптимизационной задачи, библиотекой линейной оптимизации HiGHS.jl, библиотекой генерации случайных чисел Random.jl и библиотекой Plots.jl для визуализации результатов.

Установка библиотек

Если в вашем окружении не установлена последняя версия пакета JuMP, раскомментируйте и запустите ячейку ниже:

In [ ]: 
Pkg.add(["JuMP", "HiGHS"])
In [ ]: 
#Pkg.add("JuMP");

Для запуска новой версии библиотеки после завершения установки нажмите на кнопку «Личный кабинет»:

screenshot_20240710_134852.png Затем нажмите на кнопку «Стоп»:

screenshot_20240710_2.png

Перезапустите сессию нажатием кнопки «Старт Engee»:

screenshot_20240710_135431.png

Описание задачи

Судоку — это логическая комбинаторная головоломка с размещением чисел. Цель состоит в том, чтобы заполнить сетку 9x9 цифрами так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3x3 содержали все цифры от 1 до 9.

Правила:

  1. Каждая строка должна содержать цифры от 1 до 9 без повторений.
  2. Каждый столбец должен содержать цифры от 1 до 9 без повторений.
  3. Каждая подсетка 3х3 должна содержать цифры от 1 до 9 без повторений.

Для того чтобы решение головоломки было возможно, предоставлены первоначальные подсказки:

newplot_3.png

Пример решенного судоку:

newplot_4.png

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

Подключение библиотек

Подключите библиотеку JuMP:

In [ ]: 
using JuMP;

Подключите библиотеку решателя HiGHS:

In [ ]: 
using HiGHS;

Подключите библиотеку построения графиков Plots:

In [ ]: 
using Plots;

Подключите библиотеку генерации случайных чисел Random:

In [ ]: 
using Random;

Создание функции визуализации судоку

Создайте функцию plot_sudoku(), визуализирующую судоку:

In [ ]: 
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
Out[0]:
plot_sudoku (generic function with 1 method)

Мы будем использовать данную функцию для визуализации судоку в этом примере.

Генерация головоломок судоку

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

Создайте функцию generate_full_grid(), отвечающую за построение сетки судоку:

In [ ]: 
function generate_full_grid()
    grid = zeros(Int, 9, 9)
    fill_grid!(grid, 1)
    return grid
end
Out[0]:
generate_full_grid (generic function with 1 method)

Создайте рекурсивную функцию fill_grid!(), заполняющую сетку судоку числами:

In [ ]: 
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
Out[0]:
fill_grid! (generic function with 1 method)

Данная функция реализует алгоритм обратного отслеживания для заполнения сетки судоку допустимыми числами.

Создайте функцию is_valid(), проверяющую допустимо ли размещение заданного числа (num) в определенной ячейке (строке, столбце) сетки судоку:

In [ ]: 
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
Out[0]:
is_valid (generic function with 1 method)

Эта функция имеет решающее значение для соблюдения всех трех правил в процессе заполнения сетки судоку.

Создайте функцию remove_numbers!(), отвечающую за удаление чисел из заполненной сетки судоку, для создания головоломки:

In [ ]: 
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
Out[0]:
remove_numbers! (generic function with 1 method)

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

Создайте рекурсивную функцию count_solutions(), подсчитывающую количество допустимых решений для заданной сетки судоку:

In [ ]: 
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
Out[0]:
count_solutions (generic function with 2 methods)

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

Создайте функцию generate_sudoku_puzzle(), генерирующую судоку с заданным количеством подсказок:

In [ ]: 
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
Out[0]:
generate_sudoku_puzzle (generic function with 1 method)

Теоретическое минимальное количество подсказок для головоломки судоку с единственным решением — 17.

Написанная нами программа может стабильно генерировать судоку с единственным решением, где минимальное количество подсказок составляет где-то между 20 и 30, что является более чем достаточным для данного примера.

Сгенерируйте судоку с 25 подсказками:

In [ ]: 
sudoku_puzzle = generate_sudoku_puzzle(25);

Визуализируйте судоку с подсказками:

In [ ]: 
plot_sudoku(sudoku_puzzle)
Out[0]:

Формулировка задачи смешанного целочисленного линейного программирования

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

Создайте оптимизационную задачу с помощью функции Model() и укажите название решателя в скобках:

In [ ]: 
sudoku_milp = Model(HiGHS.Optimizer)
Out[0]:
A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Создайте переменную x, представляющую собой трехмерный массив $x(i, j, k)$, где i, j и k находятся в диапазоне от 1 до 9. Аргумент Bin указывает на то, что переменная x является двоичной.

In [ ]: 
@variable(sudoku_milp, x[i = 1:9, j = 1:9, k = 1:9], Bin);

Массив x состоит из:

  • i (индекс строки): представляет номер строки в сетке судоку в диапазоне от 1 до 9
  • j (индекс столбца): представляет номер столбца в сетке судоку, также в диапазоне от 1 до 9
  • k (индекс цифры): представляет потенциальную цифру (от 1 до 9), которую можно поместить в ячейку (i, j)

Таким образом, двоичное представление x означает что:

  • $x(3, 3, 8) = 1$ — цифра 8 помещена в ячейку, расположенную в строке 3, столбце 3

  • $x(3, 3, 8)$ = 0 — цифра 8 не помещена в эту ячейку

Используя циклы for для перебора строк i и столбцов j, создайте следующее условие для оптимизационной задачи:

$$\sum_{k=1}^{9} x_{i, j, k} = 1$$

Данное условие гарантирует, что каждая из ячеек в сетке судоку содержит ровно одно число от 1 до 9.

In [ ]: 
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, создайте следующие условия для оптимизационной задачи: $$\sum_{j=1}^{9} x_{ind, j, k} = 1$$

Это ограничение гарантирует, что каждая цифра k появляется ровно один раз в каждой строке ind.

$$\sum_{i=1}^{9} x_{i, ind, k} = 1$$

Это ограничение гарантирует, что каждая цифра k появляется ровно один раз в каждом столбце ind.

In [ ]: 
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, создайте следующее условие для оптимизационной задачи:

$$\sum_{r=i}^{i+2} \sum_{c=j}^{j+2} x_{r, c, k} = 1$$

Самый внешний цикл для 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+2
  • c - представляет индексы столбцов в подсетке 3x3 и принимает значения от j до j+2
In [ ]: 
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():

In [ ]: 
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. Теперь вы можете решить оптимизационную задачу:

In [ ]: 
optimize!(sudoku_milp)

Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e+00, 1e+00]
  Cost   [0e+00, 0e+00]
  Bound  [1e+00, 1e+00]
  RHS    [1e+00, 1e+00]
Presolving model
200 rows, 184 cols, 736 nonzeros  0s
0 rows, 0 cols, 0 nonzeros  0s
Presolve: Optimal

Solving report
  Status            Optimal
  Primal bound      0
  Dual bound        0
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    0 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

Выведите статус результата работы решателя:

In [ ]: 
status = termination_status(sudoku_milp)
println("Статус: ", status)

if status == MOI.OPTIMAL || status == MOI.FEASIBLE_POINT
    println("Оптимальное решение найдено")
else
    println("Оптимальное решение не найдено")
end

Статус: OPTIMAL
Оптимальное решение найдено

Статус OPTIMAL означает, что решатель нашел глобальное оптимальное решение задачи.

Сохраните значения двоичной переменной x в переменной x_val:

In [ ]: 
x_val = value.(x)
Out[0]:
9×9×9 Array{Float64, 3}:
[:, :, 1] =
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0

[:, :, 2] =
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0

[:, :, 3] =
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0

[:, :, 4] =
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0

[:, :, 5] =
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0

[:, :, 6] =
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0

[:, :, 7] =
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0

[:, :, 8] =
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0

[:, :, 9] =
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
 0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0
 1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0

Вы можете убедиться в том, что каждому значению k из решения была присвоена позиция в сетке переменной x_val.

Создайте новую матрицу 9x9, заполненную нулями, которая будет использована для преобразования результатов из двоичного формата в стандартный формат сетки судоку. Аргумент Int указывает на то, что значения матрицы целые числа.

In [ ]: 
sol_milp = zeros(Int, 9, 9);

Используя циклы for для перебора всех ячейк и возможных цифр в сетке судоку, преобразуйте значения трехмерного массива x_val в двухмерный массив целых чисел sol_milp.

In [ ]: 
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 содержит фактическое решение головоломки в формате двухмерного массива целых чисел.

Визуализируйте результаты:

In [ ]: 
plot_sudoku(sol_milp)
Out[0]:

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

Формулировка задачи программирования в ограничениях

Вы также можете смоделировать данную задачу, используя программирование с ограничениями. Применим условие AllDifferent()(«все разные»), которое гласит, что никакие два элемента вектора не могут принимать одно и то же значение.

Создайте оптимизационную задачу с помощью функции Model() и укажите название решателя в скобках:

In [ ]: 
sudoku_cp = Model(HiGHS.Optimizer)
Out[0]:
A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Создайте переменную sudoku_cp, содержащую двухмерный массив $x(i, j)$. Каждая переменная находится в диапазоне от 1 до 9. Аргумент Int указывает, что значения переменных являются целыми числами.

In [ ]: 
@variable(sudoku_cp , 1 <= x[1:9, 1:9] <= 9, Int);

Задайте условие, применимое к каждой строке i сетки судоку. MOI.AllDifferent(9) гарантирует, что все элементы в строке i различны. Это означает, что каждое число от 1 до 9 появляется ровно один раз в каждой строке.

In [ ]: 
@constraint(sudoku_cp , [i = 1:9], x[i, :] in MOI.AllDifferent(9));

Задайте условие, применимое к каждому столбцу j сетки судоку. MOI.AllDifferent(9) гарантирует, что все элементы в столбце j различны. Это означает, что каждое число от 1 до 9 появляется ровно один раз в каждом столбце.

In [ ]: 
@constraint(sudoku_cp, [j = 1:9], x[:, j] in MOI.AllDifferent(9));

Задайте условие, применимое к каждой подсетке 3x3 в судоку. MOI.AllDifferent(9) гарантирует, что все элементы в каждой из подсеток различны. Это означает, что каждое число от 1 до 9 появляется ровно один раз в каждой подсетке 3x3.

In [ ]: 
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:

In [ ]: 
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. Теперь вы можете решить оптимизационную задачу:

In [ ]: 
optimize!(sudoku_cp)

Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e+00, 9e+00]
  Cost   [0e+00, 0e+00]
  Bound  [1e+00, 9e+00]
  RHS    [1e+00, 1e+00]
Presolving model
747 rows, 1568 cols, 5788 nonzeros  0s
504 rows, 1568 cols, 4108 nonzeros  0s
Objective function is integral with scale 1

Solving MIP model with:
   504 rows
   1568 cols (1512 binary, 56 integer, 0 implied int., 0 continuous)
   4108 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   0               inf                  inf        0      0      0         0     0.0s
         0       0         0   0.00%   0               inf                  inf        0      0      3       831     0.0s

10.4% inactive integer columns, restarting
Model after restart has 302 rows, 570 cols (514 bin., 56 int., 0 impl., 0 cont.), and 2281 nonzeros

         0       0         0   0.00%   0               inf                  inf       13      0      0      8462     1.7s

Solving report
  Status            Optimal
  Primal bound      0
  Dual bound        0
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    0 (objective)
                    0 (bound viol.)
                    1.34559030585e-13 (int. viol.)
                    0 (row viol.)
  Timing            1.77 (total)
                    0.08 (presolve)
                    0.00 (postsolve)
  Nodes             1
  LP iterations     8783 (total)
                    0 (strong br.)
                    1996 (separation)
                    5635 (heuristics)

Выведите статус результата работы решателя:

In [ ]: 
status = termination_status(sudoku_cp)
println("Статус: ", status)

if status == MOI.OPTIMAL || status == MOI.FEASIBLE_POINT
    println("Оптимальное решение найдено")
else
    println("Оптимальное решение не найдено")
end

Статус: OPTIMAL
Оптимальное решение найдено

Статус OPTIMAL означает, что решатель нашел глобальное оптимальное решение задачи.

Сохраните результаты в переменной. Полученные значения имеют тип Float64. Вы можете использовать функцию round вместе с аргументом Int, чтобы конвертировать значения в целые числа.

In [ ]: 
sol_cp = round.(Int, value.(x));

Визуализируйте полученное решение судоку:

In [ ]: 
plot_sudoku(sol_cp)
Out[0]:

Вы можете сравнить решения полученные путем использования смешанного целочисленного линейного программирования и путем программирования в ограничениях:

In [ ]: 
sol_milp == sol_cp
Out[0]:
true

Результаты обоих методов решения головоломки совпадают.

Заключение

В данном примере мы решили головоломку судоку с помощью двух разных подходов — смешанного целочисленного линейного программирования (англ. Mixed Integer Linear Programming, MILP) и программирования в ограничениях (англ. Constraint Programming, CP). Оба подхода могут решить головоломку, но они формулируют и решают задачу принципиально по-разному, демонстрируя различные характеристики в моделировании и решении задач. В рамках решения задачи продемонстрированной в данном примере мы можем выделить некоторые отличия между этими подходами.

Смешанное целочисленное линейное программирование:

  • Использует двоичные переменные $x(i, j, k)$
@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)
  • Более крупная модель с большим количеством переменных, но с более простыми ограничениями
  • Как правило, более устойчиво к небольшим изменениям модели и лучше масштабируется с увеличением размера задачи

Программирование в ограничениях:

  • Использует целочисленные переменные $x(i, j)$
@variable(sudoku_cp, 1 <= x[1:9, 1:9] <= 9, Int)
  • Использует глобальные ограничения, такие как AllDifferent, для обеспечения соблюдения правил судоку
@constraint(sudoku_cp, [i = 1:9], x[i, :] в MOI.AllDifferent(9))
  • Меньшая модель с меньшим количеством переменных, но с более сложными ограничениями
  • Может быть более чувствительно к размеру и структуре задачи

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

Файлы
sudoku_solver_problem_based.ngscript

Тип

Интерактивные скрипты

Краткое описание

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

Связанные материалы

Алгоритм решения задач оптимизации
Задачи смешанного целочисленного линейного программирования

Теги

Категории

Расчеты в Engee
Математика и оптимизация
Оптимизация

Языки

  • Julia

Форматы

    ngscript

Уровень

    Средний

Статус

Создано

Обновлено

Источник

Engee