Opinions · Learning Python · Huarongdao Solver

Huarongdao Solver

In 2022, I wrote a Python program that solves Huarongdao, a Chinese sliding-block puzzle, as a demonstration for my Python tutorial. Pick a starting layout, and a port of the program finds the shortest solution in your browser.

Starting layout

The puzzle

Huarongdao (华容道, "the Huarong Trail") is a sliding-block puzzle, a relative of Klotski. It is named after an episode in the Romance of the Three Kingdoms: after his defeat at the Battle of Red Cliffs, the warlord Cao Cao flees along the Huarong Trail, where the general Guan Yu, who owes him a debt of gratitude, lets him pass.

The board has four columns and five rows. Cao Cao is the large square block; the generals are blocks of two cells, standing or lying; the soldiers are single cells; and two cells are empty. The goal is to slide Cao Cao out through the exit at the bottom center. As is customary, moving one piece counts as one move, even when it slides two cells or, for a soldier, turns a corner. By this count, the classic layout, 横刀立马 ("blade leveled, horse reined in"), in which Guan Yu lies just below Cao Cao, takes 81 moves.

How the program works

A configuration is a tuple of coordinates. Each cell has a number from 0 to 19, and each piece is recorded by the number of its upper-left cell. Pieces of the same kind are interchangeable, so their coordinates are kept sorted, and the whole configuration becomes a tuple that can serve as a key in a dictionary.
Moves are found from the empty cells. Only a piece next to an empty cell can move, so Config.getNeighbors looks around the two empty cells, not at every piece, and lists every configuration one move away.
The search is breadth-first. Solution keeps a queue of configurations to examine and a dictionary recording where each one was reached from. Configurations are examined in order of the number of moves needed to reach them, so the first time Cao Cao reaches the exit, the solution is the shortest possible. The path is then traced back through the dictionary.
The search space is small. With the classic set of pieces, there are only 65,880 possible layouts, as count_possible_configs counts, so the search takes well under a second.

The original program drew each step with Matplotlib and joined the pictures into a video with OpenCV. This page draws the board instead.

The layouts in the list

The list was chosen with AI assistance (Claude). For each mix of lying and standing generals, every possible layout was listed, and the original program's move rules were used to find, for every layout, the fewest moves needed to free Cao Cao. The list runs from easy layouts to the hardest that exist, and each move count was confirmed with the original program. Apart from 横刀立马, the names are descriptions, not traditional names.

Generals (lying + standing)	Layouts	Solvable	Most moves needed
0 + 5	15,660	7,462	19
1 + 4 (classic)	65,880	53,954	93
2 + 3	109,260	83,972	138
3 + 2	106,800	82,835	135
4 + 1	51,660	30,778	97
5 + 0	14,220	8,114	56

The count of 65,880 layouts agrees with the original program's own count, and the 138-move maximum agrees with the hardest Huarongdao layout known.

Notes on the code

Written at my request by Claude, the AI assistant that ported the program.

What works well. The design is clean: Board knows the geometry, Config knows the moves, and Solution runs the search. Sorted tuples as dictionary keys make repeated configurations easy to skip, and searching from the empty cells keeps the move generation short. The test functions and count_possible_configs, which estimates the size of the search before running it, are good habits.
A false solution when there is none. If the queue empties before Cao Cao escapes, __find_path sets final_coords to the last configuration examined, and the program then draws a path to it as if it were a solution. The port returns no solution instead.
An invalid layout is only warned about. The validity check prints a warning and carries on. The port has a separate isValid method, and the page offers only valid, solvable layouts.
The cache never hits. getNeighbors stores its result as self.__Neighbors, but checks for it with '__Neighbors' in self.__dict__. Python renames double-underscore attributes, so the key in __dict__ is '_Config__Neighbors', and the check is always false. This is harmless here, since each configuration's neighbors are needed only once.
Unneeded clean-up. The __del__ methods that clear __dict__, and the del statements, are not needed: Python frees objects that are no longer used.
A simpler queue. queue.Queue is designed for passing work between threads. In a single-threaded program, collections.deque is simpler and faster.

The JavaScript port

The port was written with AI assistance (Claude). It keeps the original's classes, methods and move rules, renamed in JavaScript style (getNeighbors, findPath), so that the two programs can be read side by side. It leaves out the drawing, uses short strings instead of tuples as dictionary keys, and returns no solution when Cao Cao cannot escape. It finds solutions of the same length as the original for every layout in the list and for 1,800 randomly chosen layouts, 603 of them unsolvable. Because it follows the original design rather than being optimized, it is only modestly faster than the Python program; the status line above shows how long each search took.

