Pythonで「四角に切れ」を解く

某有名パズル雑誌の2018年夏号に載っていたパズルを解くプログラムを作ってみたくなり、Pythonの練習も兼ねて作ってみました。
パズルの名前は『四角に切れ』というものです。

盤面

四角に切れは、格子状のマスからなる盤上のパズルです。
マスの間には点線が書かれており、いくつかのマスには数字が書かれています。

ルール

パズルを解くルールは次の通りです。

1. 点線の上に縦横に線を引き、盤面をいくつかの長方形（正方形を含みます）に分けましょう。
2. どの長方形にも数字が1つづつ入るようにします。
3. 数字はマスの面積を１としたときに、その数字が入る長方形の面積がいくつになるかを表しています。
   例えば４と書いてあるマスを含む長方形は、１×４、２×２、４×１のいずれかになります。

問題のサンプルと回答は、以下の通りです。

考察

パズルのルールから分かることをは以下の通りです。これらがパズルを解くうえで役に立つかもしれません。

• 数字の合計は、盤面全体のマスの数に一致しています。
  そうでなければ解けません。間違った問題のチェックに使えるかもしれません。
• 出題者がミスすると、回答が複数になるパターンや解けないパターンがありえます（例えば下記の問題）。
  解けないときはあきらめるプログラムにしないといけないでしょう。

パズルの解き方

色々な解き方があるとは思いますが、下記の手順で解いていきます。

1. 答えの長方形と数字は１対１に対応するので、答えの長方形の数は確定しています。
   各長方形（＝各数字）にIDを振ります。
2. 数字のあるマスに、その数字の長方形のIDを書きます。
3. 長方形の形は数字で決まり、その数は有限個なので、各IDに対して、長方形の候補を全てリストアップします。
4. IDのをマスに書き続けられる限り、５〜６をループします。
5. リストの長方形の候補が盤面をはみ出したり、他の長方形のIDが書かれたマスに重なる場合は、その長方形の候補をリストから削除します。
6. リスト内の全ての長方形の候補で共通に含まれるマスにIDを書き込みます。
7. ループ終了後に、全てのマスにIDがかかれていれば、問題は解けました。

例えば、下記の問題で、数字の６に注目します。
盤面から外れる長方形を除くと、数字の６の長方形の候補は２通りあります。
２通りの長方形の共通部分は、数字の６の長方形の候補で共通に含まれるマスになります。

問題		数字の６の長方形の候補			共通に含まれるマス

次に、右上の４に注目します。
盤面から外れる長方形を除くと、数字の４の長方形の候補は３通りあります。
このうち２つの長方形は、他の数字のマスに重なるので、除外します。
残りの長方形（正方形ですが）が、数字の４の長方形の候補で共通に含まれるマスになります。

問題の続き		長方形の候補（他と重なる）		長方形の候補		共通に含まれるマス

この様な事を繰り返しで問題を解きます。

この方法で絶対に解けるとの保証はないです.。
例えば、下記の問題はこの手順では解けません。

解けない問題は気にせず、この方法でプログラムしていきます。

作ったプログラム

４つのPythonのファイルでプログラムを構成します。

1.ファイルの入出力 (file.py)

データ入力画面（ＧＵＩ）を作るのは大変なので、エクセルでデータを作って入力することにしました。
エクセルでCSV(ユニコードのカンマ区切りファイル)出力したデータの取り込みと、計算結果のCSV出力をプログラムします。

2.長方形のサイズ (factor.py)

長方形の数字に対して、長方形の取りえる縦横の値を毎回計算するのも大変なので、あらかじめ計算しておきます。

3.パズルの盤面 (board.py)

長方形、長方形のID、盤面のオブジェクトを定義します。

4.問題を解く (solver.py)

パズルの解き方で書いた処理を実際にコード化したものです。

作ったプログラムで某有名パズル雑誌に載っていた問題を解かせたところ、どれも1秒以下で解けました。
めでたしめでたし。

戻る