6°C
завтра: 7°C
Погода в Перми
6°C
днем10°C
вечером9°C
завтра7°C
Подробно
 64,43
+0.3077
Курс USD ЦБ РФна 19 сентября
64,4290
+0.3077
 71,24
+0.6351
Курс EUR ЦБ РФна 19 сентября
71,2391
+0.6351
  • Есть такая игруха sudoku. Да знаете, в газетах в кроссвордах часто стали печатать: есть поле 9*9, разделенное на квадраты 3*3, надо расставить цифры от 1 до 9 так, чтобы в квадрате 3*3, на горизонтали и вертикали не было повторяющихся цифр.

    Вот задумал нарисовать для себя такую на компе (в газете скучно). Алгоритм генерации карты сделал, ничего сложного в нем нет. А вот теперь стоит задача закрыть (или открыть) цифры, чтобы был единственный путь решения. Словами коряво получается объяснить... Попробую... Надо закрыть ячейки так, чтобы "вычислялась" однозначно лишь пара-тройка, а при открытии одной "вычислялась" другая, то есть выстраивалась последовательная цепочка ходов, приводящая к решению.
    Простым рандомом открывать ячейки хреново - возникает масса неоднозначностей, что половину поля можно тупо открыть от фанаря, а судока все равно складывается, не интересно получается.
    Мож, кто сталкивался или сам делал подобное?

    эгоист - это человек, который думает в первую очередь о себе и только потом обо мне

  • задача нетривиальная, требует знания предмета :хехе:

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

    м.б. обсуждению поможет пример качественной (красивой) судоки ?

    >>>Come back to USS...A © >>>
    долой лицемерие!

    запустить ракету вокруг Америки может быть не менее сложно и полезно, чем когда-то вокруг Земли

  • Красивую судоку надо? Пожалуйте /нули - пустые клетки/:
    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 секунд

    эгоист - это человек, который думает в первую очередь о себе и только потом обо мне

  • Логически эта судока решается так:
    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
    И так делее...
    Как видно из примера, каждый ход приводит к возможности однозначного открытия одной или нескольких клеток, в которых до этого была неоднозначность.

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

    зы определение: однозначный вариант - либо в клетке может стоять только одна единственная некоторая цифра, либо в квадрате-вертикали-горизонтали некоторая цифра может стоять только в одном месте

    эгоист - это человек, который думает в первую очередь о себе и только потом обо мне

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

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

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

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

    Подбирайте себе Судоку по Вашему уровню

  • :agree: В судоку есть очень красивые способы решения.. Нифига на первый взгляд непонятные.
    Сам люблю залипать на самой высокой сложности, пусть долго, зато интереснее, чем тупо смотреть в каких рядах/строках есть одна и та же цифра.
    В ответ на: по всем линиям выходило не менее трех-четырех вариантов в каждой клетке
    Вот это я называю интересной задачей.

    Some folks like water, some folks like wine, but I like the taste of straight strychnine

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

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

  • Так вопрос и ставится о составлении

    эгоист - это человек, который думает в первую очередь о себе и только потом обо мне

  • Да, это тоже любопытно:улыб:Тут чистым рандомом не отделаешься имхо.

  • На последнего.

    Эта задача как раз из области искусственного интеллекта. Что касается решения, то прямой перебор вариантов тут крайне неэффективен особенно если изначально заполнено мало клеточек. Чтобы отсекать лишние вариантынеобходимы эвристики. Откуда их взять - ну, порешать довольно много самому, и тогда можно что-то сформулировать. Лично я для себя придумал несколько таких, которыми пользуюсь при ручном решении.
    Что же касается составления задач, то, возможно, лучший подход - сначала попытаться вручную составлять задачи (и, к примеру, предлагать их для решения окружающим). После сотни-другой задач у Вас уже сформируются какие-то типовые подходы, где как можно поступить. Пробуйте. :хехе:

  • 3-4 года назад делал программку для нахождения решения судоку 9x9. Решение было основано на рекурсии. С её помощью решение "газетной" судоку не занимало более секунды. А вот с определением минимального набора чисел на поле, для которого существует однозначное решение - задача сложнее.
    Допустим, есть поле, с начальным набором цифр. Начальное поле можно задать случайным образом, избегая нарушений правил. Далее производить проверку всех клеток поля на количество возможных вариантов. Проверку осуществлять по формализованным правилам. Клетку, где вариант единственный - оставить скрытой, где вариантов несколько - определить случайным числом из возможных. После каждой итерации - находить решение.

  • "Самый мудрый внешне во всём подобен самому глупому", народная китайская мудрость.

Записей на странице:

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

Модератор: