YONのドバトブログ

YONの土鳩ブログ

ゲーム好きの鳩"YON"がツイッターでは言い切れないことについて書き連ねるブログ

凶悪高難度パズルゲーム｢ウボンゴ3D｣の作問&解答プログラムを書いた

ボードゲーム Python

この記事では、高難度パズルボードゲーム｢ウボンゴ3D｣の問題作成&解答作成プログラムの解説をする。コード本体はGitHubにアップロードしている。

こちらの記事でも紹介したが、ウボンゴ3Dは立体ブロックを組み合わせてお題の立体を作るパズルボードゲームで、使用するブロックの個数が少ない癖に大変難しい。昨今の自宅待機ムードの中、500問以上ある公式問題を全て解いてしまったため、独自の問題を作成するコードを書いた。公式問題より高い難易度の問題も作れるようになっている。

実装にはPython3.8を使用している。Python環境が無いが高難度問題に挑戦したい人のために、作った問題例をこちらやこの記事内で公開している。

f:id:YON_4:20191230092148j:plain

△手前のカードの白いマスの上に、奥に見えるカラフルなブロックのうち指定された物を組合せてちょうど2段の立体を作る

f:id:YON_4:20201108040419p:plain

△4つのブロックを組合せ、目的の立体を作った所

プログラムの使い方

事前準備

  1. Python実行環境を用意する。"Windows Python"等でググった結果を参考に環境構築しよう *1
  2. モジュールcv2, tqdmをインストールする。コマンドラインから"pip install cv2"と"pip install tqdm"を実行すればよい。詳細は"python pip 使い方"などでググってほしい
  3. リンク先からファイル"ubongo_3d-master"を入手する。右上のCodeボタン押下→Download Zip→zipファイル解凍でOK

問題を作る

ubongo_3d-master内にあるcreate_question.pyを使用すると、任意の底面で問題を作ることができる。手順を解説する。

  1. 必要があれば、create_question.pyを適当なエディタで開き、末尾にあるshow_blocks(n_question=5, unique_block_flg=True, n_blocks=-1, return_n_ans_flg=True, random_flg=True)を編集して作問設定を変える *2
  2. create_question.pyを実行する
  3. 表示される指示に従い、問題の横、縦、高さの範囲と底面形状を入力する。たとえば以下の画像のような底面に2段に積む問題なら、横4マス、縦3マス、高さ2マスの範囲に収まるので次のように入力する。.が白マス、#が黒マスを表す
    4 3 2
    ....
    ...#
    .#.#

    f:id:YON_4:20210321182132p:plain

  4. 使用ブロックが画像で出力される。今回は5問出力している

    f:id:YON_4:20210321182618p:plain

 

試しに、一番下の1問を解いてみる。

 

今度は設定を変えて、同じ底面で3段の問題を作ってみよう。上記と同様の手順で進め、問題の形状を以下のように入力する。赤字の部分が3段であることを示している。
4 3 3
....
...#
.#.#

すると、以下が出力される(一番下段、左から4つ目などに見える太い青ブロックは最も小さなカギカッコ型のブロックである)。

f:id:YON_4:20210321191348p:plain

6ブロックを使用する難問だ。1問あたり10分以上かかってしまったが、どれも解けることを自力で確認した。一番下の1問を解いた例を示す。*3

今回は公式問題B29の底面を流用したが、任意の底面で実行できる。実行時間が長すぎる場合はcreate_question.py末尾のreturn_n_ans_flg=Trueをreturn_n_ans_flg=Falseに変更しよう。

 

問題を解く

リンク先のファイルには問題を解くコードubongo3d_solve.pyも同梱されている。作った問題が解けないときなどに活用してほしい。

  1. ubongo3d_solve.pyを実行する
  2. 表示される指示に従い、問題の横、縦、高さの範囲と底面形状を入力する。今回は作問時と同様に、以下を入力する
    4 3 2
    ....
    ...#
    .#.#
  3. 表示される指示に従い、使用ブロックを半角スペース区切りで入力する。別ウィンドウに表示される画像を確認し、そのウィンドウを閉じる *4
    Y1 B4 R1 G2

    f:id:YON_4:20210321205447p:plain

  4. 以下のように解答が出力される(実際には解答全パターンが表示されるが、1例だけ抜き出している)。=====で段が区切られており、1段目から順に表示されている。ブロック名称が記載されている箇所にそのブロックを置いてみよう。

    解答1
    R1 R1 B4 B4
    G2 G2 G2 ##
    G2 ## Y1 ##
    = = = = = = =
    R1 R1 Y1 B4
    R1 Y1 Y1 ##
    G2 ## Y1 ##
    = = = = = = =

    f:id:YON_4:20210321210212p:plain

プログラムの仕組み

一言で仕組みを説明すると、なるべく効率よく総当りしている。作問プログラムは

  1. 解ける可能性のあるブロックの組合せを全て求める
  2. それぞれのブロックの置き方を全て求める
  3. 正解となる置き方の組合せがあれば出力に加える

というフローで動いている(解答プログラムはステップ1を飛ばしている)。ステップ1では全列挙と体積の一致チェック、ステップ2ではブロックの座標の総当りをしている。ブロックを回転させる処理では、x,y,z軸周りの回転を全パターン行い、後で重複を除いている。*5

問題はステップ3だが、ブロックの敷き詰め問題をexact cover problemと捉え、Dancing LinksとKnuth's Algorithm Xにより効率よく解いている。以下の記事が詳しいので、参考にしてほしい。

 

謝辞

本プログラムの多くは、前述のポリオミノの敷き詰め問題を解く記事のプログラムを参考にしている。特にDancingLinksの実装コードはそのまま借用している。

 

また、ブロックの画像は下記リンクから拝借した。リンク先のライセンスに従い、自分のコードを置いたリンクにも同様のライセンスを格納した。

 

matsu7874氏、m-kasahr氏、さらにこれほど面白いパズルボードゲームを生み出したGrzegorz Rejchtman氏に感謝申し上げる。

 

 

*1:できればオンラインでも実行可能なプログラムにしたかったが、画像ファイルがあり使用ファイルが複数に跨るため、ローカル前提とした。オンラインなどの手軽に用意できるPython環境で本プログラムを動かす方法があれば教えてほしい

*2:n_questionが作問数(ブロックの組合せの数)、unique_block_flgがブロックの重複無しかどうか(Trueなら重複なし、Falseならウボンゴ3Dに同梱されている分だけブロックの重複を許す)、n_blocksが使用ブロックの数(マイナス値を入れると指定なし扱い)、return_n_ans_flgは解答数を返すかどうか(Trueなら返す。Falseだと解答数が出力されず、実行時間が短くなる)、random_flgはランダム抽出するかどうか(Trueならランダム抽出し、同じようなブロックを使う問題が連続しにくくなる)

*3:とても歯ごたえのある難易度だった。公式問題カードのB29を使って挑戦してみてほしい

*4:使用ブロックの文字列は作問時に画像とは別に出力されている。またall_blocks.pyや、ブロック画像ファイルの名前を見ればブロック名が分かる

*5:かなり非効率な気がするが、良い方法が思い浮かばなかった