Edited at

バックトラックを用いてスネークキューブを解いてみよう


はじめに

FUJITSU Advent Calendar 2018 その2 の19日目の記事です。

(注意)この記事は個人の見解であり、所属する会社、組織を代表するものではありません。


目的

Rubyの勉強

島根県民で知らないのは恥ずかしいかな?と


スネークキューブって何?

スネークキューブ(以下SC)とは、木でできたパズルです

DSC_0219.JPG

DSC_0218.JPG

上のようなバラバラになっている状態から、下のような立方体に直したら勝ちみたいです

やってみたけど普通に難しくて解けない!

※ちなみに画像は筆者の筆箱にいつも付いている相棒です


アルゴリズムを考えよう

少々条件が付いた、一筆書き問題です

条件とは、「ブロックのタイプが 角 or それ以外 かによって、曲がる or 直進する が決定する」という意味です

一筆書きの問題は、グラフ理論に置き換えることが可能です(解説ページ

グラフを探索すれば終わりです

以上です


図で解説しちゃうよ(ピンと来てない方へ)

※簡単化のため、3x3の平面で考えます


  1. 3x3の空間を用意する

    0.png


  2. スタート地点を適当に決める

    1.png


  3. 条件に従いつつ、1ブロックずつにょきにょき書いていく

    2.png  3.png  4.png


  4. 全部埋まったら終わり

    final.png


条件について

- 赤だったら曲がる(3次元だと4方向)

- 緑だったら直進

以上です

イメージだけでもつかめました?


よろしい、ならば探索だ

あとは機械の力に任せましょう

以下が全ソースです(汚い)


main.rb

require "matrix"

require "benchmark"

$size #一辺のサイズ
$args #ピースの形状
$hasSolved
$ans #解を保存する配列
$field #一筆書きする空間

# $field の初期化
def cre_field
# $field = new Array[$size][$size][$size]
field = Array.new($size + 2).map {
Array.new($size + 2).map { Array.new($size + 2, true) }
}

for z in 0...$size
for y in 0...$size
for x in 0...$size
field[z][y][x] = false
end
end
end

field
end

# 再帰関数
def solve(depth, pos, dir)
if depth >= $size * $size * $size
$hasSolved = true
return
end

if $field[pos[2]][pos[1]][pos[0]]
return
end

$field[pos[2]][pos[1]][pos[0]] = true

if $args[depth]
for e in cre_dir_of_right_angle(dir)
solve(depth + 1, pos + e, e)
if $hasSolved
$ans.unshift(dir_to_str(e))
return
end
end
else
solve(depth + 1, pos + dir, dir)
if 0 == depth && $hasSolved
$ans.unshift(dir_to_str(dir))
end
end

$field[pos[2]][pos[1]][pos[0]] = false
end

# 直角を返す
def cre_dir_of_right_angle(dir)
[
Vector[ 1, 0, 0],
Vector[-1, 0, 0],
Vector[ 0, 1, 0],
Vector[ 0, -1, 0],
Vector[ 0, 0, 1],
Vector[ 0, 0, -1],
].reject { |e| e == dir || e == -dir }
end

def dir_to_str(dir)
case dir
when Vector[ 1, 0, 0]
"Right"
when Vector[-1, 0, 0]
"Left"
when Vector[ 0, 1, 0]
"Up"
when Vector[ 0, -1, 0]
"Down"
when Vector[ 0, 0, 1]
"Back"
when Vector[ 0, 0, -1]
"Forward"
else
"Not Direction"
end
end

$size = 3
$args = [0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0]
$args.map! { |e| e > 0}

$hasSolved = false
$ans = []
$field = cre_field
rslt = Benchmark.realtime do
solve(0, Vector[0, 0, 0], Vector[1, 0, 0])
end

if $hasSolved
puts $ans.join("\n"), "\nTotal time: " + (rslt / 1000).to_s + " ms"
else
puts "No answer..."
end



実行結果

Right

Up
Left
Back
Up
Forward
Right
Back
Down
Left
Up
Forward
Up
Back
Down
Right
Up

Total time: 7.148909935494885e-07 ms


今回は深さ優先探索を用いました

理由は、


  • 解の最適性は重要ではない

  • 実装が簡単

の2点です

また、本来ならばパズルの形状の情報はコマンドライン引数にするべきです

めんどくさかったです

許してください


まとめ

Rubyは書いてて楽しい