Source code

Original Python program (2022)

Download: huarongdao_v22.11.16.py

from timeit import default_timer as timer
start_time = timer()
elapsed_time = lambda: timer() - start_time

from itertools import combinations
from math import comb

from queue import Queue
from sys import exit
import cv2
import os

import matplotlib.pyplot as plt
from matplotlib import rcParams
rcParams.update({'font.family' : 'serif', 'mathtext.fontset' : 'dejavuserif',
                 'font.size' : 12, 'text.latex.preamble' : r"\usepackage{amsmath}",
                 'xtick.major.pad' : 2, 'ytick.major.pad' : 2, 'xtick.major.size' : 6, 'ytick.major.size' : 6,
                 'xtick.minor.size' : 3, 'ytick.minor.size' : 3, 'axes.linewidth' : 2, 'axes.labelpad' : 1})
from matplotlib.patches import FancyBboxPatch, BoxStyle


def count_possible_configs():
    ctr = 0
    
    for generals in combinations(range(4, 20), 4):
        occupied = [general + shift for general in generals for shift in [0, -4]]
        if len(set(occupied)) < 8: continue
    
        for Caocao in range(4, 20):
            if Caocao % 4 == 3: continue
            occupied1 = occupied + [Caocao + shift for shift in [0, 1, -4, -3]]
            if len(set(occupied1)) < 12: continue
    
            for Guanyu in range(20):
                if Guanyu % 4 == 3: continue
                occupied2 = occupied1 + [Guanyu, Guanyu + 1]
                if len(set(occupied2)) < 14: continue
                ctr += 1
    
    ctr *= comb(6, 4)
    print(ctr)  # 65880


class Board():
    def __init__(self, width: int=4, height: int=5):
        self.width = width
        self.height = height


    def __del__(self):
        self.__dict__.clear()


    def __getCol(self, coord: int) -> int:
        return coord % self.width


    def __getRow(self, coord: int) -> int:
        return coord // self.width


    def getColRow(self, coord: int) -> (int, int):
        return self.__getCol(coord), self.__getRow(coord)


    # def __getLeft(self, coord: int, shift: int=1):
    #     col = self.__getCol(coord)
    #     if col < shift: return -1
    #     return coord - shift


    # def __getRight(self, coord: int, shift: int=1):
    #     col = self.__getCol(coord)
    #     if col >= self.width - shift: return -1
    #     return coord + shift


    # def __getUp(self, coord: int, shift: int=1):
    #     row = self.__getRow(coord)
    #     if row >= self.height - shift: return -1
    #     return coord + shift * self.width


    # def __getDown(self, coord: int, shift: int=1):
    #     row = self.__getRow(coord)
    #     if row < shift: return -1
    #     return coord - shift * self.width


    def getNeighbor(self, coord: int, hshift: int=0, vshift: int=0) -> int:
        col, row = self.getColRow(coord)
        col += hshift; row += vshift

        if not 0 <= col < self.width: return -1
        if not 0 <= row < self.height: return -1

        return row * self.width + col


    def getVicinity(self, coord: int) -> dict:
        vicinity = {}

        for hshift in [-2, -1, 1, 2]:
            vicinity[(hshift, 0)] = self.getNeighbor(coord, hshift=hshift)
        for vshift in [-2, -1, 1, 2]:
            vicinity[(0, vshift)] = self.getNeighbor(coord, vshift=vshift)

        return vicinity


    def getVicinity2(self, coords: (int, int)) -> (str, dict):
        coord1, coord2 = coords
        adjacent = ''
        if coord1 == self.getNeighbor(coord2, hshift=-1):
            adjacent = 'H'
        elif coord1 == self.getNeighbor(coord2, vshift=-1):
            adjacent = 'V'

        vicinity = {}

        for shift, coord in self.getVicinity(coord1).items():
            vicinity[(1,) + shift] = coord
        for shift, coord in self.getVicinity(coord2).items():
            vicinity[(2,) + shift] = coord

        if adjacent == 'H':
            for key in [(2, -2, 0), (2, -1, 0), (1, 1, 0), (1, 2, 0)]:
                vicinity[key] = -1
        elif adjacent == 'V':
            for key in [(2, 0, -2), (2, 0, -1), (1, 0, 1), (1, 0, 2)]:
                vicinity[key] = -1

        return adjacent, vicinity


