Menu GrandGames.net
Русский
⍆ ⛹ ⎕ ⌕

Чего-то я не понимаю... Какой тут ход...

3g600 Был два часа назад Likes39 Messages515 5 Solver Rank
! /sudoku/id/9366 #213047 2018-01-27 18:52
Чего-то я не понимаю... Какой тут ход?
-
Нравится + 0     16   Поделиться
Veterok Online 6 Solver Rank 2018-01-28 17:25 + 0
SPOILER
самый явный - пятерка в а5, потому что шестерка в этом квадрате может быть только в b6 и с6
3g600 Был два часа назад 5 Solver Rank 2018-01-28 20:37 + 0
Спасибо. Я думал, что этот прокол в своей программе устранил, но...
1. В каждой правильно работающей программе есть по крайней мере одна ошибка.
2. После исправления ошибки см. п. 1.
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2018-02-02 11:33 + 1
Я теперь могу думать, что решаю как программа - тоже вечно пропускаю запертых кандидатов :D
Мне тут вдруг стало любопытно... А программа х-крылья, рыб-мечей, мудуз и прочее подобное ищет?
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2018-02-02 12:27 + 1
Не, программа 3g600, которая запертых кандидатов пропускала :)
Мне интересны алгоритмы поиска групп. Когда я свою программу-решалку писала - то у меня получилось, что голые группы, скрытые группы и крылато-водный зверинец ищется одним алгоритмом. Честно говоря, для меня это было неожиданно :) Я искала способ, как настроить алгоритм, чтобы он искал от крыльев (размерность 2) до групп размерности 4 (5 и более уже не надо, 5 комбинируется с рыбой-мечом (3) при отсутствии рассматриваемых чисел на поле, поэтому достаточно найти только рыбу-меч) и чтобы все быстро. И все получилось под одну гребенку. От этого возникло два вопроса: можно ли еще каким-либо образом обработать игровое поле тем же алгоритмом, чтобы родился новый метод исключения чисел и насколько эффективно получается решение, в ходе которого по цать раз особым образом собирается массив данных, далее этот массив обрабатывается еще несколькими циклами. Я боюсь считать O(f(n)) от этого безобразия, хотя с точки зрения тренировки подсчета сложности это прекрасная задача - заковыристая, с кучей циклов, условий и с обходом массива путем дерганья указателя туда-сюда, вместо простого обхода от и до, чтоб неповадно было считать сложность. Ну и написав эту гору кода я прекратила видеть другие пути решения, хотя подозреваю, что они существуют. И вот другие пути решения меня и интересуют ^_^'
3g600 Был два часа назад 5 Solver Rank 2018-02-02 12:37 + 0
@nekonyash: я тоже. Найти запертый (последний? точечный?) кандидат труднее всего. Но, справедливости ради, надо сказать, что его поимка редко дает какой-либо эффект: по определению, он не генерирует новых ограничений, разве что иногда, при особом стечении обстоятельств.

