Существует ошибочное мнение, что пасьянс «Косынка» сходится всегда. Я думаю, вызвано это версией в ОС Windows, в которой расклады уже заложены, а не генерируются каждый раз.
Вопрос сходимости возник при создании сайта с пасьянсами, для которого нужны были расклады, выдаваемые пользователям. Для начала мы решили написать один из самых простых и распространенных вариантов игры — «Косынку» и не найдя готовую базу, стали генерировать случайные расклады. Написав JS код для игры мы обнаружили, что сходятся случайные расклады очень редко. На ~50 игр у нас сошлась только одна. Подсовывать пользователям пасьянс, который не сходится — не самый удачный вариант для сайта, поэтому стали искать пути выхода.
Выход первый — это забрутфорсить случайный расклад и определить сходимость. Помимо сложности алгоритма этот вариант еще и требовал каких-то неимоверных вычислительных мощностей, примерно, как обсчет партии в шашки. (В среднем пасьянс сходится за чуть более 100 ходов, при этом в процессе игры не всегда нужно выкладывать на стол карту). Этот вариант отпал.
Тогда решили написать правила для генератора пасьянса, посчитав что это будет более простой путь. Напомню, что в «Косынке» участвует 52 карты от двойки до туза 4-х мастей. Закрыты на столе в 7 стопках 21 карта, открыты на столе 7 и 24 карты в колоде, которую можно крутить. Нас интересуют для обсчета карты, которые в колоде и уже открытые на столе (всего 31 карта), т.к. именно ими игрок оперирует.
Правило при генерации добавили такое — среди карт в колоде и открытых на столе (31 карта) должна быть одна полная комбинация красных карт от двойки до туза и одна комбинация черных карт от двойки до туза. После применения такого правила генератор стал выдавать 1 из 150 раскладов удовлетворяющих условию (149 соответственно откидывал).
Сходимость таких раскладов резко повысилась и стала ~90% (по данным на 10.000 раскладов — 979 не сошлось ни разу, 9021 сошлось). Проверить такое количество раскладов нам помог краудсорсинг и наши пользователи, которые играли в «Косынку».
P.S.: Мы пробовали разные правила применять при генерации, но расклады получались либо совсем простые и играть в них было не интересно (когда генератор выдавал нам 1 расклад из 1.000), либо их сходимость не поднималась до приемлемых значений. Спасибо за потраченное время и если Вы знаете правило (универсальный алгоритм) определения сходимости — буду рад прочитать про него.
Вопрос сходимости возник при создании сайта с пасьянсами, для которого нужны были расклады, выдаваемые пользователям. Для начала мы решили написать один из самых простых и распространенных вариантов игры — «Косынку» и не найдя готовую базу, стали генерировать случайные расклады. Написав JS код для игры мы обнаружили, что сходятся случайные расклады очень редко. На ~50 игр у нас сошлась только одна. Подсовывать пользователям пасьянс, который не сходится — не самый удачный вариант для сайта, поэтому стали искать пути выхода.
Выход первый — это забрутфорсить случайный расклад и определить сходимость. Помимо сложности алгоритма этот вариант еще и требовал каких-то неимоверных вычислительных мощностей, примерно, как обсчет партии в шашки. (В среднем пасьянс сходится за чуть более 100 ходов, при этом в процессе игры не всегда нужно выкладывать на стол карту). Этот вариант отпал.
Тогда решили написать правила для генератора пасьянса, посчитав что это будет более простой путь. Напомню, что в «Косынке» участвует 52 карты от двойки до туза 4-х мастей. Закрыты на столе в 7 стопках 21 карта, открыты на столе 7 и 24 карты в колоде, которую можно крутить. Нас интересуют для обсчета карты, которые в колоде и уже открытые на столе (всего 31 карта), т.к. именно ими игрок оперирует.
Правило при генерации добавили такое — среди карт в колоде и открытых на столе (31 карта) должна быть одна полная комбинация красных карт от двойки до туза и одна комбинация черных карт от двойки до туза. После применения такого правила генератор стал выдавать 1 из 150 раскладов удовлетворяющих условию (149 соответственно откидывал).
Сходимость таких раскладов резко повысилась и стала ~90% (по данным на 10.000 раскладов — 979 не сошлось ни разу, 9021 сошлось). Проверить такое количество раскладов нам помог краудсорсинг и наши пользователи, которые играли в «Косынку».
P.S.: Мы пробовали разные правила применять при генерации, но расклады получались либо совсем простые и играть в них было не интересно (когда генератор выдавал нам 1 расклад из 1.000), либо их сходимость не поднималась до приемлемых значений. Спасибо за потраченное время и если Вы знаете правило (универсальный алгоритм) определения сходимости — буду рад прочитать про него.