def test_Board_methods():
    board = Board()

    for coord in range(20):
        print(coord, board.getVicinity(coord))

    print(board.getVicinity2((6, 10)))


class Config():
    def __init__(self, board: Board, coords: (int, tuple, tuple, tuple, tuple)\
                 =(17, (9,), (8, 11, 16, 19), (0, 3, 5, 6), (1, 2))):
        self.__board     =      board
        self.__Caocao    =      coords[0]
        self.__HGenerals = list(coords[1])
        self.__VGenerals = list(coords[2])
        self.__Soldiers  = list(coords[3])
        self.__Vacancies = list(coords[4])


    def __del__(self):
        self.__dict__.clear()


    def display(self, figname: str):
        fig, ax = plt.subplots(figsize=(self.__board.width + 0.1,
                                        self.__board.height))

        x, y = self.__board.getColRow(self.__Caocao)
        ax.add_artist(FancyBboxPatch([x + 0.1, y - 0.9], 1.8, 1.8,
            boxstyle=BoxStyle("Round", pad=0.05), color='tab:blue', alpha=0.7))
        ax.text(x + 1.0, y - 0.05, figname, ha='center', va='center',
                color='tab:blue', fontsize=36)

        for Hgeneral in self.__HGenerals:
            x, y = self.__board.getColRow(Hgeneral)
            ax.add_artist(FancyBboxPatch([x + 0.1, y + 0.1], 1.8, 0.8,
                boxstyle=BoxStyle("Round", pad=0.05), color='tab:red', alpha=0.7))

        for Vgeneral in self.__VGenerals:
            x, y = self.__board.getColRow(Vgeneral)
            ax.add_artist(FancyBboxPatch([x + 0.1, y - 0.9], 0.8, 1.8,
                boxstyle=BoxStyle("Round", pad=0.05), color='tab:orange', alpha=0.7))

        for soldier in self.__Soldiers:
            x, y = self.__board.getColRow(soldier)
            ax.add_artist(FancyBboxPatch([x + 0.1, y + 0.1], 0.8, 0.8,
                boxstyle=BoxStyle("Round", pad=0.05), color='tab:green', alpha=0.7))


        ax.axis('equal'); ax.axis('off')
        ax.set_xlim((-0.1, 4.1)); ax.set_xticks([])
        ax.set_ylim((-0.0, 5.0)); ax.set_yticks([])
        ax.patch.set_alpha(0.0)

        fig.tight_layout()
        fig.savefig(f'{figname}.png', dpi=128)
        plt.close(fig)


    def __moveCaocao(self, shift: (int, int)):
        new_Caocao = self.__board.getNeighbor(self.__Caocao, *shift)

        if shift == (1, 0):
            new_vacancies = (self.__board.getNeighbor(self.__Caocao, vshift=-1),
                             self.__Caocao)
        elif shift == (-1, 0):
            new_vacancies = (self.__board.getNeighbor(self.__Caocao, hshift=1, vshift=-1),
                             self.__board.getNeighbor(self.__Caocao, hshift=1))
        elif shift == (0, -1):
            new_vacancies = (self.__Caocao,
                             self.__board.getNeighbor(self.__Caocao, hshift=1))
        elif shift == (0, 1):
            new_vacancies = (self.__board.getNeighbor(self.__Caocao, vshift=-1),
                             self.__board.getNeighbor(self.__Caocao, hshift=1, vshift=-1))

        coords = (new_Caocao, tuple(self.__HGenerals), tuple(self.__VGenerals),
                  tuple(self.__Soldiers), new_vacancies)
        self.__Neighbors.append(coords)


    @staticmethod
    def list_replace(array: list, old: int, new: int):
        array[array.index(old)] = new
        array.sort()


    def __moveHGeneral(self, old_coord: int, shift: (int, int)):
        new_HGenerals = self.__HGenerals.copy()
        Config.list_replace(new_HGenerals, old_coord,
                            self.__board.getNeighbor(old_coord, *shift))

        if shift == (1, 0):
            new_vacancies = self.__Vacancies.copy()
            Config.list_replace(new_vacancies,
                                self.__board.getNeighbor(old_coord, hshift=2),
                                old_coord)
        elif shift == (-1, 0):
            new_vacancies = self.__Vacancies.copy()
            Config.list_replace(new_vacancies,
                                self.__board.getNeighbor(old_coord, hshift=-1),
                                self.__board.getNeighbor(old_coord, hshift=1))
        else:
            new_vacancies = (old_coord,
                             self.__board.getNeighbor(old_coord, hshift=1))

        coords = (self.__Caocao, tuple(new_HGenerals), tuple(self.__VGenerals),
                  tuple(self.__Soldiers), tuple(sorted(new_vacancies)))
        self.__Neighbors.append(coords)


    def __moveVGeneral(self, old_coord: int, shift: (int, int)):
        new_VGenerals = self.__VGenerals.copy()
        Config.list_replace(new_VGenerals, old_coord,
                            self.__board.getNeighbor(old_coord, *shift))

        if shift == (0, 1):
            new_vacancies = self.__Vacancies.copy()
            Config.list_replace(new_vacancies,
                                self.__board.getNeighbor(old_coord, vshift=1),
                                self.__board.getNeighbor(old_coord, vshift=-1))
        elif shift == (0, -1):
            new_vacancies = self.__Vacancies.copy()
            Config.list_replace(new_vacancies,
                                self.__board.getNeighbor(old_coord, vshift=-2),
                                old_coord)
        else:
            new_vacancies = [old_coord,
                             self.__board.getNeighbor(old_coord, vshift=-1)]
            new_vacancies.sort()

        coords = (self.__Caocao, tuple(self.__HGenerals), tuple(new_VGenerals),
                  tuple(self.__Soldiers), tuple(new_vacancies))
        self.__Neighbors.append(coords)


    def __moveSoldier(self, old_coord: int, new_coord: int):
        new_Soldiers = self.__Soldiers.copy()
        Config.list_replace(new_Soldiers, old_coord, new_coord)

        new_vacancies = self.__Vacancies.copy()
        Config.list_replace(new_vacancies, new_coord, old_coord)

        coords = (self.__Caocao, tuple(self.__HGenerals), tuple(self.__VGenerals),
                  tuple(new_Soldiers), tuple(new_vacancies))
        self.__Neighbors.append(coords)


    def getNeighbors(self, allow_twice: bool=True):
        if '__Neighbors' in self.__dict__:
            return self.__Neighbors

        self.__Neighbors = []
        adjacent, vicinity = self.__board.getVicinity2(self.__Vacancies)
        vacancy1, vacancy2 = self.__Vacancies

        # try to move Caocao
        if adjacent == 'V':
            if vicinity[(2, -2, 0)] == self.__Caocao:
                self.__moveCaocao((1, 0))
            elif vicinity[(2, 1, 0)] == self.__Caocao:
                self.__moveCaocao((-1, 0))

        elif adjacent == 'H':
            if vicinity[(1, 0, 2)] == self.__Caocao:
                self.__moveCaocao((0, -1))
            elif vicinity[(1, 0, -1)] == self.__Caocao:
                self.__moveCaocao((0, 1))

        # try to move an HGeneral
        for v in [1, 2]:
            if vicinity[(v, -2, 0)] in self.__HGenerals:
                self.__moveHGeneral(vicinity[(v, -2, 0)], (1, 0))
            if vicinity[(v, 1, 0)] in self.__HGenerals:
                self.__moveHGeneral(vicinity[(v, 1, 0)], (-1, 0))

        if adjacent == 'H':
            if vicinity[(1, 0, 1)] in self.__HGenerals:
                self.__moveHGeneral(vicinity[(1, 0, 1)], (0, -1))
            if vicinity[(1, 0, -1)] in self.__HGenerals:
                self.__moveHGeneral(vicinity[(1, 0, -1)], (0, 1))

            if allow_twice:
                if vicinity[(1, -2, 0)] in self.__HGenerals:
                    self.__moveHGeneral(vicinity[(1, -2, 0)], (2, 0))
                if vicinity[(2, 1, 0)] in self.__HGenerals:
                    self.__moveHGeneral(vicinity[(2, 1, 0)], (-2, 0))

        # try to move a VGeneral
        for v in [1, 2]:
            if vicinity[(v, 0, -1)] in self.__VGenerals:
                self.__moveVGeneral(vicinity[(v, 0, -1)], (0, 1))
            if vicinity[(v, 0, 2)] in self.__VGenerals:
                self.__moveVGeneral(vicinity[(v, 0, 2)], (0, -1))

        if adjacent == 'V':
            if vicinity[(2, -1, 0)] in self.__VGenerals:
                self.__moveVGeneral(vicinity[(2, -1, 0)], (1, 0))
            if vicinity[(2, 1, 0)] in self.__VGenerals:
                self.__moveVGeneral(vicinity[(2, 1, 0)], (-1, 0))

            if allow_twice:
                if vicinity[(1, 0, -1)] in self.__VGenerals:
                    self.__moveVGeneral(vicinity[(1, 0, -1)], (0, 2))
                if vicinity[(2, 0, 2)] in self.__VGenerals:
                    self.__moveVGeneral(vicinity[(2, 0, 2)], (0, -2))

        # try to move a Soldier
        for v, vacancy in enumerate(self.__Vacancies, start=1):
            for shift in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
                old_coord = vicinity[(v,) + shift]
                if old_coord in self.__Soldiers:
                    self.__moveSoldier(old_coord, vacancy)
                    if allow_twice and adjacent:
                        self.__moveSoldier(old_coord, sum(self.__Vacancies) - vacancy)

        return self.__Neighbors


