PRM.Форум /Компьютеры Интернет Связь / Программирование /

SUDOKU

Печать RSS Деревом

Picaro
гундос
Сообщений: 16286
02.10.09 14:15
Есть такая игруха sudoku. Да знаете, в газетах в кроссвордах часто стали печатать: есть поле 9*9, разделенное на квадраты 3*3, надо расставить цифры от 1 до 9 так, чтобы в квадрате 3*3, на горизонтали и вертикали не было повторяющихся цифр.

Вот задумал нарисовать для себя такую на компе (в газете скучно). Алгоритм генерации карты сделал, ничего сложного в нем нет. А вот теперь стоит задача закрыть (или открыть) цифры, чтобы был единственный путь решения. Словами коряво получается объяснить... Попробую... Надо закрыть ячейки так, чтобы "вычислялась" однозначно лишь пара-тройка, а при открытии одной "вычислялась" другая, то есть выстраивалась последовательная цепочка ходов, приводящая к решению.
Простым рандомом открывать ячейки хреново - возникает масса неоднозначностей, что половину поля можно тупо открыть от фанаря, а судока все равно складывается, не интересно получается.
Мож, кто сталкивался или сам делал подобное?
эгоист - это человек, который думает в первую очередь о себе и только потом обо мне
КопироватьСсылка
Рассказать друзьям
wobbler
v.i.p.
Сообщений: 11157
05.10.09 11:13Ответ на сообщение SUDOKU пользователя Picaro
задача нетривиальная, требует знания предмета

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

м.б. обсуждению поможет пример качественной (красивой) судоки ?
>>>Come back to USS...A © >>>
долой лицемерие!

запустить ракету вокруг Америки может быть не менее сложно и полезно, чем когда-то вокруг Земли
КопироватьСсылка
Рассказать друзьям
Picaro
гундос
Сообщений: 16286
05.10.09 13:57Ответ на сообщение Re: SUDOKU пользователя wobbler
Красивую судоку надо? Пожалуйте /нули - пустые клетки/:
130 070 000
000 000 008
000 009 405
800 000 000
000 060 100
004 000 029
008 310 000
400 000 000
007 000 604

Эта судока решается очень красиво за... у меня ушло 2 минуты 49 секунд
эгоист - это человек, который думает в первую очередь о себе и только потом обо мне
КопироватьСсылка
Рассказать друзьям
Picaro
гундос
Сообщений: 16286
05.10.09 15:06Ответ на сообщение Re: SUDOKU пользователя Picaro
Логически эта судока решается так:
1. однозначно открываются последовательно четверки в клетках (строка/столбец): 2/2, 7/6, 4/5, 1/4, 5/8
2. единицы: 8/9, 9/2, 4/3
3. восьмерки: 1/6, 3/2
4. пятерка: 1/3
И так делее...
Как видно из примера, каждый ход приводит к возможности однозначного открытия одной или нескольких клеток, в которых до этого была неоднозначность.

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

зы определение: однозначный вариант - либо в клетке может стоять только одна единственная некоторая цифра, либо в квадрате-вертикали-горизонтали некоторая цифра может стоять только в одном месте
эгоист - это человек, который думает в первую очередь о себе и только потом обо мне
КопироватьСсылка
Рассказать друзьям
Ananas
veteran
Сообщений: 1978
06.10.09 07:06Ответ на сообщение Re: SUDOKU пользователя wobbler
В ответ на: пришел к выводу, что разгадывать её нужно именно методом перебора - по всем линиям выходило не менее трех-четырех вариантов в каждой клетке, соответственно решать её можно было только прямым перебором (в процессе которого количество вариантов не уменьшалось, как требовал интеллект, а тупо росло в геометрической прогресии)... м.б. судока некачественная попалась...
Т.е., по Вашему, качественно и красиво - это когда тупо и быстро просчитываются все варианты?

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

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

Мне за 2 мин. - неинтересно и некрасиво

