パリティ (パズル)

パズルにおけるパリティとは

パズルにおいてパリティは、解を探す際の指針となる概念の一つです。多くの場合、パリティは解の存在を否定する場合に使用されます。パズルを作成する人はパリティをチェックすることで、解のない問題の解を探す手間から解放されます。

市販のパズルには解がないことは普通はないため、解く際に解答の候補を絞り込むために利用できます。また、パズルの問題集の中にはパリティを利用して不可能であることを証明する問題が掲載されることもあります。

各パズルにおけるパリティ

ポリオミノにおけるパリティ

ポリオミノを並べる際に、盤面を白黒に塗り分けることがあります。このように塗り分けられた白と黒のマス目の数を調べることをパリティチェックと呼びます。

例1：ドミノとチェス盤

右上と左下が欠けたチェス盤にドミノ（正方形が2つつながってできた形）を敷き詰めることを考えます。

1つのドミノは必ず白マスと黒マスを1つずつ占めます。しかし、欠けたチェス盤には白マスが32個、黒マスが30個しかありません。
したがって、ドミノで盤面を完全に覆うことは不可能です。

日本ではドミノの代わりに部屋に畳を敷く問題として出題されることもあります。畳の敷き方はパリティによって制限を受けることがあるため、同様の考え方が適用できます。

例2：Tテトロミノと正方形

Tテトロミノ（正方形1つに3つの正方形を接続した形）9個を並べて6×6の正方形を作ることを考えます。

盤面を市松模様に塗り分けると、白マスも黒マスも18個ずつになります。
1つのTテトロミノは、白マスと黒マスを奇数個ずつ占めます（3:1または1:3）。したがって、9個のTテトロミノが占めるマスも奇数個ずつとなります。
* しかし、正方形の白マスと黒マスの数は偶数個ずつなので、Tテトロミノで正方形を作ることは不可能です。

スライディングブロックパズルにおけるパリティ

スライディングブロックパズルにおいて、空所の大きさが最小のコマと同じ大きさの場合、並べることができないパターンが存在します。これを確認するためにパリティの概念が重要になります。

初期状態からコマを一組ずつ交換して最終状態にしたとき、交換の回数が偶数ならばその形に並べることができ、奇数ならば並べることができません。この性質をパリティ（偶奇性）と呼びます。

この性質を扱った有名な問題に14-15パズルがあります。サム・ロイドは、この問題が解答不可能であることを知りながら懸賞問題として出題しました。

その後に発売されたパズルの中には「Get my goat」のように、何らかの方法でパリティによる不可能性を回避しなくてはならない問題もあります。

このように、パリティはパズルの解の存在を判定する強力なツールとなります。パリティを理解することで、無駄な試行錯誤を減らし、効率的にパズルを解くことができるようになります。

もう一度検索