def test_Config_methods():
    board = Board()
    # init_coords = (17, (9,), (8, 11, 16, 19), (0, 3, 5, 6), (1, 2))
    init_coords = (17, (9,), (4, 6, 16, 19), (1, 3, 5, 11), (7, 8))
    config = Config(board, init_coords)
    config.display('0')

    neighbors = config.getNeighbors()
    del config

    for i, neighbor in enumerate(neighbors, start=1):
        print(i, neighbor)
        config = Config(board, neighbor)
        config.display(repr(i))
        del config

    del board


class Solution():
    def __init__(self, board: Board, init_coords: (int, tuple, tuple, tuple, tuple)=\
                 (17, (9,), (8, 11, 16, 19), (0, 3, 5, 6), (1, 2)),
                 max_nsteps: int=100000, allow_twice: bool=True):
        self.board = board
        self.init_coords = init_coords
        self.max_nsteps = max_nsteps
        self.allow_twice = allow_twice

        validity_check = [self.board.getNeighbor(init_coords[0], *shift)
                          for shift in [(0, 0), (1, 0), (0, -1), (1, -1)]]
        for i in range(1, 5):
            for coord in init_coords[i]:
                validity_check.append(coord)
                if i == 1: validity_check.append(self.board.getNeighbor(coord, hshift=1))
                if i == 2: validity_check.append(self.board.getNeighbor(coord, vshift=-1))
        validity_check.sort()
        if validity_check != list(range(self.board.width * self.board.height)):
            print(f' > Warning: Config({init_coords}) is invalid')


    def __del__(self):
        self.__dict__.clear()


    def __find_path(self):
        self.__coords_dict = {self.init_coords: None}
        self.__coords_queue = Queue()
        self.__coords_queue.put(self.init_coords)
        self.final_coords = None

        for i in range(self.max_nsteps):
            coords = self.__coords_queue.get()
            if i % 1000 == 0: print(i, coords)

            if coords[0] == 5:
                print(i, coords)
                self.final_coords = coords
                del self.__coords_queue
                break

            config = Config(self.board, coords)
            # config.display(repr(i))
            # print(i, coords, self.__coords_dict[coords])

            neighbors = config.getNeighbors(allow_twice=self.allow_twice)
            for neighbor in neighbors:
                if neighbor in self.__coords_dict: continue
                self.__coords_dict[neighbor] = coords
                self.__coords_queue.put(neighbor)
            del config

            if self.__coords_queue.empty():
                self.final_coords = coords
                break

        self.path = []
        if self.final_coords is not None:
            coords = self.final_coords
            while coords:
                self.path.append(coords)
                coords = self.__coords_dict[coords]
            self.path.reverse()
        self.__coords_dict.clear()


    def __display(self):
        print(' > Visualizing', '@', elapsed_time())

        images = []
        for i, coords in enumerate(self.path):
            print(i, coords)
            config = Config(self.board, coords)
            config.display(repr(i))
            images.append(f'{i}.png')
            del config

        frame = cv2.imread(images[0])
        height, width, layers = frame.shape
        video = cv2.VideoWriter('huarongdao.mp4', 0, 5, (width, height))

        for image in images:
            video.write(cv2.imread(image))
            os.remove(image)

        cv2.destroyAllWindows()
        video.release()


    def __call__(self):
        self.__find_path()
        if self.path: self.__display()


