Решение судоку помощью базисов Гребнерa

Аннотация

Мы изучаем решение судоку и обобщенного судоку, используя технику базисов Грёбнера. Пусть x_1, ... , x_81 переменные, связанные с 81 квадратами, которые образует головоломку судоку и линейно упорядочены сначала по строкам, затем по столбцам. Решение судоку есть набор чисел (a_1, ... ,a_81), где a_i число в квадрате, ассоциированном с переменной x_i. Пусть также S - судоку с предварительно заполненными данными {c_i}_{iin L для Lsubset {1, ..., 81}. Вся необходимая информация для решения такого судоку содержится в алгебраическом множестве mathbb V (I+<{x_{i}-c_{i}}_{iin L}>). Мы используем технику базисов Грёбнера для поиска такого решения и приводим соответсвующий код в~системе компьютерной алгебры SAGE для программы, решающей эту задачу.