Заметки к нулевому заседанию математического кружка.

Математика Оставить комментарий

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

Занимались, по инициативе superchips, Судоку.

Для справки:

Судоку являются специальным случаем латинских квадратов размера 9x9. Латинские квадраты 9x9 заполняются числами от 1 до 9 и определяются следующим свойством: в каждой строке квадрата должна стоять перестановка чисел 1..9, в каждом столбце - перестановка чисел 1..9. Судоку, в дополнение к этим условиям обладают ещё и тем свойством, что в каждом из 9 квадратиков размера 3х3, на которые разделяется квадрат 9х9, также стоит перестановка чисел 1..9.

Головоломка Судоку заключается в восстановлении заполнения квадрата по заданным значениям некоторых позиций квадрата. Оказывается, что решение головоломки, а также проверка единственности данного решения является NP-полной задачей.

Подробнее см. здесь.


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

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

В процессе рассуждений появился следующий вопрос, решить который было бы интересно. Пусть таблица Судоку заполняется сверху вниз корректно - т.е. с соблюдением всех правил. Предположим, что мы заполнили 6 верхних строк.


sudoku

Следует ли из этого, что оставшиеся 3 строки всегда можно дозаполнить корректно? (Вопрос о единственности дозаполнения, видимо, не стоúт, так как существуют Судоку, в которых недозаполнены всего 4 клеточки, которые при этом имеют 2 различных корректных дозаполнения)

Оставить комментарий

Тема WordPress и иконки разработаны N.Design Studio
© 2024 Страница Алексея Яшунского RSS записей RSS комментариев Войти