if __name__ == "__main__":
    # count_possible_configs()
    # test_Board_methods()
    # test_Config_methods()

    board = Board()
    solution = Solution(board,
                        # init_coords=(17, (1, 5, 9), (11, 19), (4, 8, 12, 16), (0, 3)),
                        allow_twice=True)
    solution()
    del solution

    print(' > Finished!', '@', elapsed_time())

JavaScript port

Download: solver.js

// Huarongdao solver: a JavaScript port of Kaili Cao's Python program
// (huarongdao_v22.11.16.py), ported with AI assistance (Claude).
//
// The port keeps the original's classes (Board, Config, Solution), methods and
// move rules, so the two can be read side by side. It leaves out the drawing
// (matplotlib, OpenCV), which the web page does instead, and it changes two
// things: Solution.findPath returns null when no solution exists, and the
// queue is a plain array with a moving head instead of queue.Queue.
//
// Coordinates follow the original: the board is 4 columns by 5 rows, a cell's
// coordinate is row * 4 + col, and row 0 is the bottom row. A piece's
// coordinate is its upper-left cell. A configuration ("coords") is
//   [caocao, hGenerals, vGenerals, soldiers, vacancies]
// with every list sorted, e.g. the classic 横刀立马:
//   [17, [9], [8, 11, 16, 19], [0, 3, 5, 6], [1, 2]]
// Cao Cao escapes when his coordinate is 5 (bottom center).

