Wpisz
⎕ ⍆
X

Wpis #213047

3g600 21
2018-01-27 18:52
Чего-то я не понимаю... Какой тут ход?
-

Polub + 0     16
Veterok 29  2018-01-28 17:25 + 0
SPOILER
самый явный - пятерка в а5, потому что шестерка в этом квадрате может быть только в b6 и с6
3g600 21  2018-01-28 20:37 + 0
Спасибо. Я думал, что этот прокол в своей программе устранил, но...
1. В каждой правильно работающей программе есть по крайней мере одна ошибка.
2. После исправления ошибки см. п. 1.
nekonyash 36  2018-02-02 11:33 + 1
Я теперь могу думать, что решаю как программа - тоже вечно пропускаю запертых кандидатов :D
Мне тут вдруг стало любопытно... А программа х-крылья, рыб-мечей, мудуз и прочее подобное ищет?
nekonyash 36  2018-02-02 12:27 + 1
Не, программа 3g600, которая запертых кандидатов пропускала :)
Мне интересны алгоритмы поиска групп. Когда я свою программу-решалку писала - то у меня получилось, что голые группы, скрытые группы и крылато-водный зверинец ищется одним алгоритмом. Честно говоря, для меня это было неожиданно :) Я искала способ, как настроить алгоритм, чтобы он искал от крыльев (размерность 2) до групп размерности 4 (5 и более уже не надо, 5 комбинируется с рыбой-мечом (3) при отсутствии рассматриваемых чисел на поле, поэтому достаточно найти только рыбу-меч) и чтобы все быстро. И все получилось под одну гребенку. От этого возникло два вопроса: можно ли еще каким-либо образом обработать игровое поле тем же алгоритмом, чтобы родился новый метод исключения чисел и насколько эффективно получается решение, в ходе которого по цать раз особым образом собирается массив данных, далее этот массив обрабатывается еще несколькими циклами. Я боюсь считать O(f(n)) от этого безобразия, хотя с точки зрения тренировки подсчета сложности это прекрасная задача - заковыристая, с кучей циклов, условий и с обходом массива путем дерганья указателя туда-сюда, вместо простого обхода от и до, чтоб неповадно было считать сложность. Ну и написав эту гору кода я прекратила видеть другие пути решения, хотя подозреваю, что они существуют. И вот другие пути решения меня и интересуют ^_^'
3g600 21  2018-02-02 12:37 + 0
@nekonyash: я тоже. Найти запертый (последний? точечный?) кандидат труднее всего. Но, справедливости ради, надо сказать, что его поимка редко дает какой-либо эффект: по определению, он не генерирует новых ограничений, разве что иногда, при особом стечении обстоятельств.

@Memo Много раз замечал, что официальный анализатор пропускает четверки и выше.
nekonyash 36  2018-02-02 12:43 + 1
@3g600 Запертые кандидаты все равно могут дать ход последующему решению, как и любое снятие кандидата. Только тут проблема в сложности поимки этих кандидатов, игра не всегда стоит свеч >_>
И все же мой вопрос о поиске вашей программой водно-крылатой живности остается открытым.
3g600 21  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 36  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 21  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 36  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 21  2018-02-08 23:19 + 1
Вы правы. Я сконструировал позицию, о которой Вы говорите, и программа не вычеркнула троечки на g7 и g9.
Но как не хочется писать отдельные алгоритмы для всяческих зверей! Это уже не программа, а новогодняя елка, неизящно, но пока никаких мыслей нет.
Короче, вызов принят.
Подскажите, могут ли быть крылья, располагающиеся не в двух, а в четырех квадратах?

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

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


-


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

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

Ваша новая идея мне понятна. Запускать цепочки ограниченной глубины (6-8) со всех полей, отслеживая исчезновение единственных кандидатов во всех Q/H/V и потом выбирать из них минимальную. Все линейные ограничения и весь зверинец точно найдется. А вот ограничения, накладываемые большими группами, или такими, которые немедленно не реализуются - вряд ли. Единственность - точно нет: условие единственности никак не связано с правилами размещения цифр, точнее, связано косвенно. Этого условия в задаче могло бы и не быть.
Jeśli znajdziesz niedokładne lub błędne tłumaczenie elementów interfejsu witryny, zgłoś: @GrandGames
#608774
@GrandGames
Открыт новый раздел головоломок...
🗓️ 👍 20 ✍️14
#608486
@GrandGames
Открыт новый раздел Ежедневные головоломки : https...
🗓️ 👍 16 ✍️6
#607326
@Vovka.
Свершилось и мне Артефакт в Ежедневном призе пришёл!
🗓️ 👍 13 ✍️10
:)
Przywróć zminimalizowane okno
Close