华容道求解器

下载：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())

下载：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 };