개시하다

FUJITSU Advent Calendar 2018 중 2 19일째 보도다.
(주의) 이 글은 개인의 견해이지 소속사, 조직의 대표가 아니다.

의 목적

루비의 학습
시마네현민으로서 모르면 부끄럽나요?및

큐브가 뭐예요?

큐브(이하 SC)는 나무로 만든 수수께끼입니다.


위쪽처럼 흩어진 상태에서 아래쪽 같은 입방체로 바꾸면 승리한 것 같아요
해봤는데 어려워서 못 풀겠어!
※ 참고로 사진은 필자의 필통에 늘 곁들인 파트너

계산법을 생각해 보세요.

약간 조건이 있는 문제입니다.
조건이란'블록의 유형이 각도나 다른 것에 따라 모퉁이나 직진을 결정한다'는 뜻이다.
한 획으로 쓴 문제는 도표 이론으로 바꿀 수 있다설명 페이지
차트 검색이 끝납니다.
이것뿐이다

그림으로 설명할게요.

※ 단순화를 위해 3x3의 평면을 고려

3x3의 공간 준비

시작 장소를 적절히 결정

조건에 따라 하나씩 적는다
　　 　　

모두 채우고 끝

조건 정보
-빨간색이면 꺾여(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가 너무 좋다고 써있어요.