cube_puzzle_solver.rb

require 'matrix'


BASIC_ROTATIONS = {
  :x => Matrix[
    [1, 0, 0],
    [0, 0, -1],
    [0, 1, 0]
  ],
  :y => Matrix[
    [0, 0, 1],
    [0, 1, 0],
    [-1, 0, 0]
  ],
  :z => Matrix[
    [0, -1, 0],
    [1, 0, 0],
    [0, 0, 1]
  ]
}

ROTATIONS = []
(0..3).each do |i|
  power = BASIC_ROTATIONS[:z] ** i
  ROTATIONS << power
  ROTATIONS << power * (BASIC_ROTATIONS[:x] ** 2)
end
(0..3).each do |i|
  power = BASIC_ROTATIONS[:y] ** i
  ROTATIONS << power * BASIC_ROTATIONS[:x]
  ROTATIONS << power * (BASIC_ROTATIONS[:x] ** 3)
end
(0..3).each do |i|
  power = BASIC_ROTATIONS[:x] ** i
  ROTATIONS << power * BASIC_ROTATIONS[:y]
  ROTATIONS << power * (BASIC_ROTATIONS[:y] ** 3)
end

pieces = [
  [Vector[0, -1, -1], Vector[-1, 0, -1], Vector[0, 0, -1], Vector[0, -1, 0], Vector[1, -1, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[0, 0, -1], Vector[0, 0, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[1, -1, -1], Vector[-1, 0, -1], Vector[-1, 0, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[1, -1, -1], Vector[-1, 0, -1], Vector[0, -1, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[-1, 0, -1], Vector[-1, 0, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[1, -1, -1], Vector[-1, 0, -1]]
]

cells = []
(-1..1).each do |x|
  (-1..1).each do |y|
    (-1..1).each do |z|
      cells << Vector[x, y, z]
    end
  end
end

def check_single(cells, piece, rotation, translation)
  new_cells = cells.clone
  piece.each do |cube|
    after_cube = rotation * cube + translation
    if after_cube.all?{|s| s.between?(-1, 1)}
      if cells.include?(after_cube)
        new_cells.delete(after_cube)
      else
        return nil
      end
    else
      return nil
    end
  end
  return new_cells
end

def check(cells, pieces, result) 
  return result if pieces.empty?
  piece = pieces[0]
  ROTATIONS.each do |rotation|
    first_cube = rotation * piece[0]
    cells.each do |cell|
      translation = cell - first_cube
      new_cells = check_single(cells, piece, rotation, translation)
      if new_cells
        new_result = result + [new_cells]
        final_result = check(new_cells, pieces.reject{|s| s == piece}, new_result)
        if final_result
          return final_result
        end
      end
    end
  end
  return nil
end

def output(cells)
  (-1..1).each do |z|
    (-1..1).each do |y|
      print("[")
      (-1..1).each do |x|
        if cells.include?(Vector[x, y, z])
          print(" ")
        else
          print("#")
        end
      end
      puts("]")
    end
  end
end

result = check(cells, pieces, [])
if result
  result.each do |each_result|
    output(each_result)
    puts("---")
  end
else
  puts("impossible")
end