目錄
1. 問題描述
2. 解題分析
2.1 如何判斷能否鋪
2.2 狀态表示和周遊
2.3 圍欄
3. 代碼及測試
4. 後記
1. 問題描述
考慮叫做“儀式鋪法”的榻榻米鋪法，這種鋪法可以使相鄰榻榻米之間的接縫不會形成十字，象征着吉祥。舉個例子，如果一個房間看作由縱3*橫4個正方形方格構成，鋪滿這個房間需要6張榻榻米（榻榻米的大小是統一的1*2的長方形），則鋪法如下所示（還有與這兩個成上下或左右對稱的圖案此處略去）：
圖1 (3,4)的房間的兩種鋪法
求用14張榻榻米鋪滿大小為4*7的房間的鋪法。
2. 解題分析
深度優先路徑周遊問題。
這一類問題的難點主要展現在（具體問題的形式千差萬别）如何将問題轉換為易于周遊搜尋的問題表述形式，或者如何找到有效的周遊方式（包括節點狀态表示，以及如何确定鄰節點或者說子節點）。
2.1 如何判斷能否鋪
經過分析可以發現，構成非法鋪法的一個關鍵特征是在某一個點的周圍4個塊均屬于4塊不同的榻榻米。如下圖所示兩個都是NG的鋪法。
圖2 非法的鋪法例
那如何把這種限制條件轉化為容易判别的形式（換句話說人眼識别以上NG圖案很容易，如何讓計算機能做出判斷）呢？比如說，如下圖的狀态，現在要判斷帶問号“？”的格子是否可以鋪下一張榻榻米（無論是縱還是橫？）
圖3 “？”格子能夠鋪？
如前所述，非法的鋪法中是指在某個交點周圍的4個格子分屬于不同的榻榻米。是以在判斷“？”處是否能鋪，作為充要條件（這裡先不考慮觸及邊界的情況）就是判斷“左上、上、左”這個三個格子是否不全部屬于不同的榻榻米。換言之，隻要“左上、上”屬于同一榻榻米、或者“上、左”屬于同一榻榻米即表明目前格子可以鋪新的榻榻米（“左上、左”肯定分屬不同的榻榻米不必判斷）。反之，如果“左上、上”屬于不同榻榻米、且“上、左”屬于不同榻榻米則表明目前格子肯定不能鋪。據此可以判斷，上圖中，左邊不能鋪，右邊可以鋪。
這也就自然地引出了給到目前狀态為止已經鋪好的榻榻米進行編号的考慮，以友善進行以上判斷。
2.2 狀态表示和周遊
【有點複雜的想法】
以整個房間的鋪設狀态作為圖的節點，可以表示為H*W的矩陣（H為縱向高度，W為橫向寬度），矩陣元素取值{0：尚未覆寫；非零IDX：已經序号IDX的榻榻米被覆寫}。起始狀态（即深度優先搜尋樹的根節點）為全0狀态。終止狀态為全非零狀态。這樣這個問題就轉變成在一張圖中搜尋從某個節點（全‘0’狀态）出發，到達另一個節點（全非零狀态）的所有路徑的問題。
然後，鄰節點搜尋可以這樣考慮，周遊與移近覆寫的區域相鄰（有共同的邊）的格子，檢查從各鄰接格子是否能夠鋪設（因為是從左上往右下搜尋的方式，針對每個格子隻需要考慮向右鋪或向下鋪）。這種方法的好處是遞歸深度會小一些，但是已覆寫區域的鄰接格子的查詢似乎比較麻煩。
【逐行掃描】
原書中給出的解法（這道題原書給出的Javascript代碼比ruby容易了解些好歹看懂了）很巧妙（當然要自己先撞牆了然後再讀懂了才能體會其中妙處并感歎我怎麼沒想到）。
簡單地逐行（當然逐列也可以）逐格掃描過去，碰到邊界就切換到下一行，碰到已經被覆寫的就跳過去，針對既非越界也沒有被覆寫的格子結合目前已經鋪就的狀态進行是否能鋪（參見上一節的描述）的判斷。加上“圍欄”技巧（參見下一節）以及給榻榻米編号的技巧，得到了一個非常簡潔的實作。
這一解法的缺點可能是遞歸深度相對來說會比較大，當問題規模比較大的時候容易觸及遞歸深度限制（有待确認）
以下為(H=3,W=4)的遞歸搜尋示意圖（沒有畫出圍欄，可以把格點坐标按照matlab-style的從1開始的方式了解；黑點表示目前探索的格子，旁邊(x,y,idx)對應的遞歸調用的參數）
2.3 圍欄
如原書中所述，對于棋盤類問題，很多時候，在問題界定的範圍外側加上圍欄就可以簡化邊界條件的判定。在本題解中，在H*W格子矩陣外圍追加一圈格子，并全部指派為“-1”。在代碼中雖然沒有顯式地（explicitly）用到“-1”的判斷，但是在“if room[h,w+1]==0:”和“if room[h+1,w]==0:”判斷中隐式地（implicitly）利用到了。因為追加了外圍的一層，是以不必擔心(w+1)和(h+1)越界而導緻矩陣通路出錯；另外，由于初始化為“-1”，是以在上述判斷不會被誤判為有效的可填的格子。
3. 代碼及測試
以下代碼是參照原書的“逐行掃描”政策的解法，改為“逐列掃描”也可以。另外，也沒有特意地寫一個列印出鋪好的圖案的函數--相對來說是一個比較trivial的事情。從列印出來的table應該很容易描畫出鋪好的圖案來。
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 16 07:18:04 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
# import random
from typing import List
# from queue import Queue
# from collections import deque
import itertools as it
import numpy as np
H = 4 # Heigth of the room
W = 7 # Weigth of the room
# room initialization, with a guard band surrounding the original room
# The guard band is initialized to '-1' to simplify the judgement processing.
room = np.zeros((H+2, W+2))
room[0,:] = -1
room[H+1,:] = -1
room[:,0] = -1
room[:,W+1] = -1
count = 0
def setTatami_rowscan(h,w,idx)->int:
'''
Parameters
----------
(h,w) : The current exploration point. h represents row number, w represents col number.
idx : The identifier index of Tatami to be arranged.
Returns: int
The number of total arrangement from the input condition.
'''
global count
# print(h,w,idx)
if h == H + 1:
count = count + 1
print(room)
elif w == W + 1:
# Reach the right boundary, go to explore the next row from the left
setTatami_rowscan(h+1, 1, idx)
elif room[h,w] > 0:
# This grid has been occupied, move to the right one
setTatami_rowscan(h, w+1, idx)
elif room[h-1,w]==room[h-1,w-1] or room[h,w-1]==room[h-1,w-1]:
# if (the same IDX for up and left-up) or (the same IDX for left and left-up),
# Tatami arrangement is allowed.
if room[h,w+1]==0:
# Horizontal arrangement is allowed
room[h,w] = idx
room[h,w+1] = idx
setTatami_rowscan(h, w+2, idx+1)
room[h,w] = 0
room[h,w+1] = 0
if room[h+1,w]==0:
# Vertical arrangement is allowed
room[h,w] = idx
room[h+1,w] = idx
setTatami_rowscan(h, w+1, idx+1)
room[h,w] = 0
room[h+1,w] = 0
tStart = time.perf_counter()
setTatami_rowscan(1, 1, 1)
tCost = time.perf_counter() - tStart
print('count = {0}, tCost = {1:6.3f}(sec)'.format(count,tCost))
運作結果（H=4, W=7）:
4. 後記
後面要回頭再把第一種【有點複雜的想法】也實作一下，并比較一下前面的關于目前實作方式會導緻更深的遞歸深度的問題是否存在。
上一篇：Q31: 計算最短路徑
下一篇：Q33: 飛車與角行的棋步
本系列總目錄參見：程式員的算法趣題：詳細分析和Python全解