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


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

盤面

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

ルール

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

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

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

問題の例 答え

考察

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

答えが複数ある問題の例 1つ目の答え 2つ目の答え 3つ目の答え 4つ目の答え

パズルの解き方

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

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

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

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

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

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

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

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

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

作ったプログラム

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

1.ファイルの入出力 (file.py)
データ入力画面(GUI)を作るのは大変なので、エクセルでデータを作って入力することにしました。
エクセルでCSV(ユニコードのカンマ区切りファイル)出力したデータの取り込みと、計算結果のCSV出力をプログラムします。
2.長方形のサイズ (factor.py)
長方形の数字に対して、長方形の取りえる縦横の値を毎回計算するのも大変なので、あらかじめ計算しておきます。
3.パズルの盤面 (board.py)
長方形、長方形のID、盤面のオブジェクトを定義します。
4.問題を解く (solver.py)
パズルの解き方で書いた処理を実際にコード化したものです。

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



トップ戻る
記述内容について一切保障しません。 リンクは自由に行ってかまいません。
Since 2019/06/08, Final update 2019/07/11, Presented by Ishida So