'use strict';

class Board {
  constructor(width = 4, height = 5) {
    this.width = width;
    this.height = height;
  }

  getColRow(coord) {
    return [coord % this.width, Math.floor(coord / this.width)];
  }

  // The cell shifted by (hshift, vshift) from coord, or -1 if off the board.
  getNeighbor(coord, hshift = 0, vshift = 0) {
    let [col, row] = this.getColRow(coord);
    col += hshift; row += vshift;
    if (!(col >= 0 && col < this.width)) return -1;
    if (!(row >= 0 && row < this.height)) return -1;
    return row * this.width + col;
  }

  // Cells up to two steps away from coord in each direction,
  // keyed by "hshift,vshift".
  getVicinity(coord) {
    const vicinity = {};
    for (const hshift of [-2, -1, 1, 2]) {
      vicinity[`${hshift},0`] = this.getNeighbor(coord, hshift, 0);
    }
    for (const vshift of [-2, -1, 1, 2]) {
      vicinity[`0,${vshift}`] = this.getNeighbor(coord, 0, vshift);
    }
    return vicinity;
  }

  // The vicinity of both vacancies, keyed by "v,hshift,vshift" (v = 1 or 2),
  // and whether the vacancies are adjacent horizontally ('H') or
  // vertically ('V'). Cells that are the other vacancy, or lie beyond it,
  // are masked with -1.
  getVicinity2(coords) {
    const [coord1, coord2] = coords;
    let adjacent = '';
    if (coord1 === this.getNeighbor(coord2, -1, 0)) {
      adjacent = 'H';
    } else if (coord1 === this.getNeighbor(coord2, 0, -1)) {
      adjacent = 'V';
    }

    const vicinity = {};
    for (const [shift, coord] of Object.entries(this.getVicinity(coord1))) {
      vicinity[`1,${shift}`] = coord;
    }
    for (const [shift, coord] of Object.entries(this.getVicinity(coord2))) {
      vicinity[`2,${shift}`] = coord;
    }

    if (adjacent === 'H') {
      for (const key of ['2,-2,0', '2,-1,0', '1,1,0', '1,2,0']) vicinity[key] = -1;
    } else if (adjacent === 'V') {
      for (const key of ['2,0,-2', '2,0,-1', '1,0,1', '1,0,2']) vicinity[key] = -1;
    }
    return { adjacent, vicinity };
  }
}

const numeric = (a, b) => a - b;

class Config {
  constructor(board, coords) {
    this.board = board;
    this.caocao = coords[0];
    this.hGenerals = [...coords[1]];
    this.vGenerals = [...coords[2]];
    this.soldiers = [...coords[3]];
    this.vacancies = [...coords[4]];
    this.neighbors = null;
  }

  static listReplace(array, oldValue, newValue) {
    array[array.indexOf(oldValue)] = newValue;
    array.sort(numeric);
  }

