#
# Solution to the 3x3x3 block puzzle Sander gave me.
# http://nat.org/blog/?p=831
#
# Copyright (C) 2008, Nat Friedman (nat@nat.org)
# Available under http://en.wikipedia.org/wiki/MIT_License
# 

class Debug
  @level = 1

  def self.print level, str
    if level <= @level
      puts str
    end
  end
end

class Space
  def initialize size=5
    @size = size
    @grid = Array.new(@size * @size * @size, false)
  end

  def size
    @size
  end

  def setGrid(grid)
    @grid = grid.clone
  end

  def set(x,y,z)
    @grid[x + y * @size + z * @size * @size] = true
  end

  def get(x,y,z)
    @grid[x + y * @size + z * @size * @size]
  end

  def copy
    newSpace = Space.new @size
    newSpace.setGrid(@grid)
    newSpace
  end
end

# 3D Directions
RIGHT    = [ 1,  0,  0, "Right"]
LEFT     = [-1,  0,  0, "Left"]
FORWARD  = [ 0,  1,  0, "Forward"]
BACK     = [ 0, -1,  0, "Back"]
UP       = [ 0,  0,  1, "Up"]
DOWN     = [ 0,  0, -1, "Down"]

class Snake
  STRAIGHT = 0
  TURN     = 1

  def initialize
    @snake = [STRAIGHT, STRAIGHT, TURN, TURN, TURN, STRAIGHT, TURN,
              TURN, STRAIGHT, TURN, TURN, TURN, STRAIGHT, TURN,
              STRAIGHT, TURN, TURN, TURN, TURN, STRAIGHT, TURN,
              STRAIGHT, TURN, STRAIGHT, TURN, STRAIGHT, nil ]
  end

  def length
    @snake.length
  end

  def nextDir3D(dir, snakeIdx)
    if @snake[snakeIdx] == STRAIGHT
      return [dir]
    end

    # Turning
    if dir == RIGHT or dir == LEFT
      return [FORWARD, BACK, UP, DOWN]
    elsif dir == FORWARD or dir == BACK
      return [LEFT, RIGHT, UP, DOWN]
    elsif dir == UP or dir == DOWN
      return [LEFT, RIGHT, FORWARD, BACK]
    end
  end
end

class Solver3D
  def initialize
    @solutions = 0
    @deadends = 0
  end

  def isTurnLegal(x, y, z, dir, space)
    (xdir, ydir, zdir) = dir
    (newx, newy, newz) = [x + xdir, y + ydir, z + zdir]
      
    Debug.print 2, "Checking legality of turn to (#{newx},#{newy},#{newz})"

    # Bounds checking
    if newx >= space.size or newy >= space.size or newz >= space.size or
        newx < 0 or newy < 0 or newz < 0
      Debug.print 2, "Turn violates bounds #{space.size}"
      return false
    end

    # Check that the next space isn't already occupied
    space.get(x + xdir, y + ydir, z + zdir) == false
  end

  def solveStep(x, y, z, dir, snake, snakeIdx, space, history)
    # Mark that this square in the cube is occupied
    space.set(x, y, z)

    # Compute the next square
    (xdir, ydir, zdir) = dir
    (x, y, z) = [x + xdir, y + ydir, z + zdir]

    # Save the direction
    history.push dir[3]
    
    snakeIdx += 1

    # Solution?
    if snakeIdx == snake.length - 1
      puts "Solution: #{history.join(', ')}"
      @solutions += 1
      return
    end

    # What directions are available from here?
    turns = snake.nextDir3D(dir, snakeIdx)

    # Filter out any turns that would place blocks on top of each
    # other, or cause the snake to extend out of the 3x3x3 space
    legalTurns = turns.select { |t| isTurnLegal(x, y, z, t, space) }

    @deadends += 1 if legalTurns.length == 0
    
    legalTurns.each do |t|
      spaceCopy = space.copy
      historyCopy = history.clone
      solveStep(x, y, z, t, snake, snakeIdx, spaceCopy, historyCopy)
    end
  end

  def solve
    snake = Snake.new
    space = Space.new 3
    snakeidx = 0
    solveStep(0, 0, 0, RIGHT, snake, 0, space, [])
    puts "Found #{@solutions} solutions, #{@deadends} deadends"
  end
end

solver = Solver3D.new
solver.solve