КИРИЛЛ ТКАЧЕНКО, инженер 1-й категории, ФГАОУ ВО «Севастопольский государственный университет», tkachenkokirillstanislavovich@gmail.com

Решение головоломки «Отшельник»
Высокоуровневый и низкоуровневый подход

На высокоуровневом языке Common Lisp разрабатывается программа поиска решения на основе алгоритма рекурсивного поиска с возвратом. Другой вариант – применение прикладного интерфейса приложений Windows API на Си для создания программы реализации игрового интерфейса с исполняемым файлом небольшого размера

Работа современных ИТ-специалистов требовательна к охвату знаний и используемых средств, поскольку именно они позволяют «воплощать идеи, концепции и рецепты в работающие программы» [1]. Для увеличения знаний можно использовать рассмотрение языков программирования, не связанных с предметной областью специалиста. Такими языками могут стать эзотерические языки. Но лучше воспользоваться языком программирования, который пережил десятилетия совершенствования на пути к промышленному стандарту, – Common Lisp.

Для иллюстрации нужна игра либо головоломка. Головоломка должна быть достаточно сложной, чтобы не оттолкнуть подготовленного специалиста, и при этом несколько простой для облегчения деятельности на этапе обучения и уменьшения числа возможных стратегий поиска решения. Отлично подходящей для этих целей является «Отшельник» [2-5] (известный в виде изделия из дерева и пластмассы как «Йога»). Название определяет ограничения задачи – это умственная игра для одного игрока, требовательная к внимательности и сосредоточению. Целью игры является уменьшить до предела количество оставленных на доске колышков. Колышки могут поедать друг друга, перепрыгивая по горизонтали или вертикали через соседа на свободное место игры. Эта головоломка может быть решена, как и многие другие, методом рекурсивного поиска с возвратом [6].

Высокоуровневый подход

Конечно, эта известная головоломка имеет большое количество программных реализаций поиска решения [5, 7, 8]. Но особый интерес представляет переделка готовых реализаций с высокоуровневых языков на такой язык, как Common Lisp.

Поскольку, возможно, для большинства читателей Common Lisp не будет являться наиболее часто используемым ими на практике языком, идентификаторы всех переменных и констант, а также аргументы функций в программе, используемых для одной цели, названы одинаково:

• *PEG* – константа, символ, обозначающий колышек на игровой доске;
• *HOLE* – константа, символ, обозначающий пустое место на игровой доске;
• *LINE* – константа, длина строки игрового поля, включая символ-терминатор;
• *LF* – константа, строка, обозначающая конец строки;
• *DIRECTIONS* – константа, список, содержащий разницу между целевым полем и текущим для направлений;
• *board* – строковая переменная, хранящая состояние игрового поля;
• *noOfTests* – целочисленная переменная, хранящая число проведенных проверок возможности хода;
• positio – целочисленная величина, хранящая текущую рассматриваемую позицию поля;
• direction – целочисленная величина, хранящая текущее рассматриваемое направление поля;
• pegsOnBoard – целочисленная переменная, хранящая количество колышков на доске;
• isSolved – целочисленная переменная, хранящая факт успешности рекурсивного вызова.

В таких обозначениях и строится исходный код программы. Конспективное изложение и описание использованных возможностей языка Common Lisp по [9] приводится ниже.

• #\linefeed – символ перевода строки;
• + – сумма элементов;
• and – макрос, который вычисляет S-выражения слева направо. Когда хоть одно из них станет nil, возвращает nil, иначе возвращает значение последнего S-выражения;
• char= – предикат возвращает true, если символы равны, иначе false;
• concatenate – функция, возвращающая последовательность, в которую входят все отдельные элементы последовательностей в заданном порядке;
• defparameter – макрос, который связывает значение с константой;
• defun – макрос, который определяет новую функцию;
• defvar – макрос, который присваивает начальное значение динамической переменной;
• dolist – макрос, который проходит по элементам списка, выполняет тело для каждого;
• dotimes – макрос, который проходит по сформированной целочисленной последовательности и каждый раз выполняет тело цикла;
• elt – средство доступа к элементу последовательности по индексу;
• exit – выход из программы;
• format – функция форматированного вывода;
• if – специальный оператор, который вычисляет первое S-выражение, если оно истинно, то выполняется первая ветвь, иначе вторая;
• incf – макрос, который увеличивает значение на единицу;
• length – функция, которая возвращает число элементов в последовательности – длину строки в данном случае;
• let – специальный оператор, который определяет новые локальные переменные;
• list – функция, возвращающая список аргументов;
• return-from – специальный оператор, который возвращает управление и значения из блока;
• setf – макрос, который изменяет значение;
• string – в используемом случае функция, которая возвращает строку, содержащую единственный заданный символ;
• t – константное значение истины;
• when – макрос, который в случае истинности первого S-выражения, выполняет остальные слева направо.

