Задача о судоку
Модераторы: Азарапетыч, Администрация
- Шшок
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Задача о судоку
Надеюсь, все вы знаете, что такое судоку. Те, кто не знают, могут посмотреть правила по этой ссылке:
http://www.cydoky.ru/?page=rules
А теперь - собственно задача. Это олимпиадная задача, решение которой мне неизвестно. Мне эта задача не по зубам - даже не знаю, с какого конца к ней подступиться.
Введем два определения:
1. Судоку N-го порядка - это судоку, в начальных условиях которого заполнено ровно N клеток.
2. Правильным называется судоку, имеющее единственное решение.
При каком максимальном N не существует ни одного правильного судоку N-го порядка?
http://www.cydoky.ru/?page=rules
А теперь - собственно задача. Это олимпиадная задача, решение которой мне неизвестно. Мне эта задача не по зубам - даже не знаю, с какого конца к ней подступиться.
Введем два определения:
1. Судоку N-го порядка - это судоку, в начальных условиях которого заполнено ровно N клеток.
2. Правильным называется судоку, имеющее единственное решение.
При каком максимальном N не существует ни одного правильного судоку N-го порядка?
В борьбе бобра с козлом побеждает бобро. Или козло.
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Задача о судоку
Насколько помню, существует множество судок с 16 задающими цифрами и единственным решением. В них задающие цифры довольно хаотичны.
Про судоки с 15 задающими цифрами ничего не знаю. Но задача представляется не олимпиадной, а нехило компьютерной.
Возможно, речь идет о каком-то очень жестком расположении цифр с правильной структурой, которую задают совсем небольшое начальное количество.
Про судоки с 15 задающими цифрами ничего не знаю. Но задача представляется не олимпиадной, а нехило компьютерной.
Возможно, речь идет о каком-то очень жестком расположении цифр с правильной структурой, которую задают совсем небольшое начальное количество.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
- Шшок
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: Задача о судоку
Ну, смысл именно такой: при каком минимальном количестве заданных цифр вообще можно придумать судоку, имеющее единственное решение. Хрен его знает, как это решать... Может, Дендр чего-то сообразит?
В борьбе бобра с козлом побеждает бобро. Или козло.
- Semak
- Акула пера
- Сообщения: 7894
- Зарегистрирован: 13 май 2004, 18:30
- Пол: Мужской
- Откуда: Москва
- Контактная информация:
Re: Задача о судоку
Кстати, по поводу судоку. Одно время я увлекался из разгадыванием, но потом встал вопрос: а любое ли судоку решается однозначно и логически? Просто встретилась парочка, где был конкретный затык, а все люди, у которых я пытался спросить, как это решать, отвечали, что они решают перебором. Перебор - это уже некрасиво. Если так подходить, то можно вообще программу написать и за секунду получить ответ.
Вопрос к тем, кто увлекается этой штукой. Действительно ли некоторые можно только перебором решить? Или мы просто не нашли ключ к нормальному решению?
P.S. Если кто захочет подумать - выложу и само судоку.
Вопрос к тем, кто увлекается этой штукой. Действительно ли некоторые можно только перебором решить? Или мы просто не нашли ключ к нормальному решению?
P.S. Если кто захочет подумать - выложу и само судоку.
Каждой хорошенькой девушке - по плохому танцору!
Хотите научиться играть в бридж? Тогда вам СЮДА
Хотите научиться играть в бридж? Тогда вам СЮДА
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Задача о судоку
Семак, я в курсе.
Всё зависит от изданий.
Где-то идет откровенная халтура, когда оказываются тысячи решений.
Хорошие издания делают задачи, подразумевающие логические поэтапные ходы.
Тут надо определиться, где заканчивается логика и начинается перебор.
Вот рассуждение: "если тут стоит X, то тогда Х стоит и здесь, а значит вот тут только Y, что оставляет в этой клетке место только для Z, а это невозможно". Это - логическое рассуждение, или уже перебор?
Но не в массовых изданиях бывают судоки с очень длинными многоходовыми рассуждениями. Есть даже сайты, где классифицируются эти сложные рассуждения.
А один из методов решения - если в клетке могут быть 2-3 цифры, прямо писать их там мелко. И анализировать с учетом этой информации.
Всё зависит от изданий.
Где-то идет откровенная халтура, когда оказываются тысячи решений.
Хорошие издания делают задачи, подразумевающие логические поэтапные ходы.
Тут надо определиться, где заканчивается логика и начинается перебор.
Вот рассуждение: "если тут стоит X, то тогда Х стоит и здесь, а значит вот тут только Y, что оставляет в этой клетке место только для Z, а это невозможно". Это - логическое рассуждение, или уже перебор?
Но не в массовых изданиях бывают судоки с очень длинными многоходовыми рассуждениями. Есть даже сайты, где классифицируются эти сложные рассуждения.
А один из методов решения - если в клетке могут быть 2-3 цифры, прямо писать их там мелко. И анализировать с учетом этой информации.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Задача о судоку
Не знаю, как журнальные судоку - давно забросил их покупать.
Имею программку на наладоннике. На высшем уровне сложности 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 заполненная клетка. Однако... возможно и меньше. Но двадцати одной должно хватить.
Имею программку на наладоннике. На высшем уровне сложности 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 заполненная клетка. Однако... возможно и меньше. Но двадцати одной должно хватить.
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Задача о судоку
Ошиблась, не 16, 17.
Вот, много судок с 17 задающими и единственным решений можно найти здесь.
http://people.csse.uwa.edu.au/gordon/sudokupat.php
Вот, много судок с 17 задающими и единственным решений можно найти здесь.
http://people.csse.uwa.edu.au/gordon/sudokupat.php
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Задача о судоку
Да... действительно - 17 цифр, единственное решение. С "помогалкой" (программка, автоматически заполняющая пустые клетки возможными значениями, которые могут стоять в данной клетке) решаются минут за 10. С карандашом и бумажкой, наверное (не проверял), и за полчаса можно.Инна писал(а):Ошиблась, не 16, 17.
Вот, много судок с 17 задающими и единственным решений можно найти здесь.
http://people.csse.uwa.edu.au/gordon/sudokupat.php
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Задача о судоку
Раньше никто не интересовался, но может сейчас заинтересуется кто-то.
8 февраля пройдет очередной очный чемпионат России по решению судоку. Приглашаются все желающие.
Если у кого-то есть интерес, будут подробности.
8 февраля пройдет очередной очный чемпионат России по решению судоку. Приглашаются все желающие.
Если у кого-то есть интерес, будут подробности.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
-
- Писатель на заборах
- Сообщения: 222
- Зарегистрирован: 02 май 2007, 22:28
- Пол: Мужской
- Откуда: Москва
Re: Задача о судоку
Давайте подробности.
Особенно интересно, как организаторы борются с использованием программ, решающих судоку. Как человек, с многолетним опытом списывания, боюсь, что побоного рода соревнования могут превратиться в борьбю технических приспособ.
Особенно интересно, как организаторы борются с использованием программ, решающих судоку. Как человек, с многолетним опытом списывания, боюсь, что побоного рода соревнования могут превратиться в борьбю технических приспособ.
Думать надо всегда. И когда идёшь в гору - тоже.
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Задача о судоку
Все участники сидят в одном зале.
Как на вступительных экзаменах борются со списыванием? Вот приблизительно так же.
К тому же чисто классических там самый минимум.
А подробности - www.diogen.h1.ru
Как на вступительных экзаменах борются со списыванием? Вот приблизительно так же.
К тому же чисто классических там самый минимум.
А подробности - www.diogen.h1.ru
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
-
- Писатель на заборах
- Сообщения: 222
- Зарегистрирован: 02 май 2007, 22:28
- Пол: Мужской
- Откуда: Москва
Re: Задача о судоку
Где обыскивают, а у нас стоят радиоподавляющие устройства.Как на вступительных экзаменах борются со списыванием?
Спасибо, за инфу.
Думать надо всегда. И когда идёшь в гору - тоже.
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Задача о судоку
Очередной, вот уже пятый чемпионат по судоку пройдет 7 февраля в Москве.
Что-то я зову, зову, ни разу никто с этого сайта не пришел.
Дело проходит в течение одного дня. Участие - бесплатное...
Что-то я зову, зову, ни разу никто с этого сайта не пришел.
Дело проходит в течение одного дня. Участие - бесплатное...
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Задача о судоку
http://www.nature.com/news/mathematicia ... zle-1.9751
Вот, доказали, что нет судоку с единственным решением и 16 задающими.
Вот, доказали, что нет судоку с единственным решением и 16 задающими.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...