制約充足問題（Constraint Satisfaction Problem）
制約充足問題は、複数の制約条件を満たすオブジェクトや状態を見つけるという数学の問題を指す。
制約充足問題は完全な解の存在する問題であり、要素の順序は問題とはならない。
一連の変数が与えられ、指定された制約を満足するようにそれらに値を設定しなければならない。
バックトラッキング（Backtracking）
バックトラッキングは、制約充足問題の解を探索する戦略の一種で、力まかせ探索を改良したもの。
バックトラッキングでは、変数の値の組み合わせを試行錯誤して解を探す。
バックトラッキングの効果は部分的組み合わせを排除（枝刈り）する実装にあり、それによって実行時間を短縮する。
バックトラッキングのアルゴリズムは、単に正しい解を得るまで可能な組み合わせを試していくだけであり、一種の深さ優先探索である。
擬似コード
問題を解いている途中の部分問題において、可能な解の候補がいくつかあったとき、
- 解の候補のうち、一つを選択し、その部分問題の「仮の」解にする。
- 問題の続きを解いてみる。
- 成功ならそのまま。失敗なら、1.の選択を破棄し、別の候補を「仮の」解にし、2.へ。
上記2.の部分は再帰的になる。
func_backtrack():
候補選択の初期化
while 解が見つからない or 次の候補がある:
次の候補の選択
if 仮の解として適する:
解の一部として記録
if まだ解くべき問題が残っている:
func_backtrack(次の段階) # 再帰
if 失敗:
先の記録を破棄
実戦問題 leetcode 473.
473. Matchsticks to Squareは以下のようにバックトラッキングで解ける。
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
total_len = sum(matchsticks)
# マッチ棒が4本以下 または 合計長さが4の倍数でない場合はFalse
if len(matchsticks) < 4 or total_len % 4:
return False
# マッチ棒の長さの逆順でソート
matchsticks.sort(reverse=True)
edges = [0] * 4
# マッチ棒を候補とする
def dfs(idx: int) -> bool:
if idx == len(matchsticks):
# 全てのマッチ棒を使った = 解が見つかった Trueを返す
return True
for i in range(4):
# 候補のマッチを仮の解として、4つの辺にそれぞれ入れてみる
edges[i] += matchsticks[idx]
if edges[i] <= total_len // 4 and dfs(idx + 1):
# 入れてみた解が正しい場合は、次のマッチ棒を候補とし再帰的に解を探す
return True
# 入れてみた解が正しくない場合は、辺を戻して次のマッチ棒を候補とする
edges[i] -= matchsticks[idx]
# 全てのマッチ棒を使ったが、正しい解が見つからなかった場合、 Falseを返す
return False
return dfs(0)