HardRating 2611

2056. Number of Valid Move Combinations On Chessboard

arraystringbacktrackingsimulation

解題說明

Number of Valid Move Combinations On Chessboard

題目描述：在 8x8 棋盤上有若干棋子（rook、queen、bishop），每顆棋子可以選擇停留不動或沿合法方向移動任意步數。所有棋子同時移動，每一秒移動一步。要求任何時刻（包括中途和終點）不能有兩顆棋子佔據同一格。求所有合法的移動組合數量。

解題思路：棋子數最多 4 顆，可以用回溯法（backtracking）枚舉每顆棋子的所有可能移動（方向 + 步數），然後驗證是否有衝突。

對每種棋子預處理其可移動的方向：rook 有 4 個方向（上下左右）、bishop 有 4 個方向（四個對角線）、queen 有 8 個方向。
每顆棋子的移動選項 = 停留不動 + 每個方向上 1 到最多 7 步。
用回溯法依序為每顆棋子選擇移動方案。
驗證函數：模擬所有棋子同時移動的過程，檢查每個時間步是否有位置衝突。若棋子已到達目的地則停留在原地。
統計所有合法組合數。

由於棋子數少（最多 4），每顆棋子的選項有限，回溯的搜索空間可控。

C++ 解法

複雜度分析

時間複雜度：O(M^k * k * 8) — M 為每顆棋子的移動選項數（最多約 28 種），k 為棋子數（最多 4），驗證衝突需要 O(k^2 * maxSteps)。由於 k <= 4 且 M 有限，整體可控。

空間複雜度：O(k) — 回溯的遞迴深度和 moves 陣列大小。

虛擬碼

1. For each piece type, precompute valid directions.
2. BACKTRACK(idx):
   a. If idx == n, validate all current moves for conflicts → increment ans if valid.
   b. Try staying in place (steps=0), recurse.
   c. For each valid direction of piece[idx]:
      For steps = 1 to 7 (while within board):
        Record move (startPos, direction, steps), recurse, undo.
3. VALIDATE: Simulate all pieces moving simultaneously step by step.
   At each time step, check no two pieces share the same cell.
4. Return ans.

其他解法

提前剪枝優化：在回溯過程中，每加入一顆棋子的移動方案後立即檢查與已確定的棋子是否衝突，而非等到所有棋子都選好才驗證。這可以大幅減少無效搜索分支。
預計算 + 位元遮罩：將每顆棋子在每個時間步的位置編碼為位元遮罩，用位元 AND 快速檢測衝突。適合棋子較多時加速驗證，但此題棋子數少所以收益有限。

延伸思考

若棋盤大小從 8x8 擴大到 NxN，演算法的可擴展性如何？
若加入騎士（knight）棋子，其 L 形移動如何整合到現有框架中？
若要求找出使所有棋子移動總步數最小的合法方案，如何修改解法？

Number of Valid Move Combinations On Chessboard — CaffeCode