Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 18.08.2014, 18:14   #1
gheljenor
Новичок
Джуниор
 
Регистрация: 18.08.2014
Сообщений: 1
Вопрос Судоку, задачка для гиков

Время от времени люблю решать всяческие математичесские/программистские задачки. Хочется найти единомышленников, которым тоже интересно поломать голову над сложными и интересными вещами.
Сегодня вот дошёл до судоку. Интересует скорее даже не сам решатель судоку, а опровержение или доказательство одной теории. Речь идёт о уже решённых судоку (всё поле заполнено по правилам)

Дано:
Если в судоку поменять 2 любые цифры местами (допустим все дойки заменить тройками, а тройки двойками), то судоку будет по прежнему правильной.
Если в судоку поменять местами 2 любых столбца/строки в рамках одного блока из 3х линий, судоку останется правильной
Если судоку повернуть на 90градусов, судоку останется правильной.
(каждое утверждение достаточно легко доказывается)

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

Задача явно соотносится с задачей построения латинских квадратов (на вики есть хорошая статья про это). Известно, что число главных классов эквивалентности для квадратов 9-порядка = 19 270 853 541. Но в классической задаче о построении латинских квадратов нет условия о том что квадрат поделён на 9 блоков в которых каждая цифра должна встречаться только один раз. Мне кажется, что данное условие резко изменит количество классов эквивалентности до весьма малой цифры, но пока что никак не могу придумать с какой стороны подойти к вопросу.
gheljenor вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Таблица для игры Судоку ODDsama C++ Builder 1 05.04.2013 18:02
Переделать обычное судоку в судоку чёт-нечёт Dark Illusion Общие вопросы Delphi 0 28.03.2012 20:33
Программа для решения Судоку Atlika Помощь студентам 1 25.05.2011 20:34
Программа для решения судоку e1teck Общие вопросы C/C++ 1 11.03.2011 09:23
Логика для Кроссвордов Судоку. С.М.С Свободное общение 7 02.04.2009 16:07