2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 
Сообщение05.02.2007, 21:58 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Lion писал(а):
Это с непривычки. Поверьте, 99% всех судоку разгадывается за 5 минут. Если хотите. я могу привести действительно сложные судоку.

Это если процессор хороший. А головой — не получается. Что такое 99% судоку — см. ниже.

Lion писал(а):
Скорее всего --- нет. Можно придумать конкретный алгоритм, который в 99 % случаев не использует перебор вообще.

Лично мое впечатление, что существует заметное количество судоку, не решаемое без перебора. В определенном смысле.

Lion писал(а):
1. Придумать алгоритм, который будет строить судоку.

Таких алгоритмов — несть числа. Правильная постановка задачи: придумать алгоритм, который будет строить судоку без перебора (то есть, не добавляя новую клетку и потом проверяя, судоку ли это).

Lion писал(а):
2. Каково минимальное количество цифр, необходимое для того, чтобы соответствующая судоку имела единственное решение?

Тут несколько неточностей.

(а) судоку, по определению, должна иметь единственное решение. Хотя возможны начальные конфигурации, принципиально не разрешимые, они просто не судоку. Минимальное количество свободных клеток в неоднозначной конфигурации — четыре.
(б) Что такое цифры? Если это 1, 2, … 9, то ответ 8. В судоку (в постановке, в начальной конфигурации) может отсутствовать одна цифра, и такое я встречал. Если отсутствует больше чем одна, то, очевидно, решение неоднозначно (отсутствующие цифры можно менять местами).
(в) Если речь идет о количестве первоначально данных клеток, то вопрос, по-моему, открыт. Вроде известны примеры с 16 клетками, построенные вручную. На ответ накладывается вопрос о симметрии. Традиционно, судоку центрально симметричен. Очевидно, что если отказаться от симметрии, то может быть удастся уменьшить количество заполненных клеток.

Brukvalub писал(а):
Интересно было бы, на мой взгляд, оценить сверху и снизу сложность алгоритма решения судоку (речь я веду о нетривиальной оценке с использованием алгоритма,заранее отбрасывающего заведомо неприемлемые варианты, а не о количестве вариантов при прямом переборе всех, даже явно невозможных, случаев)

Константа :) Потому, что судоку конечная задача. Можно ставить вопрос, например, заменяя 3 на $n$. Но тут неизвестно даже как растет количество первоначально заполненых клеток.

~~~
Lion писал(а):
Насчет решения на компьютере: один мой друг утверждает, что он написал макрос для решения судоку.

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

Всего существует порядка десятка логических правил, подобных приведенным выше. (Одно из них, имеющих спорный статус: пусть возможные цифры приведены в фрагменте $\begin{array}{cc} 123 & 12 \\ 12 & 12 \end{array}$. Тогда если можно исключить 3, то судоку неоднозначен. Поэтому выбираем три.) По опыту, заметное количество автоматически сгенерированных судоку (порядка 10%, или даже больше), в какой-то момент утыкаются в ситуацию, когда ни одно из правил не применимо. Тогда остаются перебор и его замаскированные разновидности (например, раскраска). Их мало кто-может сделать устно за 5 минут. Итого: нормальным считается решение судоку за 10–40 минут в зависимости от сложности.

Основная проблема при программной генерации судоку — сделать их похожими на ручные, составленные человеком.

Некоторое количество ссылок (все английские, японский продолжает ржаветь).

Добавлено спустя 54 минуты 16 секунд:

Lion писал(а):
Привожу пример достаточно сложного судоку:

У меня получился с одной точкой перебора (догадкой). Кто-нибудь может без догадок?

Наш ответ Чемберлену:
    $$\begin{array}{|ccc|ccc|ccc|}\hline 
8&3&*&6&*&*&*&*&1\\ 
*&*&6&*&3&*&*&8&*\\
*&*&1&8&*&*&*&6&*\\ \hline 
*&*&*&9&*&*&*&4&*\\ 
*&*&3&*&7&*&2&*&*\\ 
*&7&*&*&*&5&*&*&*\\ \hline 
*&1&*&*&*&4&6&*&*\\ 
*&5&*&*&9&*&8&*&*\\ 
9&*&*&*&*&6&*&2&3\\ \hline  \end{pmatrix}$$

 Профиль  
                  
 
 
