サブロウ丸

主にプログラミングと数学

イラストロジックを解く 第3回 ボゴ法

さっそくイラストロジックを解くアルゴリズムを考えていきます。

ボゴ法

ボゴソート(ボゴソート - Wikipedia)を参考にしたのでボゴ法と名付けました。神頼みによる解法になります。

  1. まず各行それぞれについて、行の条件を満たすようにランダムにマスを塗る
  2. 全ての列について、キーを満たすマスの塗り方がなされているかを検査する
    • もし全ての列について、条件を満たしていればその盤面を出力する
    • もし条件を満たしていない列が一つでもあれば、その盤面を白紙に戻し2からやり直す



1. まず各行それぞれについて、行の条件を満たすようにランダムにマスを塗ります。
f:id:inarizuuuushi:20171104200625p:plain:w400
f:id:inarizuuuushi:20171104200710p:plain:w400
どんどん塗っていきます。
f:id:inarizuuuushi:20171104200730p:plain:w400
そして、
2. 全ての列について、キーを満たすマスの塗り方がなされているかをチェックします。
この場合、明らかに条件をみたしていないので、また1からやり直します。

上記アルゴリズムを見れば、効率の悪さは分かると思いますが、それでもたった1回で終わる可能性も秘めています。(恐ろしく確率は低いですが...)
f:id:inarizuuuushi:20180106101042g:plain:w400
終わらなさそうですね。。


小さいサイズの問題なら, 数回で終了することもあります。
f:id:inarizuuuushi:20180106100916g:plain:w400

ソースコード

追加したのはbogo_searchfeasible関数の2つです。
上記アルゴリズムで動作するようになっています。


参考サイト:
連番画像から簡単にgifアニメを作る - Qiita