Задача о судоку

[Шшок]

Надеюсь, все вы знаете, что такое судоку. Те, кто не знают, могут посмотреть правила по этой ссылке:

http://www.cydoky.ru/?page=rules

А теперь - собственно задача. Это олимпиадная задача, решение которой мне неизвестно. Мне эта задача не по зубам - даже не знаю, с какого конца к ней подступиться.

Введем два определения:

1. Судоку N-го порядка - это судоку, в начальных условиях которого заполнено ровно N клеток.
2. Правильным называется судоку, имеющее единственное решение.

При каком максимальном N не существует ни одного правильного судоку N-го порядка?

[Инна]

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

[Шшок]

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

[Semak]

Кстати, по поводу судоку. Одно время я увлекался из разгадыванием, но потом встал вопрос: а любое ли судоку решается однозначно и логически? Просто встретилась парочка, где был конкретный затык, а все люди, у которых я пытался спросить, как это решать, отвечали, что они решают перебором. Перебор - это уже некрасиво. Если так подходить, то можно вообще программу написать и за секунду получить ответ.

Вопрос к тем, кто увлекается этой штукой. Действительно ли некоторые можно только перебором решить? Или мы просто не нашли ключ к нормальному решению?

P.S. Если кто захочет подумать - выложу и само судоку.

[Инна]

Семак, я в курсе.
Всё зависит от изданий.
Где-то идет откровенная халтура, когда оказываются тысячи решений.
Хорошие издания делают задачи, подразумевающие логические поэтапные ходы.
Тут надо определиться, где заканчивается логика и начинается перебор.
Вот рассуждение: "если тут стоит X, то тогда Х стоит и здесь, а значит вот тут только Y, что оставляет в этой клетке место только для Z, а это невозможно". Это - логическое рассуждение, или уже перебор?
Но не в массовых изданиях бывают судоки с очень длинными многоходовыми рассуждениями. Есть даже сайты, где классифицируются эти сложные рассуждения.
А один из методов решения - если в клетке могут быть 2-3 цифры, прямо писать их там мелко. И анализировать с учетом этой информации.

[Dendr]

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

К сабжу.
На 9х9 непросто решить, начал с малого.
Если размерность 1х1. Сетка, понятно, одна-единственная. Заполнется в один ход.
Размерность 2х2 - 2 разных сетки. Одна открытая клетка дает полное решение. (две комбинации)
3х3 - шесть сеток. Одной клетки мало. Нужно 2. (9 комбинаций)
4х4 - 288 сеток, 3 открытых клеток мало, 4 достаточно. (256 комбинаций)

Эмпирическая формула (непроверенная).
nxn - Fn=1!x2!x...xn! разных сеток. Число клеток такое, чтобы число комбинаций заполнения превышало половину числа сеток.
K^n>Fn/2
Для 9 выходит, что нужна 21 заполненная клетка. Однако... возможно и меньше. Но двадцати одной должно хватить.

[Инна]

Ошиблась, не 16, 17.
Вот, много судок с 17 задающими и единственным решений можно найти здесь.
http://people.csse.uwa.edu.au/gordon/sudokupat.php

[Dendr]

Ошиблась, не 16, 17.
Вот, много судок с 17 задающими и единственным решений можно найти здесь.
http://people.csse.uwa.edu.au/gordon/sudokupat.php

Да... действительно - 17 цифр, единственное решение. С "помогалкой" (программка, автоматически заполняющая пустые клетки возможными значениями, которые могут стоять в данной клетке) решаются минут за 10. С карандашом и бумажкой, наверное (не проверял), и за полчаса можно.

[Инна]

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

[baumanpeople]

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

[Инна]

Все участники сидят в одном зале.
Как на вступительных экзаменах борются со списыванием? Вот приблизительно так же.
К тому же чисто классических там самый минимум.
А подробности - www.diogen.h1.ru

[baumanpeople]

Как на вступительных экзаменах борются со списыванием?

Где обыскивают, а у нас стоят радиоподавляющие устройства.
Спасибо, за инфу.

[Инна]

Очередной, вот уже пятый чемпионат по судоку пройдет 7 февраля в Москве.
Что-то я зову, зову, ни разу никто с этого сайта не пришел.
Дело проходит в течение одного дня. Участие - бесплатное...

[Инна]

http://www.nature.com/news/mathematicia ... zle-1.9751
Вот, доказали, что нет судоку с единственным решением и 16 задающими.