Сообщение07.02.2007, 15:22 
Аватара пользователя


15/11/06
2689
Москва Первомайская
2 Незваный гость

Скажите, а что известно про статистические свойства судоку? Сколько этих судоку вообще (какова их доля)? При каком количестве цифр в начальной композиции число судоку максимально? Каково среднее значение суммы цифр начальной композиции? И т.п.

Я вот попросту взял несколько судоку и попробовал суммировать цифры начальной композиции и каждый раз делить сумму на число этих цифр. Получается примерно 5, чуть больше или чуть меньше.

 Профиль  
                  
 
 
Сообщение07.02.2007, 19:28 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Сам ничего не считал, поэтому только ссылки:
Wikipedia
Science News Online — намного более скучная, но зато есть ссылки.

Вообще, гугл: sudoku math

По поводу Вашего наблюдения: в среднем должно быть 5. Все отклонения от этой величины связаны с психологией составителя. Резон прост: для каждого судоку корректным судоку останется и судоку, получающийся при любой замене цифр, в частности, $ d \leftrightarrow 10 - d$. Среднее у этих судоку отклоняется от 5 в противоположные стороны на одну и ту же величину. Поэтому, любое систематическое отклонение — результат влияния человека на обозначения (выбор цифр).

P.S. Говорят, эта судоку считается самой сложной: AI Escargot.

 Профиль  
                  
 
 
Сообщение08.02.2007, 17:52 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Замечание к статье в Wikipedia: там (да и в других местах) считают число полностью решенных судоку. Число задач нигде не встречал (да и вряд ли встречу).

Brukvalub писал(а):
Интересно было бы, на мой взгляд, оценить сверху и снизу сложность алгоритма решения судоку

Согласно Wikipedia, это NP-проблема.

 Профиль  
                  
 
 
Сообщение10.02.2007, 00:59 
Аватара пользователя


27/08/06
23
Я вас люблю :D :oops:

Сидел-сидел страдал фигнёй, поедал маслины и флудил на форумах. И тут, бац, интересную задачку подкинули.

Вобщем, вотъ моя прога для решения "судоку". Пока что сделал половину алгоритмов, ибо сложно. Скоро допишу. Пока что сложные судоку само врядли решит, но, если цифр известно много, то вполне может. Например, вот на этом сайте ( http://sudoku.bestcrosswords.ru/ ) на простой сложности решает всё.

Скачать можно с моего сайта: http://systemhalt.org/index.php?req=MakarovSudoku

Изображение

 Профиль  
                  
 
 
Сообщение10.02.2007, 04:06 
Аватара пользователя


27/08/06
23
Хы, дописал. Теперь прога решает любые. Не думал, что получится так просто. Ну да ладно :)

 Профиль  
                  
 
 
Сообщение10.02.2007, 16:35 
Заслуженный участник
Аватара пользователя


09/10/05
1142
NightmareZ

Cool, сайт очень понравился

 Профиль  
                  
 
 
Сообщение16.02.2007, 15:03 
Аватара пользователя


15/11/06
2689
Москва Первомайская
незваный гость писал(а):
Итого: нормальным считается решение судоку за 10–40 минут в зависимости от сложности.

Вчера в метро наблюдал, как женщина решает судоку. За 15 минут, пока я не вышел, она не сумела отгадать ни одной цифры, поставила только (карандашом) для пробы две смежные пары цифр. Однако задача у нее, по-моему, очень сложная: в начальной композиции я насчитал всего 17 цифр!

Добавлено спустя 5 минут 19 секунд:

Вот еще головоломка какуро, похожая на судоку.

http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D0%BA%D1%83%D1%80%D0%BE
http://mamadu.ru/games2/kakuro/index.htm

 Профиль  
                  
 
 
Сообщение16.02.2007, 20:10 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
geomath писал(а):
Однако задача у нее, по-моему, очень сложная: в начальной композиции я насчитал всего 17 цифр!

То, что весьма редкая — бесспорно. А вот сложная? — не знаю. По крайней мере сложность определяется не только и не столько количеством цифр. Хотя, чем меньше цифр, тем сложнее начинать...

 Профиль  
                  
 
 
Сообщение16.02.2007, 23:50 
Экс-модератор


