• Авторизация
Дневник Капля_Иван Лента друзей - Дневник - Полная версия


“Солитер” – карточный пасьянс “Свободная ячейка” 17-08-2016 12:22 к комментариям - к полной версии - понравилось!


“Солитер” – карточный пасьянс “Свободная ячейка”



Пасьянс MS “Solitaire” удачно сочетает высокую сложность (намного сложнее “Косынки”), полную информацию и мизерный процент комбинаций, которые невозможно сложить.

Реализация Джима Хорна, опубликованная под именем Microsoft “FreeCell” (“Свободная ячейка”), считается классической. Сторонние разработчики обычно делают в своих программах генератор раскладов, совместимый с нумерацией пасьянса Microsoft Windows Solitaire. В MS “Солитер” представлено 32000 раскладов, генерирующихся 15-битным датчиком псевдослучайных чисел.

Чтобы проверить эти 32000 раскладов, в интернете появился краудсорсинг-проект, проверяющий, действительно ли все расклады Майкрософт “Солитер” разрешимы. В проекте были задействованы более чем 100 заядлых картёжников; к 1995 году только расклад № 11982 не поддался ни одному участнику. Несмотря на то, что задача NP-полна по количеству карт, к середине 2000-х годов удалось реализовать достаточно быстрый полный перебор и показать, что для этого расклада решения действительно нет.

По современным данным, вероятность выпадения разрешимой комбинации оценивается более чем в 99,99 % – одна неразрешимая комбинация на 78 000 разрешимых. Без свободных ячеек сходится всего 0,2 % раскладов. Чтобы любой расклад гарантированно сошёлся, нужно не менее семи свободных ячеек.
вверх^ к полной версии понравилось! в evernote


Вы сейчас не можете прокомментировать это сообщение.

Дневник “Солитер” – карточный пасьянс “Свободная ячейка” | Капля_Иван - Капля Иван | Лента друзей Капля_Иван / Полная версия Добавить в друзья Страницы: раньше»