@Memo Много раз замечал, что официальный анализатор пропускает четверки и выше.
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2018-02-02 12:43 + 1
@3g600 Запертые кандидаты все равно могут дать ход последующему решению, как и любое снятие кандидата. Только тут проблема в сложности поимки этих кандидатов, игра не всегда стоит свеч >_>
И все же мой вопрос о поиске вашей программой водно-крылатой живности остается открытым.
3g600 Был два часа назад 5 Solver Rank 2018-02-02 15:35 + 1
Я не вполне прилежно овладел общепринятой терминологией, поэтому могу ошибаться. Я изначально принял, что голые и скрытые группы - это, в принципе, одно и то же, и поиск голой тройки равносилен поиску скрытой шестерки и наоборот. А поскольку число сочетаний n элементов из m равно числу сочетаний m-n элементов из m (бином Ньютона), то перебрать все возможные шестерки (в пустом квадрате) по трудозатратам равнозначно перебору всех возможных троек.
Поэтому я реализовал только один вид поиска - от двоек до семерок. Зверинец же, как я понимаю, это не принципиально новые приемы, а тот же поиск групп, только, благодаря некоторым особенностям позиции более эффективный. Но размерность задачи невелика, так что заморачиваться на эту тему я не стал.
Ниже по уровню стоят линейные ограничения и поиски последних кандидатов, выше - алгоритм, основанный на презумпции единственности решения (крылья?). Он у меня реализован не до конца. Но я знаю, что и как надо делать, и поэтому стало неинтересно, творчества там осталось мало, сплошное скрупулезное программирование. То же самое и с цепочками. Тут вообще становиться трудно отделить логику от подбора: какая глубина еще считается логикой, а какая - подбором? И это все.
Коллега, если Вы видите мою ограниченность (принципиальную), то посоветуйте, что почитать: только не "такую-то статью", а конкретно про такой-то прием, который мне неведом - я все-таки остаюсь на любительском уровне и писать статью в мат. журнал не собираюсь.
Меня сейчас занимает другая задача - не решение, а составление судоку. Никаких логических приемов я придумать не могу; скорее всего берется решенный судоку и последовательно случайно удаляются цифры с последующей проверкой на единственность решения - как только решение становится неединственным, судоку готов. Если ничего более вразумительного не существует, то это тоже неинтересно.
Кроме того, генерить новые судоку можно путем перестановок V/H внутри троек V/H и переобозначения цифр, напр., (abc/def/ghi) -> (cba/dfe/igh) и т.д. Возможно, что тысячи опубликованных судоку на самом деле распадаются на дюжину-другую семейств, хотя и вряд ли.
Но зато у меня есть сильные подозрения, что составитель публикуемых на сайте задач играет с цифрами. Процесс решения обычно ведь начинается с того, что ищутся линейные ограничения для цифры 1, потом - для 2, 3 и т.д. Можно переобозначать цифры таким образом, чтобы максимально замедлить поиск (напр, после сделанного хода с цифрой 7 следующий ход д.б. с цифрой 6). С некоторых пор я начинаю решение с поиска хода с цифрой 9, потом - 8 и т.д.
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2018-02-02 16:48 + 1
По поводу голых и скрытых - вы абсолютно правы. Но я ставила задачу эмулировать человеческий поиск для возможности последующего расчета сложности, а люди обычно охотнее находят скрытую двойку, чем голую шестерку. Хотя тут зависит от людей. Так что расчет сложности судоку - это вообще отдельная тема, где нужно много экспериментов.

Зверинец - это такие штуки:
SPOILER
Х-крыло:
-


Рыба-меч:
-


Для 4 строк/столбцов - медуза.

Эти методы крайне редко встречаются, еще более редко дают ход решению. Но все же встречаются судоку, где надо найти такую группу, поэтому я внедряла в свои алгоритмы поиск этих групп.
На счет эффективности - по моему, не эффективно... В группе можно пробежать по одной строке, определить, есть там или нет группа, если есть - удалить лишних кандидатов и идти применять более легкие методы. А в зверинце так как рассматриваются кандидаты лишь одного числа, но на всем поле - то приходится сначала пройтись по всем числам всего судоку, составить 9 массивов позиций на каждое число, а по завершению пройтись по всем этим массивам с поиском групп. Даже если группа будет найдена на первом числе, я все равно прошлась по всем кандидатам всего судоку, а это уже долго.
Я тут еще подумала, что можно подумать о увеличении производительности решателя, если составлять отдельно массив задействованных клеток и искать всеми методами конкретно в участвующей строке/столбце/квадрате/числу, а не бегать каждый раз заново по всему судоку...
Все же мне в первую очередь интересна задача составления максимально эффективных алгоритмов. Эта задача и математична и интересна и практически бесконечна х_х

Алгоритм, основанный на презумпции единственности я не реализовывала, так как по плану должна была быть одновременно проверка на единственность решения. И это не х-крыло, а как называются выводы из единственности я не знаю... В моем "кратком руководстве по решению судоку" в программке это названо "Unique Rectangle Type 1":
SPOILER
-


