?

Log in

No account? Create an account
необычное судоку - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

необычное судоку [янв. 4, 2015|06:41 pm]
Anatoly Vorobey
[Tags|]

Программист и криптограф Бен Лори сказал как-то: "Судоку - это DoS-атака на человеческий интеллект".

Сегодня я потратил часа два на вот этот необычный вариант, но все же решил:

sudoku-empty
(можно нажать и получить размер больше)

Как в обычном судоку, нужно заполнить доску цифрами от 1 до 9, так, чтобы в каждой строке, каждом столбце, и каждом из девяти квадратов 3x3 цифры не повторялись. В отличие от обычного судоку, здесь нет заранее заполненных цифр, зато даны отношения больше-меньше внутри каждого из девяти квадратов 3x3. Решение есть, причем единственное. Приятного времяпровождения :)
СсылкаОтветить

Comments:
[User Picture]From: grundik
2015-01-04 07:24 pm
Пожалуйста, приведите пример программы, которая решает вот это вот судоку.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2015-01-04 08:18 pm
перестановок девяти чисел несколько десятков тысяч, неравенства из условия уменьшают это число на порядки, так что всё это с лёгкостью перебирается; совершенно не понимаю, зачем такой фигнёй страдать, когда действительно написать программу проще (и в некотором смысле приятнее)
(Ответить) (Parent) (Thread)
[User Picture]From: _winnie
2015-01-04 09:41 pm
Пример программы, или не верю!
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2015-01-04 10:52 pm
если ваши навыки программирования составляют хотя бы один процент вашего же ЧСВ, то вы запросто эту программу самостоятельно напишете
(Ответить) (Parent) (Thread)
[User Picture]From: _winnie
2015-01-04 11:49 pm
Напишу, но сомневаюсь, уложусь ли я в 2 часа за которые задачу решил avva
(Ответить) (Parent) (Thread)
[User Picture]From: grundik
2015-01-05 10:37 am
Я, как стартер треда, просил просто дать программу. Я в программировании с 91 года, я читаю Норвига, я знаю, что написать можно. Об этом рассуждать совершенно неинтересно.

Интересно, что из всех людей, которые говорят "да проще написать", привёл решение только ОДИН (плюс автор журнала упомянул, что он доработал чужое решение).
(Ответить) (Parent) (Thread)
From: ilyakor
2015-01-05 04:12 pm
Программа (в "олимпиадном" стиле, написана с нуля за 7 минут, + ещё ~5 минут на вбивание знаков <> с картинки): http://ideone.com/8mKZAk

Почему все так недооценивают возможности написания говнокода на скорость...

Edited at 2015-01-05 16:13 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
ой.. - (Анонимно) Развернуть
[User Picture]From: ftqkatel
2015-01-05 07:24 am
интересно, какой алгоритм перебора здесь будет самым эффективным. Генетический?

но это конечно не отвечает на первостепенный вопрос )
(Ответить) (Parent) (Thread)
[User Picture]From: hyperpov
2015-01-04 08:35 pm
Не проблема написать.
(Ответить) (Parent) (Thread)
[User Picture]From: grundik
2015-01-05 10:31 am
Не проблема и решить.

В комментах один вариант уже предложили, и ещё один от avva (но он читор, не с нуля).

Вы программу дайте, чо рассуждать-то.
(Ответить) (Parent) (Thread)
[User Picture]From: obill
2015-01-04 08:55 pm
12*9 неравенства +
27 точных равенств
для 81 переменной на множестве целых чисел от 1 до 9.

Это можно и Матлабом решить. Или другими универсальными решалками.

Но можно и мозгом. Что сейчас и попробуем.
(Ответить) (Parent) (Thread)
[User Picture]From: obill
2015-01-04 10:49 pm
Не так уж и сложно оказалось.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2015-01-04 09:13 pm
Я сейчас любопытства ради добавил немного некрасивого кода к красивому решателю Норвига (http://norvig.com/sudoku.html), и программа легко нашла решение. Это не очень сложно.
(Ответить) (Parent) (Thread)
[User Picture]From: kit1980ukr
2015-01-05 05:57 am
Я решил при помощи constraint logic programming: http://sdymchenko.com/blog/2015/01/04/greater-than-sudoku-clp/
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2015-01-05 08:17 am
Очень мило, спасибо!
(Ответить) (Parent) (Thread)