Создание решателя свободных ячеек за несколько ходов

54

В игре Freecell вам поручено построить четыре кучи фундамента от туза до короля по схеме, в которой вы строите вниз чередующимися цветами. Однако вы можете создавать только одну карту за раз, поэтому вам предоставляется четыре «свободных клетки», каждая из которых может содержать одну карту, чтобы помочь вам перемещать целые последовательности. Идея состоит в том, что вы вкладываете отдельные карты в свободные ячейки и из них, как требуется, чтобы помочь вам решить игру.

Ваша задача - создать программу, которая решит эти игры за наименьшее количество ходов.

Ваша программа примет последовательность из 52 карточек в следующем формате:

2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...

Который будет рассматриваться в первоначальном макете в следующем порядке:

01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52

И вернуть список ходов, чтобы решить игру. Каждый ход будет в этом формате:

  • Число, представляющее номер кучи ( 1сквозной 8), или свободная ячейка ( Aдо D), представляющая исходную кучу.
  • Другой номер или буква, представляющая кучу или свободную ячейку назначения, или Fдля основания этой масти.

Вывод будет выглядеть примерно так:

18 28 3A 8B 8C 85 B5 35 4F etc.

Как только карта помещена в фундамент, она не может быть удалена. Поскольку одновременно перемещается только одна карта, перемещение последовательности из 3 карт требует 5 ходов, а последовательность из 5 карт требует 9 ходов.

Если игра неразрешима, ваша программа должна указывать как таковую. Однако ваша программа должна быть способна решить любую разрешимую игру.

Ваша программа будет оценена по 32 768 сделкам, найденным в оригинальной программе Microsoft FreeCell. Для того чтобы ваша программа была действительной, она должна успешно завершить каждую сделку, кроме сделки № 11 982 , которая не может быть разрешена . Ваша оценка будет равна общему количеству ходов, необходимых для совершения этих 32 767 сделок, с более коротким кодом, являющимся тай-брейком.


Файл со всеми колодами в формате, требуемом вышеуказанной спецификацией, доступен для загрузки здесь (файл 5,00 МБ): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks

Джо З.
источник
1
Теперь мне просто нужно взять генератор случайных чисел, который они использовали для генерации этих 32 768 игр. : S
Джо З.
3
Генератор находится здесь: rosettacode.org/wiki/Deal_cards_for_FreeCell
nutki
1
Неплохо подмечено. Как бы вы справились со случаем, когда, скажем, две карты одного цвета и номера (например, 7C и 7S) находятся в свободных ячейках? Затем, если вы переместитесь из «С» в черную восьмерку, это может быть любая из этих двух карт.
Джо З.
2
Вы могли бы получить некоторые ответы, сняв ограничение на то, что все решаемые сделки должны быть решены с помощью представления. Затем, оценка на основе количества заключенных сделок, затем наименьшее количество ходов.
mbomb007
1
карты могут быть 0-проиндексированы?
Tuskiomi

Ответы:

22

C 64 643 байта, оценка: ~ 6,5 млн.

Следующий фрагмент стека (любезно предоставленный Mego) выводит весь код в виде отдельного автономного файла C:

Скачать оригинальный источник здесь . Используйте GCC и запустите makeзатем, следуя указаниям в файле readme.

Мое форматирование плохое (все разные файлы находятся в одном блоке кода), и это может быть больше (12 тыс. Байт). Любая помощь будет любимой!

Часть кода не моя. Я использовал это из незащищенного авторского права источника. Тем не менее, я исправил метод ввода / вывода в рамках задачи (долгая задача, так как я ужасен в C (5 часов). Мне также пришлось переписать большую часть кода и отладить все. Большое спасибо моему отцу за помощь и за то, что он резиновая утка (и указание на мои ошибки в управлении памятью), и за всех в TNB, кто имел дело с моей злобой о segfaults и C.

Кристофер
источник
Вы можете использовать это, чтобы обойти ограничение длины ответа и иметь весь свой код в ответе, вместо необходимости внешней загрузки.
Mego
@Mego, я имею в виду, да, но это в нескольких файлах
Кристофер
Легко объединить несколько файлов C в один.
Mego
Вот фрагмент стека, который показывает код, объединенный в один файл.
Mego
@MEGO вы можете редактировать это в? На мобильном телефоне
Кристофер