Здравствуйте, уважаемые эксперты! Предлагаемый к рассмотрению вопрос исходит из небезызвестного карточного пасьянса "Клондайк", который известен широкому кругу людей благодаря игре "Косынка"; ясно, что стоящая в основе задача является NP-полной, и нахождение общего правильного решения может быть получено полным перебором с некоторыми оптимизациями; на практике это выражается в том, что последовательность очевидных ходов не всегда может привести к верному решению
Изначально суть вопроса состояла в том, являются ли все предполагаемые в сей игре расклады решаемыми? Если имеется возможность проходить один расклад только один раз, то очевидно что вероятность выигрыша далека от единицы, однако при наличии возможности отката назад на произвольное число шагов, вероятность решения задачи резко возрастает, поскольку становится известным, какие ходы необходимо переделать для достижения глобального решения
Имея возможность отката на произвольное число ходов назад, любой потенциально решаемый расклад должен разрешаться; следующий пример демонстрирует, что далеко не любой расклад косынки разрешим
В предложенном примере расклада видно, что все стопки карт, кроме самой правой, являются открытыми, а в верхней колоде имеется только одна карта - пятерка бубен; валет бубен, на который указывает стрелка, был расположен на своей позиции с самого начала расклада пасьянса; это говорит о том, что обе черных дамы расположены ровно под ним в колоде, и решить предложенный расклад не представляет никакой возможности
Из вышеуказанного следует, что классическая "Косынка" не обеспечивает гарантии возможности верного расклада для генерируемой комбинации карт
Внимание вопрос: возможно ли осуществить создание такого генератора раскладов для пасьянса "Клондайк", который без предварительного решения соответственной NP-задачи расклада карт, определяет, возможно ли гарантированно разложить сгенерированную комбинацию карт, или хотя бы сделать оценку с очень высокой вероятностью, более 99.99%
P.S. Вопрос навеян в том числе и тем фактом, что для пасьянса "Свободная ячейка" имеется вероятностный анализ раскладов, который можно найти в русско- и англоязычных источников, в то время как для "Клондайка" таковой информации нет, и хотелось бы разобраться с материальной частью сего пасьянса более подробно
