找出图8.37所示的6X6残缺棋盘（阴影部分表示已割去的方块)的一个完全覆盖（完全覆盖是指用多米诺

令h_n表示用多米诺牌和单牌(半张多米诺牌)对1×n棋盘进行完美覆盖(即没有发生重叠的完全覆盖)的方法数，其中要求任意两张多米诺牌都不相邻，找出h_n所满足的递推关系和初始条件。

盖。

[迷宫问题]从迷宫中找出从入口到出口的所有路径是一个经典的程序设计问题。迷宫可用图(a)所示的方块来表示，每个方块或为通道(以空白方块表示)或为墙(以带阴影的方块表示)。要求找到一条从入口到出口的简单路径，即在求得的路径上不能重复出现同一通道块。

23所示。试证明该棋盘有用多米诺牌的完美覆盖当且仅当允许放子的白格个数等于允许放子的黑格个数。这里已假定行的方向和列的方向都是黑白格相间的。

上恰有一个黑方格禁止放子，那么该棋盘有一个用多米诺牌的完美覆盖。