  moveCaocao(shift) {
    const b = this.board, c = this.caocao;
    const newCaocao = b.getNeighbor(c, ...shift);
    let newVacancies;
    if (shift[0] === 1 && shift[1] === 0) {
      newVacancies = [b.getNeighbor(c, 0, -1), c];
    } else if (shift[0] === -1 && shift[1] === 0) {
      newVacancies = [b.getNeighbor(c, 1, -1), b.getNeighbor(c, 1, 0)];
    } else if (shift[0] === 0 && shift[1] === -1) {
      newVacancies = [c, b.getNeighbor(c, 1, 0)];
    } else {  // (0, 1)
      newVacancies = [b.getNeighbor(c, 0, -1), b.getNeighbor(c, 1, -1)];
    }
    this.neighbors.push([newCaocao, [...this.hGenerals], [...this.vGenerals],
                         [...this.soldiers], newVacancies]);
  }

  moveHGeneral(oldCoord, shift) {
    const b = this.board;
    const newHGenerals = [...this.hGenerals];
    Config.listReplace(newHGenerals, oldCoord, b.getNeighbor(oldCoord, ...shift));

    let newVacancies;
    if (shift[0] === 1 && shift[1] === 0) {
      newVacancies = [...this.vacancies];
      Config.listReplace(newVacancies, b.getNeighbor(oldCoord, 2, 0), oldCoord);
    } else if (shift[0] === -1 && shift[1] === 0) {
      newVacancies = [...this.vacancies];
      Config.listReplace(newVacancies, b.getNeighbor(oldCoord, -1, 0),
                         b.getNeighbor(oldCoord, 1, 0));
    } else {  // vertical moves, and horizontal moves by two cells
      newVacancies = [oldCoord, b.getNeighbor(oldCoord, 1, 0)];
    }
    this.neighbors.push([this.caocao, newHGenerals, [...this.vGenerals],
                         [...this.soldiers], newVacancies.sort(numeric)]);
  }

  moveVGeneral(oldCoord, shift) {
    const b = this.board;
    const newVGenerals = [...this.vGenerals];
    Config.listReplace(newVGenerals, oldCoord, b.getNeighbor(oldCoord, ...shift));

    let newVacancies;
    if (shift[0] === 0 && shift[1] === 1) {
      newVacancies = [...this.vacancies];
      Config.listReplace(newVacancies, b.getNeighbor(oldCoord, 0, 1),
                         b.getNeighbor(oldCoord, 0, -1));
    } else if (shift[0] === 0 && shift[1] === -1) {
      newVacancies = [...this.vacancies];
      Config.listReplace(newVacancies, b.getNeighbor(oldCoord, 0, -2), oldCoord);
    } else {  // horizontal moves, and vertical moves by two cells
      newVacancies = [oldCoord, b.getNeighbor(oldCoord, 0, -1)].sort(numeric);
    }
    this.neighbors.push([this.caocao, [...this.hGenerals], newVGenerals,
                         [...this.soldiers], newVacancies]);
  }

  moveSoldier(oldCoord, newCoord) {
    const newSoldiers = [...this.soldiers];
    Config.listReplace(newSoldiers, oldCoord, newCoord);
    const newVacancies = [...this.vacancies];
    Config.listReplace(newVacancies, newCoord, oldCoord);
    this.neighbors.push([this.caocao, [...this.hGenerals], [...this.vGenerals],
                         newSoldiers, newVacancies]);
  }