Вначале происходит определение глобальных констант:

(defparameter *PEG* #\x)
(defparameter *HOLE* #\-)
(defparameter *LINE* 12)
(defparameter *LF* (string #\linefeed))
(defparameter *DIRECTIONS* (list -1 (- *LINE*) 1 *LINE*))

В *LF* присваивается преобразованный в строку символ, который используется как терминатор отдельных строк при их конкатенации, в *DIRECTIONS* – сформированный список из четырех элементов.

Порядок направлений для просмотра определяется исходя из того, что при таком способе будет наименьшее возможное число проверок при полном просмотре игрового поля.

Само игровое поле представляет собой конкатенацию отдельных строк, составляющих игровое поле, терминаторов, преобразованную в строку:

(defvar *board* (concatenate 'string
    "..........." *LF*
    "..........." *LF*
    "....xxx...." *LF*
    "....xxx...." *LF*
    "..xxxxxxx.." *LF*
    "..xxx-xxx.." *LF*
    "..xxxxxxx.." *LF*
    "....xxx...." *LF*
    "....xxx...." *LF*
    "..........." *LF*
    "..........." *LF*
))

Число проведенных проверок вначале равно 0:

(defvar *noOfTests* 0)

Подпрограмма canMove выполняет проверку осуществимости хода для колышка, находящегося в positio, по направлению, разница которого от текущей ячейки составляет direction:

(defun canMove (positio direction)
    (incf *noOfTests*)
    (and
        (char= (elt *board* positio) *PEG*)
        (char= (elt *board* (+ positio direction)) *PEG*)
        (char= (elt *board* (+ positio direction direction)) *HOLE*)))

В начале подпрограммы происходит увеличение счетчика *noOfTests*.

Подпрограмма makeMove производит ход из позиции positio со сдвигом direction:

(defun makeMove (positio direction)
    (setf (elt *board* positio) *HOLE*)
    (setf (elt *board* (+ positio direction)) *HOLE*)
    (setf (elt *board* (+ positio direction direction)) *PEG*))

Для такого хода в рассматриваемую позицию устанавливается пустота, в следующую по сдвигу – пустота, в следующую – колышек.

Подпрограмма removeMove производит отмену хода из позиции positio со сдвигом direction:

(defun removeMove (positio direction)
    (setf (elt *board* positio) *PEG*)
    (setf (elt *board* (+ positio direction)) *PEG*)
    (setf (elt *board* (+ positio direction direction)) *HOLE*))

Для отмены хода в рассматриваемую позицию устанавливается колышек, в следующую по сдвигу – колышек, в следующую – пустота.

Ядро системы лежит в подпрограмме solve:

(defun solve ()
    (let ((pegsOnBoard 0) isSolved)

Вначале полагается, что счетчик колышков нулевой, определяется флажок isSolved. В цикле со счетчиком выполняется проход по всем ячейкам игрового поля. Если в ячейке содержится колышек:

        (dotimes (positio (length *board*))
            (when (char= (elt *board* positio) *PEG*),

то увеличивается счетчик колышков. И для всех возможных направлений по порядку:

                (incf pegsOnBoard)
                (dolist (direction *DIRECTIONS*)

Когда возможно из рассматриваемой позиции ячейки в заданном смещении перемещения совершить ход, этот ход совершается, присваивается флажку решения значение рекурсивного вызова функции поиска решения, ход отменяется:

                    (when (canMove positio direction)
                        (makeMove positio direction)
                        (setf isSolved (solve))
                        (removeMove positio direction)

Когда решение найдено, состояние игрового поля сообщается пользователю и происходит возврат из функции с успехом:

                        (when isSolved
                            (format t "~a~%" *board*)
                            (return-from solve 't))
                    ))
            ))

Когда после прохода по полю на нем остается один колышек, также состояние игрового поля сообщается пользователю и происходит возврат из функции с успехом:

        (when (= pegsOnBoard 1)
            (format t "~a~%" *board*)
            t)))

В головной функции main:

(defun main ()
    (if (solve)
        (format t "Решение найдено.~%")
        (format t "Решение не найдено.~%"))
    (format t "Число проверок: ~d.~%" *noOfTests*))

по точке входа выполняется головная функция:

(main)

Происходит выход:

(exit)

Готовую программу можно сохранить в файл, например, с названием SamagPeg.lisp. Стоит отметить меньшее число строк кода в этой программе по сравнению с приведенными в [7, 8].

Для исполнения можно использовать команды либо:

sbcl --script SamagPeg.lisp

либо:

sbcl --noinform --load SamagPeg.lisp

Эти команды вводятся удобным способом, при этом предполагается, что используется транслятор SBCL, доступный из переменной окружения %PATH% или $PATH. Установка и настройка среды разработки, редакторов кода и трансляторов выходит за рамки работы.

Низкоуровневый подход

Теперь пришло время нам с вами рассмотреть низкоуровневый подход.

Как широко известно, Windows API (WinAPI) может использоваться [10-12] для прямого взаимодействия между прикладной программой и операционной системой из соответствующего семейства. Этот API включает в себя также базовые, родные модули графического интерфейса пользователя (GUI), который, в свою очередь, относят к низкоуровневым инструментам разработки элементов графического интерфейса. Их использование применимо также и в ряде свободных альтернативных реализаций, здесь не рассматриваемых.

Разработке с использованием WinAPI посвящена обширная литература и публикации. Так, например, статья [11] посвящена азам программирования с использованием этого интерфейса. Общедоступный справочник [12] содержит необходимые материалы по программированию настольных и серверных приложений.

При этом, к большому сожалению, имеется существенный пробел между непосредственно самыми основами использования WinAPI и ее профессиональным применением, который и можно заполнить.

Разработка любого приложения на языке Си с их использованием начинается с описания головной функции – так называемой точки входа WinMain. Сигнатура для этой функции в общем случае имеет вид:

int WINAPI WinMain(HINSTANCE hThisInstance, HINSTANCE hPrevInstance, LPSTR lpszArgument, int nCmdLine),

где явно указывается, что возвращаемым результатом является знаковая целочисленная величина – код завершения приложения.

Первый параметр hThisInstance содержит дескриптор текущего экземпляра приложения и может использоваться при работе с ресурсами. В то же время второй параметр hPrevInstance предназначен для содержания дескриптора предыдущего экземпляра приложения. Командная строка приложения содержится в lpszArgument, а желаемое состояние основного окна – в nCmdLine.

Прежде чем описывать игровую логику работы этой функции, необходимо остановиться на логике взаимодействия со средствами библиотек [3].

Вначале заполняется необходимая структура данных и на ее основе создается класс головного окна приложения вызовом RegisterClassEx(&wincl), где wincl – переменная, содержащая в себе структуру данных оконного класса WNDCLASSEX.

В ней имеются следующие поля:

• hInstance – дескриптор текущего экземпляра приложения;
• lpszClassName – указатель на строку, содержащую в себе идентификатор – имя класса;
• lpfnWndProc – указатель на функцию обратного вызова, предназначенную для обработки сообщений;
• style – особенности обработки некоторых входящих воздействий;
• cbSize – размер описываемой структуры данных;
• hIcon и hIconSm – нормальная и уменьшенная иконки окна приложения;
• hCursor – курсор;
• lpszMenuName – указатель на строку, содержащую в себе идентификатор – имя меню;
• cbClsExtra и cbWndExtra – дополнительные и нами не рассматриваемые поля;
• hbrBackground – фоновый цвет окна.

Если возвращенная вызовом функции RegisterClassEx величина отлична от нуля, то можно продолжать функционирование приложения, в противном случае рекомендуется выполнить аварийный останов.

Для разрабатываемой программы сопоставление можно внести в таблицу 1.

Таблица 1. Сопоставление полей для класса окна

Затем происходит вызов функции

HWND WINAPI CreateWindowEx (dwExStyle, lpClassName, lpWindowName, dwStyle, x, y, nWidth, nHeight, hWndParent, hMenu, hInstance, lpParam)

для создания головного окна, которая возвращает дескриптор созданного окна (и ноль в противном случае).

Аргументы:

• dwExStyle – дополнительные стили;
• lpClassName – указатель на строку, содержащую в себе идентификатор класса;
• lpWindowName – указатель на строку, содержащую в себе заголовок окна;
• dwStyle – комбинация значений оконных и контрольных стилей;
• x и y – начальные координаты левого верхнего угла окна, для которых можно использовать системное значение CW_USEDEFAULT;
• nWidth и nHeight – начальные ширина и высота окна, для которых можно использовать системное значение CW_USEDEFAULT;
• hWndParent – дескриптор родительского окна или окно владельца для создаваемого, можно использовать HWND_DESKTOP для дескриптора рабочего стола;
• hMenu – дескриптор меню;
• hInstance – дескриптор экземпляра приложения;
• lpParam – дополнительная вспомогательная информация, пересылаемая в окно перед его созданием.

Значения аргументов сводятся в таблицу 2.

Таблица 2. Значения аргументов CreateWindowEx для создания головного окна

После чего происходит вызов CreateWindowEx для создания кнопки очистки экрана, аргументы которой сведены в таблицу 3. В качестве аргумента hMenu указывается целое число – уникальный идентификатор кнопки.

Таблица 3. Значения аргументов CreateWindowEx для создания кнопки начала новой игры

Вызовы этой функции используются для создания кнопок игрового поля, таблица аргументов № 4, при этом x и y меняются от 0 до 7 во вложенных циклах.

Таблица 4. Значения аргументов CreateWindowEx для создания кнопок игрового поля

Происходит обновление игрового поля, что будет рассмотрено ниже по тексту.

Функция ShowWindow для заданного дескриптором окна устанавливает режим отображения (в нашем случае – нормальный SW_SHOWNORMAL).

UpdateWindow для заданного дескриптором окна обновляет графическое содержимое окна.

С помощью функций GetMessage, TranslateMessage и DispatchMessage организуется цикл обработки сообщений.

GetMessage получает сообщение из очереди сообщений, диспетчеризует входящие сообщения, пока они доступны для получения. Аргументы:

• lpMsg – указатель на структуру сообщения;
• hWnd – дескриптор обрабатываемого окна;
• wMsgFilterMin и wMsgFilterMax – минимальная и максимальная границы фильтра равны нулю для обработки всех сообщений.

Возвращает логическую величину FALSE – если получено WM_QUIT, иначе TRUE (в случае ошибки при задании неправильных аргументов возвращает -1).

TranslateMessage преобразует сообщения виртуальных клавиш в символьные сообщения.

DispatchMessage отправляет сообщение в оконную процедуру. Головная функция возвращает 0 – значение, полученное от функции PostQuitMessage.

Оконная процедура имеет заголовок вида:

LRESULT CALLBACK WindowProcedure (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)

Возвращаемый результат зависит от обработанного сообщения. Аргументы:

• hwnd – дескриптор окна;
• message – сообщение;
• wParam и lParam – дополнительная информация, зависимая от сообщения.

В этой процедуре-функции в селекторе по аргументу message происходит выбор:

• Если получено сообщение WM_DESTROY, то с помощью вызова функции PostQuitMessage(0) происходит отправка WM_QUIT в очередь сообщений.
• Если получено сообщение WM_COMMAND и верхнее слово wParam равно BN_CLICKED, то в нижнем слове wParam имеется идентификатор кнопки. Для кнопки начала новой игры он BTN_CLEAR, а для кнопок игрового поля он равен x*10+y, где x и y – горизонталь и вертикаль кнопки. После этого сравнения вызывается необходимая функция-обработчик – либо для создания новой игры, либо для обработки нажатия на кнопку игрового поля.
• Иначе происходит вызов DefWindowProc (hwnd, message, wParam, lParam) для передачи управления обработчику по умолчанию.

Функция возвращает 0.

Не останавливаясь на механике внутреннего функционирования ранее описанной игры [13], описываются остальные функции.

Функция int InCross (int x, int y) возвращает значение TRUE, если клетка с указанными горизонталью x и вертикалью y принадлежит крестовому игровому полю, иначе возвращает FALSE.

В функции void InitBoard() массив для хранения содержимого доски инициализируется следующим образом, а именно: для всех клеток с горизонталями от 0 до 6 и вертикалями от 0 до 6, если клетка принадлежит крестовому игровому полю и не является центральной, то значение TRUE, иначе FALSE, а для списков координат нажатых кнопок игрового поля на базе массивов устанавливается нулевая длина.

Функция void RedrawBoard() выполняет отрисовку игровой доски. В нем для всех горизонталей с номерами x от 0 до 6 и для всех вертикалей с номерами y от 0 до 6 выполняется: если клетка принадлежит крестовому игровому полю, то для кнопки игрового поля устанавливается отображаемый текст.

Используется функция SendMessage (hWnd, Msg, wParam, lParam). Аргументы:

• hWnd – дескриптор окна, в которое происходит отправка сообщения;
• Msg – сообщение, которое необходимо отправить;
• wParam и lParam – дополнительная информация.

Поэтому вызов SendMessage (pegs[x][y], WM_SETTEXT, 0, (LPARAM)(board[x][y] ? "o" : szEmpty) задаст кнопке надпись «o», если колышек имеется, и «», если колышка нет.

Функция void Renew() вызывает InitBoard() и RedrawBoard().

Функция int sign (int x) возвращает знак числа.

Функция int IsOnOneLine (int a1, int a2, int a3, int b1, int b2, int b3) проверяет, лежат ли три поля на одной горизонтали/вертикали непосредственно рядом, выполняет проверку. Если три поля находятся на одной горизонтали/вертикали, поля находятся рядом, последовательность полей – в одну сторону.

Функция void MaybeWin() проверяет наличие победной ситуации и создает в случае победы новую игру.

Функция void TryMakeMove() осуществляет попытку и последующее выполнение хода. Распаковываются горизонтали и вертикали. Если поля лежат на одной горизонтали или вертикали непосредственно рядом и содержат, соответственно, колышек, колышек и его отсутствие, то делается ход, очищаются координаты, отрисовывается доска и проверяется победная ситуация.

Функция void BoardClicked (int x, int y) выполняет следующее: в списки горизонталей и вертикалей добавляются нажатая горизонталь и вертикаль. Если в списках больше трех координат, то остаются только последние три нажатия. Если в списках ровно три координаты, то происходит попытка выполнения перемещения колышка.

Рекомендуется для разработки и отладки использовать любую среду разработки, а для сборки итоговой программы – транслятор Tiny C Compiler.

Рисунок 1. Результат работы программы

Листинг программы приводится на сайте журнала http://samag.ru. В результате трансляции получается небольшой исполняемый файл разработанной программы для ручного решения головоломки.

1. Вторников А. Стек, или Путешествие туда и обратно / А. Вторников. – М.: Изд-во «ДМК Пресс», 2017. – 140 с.
2. Арсак Ж. Программирование игр и головоломок / Ж. Арсак. – М.: Наука, 1990. – 224 с.
3. Solitaire - balls on an 8x8 cross shaped grid [Электронный ресурс] / Ресурс переменной длины. Режим доступа: https://www.emacswiki.org/emacs/CategoryGames, свободный. Загл. с экрана. (Online).
4. Peg solitaire [Электронный ресурс] / Ресурс переменной длины. Режим доступа: http://en.wikipedia.org/wiki/Peg_solitaire, свободный. Загл. с экрана. (Online).
5. This program solves the (English) peg solitaire board game. [Электронный ресурс] / Ресурс переменной длины. Режим доступа: http://play.golang.org/p/JWwEyecar0, свободный. Загл. с экрана. (Online).
6. Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. – М.: Мир, 1985. – 406 с.
7. Ткаченко К. Головоломка «Отшельник». Реализации решения «выигрывающих стратегий» .// «Системный администратор», № 10, 2014 г. – С. 82-85. Режим доступа: http://samag.ru/archive/article/2803, свободный. Загл. с экрана. (Online).
8. Ткаченко К. Рекурсивный поиск в глубину в 1С на примере решения головоломки «Отшельник».// «Системный администратор», № 10, 2017 г. – С. 55-57. Режим доступа: http://samag.ru/archive/article/3522, свободный. Загл. с экрана. (Online).
9. Pitman Kent. Common Lisp HyperSpec. Index entries [Электронный ресурс] / Kent Pitman // Ресурс переменной длины. Режим доступа: http://www.lispworks.com/documentation/HyperSpec/Front/X_Master.htm, свободный. Загл. с экрана. (Online).
10. Windows API [Электронный ресурс] / Ресурс переменной длины. Режим доступа: https://ru.wikipedia.org/wiki/Windows_API, свободный. Загл. с экрана. (Online).
11. Яковлев И.С. Пишем на WinAPI с «нуля» / И.С. Яковлев // RSDN Magazine #4-2005. Режим доступа: http://rsdn.ru/article/baseserv/api32.xml, свободный. Загл. с экрана. (Online).
12. Windows API Index [Электронный ресурс] / Ресурс переменной длины. Режим доступа: https://msdn.microsoft.com/ru-ru/library/windows/desktop/ff818516.aspx, свободный. Загл. с экрана. (Online).
13. Ткаченко К. Играем с компьютером в головоломку «Отшельник». // «Системный администратор», № 3, 2016 г. – С. 80-82. Режим доступа: http://samag.ru/archive/article/3158, свободный. Загл. с экрана. (Online).

Ключевые слова: головоломки, отшельник, йога, рекурсивный поиск с возвратом, Windows API, Си, Common Lisp.

Комментарии могут оставлять только зарегистрированные пользователи