グレブナー基底でピクロスを解く

グレブナー基底って何？

Q. グレブナー基底とはなんぞや？
A. 簡単にいうと多項式を代数学的に解くための方法。詳しくは以下の記事や大学の講義資料などを参照

• https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%AC%E3%83%96%E3%83%8A%E3%83%BC%E5%9F%BA%E5%BA%95

ピクロスって何？

マリオのピクロスで有名なやつ

• https://ja.wikipedia.org/wiki/%E3%83%94%E3%82%AF%E3%83%AD%E3%82%B9_(%E3%82%B2%E3%83%BC%E3%83%A0%E3%82%BD%E3%83%95%E3%83%88)

ピクロスについてもう少し詳しく

3x3のピクロスを考える。
以下のように行と列にそれぞれヒントが与えられる。

    1   1
    1 1 1
1 1 □ □ □
  0 □ □ □
  3 □ □ □

ヒントは、連続して塗られているマスを表す。
3と書いてあれば、3マス連続して塗られている事を表す。
1 2(1と2)と書いてあれば、「連続した1マス」と「連続した2マス」が塗られており、1マスと2マスが連続すると3になってしまうので、両者の間は1マス以上開くことになる。

先程の問題は最終的に以下のようになる。
■ : 塗ってある
□ : 塗ってない

    1   1
    1 1 1
1 1 ■ □ ■
  0 □ □ □
  3 ■ ■ ■

グレブナー基底で解く

これをグレブナー基底で解いていく。

算出する手順は以下の通り

1. 各マスに変数を割り当てる
2. 制約（方程式）を作成する
3. ブール制約を入れる
4. グレブナー基底のアルゴリズムで解く

1. 各マスに変数を割り当てる

各マスに変数を割り当てる

x00 x01 x02
x10 x11 x12
x20 x21 x22

2. 制約（方程式）を作成する

以下の方針で方程式を作成する。

1. マスを塗る : (x - 1)^2
2. マスを塗らない : (x - 0)^2 (= x^2)
3. 各行毎に、塗る／塗らないのパターンを作成し、加算でつなぐ
4. 複数の可能性がある場合は、乗算でつなぐ
5. 各列に対しても同様にする

わかりにくいので、実際に以下の例で考えてみる

    1   1
    1 1 1
1 1 □ □ □
  0 □ □ □
  3 □ □ □

各行について方程式を作成すると、以下のようになる

1. (x00 - 1)**2 + x01**2 + (x02 - 1)**2
   • 1マス目 : 塗る
   • 2マス目 : 塗らない
   • 3マス目 : 塗る
2. x10**2 + x11**2 + x12**2
   • 1マス目 : 塗らない
   • 2マス目 : 塗らない
   • 3マス目 : 塗らない
3. (x20 - 1)**2 + (x21 - 1)**2 + (x22 - 1)**2
   • 1マス目 : 塗る
   • 2マス目 : 塗る
   • 3マス目 : 塗る

各列について方程式を作成すると、以下のようになる

1. (x00 - 1)**2 + x10**2 + (x20 - 1)**2
   • 1マス目 : 塗る
   • 2マス目 : 塗らない
   • 3マス目 : 塗る
2. (x01**2 + x11**2 + (x21 - 1)**2)*(x01**2 + x21**2 + (x11 - 1)**2)*(x11**2 + x21**2 + (x01 - 1)**2)
   • この場合は、以下の3パターンが考えられるので、それぞれ方程式を作成して、乗算でつなぐ
     • 1マス目が塗られている : (x11**2 + x21**2 + (x01 - 1)**2)
     • 2マス目が塗られている : (x01**2 + x21**2 + (x11 - 1)**2)
     • 3マス目が塗られている : (x01**2 + x11**2 + (x21 - 1)**2)
3. (x02 - 1)**2 + x12**2 + (x22 - 1)**2
   • 1マス目 : 塗る
   • 2マス目 : 塗らない
   • 3マス目 : 塗る

3. ブール制約を入れる

一般的にはグレブナー基底で方程式を解くと、特定の値ではなく範囲が求まる。
今回は、塗る／塗らない(1/0)の2パターンしか存在しないので、以下の制約を入れる。

• x(x - 1) (= x^2 - x)

x(x-1)=0を解くとわかるが、x=0,1となり、算出される解を0,1に制限できる

これを、x00〜x22の各変数に対して方程式を作成して制約とする

4. グレブナー基底のアルゴリズムで解く

作成したコードは以下にあります。

• https://github.com/ripplex-soichiro-mori/groebner_picros_sample/blob/main/main.py

最後に

グレブナー基底で数独を解くプログラムがあるのは知っていたので、他のパズルゲームにも応用できるハズだよなと思ったので作成しました。
(大筋はChatGPTで生成したものなので、自分で1から作成したわけでは無いですが)

数独と異なり、塗る／塗らないの1/0で考えられるので、条件としては、こちらの方が解きやすいのではないかと思いますが、そもそもグレブナー基底の速度自体が遅いので、6次元以上のデータになると、終わらなくなってしまいました。

CGS-QEなるアルゴリズムがあり、通常のアルゴリズムよりは高速に解けるとの事ですが、残念ながら sympyには実装されておらず、SINGULARやRisa/Asirのような代数計算システムにのみ実装されているとのことだったので、今回は諦めました。