Подбирайте себе Судоку по Вашему уровню
КопироватьСсылка
Рассказать друзьям
Markovich
Man in Black
Сообщений: 24250
07.10.09 06:04Ответ на сообщение Re: SUDOKU пользователя Ananas
В судоку есть очень красивые способы решения.. Нифига на первый взгляд непонятные.
Сам люблю залипать на самой высокой сложности, пусть долго, зато интереснее, чем тупо смотреть в каких рядах/строках есть одна и та же цифра.

В ответ на: по всем линиям выходило не менее трех-четырех вариантов в каждой клетке
Вот это я называю интересной задачей.
Some folks like water, some folks like wine, but I like the taste of straight strychnine
КопироватьСсылка
Рассказать друзьям
Крыска
unreal
Сообщений: 119369
07.10.09 10:24Ответ на сообщение SUDOKU пользователя Picaro
Вариант решения судоку может быть не единственным... я сама наталкивалась несколько раз, когда можно было поставить в клетку одну цифру из возможных двух, а можно и другую, и сойдётся.
Причём, от сложности это не сильно зависело.

На мой взгляд, интереснее задача составлять правильную судоку, а не решать её.
Но могу ошибаться...
КопироватьСсылка
Рассказать друзьям
Picaro
гундос
Сообщений: 16286
07.10.09 13:12Ответ на сообщение Re: SUDOKU пользователя Крыска
Так вопрос и ставится о составлении
эгоист - это человек, который думает в первую очередь о себе и только потом обо мне
КопироватьСсылка
Рассказать друзьям
BWhite
veteran
Сообщений: 1291
08.10.09 11:49Ответ на сообщение Re: SUDOKU пользователя Picaro
Да, это тоже любопытноТут чистым рандомом не отделаешься имхо.
КопироватьСсылка
Рассказать друзьям
wowik_2
activist
Сообщений: 109
08.10.09 12:53Ответ на сообщение Re: SUDOKU пользователя BWhite
На последнего.

Эта задача как раз из области искусственного интеллекта. Что касается решения, то прямой перебор вариантов тут крайне неэффективен особенно если изначально заполнено мало клеточек. Чтобы отсекать лишние вариантынеобходимы эвристики. Откуда их взять - ну, порешать довольно много самому, и тогда можно что-то сформулировать. Лично я для себя придумал несколько таких, которыми пользуюсь при ручном решении.
Что же касается составления задач, то, возможно, лучший подход - сначала попытаться вручную составлять задачи (и, к примеру, предлагать их для решения окружающим). После сотни-другой задач у Вас уже сформируются какие-то типовые подходы, где как можно поступить. Пробуйте.
КопироватьСсылка
Рассказать друзьям
RT8
junior
Сообщений: 5
18.10.09 23:45Ответ на сообщение Re: SUDOKU пользователя wowik_2
3-4 года назад делал программку для нахождения решения судоку 9x9. Решение было основано на рекурсии. С её помощью решение "газетной" судоку не занимало более секунды. А вот с определением минимального набора чисел на поле, для которого существует однозначное решение - задача сложнее.
Допустим, есть поле, с начальным набором цифр. Начальное поле можно задать случайным образом, избегая нарушений правил. Далее производить проверку всех клеток поля на количество возможных вариантов. Проверку осуществлять по формализованным правилам. Клетку, где вариант единственный - оставить скрытой, где вариантов несколько - определить случайным числом из возможных. После каждой итерации - находить решение.
КопироватьСсылка
Рассказать друзьям
tpi
guru
Сообщений: 8043
02.12.09 00:07Ответ на сообщение SUDOKU пользователя Picaro
Поиск рулит -

http://archive.ubuntu.com/ubuntu/pool/universe/s/sudoku/sudoku_1.0.1.orig.tar.gz
"Самый мудрый внешне во всём подобен самому глупому", народная китайская мудрость.
КопироватьСсылка
Рассказать друзьям

PRM.Форум /Компьютеры Интернет Связь / Программирование /

Перейти в форум

открыть в новом окне

Модератор:

flopic