Вообще, в этой программке на андроид есть коротенькие заметки по решению. Если сесть со словариком и немного повникать, то можно повысить свой уровень. Вот ссылка, если нужно: https://play.google.com/store/apps/details?id=com.coolandroidappzfree.freesudoku&hl=ru


А решение через цепочки я пока сама не осознала на математически должном уровне, чтобы их реализовать =_= Хочется везде и всюду. И судоку анализатор написать классный и 100500 сложных разнообразных судоку решить и методы изучить и еще вагон и маленькая тележка разнообразных задач не связанных с судоку, но не менее нужных/интересных ._.

Про составление судоку, я читала пост на хабре: https://habrahabr.ru/post/192102/ Правда к написанию своего генератора так и не приступила. В теории, если составление судоку вручную - это совсем другой процесс, в котором можно задавать ход решению. Но и этот процесс я не освоила ._.
3g600 Был два часа назад 5 Solver Rank 2018-02-02 18:25 + 1
Смотрите: у меня в программе специальной ветви для "зверинца" нет, но тройки на g9 и g7 она по ходу отсекла.
-


Вам, наверное, будет интересно, вот основной массив:
-


Думаю, программисту все понятно, одно замечание: "х" - цифра, стоящая на i-м поле строки может стоять на данном поле, "q" - обязана стоять на этом поле или на поле в том же квадрате с тем же символом q. Так что, действительно, "зверинец" - это несамостоятельные методы.
Вот здесь у меня как раз и произошел прокол в программе. Изначально планировалось вместо q использовать v и h - в зависимости от того, по V или H должна стоять цифра. Потом я решил, что в квадрате она не может быть одновременно и по V, и по H, и сократил, таким образом, длину проверок:
nxq = IIf(Mid(A(nh, na), nz, 1) = "x", na, 0) + IIf(Mid(A(nh, na), nz, 1) = "q", na, 0)
Действительность оказалась сложнее.
По поводу расчета сложности - мой подход его не ограничивает. Если программа нашла голую семерку, то в расчет сложности надо записать нахождение скрытой двойки. Можно даже на печать выводить то, что меньше по рангу.
По поводу алгоритма, основанного на презумпции единственности решения. Это очень мощный прием. В программе он включается только тогда, когда линейные группы заканчиваются, а вот решая вручную, я его часто использую, как говорится, на ровном месте - когда, например, в столбце остаются 2 пустых поля - проверяю, нет ли параллельно двух подходящих пустых полей. И часто (наверно, в 20% судоку) такое встречается. Причем часто это не единственное продолжение, зато эффективное. Я заметил, многие игроки не освоили этот прием, или же считают его некорректным. На самом деле, он вполне корректен - игрок вправе использовать все условия задачи.
По поводу цепочек. Тут вполне будет работать алгоритм, схожий с алгоритмом поиска кратчайшего пути в лабиринте методом волны.
Очень интересно и приятно с Вами общаться.
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2018-02-07 17:04 + 1
"Очень интересно и приятно с Вами общаться."

Спасибо *^_^* Я, правда, умудрилась пропасть на 4 дня - заболела. Но я восстала и могу продолжить дискуссию :)

Да, массив мне понятен :) Я делала совсем не так, смотрела на свое творчество, понимала, что что-то не так, но не могла сказать, что :D Теперь понимаю. Мои вложенные ассоциативные массивы никуда не годятся, буду их выкидывать, как руки дойдут :)

Тройки на g9 и g7 были отсечены как запертые кандидаты в квадрате (клетки g4 и g6). Но если бы (ну допустим), в клетках h5 или i5 была тройка, то это уже не было бы запертым кандидатом, но при этом b6, g6 и b4, g4 образовали бы крыло (в строке 4 и 6 нет больше троек, кроме этих четырех клеток) и все равно можно было бы удалить тройки с g9 и g7. Но, по факту, крыло играет свою решающую роль редко, рыба меч - еще реже, а медуза встречается просто фантастически редко. Но помнится, как-то раз я нашла рыбу-меч в тупике - от радости по квартире прыгала даже не дорешав судоку. Все же редко этот зверинец встречается :)