  // All configurations reachable in one move. With allowTwice, a piece may
  // also move two cells in a straight line, or a soldier may turn a corner,
  // which still counts as one move.
  getNeighbors(allowTwice = true) {
    if (this.neighbors !== null) return this.neighbors;
    this.neighbors = [];
    const { adjacent, vicinity: vic } = this.board.getVicinity2(this.vacancies);
    const H = this.hGenerals, V = this.vGenerals;

    // try to move Caocao
    if (adjacent === 'V') {
      if (vic['2,-2,0'] === this.caocao) this.moveCaocao([1, 0]);
      else if (vic['2,1,0'] === this.caocao) this.moveCaocao([-1, 0]);
    } else if (adjacent === 'H') {
      if (vic['1,0,2'] === this.caocao) this.moveCaocao([0, -1]);
      else if (vic['1,0,-1'] === this.caocao) this.moveCaocao([0, 1]);
    }

    // try to move an HGeneral
    for (const v of [1, 2]) {
      if (H.includes(vic[`${v},-2,0`])) this.moveHGeneral(vic[`${v},-2,0`], [1, 0]);
      if (H.includes(vic[`${v},1,0`])) this.moveHGeneral(vic[`${v},1,0`], [-1, 0]);
    }
    if (adjacent === 'H') {
      if (H.includes(vic['1,0,1'])) this.moveHGeneral(vic['1,0,1'], [0, -1]);
      if (H.includes(vic['1,0,-1'])) this.moveHGeneral(vic['1,0,-1'], [0, 1]);
      if (allowTwice) {
        if (H.includes(vic['1,-2,0'])) this.moveHGeneral(vic['1,-2,0'], [2, 0]);
        if (H.includes(vic['2,1,0'])) this.moveHGeneral(vic['2,1,0'], [-2, 0]);
      }
    }

    // try to move a VGeneral
    for (const v of [1, 2]) {
      if (V.includes(vic[`${v},0,-1`])) this.moveVGeneral(vic[`${v},0,-1`], [0, 1]);
      if (V.includes(vic[`${v},0,2`])) this.moveVGeneral(vic[`${v},0,2`], [0, -1]);
    }
    if (adjacent === 'V') {
      if (V.includes(vic['2,-1,0'])) this.moveVGeneral(vic['2,-1,0'], [1, 0]);
      if (V.includes(vic['2,1,0'])) this.moveVGeneral(vic['2,1,0'], [-1, 0]);
      if (allowTwice) {
        if (V.includes(vic['1,0,-1'])) this.moveVGeneral(vic['1,0,-1'], [0, 2]);
        if (V.includes(vic['2,0,2'])) this.moveVGeneral(vic['2,0,2'], [0, -2]);
      }
    }

    // try to move a Soldier
    const vacancySum = this.vacancies[0] + this.vacancies[1];
    this.vacancies.forEach((vacancy, i) => {
      const v = i + 1;
      for (const [h, vs] of [[1, 0], [-1, 0], [0, -1], [0, 1]]) {
        const oldCoord = vic[`${v},${h},${vs}`];
        if (this.soldiers.includes(oldCoord)) {
          this.moveSoldier(oldCoord, vacancy);
          if (allowTwice && adjacent) this.moveSoldier(oldCoord, vacancySum - vacancy);
        }
      }
    });

    return this.neighbors;
  }
}

class Solution {
  constructor(board, initCoords, { maxNsteps = 100000, allowTwice = true } = {}) {
    this.board = board;
    this.initCoords = initCoords;
    this.maxNsteps = maxNsteps;
    this.allowTwice = allowTwice;
    this.path = null;
    this.nsearched = 0;
  }

  // True if the pieces cover the board exactly once.
  isValid() {
    const b = this.board, c = this.initCoords;
    const cells = [[0, 0], [1, 0], [0, -1], [1, -1]].map(s => b.getNeighbor(c[0], ...s));
    for (let i = 1; i < 5; i++) {
      for (const coord of c[i]) {
        cells.push(coord);
        if (i === 1) cells.push(b.getNeighbor(coord, 1, 0));
        if (i === 2) cells.push(b.getNeighbor(coord, 0, -1));
      }
    }
    cells.sort(numeric);
    return cells.length === b.width * b.height && cells.every((x, i) => x === i);
  }

  // Breadth-first search: the first configuration found with Cao Cao at the
  // exit is reached in the fewest moves. Returns the list of configurations
  // from start to finish, or null if Cao Cao cannot escape.
  findPath() {
    // a configuration as a short string, e.g. '17|9|8,11,16,19|0,3,5,6|1,2'
    const key = coords => coords.join('|');
    const parents = new Map([[key(this.initCoords), null]]);
    const queue = [this.initCoords];
    let head = 0, finalCoords = null;

    for (let i = 0; i < this.maxNsteps && head < queue.length; i++) {
      const coords = queue[head++];
      if (coords[0] === 5) { finalCoords = coords; break; }

      const config = new Config(this.board, coords);
      for (const neighbor of config.getNeighbors(this.allowTwice)) {
        const k = key(neighbor);
        if (parents.has(k)) continue;
        parents.set(k, coords);
        queue.push(neighbor);
      }
    }
    this.nsearched = parents.size;

    if (finalCoords === null) { this.path = null; return null; }
    const path = [];
    for (let coords = finalCoords; coords !== null; coords = parents.get(key(coords))) {
      path.push(coords);
    }
    this.path = path.reverse();
    return this.path;
  }
}

if (typeof module !== 'undefined') module.exports = { Board, Config, Solution };

The page also uses puzzles.js, the list of layouts, and app.js, which draws the board and runs the buttons; both were written with AI assistance (Claude). More about my Python tutorial is on Learning Python.