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

#はじめに

FUJITSU Advent Calendar 2018 その2 の19日目の記事です。
(注意)この記事は個人の見解であり、所属する会社、組織を代表するものではありません。

#目的
Rubyの勉強
島根県民で知らないのは恥ずかしいかな？と

#スネークキューブって何？
スネークキューブ（以下SC）とは、木でできたパズルです

上のようなバラバラになっている状態から、下のような立方体に直したら勝ちみたいです
やってみたけど普通に難しくて解けない！
※ちなみに画像は筆者の筆箱にいつも付いている相棒です

#アルゴリズムを考えよう
少々条件が付いた、一筆書き問題です
条件とは、「ブロックのタイプが 角 or それ以外 かによって、曲がる or 直進する が決定する」という意味です
一筆書きの問題は、グラフ理論に置き換えることが可能です（解説ページ）
グラフを探索すれば終わりです

以上です

##図で解説しちゃうよ（ピンと来てない方へ）

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

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

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

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

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

条件について

• 赤だったら曲がる（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は書いてて楽しい