パリティ (パズル)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/09/09 23:25 UTC 版)
パズルにおいてパリティは、解を探す際に指針となる概念の一つである。
多くの場合、パリティは解の存在を否定する場合に使用される。パズルを作成する人はパリティをチェックすることで、解のない問題の解を探す手間から解放される。
市販のパズルには解がないことは普通はないため、解く際に解答の候補を絞り込むために利用できる。また、パズルの問題集の中にはパリティを利用して不可能であることを証明する問題が掲載されることもある。
目次 |
各パズルにおけるパリティ
ポリオミノにおけるパリティ
ポリオミノを並べる際に、盤面を白黒に塗り分けることがある。このように塗り分けられた白と黒のマスの数を調べることをパリティチェックと呼ぶ。
例1
- ドミノ（正方形が2つつながってできた形）を右上と左下が欠けたチェス盤におくことを考える。
- 1つのドミノは白マスと黒マス各1マスずつを占めるが、盤面には白マス32個に対して黒マスは30個しかない。よってドミノを敷き詰めるのは不可能である。
- 日本ではドミノの代わりに部屋に畳を敷く問題に変わることもある。
例2
- Tテトロミノ（1つの正方形に3つの正方形をつなげた形）9個を並べて6×6の正方形を作ることを考える。
- 盤面を市松に塗ると、白マスも黒マスも18個ずつになる。
- 1つのTテトロミノが占めるのは、奇数個の白マスと奇数個の黒マス（3:1か1:3のマスを占める）ので、9個のテトロミノが占めるマスも奇数。よって正方形を作るのは不可能である。
スライディングブロックパズルにおけるパリティ
スライディングブロックパズルにおいて空所の大きさが最小のコマと同じ大きさの場合、並べることができないパターンがある。これを確認するためにパリティが必要になる。
初期状態からコマを一組ずつ交換して最終状態にしたときに、交換の回数が偶数ならばその形に並べることができるが、奇数ならば並べることができない。この性質をパリティ（偶奇性）と呼ぶ。
この性質を扱った有名な問題に14-15パズルがある。サム・ロイドは、この問題が解答不可能であることを知りながら懸賞問題として出題した。
その後に発売されたパズルの中には「Get my goat」のように、何らかの方法でパリティによる不可能性を回避しなくてはならない問題もある。
関連項目
「パリティ (パズル)」の例文・使い方・用例・文例
- パリティ (パズル)のページへのリンク