По поводу x и q - я не думала сразу вносить аналитику ситуации в запись текущей расстановки кандидатов... Я делаю аналитику на ходу по конкретным методам, даже не пользуясь понятиями что и где стоять обязано... Хотя когда решаю вручную сложные судоку - все время пытаюсь удержать в голове какие числа и где стоять обязаны, только мозгоресурсов на весь судоку не хватает :) А в программе как используются эти понятия?
По поводу действительности, в судоку три измерения - это строки, столбцы и квадраты. Очевидно то, что любой метод или способ анализа судоку, применимый к строке, так же применим к столбцу (доказательство через транспонирование). Но практика показывает, что этот же метод/способ так же применим и к квадрату (доказательства нет, надо подумать над этим). То есть, если есть число, которое обязано стоять в клетке A или B, находящиеся на одной строке, то почему не может быть ситуации, что есть число, которое обязано стоять в клетке C или D, при том, что C и D не находятся в одной строке или в одном столбце, но находятся в одном квадрате? При чем число в конкретной ячейке в теории может быть связано по всем трем осям. Выключение этого числа означает расстановку трех других чисел, а включение - исключение остальных кандидатов. Учитывая сложность отслеживания и записи всех этих связей - стоит ли игра свеч? Какой выигрыш дает этот подход?

По поводу цепочек - да, действительно. Тут нужно найти путь к ячейке, запустившей волну (так сказать, нужно, чтобы змея укусила себя за хвост), если будет достигнуто противоречие - то это джекпот и исключение кандидата. А найти путь > 2 шагов из точки А в точку А - вполне себе конкретная задача. Если еще брать для составления цепей только ячейки, где по 2 кандидата, то становится еще проще.
3g600 Был два часа назад 5 Solver Rank 2018-02-08 23:19 + 1
Вы правы. Я сконструировал позицию, о которой Вы говорите, и программа не вычеркнула троечки на g7 и g9.
Но как не хочется писать отдельные алгоритмы для всяческих зверей! Это уже не программа, а новогодняя елка, неизящно, но пока никаких мыслей нет.
Короче, вызов принят.
Подскажите, могут ли быть крылья, располагающиеся не в двух, а в четырех квадратах?

>>А в программе как используются эти понятия?
Если в строке/столбце x заменяется на q, то в этой же строке/столбце все х заменяются нулями.

>>метод/способ так же применим и к квадрату
Кажется, неприменим.


-


>>Если еще брать для составления цепей только ячейки, где по 2 кандидата
Я вот тоже: написать-то написал про алгоритм волны, а потом подумал, а что делать, если на поле не 2, а больше кандидатов? разрешить волне проходить через поле несколько раз? И какие тогда должны быть рабочие массивы? А потом придумал:
- если на поле 2 кандидата - все ОК, один убивается, а волна приходит на это поле
- если >2 - один кандидат убивается, но волна на это поле не идет. Как будто там остров с горой, и высота этой горы уменьшается на 1.
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2018-02-09 09:54 + 1
>> Подскажите, могут ли быть крылья, располагающиеся не в двух, а в четырех квадратах?
Да, это и есть медуза.
По поводу зверинца, посмотрите на ситуацию со следующей стороны:
Скрытая группа - N чисел, которые располагаются в N ячейках на одной строке/столбце/квадрате и нигде в столбце/строке/квадрате, кроме этих ячеек.
Голая группа - N ячеек в одной строке/столбце/квадрате, в которых располагаются N чисел и нет ни одного числа, кроме этих.
Зверинец - N строк, в которых определенное число располагается в N столбцах и в этих строках более нет ни одного числа, кроме тех, расположены в указанных столбцах (в примере с 3 и b6, g6, b4, g4 строки 6 и 4, числа располагаются в столбцах b и g, в других столбцах на троек нет => группа).
И транспонировано - N столбцов, в которых определенное число располагается в N строках и нигде более.