12/06/05
1595
MSU
Судоку, предложенную Lion'ом, я решил с двумя или тремя точками перебора первого уровня (то есть, два или три раза я подбирал цифру в какой-то клетке, и она однозначно определялась). В общей сложности я затратил, наверное, пару часов, так что она была на тот момент самой сложной из тех, что я решал.

Потом настала очередь вот этой:
незваный гость писал(а):
Наш ответ Чемберлену:
    $$\begin{array}{|ccc|ccc|ccc|}\hline 
8&3&*&6&*&*&*&*&1\\ 
*&*&6&*&3&*&*&8&*\\
*&*&1&8&*&*&*&6&*\\ \hline 
*&*&*&9&*&*&*&4&*\\ 
*&*&3&*&7&*&2&*&*\\ 
*&7&*&*&*&5&*&*&*\\ \hline 
*&1&*&*&*&4&6&*&*\\ 
*&5&*&*&9&*&8&*&*\\ 
9&*&*&*&*&6&*&2&3\\ \hline  \end{pmatrix}$$

Я дорешал ее до конца в екселе (вручную), там очень удобно рассматривать различные варианты. Пожалуйста, проверьте ее кто-нибудь, потому что, насколько я помню, у меня получилось около восьми вариантов решения. При этом приходилось делать точки перебора вплоть до четвертого порядка, чтобы пройтись по всему дереву вариантов. К сожалению, я не сохранял решение, но два правильных ответа у меня вроде где-то валяются.

Цитата:
Однако задача у нее, по-моему, очень сложная: в начальной композиции я насчитал всего 17 цифр!

Да, это должно быть круто. В игрушке "Astraware Sudoku", которая у меня есть, на уровне Diabolical (самые сложные, я их в среднем минут за 45 решаю) порядка 25 цифр в первоначальной расстановке.

 Профиль  
                  
 
 
Сообщение20.02.2007, 14:51 
Аватара пользователя


15/11/06
2689
Москва Первомайская
А про какуро чего ничего не скажете?

 Профиль  
                  
 
 
Сообщение20.02.2007, 19:34 
Заслуженный участник
Аватара пользователя


26/11/06
696
мехмат
geomath писал(а):
Вот еще головоломка какуро, похожая на судоку.

http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D0%BA%D1%83%D1%80%D0%BE
http://mamadu.ru/games2/kakuro/index.htm

Лично мне какуро нравится меньше судоку, поскольку в судоку развивается наблюдательность и сообразительность, в то время как в какуро в основном необходим перебор.

 Профиль  
                  
 
 
Сообщение21.02.2007, 00:54 
Экс-модератор


12/06/05
1595
MSU
Dan_Te писал(а):
Я дорешал ее до конца в екселе (вручную), там очень удобно рассматривать различные варианты. Пожалуйста, проверьте ее кто-нибудь, потому что, насколько я помню, у меня получилось около восьми вариантов решения.

Нашел у себя ошибку, неправильно "списал условие".

 Профиль  
                  
 
 
Сообщение22.02.2007, 06:03 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Dan_Te писал(а):
Нашел у себя ошибку, неправильно "списал условие".

У меня есть решение (и я готов его продемонстрировать) с двумя точками ветвления. Но я и это считаю много. Правда, я плохо решаю.

 Профиль  
                  
 
 
Сообщение02.03.2007, 16:59 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Это пример из другой ветки.
Вот первый куплет Гимна РФ.

Россия — священная наша держава,
Россия — любимая наша страна.
Могучая воля, великая слава —
Твоё достоянье на все времена!

А вот его перевод на "язык цифр".
Спойте на музыка Гимна.

4 14 8 12
4 400 8 500
14 9 400 20
600 19 700 800

Однако перевод этот неединственный.
Вот еще вариант оттуда.

1 48 15 17
14 8 16 1!
12 15 14 20
11 40 141

Налицо неоднозначность.
Как ее устранить?
Ну, например, в духе судоку.

* 1* 8 12
* *00 8 5*0
1* 9 *0* 20
6*0 *9 70* 8**

Вместо * вставьте подходящую цифру,
необязательно одну и ту же.
Не знаю, будет ли теперь однозначность?
Можете привести пример посложнее?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 78 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group