zelda.rb

require 'Matrix'

class Matrix
  public :"[]=", :set_element, :set_component
end

# Prints de Matrix
def print_matrix(m)
  puts "----------"
  print m[0,0] ? 1 : 0, " ", m[0,1] ? 1 : 0, " ", m[0,2] ? 1 : 0
  puts ""
  print m[1,0] ? 1 : 0, " ", m[1,1] ? 1 : 0, " ", m[1,2] ? 1 : 0
  puts ""
  print m[2,0] ? 1 : 0, " ", m[2,1] ? 1 : 0, " ", m[2,2] ? 1 : 0
  puts ""
  puts "----------"
end

# Checks if all matrix is true
def check_true(m)
  m.each do |element|
    if !element
      return false
    end 
  end
  return true
end

# Checks if index inside Matrix
def inbound(m,x,y)
  if (x >= 0 and y>= 0 and x < m.column(0).size and y < m.row(0).size) 
    return true
  end
  return false
end

# Returns random integer between 0 and max that is different than i
def randint(max,i)
  r=i
  while (r==i)
    r = rand(max)
  end
  return r
end

# Hits a ball reproducing the behaviour in Zelda's game
def hit(m,x,y)
  m[x,y] = !m[x,y]
  inbound(m,x+1,y) ? m[x+1,y] = !m[x+1,y] : false
  inbound(m,x-1,y) ? m[x-1,y] = !m[x-1,y] : false
  inbound(m,x,y+1) ? m[x,y+1] = !m[x,y+1] : false
  inbound(m,x,y-1) ? m[x,y-1] = !m[x,y-1] : false
end

# Where the magic happens
def backtracking(m,l,x,y,depth)
  # Add the first ball to the list
  l.push(x.to_s+','+y.to_s)

  # Hit the ball
  hit(m,x,y)

  # Print the resulting matrix
  print_matrix(m)

  # Check if all balls are blue
  if check_true(m)
    return l
  end

  # Check if we reached the desired depth
  if depth <= 0
    return nil
  end

  # "Decide" the next hit avoiding to hit the same element
  next_x = randint(3,x)
  next_y = randint(3,y)

  # Backtracking with the new elements
  l = backtracking(m,l,next_x,next_y,depth-1)

  # Return the list
  return l
end

# Empty list
l = []

# The Matrix represents the initial status (true = blue)
m = Matrix[
  [true,false,true], 
  [false, true, false], 
  [true,false,true]
]

# Decided to start the seqeucne at (1,1) with a depth of 30 hits.
l = backtracking(m,l,1,1,30)

# Writes the sequence
puts l