По поводу остального - надо подумать.
3g600 Был два часа назад 5 Solver Rank 2018-02-09 09:55 + 1
>>Если в строке/столбце x заменяется на q, то в этой же строке/столбце все х заменяются нулями.
Пытаюсь разобраться в собственной программе: а почему нельзя было сразу проставить нули, без промежуточных q? Какие-то еще проверки идут, непонятные.
В общем, все надо переписывать.
nekonyash Был несколько месяцев назад (2018-12-09 23:00:06) P E 19 Solver Rank 2018-02-09 10:19 + 1
>> В общем, все надо переписывать.
О, у нас на работе недавно поднялся вопрос о том, что программисты вечно хотят все переписать, на что один из наших админов заявил, что просто мы старые баги править не любим, а любим создавать новые баги :D
У меня, в общем-то, тоже надо все переписать. Кроме ядра алгоритма вычисления групп и зверинца. Хотя я тут подумала... Много разных методов, хоть у них и можно вычленить суть и объединить множество с виду разных методов в один механизм, все равно получается несколько разных способов анализа судоку, которые применяются последовательно. Единый механизм - это проставили число, исключили кандидатов, проверили на наличие противоречий. То есть - подбор с малой глубиной. Все методы - это подбор с малой глубиной нахождения противоречия. Все описания признаков метода нужны для того, чтобы при решении вручную было легче находить где исключать кандидатов и не думать о том, что мы исключаем число потому, что если его туда подставить - то можно увидеть противоречие. Мы видим "О, голая группа, удалю лишних кандидатов". Это быстрее, но суть-то везде одна.
nettaly Online P E 25 Solver Rank 2018-02-09 16:10 + 1
Это не баги, это фичи ignat
3g600 Был два часа назад 5 Solver Rank 2018-02-10 18:09 + 1
>> Все методы - это подбор с малой глубиной нахождения противоречия.
Ну да. Вопрос только, где кончается логика, и где начинается подбор. Группы, единственность, зверье - это все доступно человеку. Отдельно - цепочки. Человек может протянуть цепочку на 6-8 ходов, тогда это логика. Если, конечно, он не гроссмейстер. Но гроссмейстеру, наверно, решать судоку неинтересно, разве что одновременно 32 и вслепую.
Каждый судоку должен быть решаем логически. В противном случае смысла в нем не вижу. Следовательно, составитель должен иметь в своем распоряжении программу, которая это проверит.

Ваша новая идея мне понятна. Запускать цепочки ограниченной глубины (6-8) со всех полей, отслеживая исчезновение единственных кандидатов во всех Q/H/V и потом выбирать из них минимальную. Все линейные ограничения и весь зверинец точно найдется. А вот ограничения, накладываемые большими группами, или такими, которые немедленно не реализуются - вряд ли. Единственность - точно нет: условие единственности никак не связано с правилами размещения цифр, точнее, связано косвенно. Этого условия в задаче могло бы и не быть.
Нравится ли Вам новая игра "Перевертыши"
Да
Еще не пробовал
Нет
Sinicin62 gst4198905
22yjz belyak62
LauraMenshikova mumof
babyshka62 rof23
posadistka 478
dikey753 gst9194925
pelican mikl
gst6907763 k336665627
oxoxox Mungojerry
olenenok Key28
Новое на сайте
Пятнашки №61650
Какуро №61653
Хитори №61559
Японская мозаика №61554
№61534
№61616
№59888
№61624
№61628
№61646
№54467
Ключворды №60447
Филиппинский №61511
№61636
№61652
№61654
Японский кроссворд №28353
Пазл №28868
Судоку №21181
Флеш игра №2153
Денди онлайн №5686
Шахматная задача №9699
Филворд №6861
Загадка №361
ADB finder
Реклама Ads Google Yandex
:)