triangle_peg.rb

# This is a programming chellenge from David Bock's series
# "What Computer Scientists Know".  This is a problem that can
# be used to discuss a bunch of computer science topics, but
# as I'm providing most of the skeleton of the solution, the
# point of this exercise is to demonstrate 'recursive backtracking'.

# http://en.wikipedia.org/wiki/Backtracking

# this problem is based on the classic 'triange peg game', a common
# sight in roadside diners in America, in particular, Cracker
# Barrel restaurants:

# http://www.memory-improvement-tips.com/pegs.html

# If we were starting from scratch, we could have a long discussion
# about the data structure we'd use to represent the board, how
# we'd choose to represent a move, and how we'd apply moves to
# the board to change its state.  While I'm not going to give you
# all of the answers to that, I'm going to give you one possible
# representation so we can get to the heart of the nature of
# recursive backtracking.
#
# Representing the Board
#
# We could choose to represent the board as a two dimensional
# array, or even 15 individual boolean values, but for this
# exercise, I'm choosing a 1-dimensional array of length 15,
# where we use the value '1' to represent a peg and '0' to
# represent a hole.  Thus a board that looks like this:
#
#          X
#         X X
#        X O X
#       X X X X
#      X X X X X
#
# would, in code, look like:
#

pegs = [1,1,1,1,0,1,1,1,1,1,1,1,1,1,1]

#
# But thats not all... We are going to have some behavior around
# this data structure, and we are in ab object-oriented language,
# so lets encapsulate that like good programmers in a class:
#

class Board
  attr_reader :pegs

  def initialize(pegs)
    @pegs = pegs
  end
  
end

# We can now think of 'moves' as an array of three elements - 
# the starting peg, the peg we are jumping over, and the ending peg.
# So possible moves would look like:
a_move = [3, 4, 5]

# We can know in advance every possible move in the game.  Lets define
# those now:

POSSIBLE_MOVES = [[3,4,5], [5,4,3],
                  [6,7,8], [8,7,6],
                  [7,8,9], [9,8,7],
                  [10,11,12], [12,11,10],
                  [11,12,13], [13,12,11],
                  [12,13,14], [14,13,12],
                  [0,1,3], [3,1,0],
                  [1,3,6], [6,3,1],
                  [3,6,10], [10,6,3],
                  [2,4,7], [7,4,2],
                  [4,7,11], [11,7,4],
                  [5,8,12], [12,8,5],
                  [0,2,5], [5,2,0],
                  [2,5,9], [9,5,2],
                  [5,9,14], [14,9,5],
                  [1,4,8], [8,4,1],
                  [4,8,13], [13,8,4],
                  [3,7,12], [12,7,3]
                 ]

# note that this isn't saying what moves are currently legal based on the
# board state... we'll need a function to determine that. see the
# definition of legal_move? and valid_moves below to see how thats done.

# A board should be able to know if it is in a solved state.  I should
# be able to say

a_board = Board.new([0,0,0,0,1,0,0,0,0,0,0,0,0,0,0])
a_board.solved?

# and get back 'true', since there is only one peg.  This function is also
# provided for you.

# And finally, given a board, we should be able to solve it.

Board.new([0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]).solve

# and every board position should be printed. (of course, you could choose to
# collect them into an array, write them to a file, or stick them in a
# database if you wanted to, but for our purposes, a 'puts' of the moves
# is all we need.

# Here is a Board class with all the behavior we just talked about. Again,
# you could choose to do this a half dozen different ways, but with this
# skeleton, you can concentrate on the recursive backtracking part of the
# problem instead of the data structure part of the problem.  Feel free
# to use whatever data structure you'd like if something else suits you...
# that could be valuable conversation in another talk in this series.

class Board
  attr_reader :pegs
  @@solution_count = 0

  def initialize(pegs)
    @pegs = pegs
  end

  # a move is legal if:
  #   - there is currently a peg in the starting position
  #   - there is currently a peg to jump over
  #   - there is an empty hole in the ending position.
  def legal_move?(move)
    @pegs[move[0]] == 1 && @pegs[move[1]] == 1 && @pegs[move[2]] == 0
  end
  
  # from all the possible moves, lets select all the legal moves
  # based on the current board state.
  def valid_moves
    POSSIBLE_MOVES.select { |m| legal_move?(m) }
  end

  # One of the pleasures of choosing a good data structure; some problems
  # just melt away.  We can sum up all the pegs - if there is only 1,
  # the board is solved.
  def solved?
    @pegs.inject(:+) == 1
  end
  
  
  # This is your method to do with as you please... you can change the
  # method signature, decide recursion isn't for you and attempt an
  # iterative solution, or whatever you want!
  #
  # The skeleton here is a reminder of the first 'recursion template'
  # we saw in the first recursion presentation.
  def solve
    if solved?
      # this is our base condition....
      @@solution_count = @@solution_count + 1
    else
      # and this is where we recurse...
    end
    nil
  end

  private
  
  # You might need other methods to solve this... for instance,
  # would it be useful to have a method that took a move and returned
  # a brand new instance of Board with the board state after that
  # move had been applied?
end

# We want to create a board for each possible starting position, which
# would be 15 possible boards.  However, there are symmetries that
# reduce this.  If you find one solution, you can do the same solution
# 'in a mirror' and get a new solution.  You can also rotate the board
# around 1/3, do the same relative movements, and get another solution.
# If we want to consider all those possible variations equivalent, then
# there are only 4 starting boards.
boards = []
boards << Board.new([0,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
boards << Board.new([1,0,1,1,1,1,1,1,1,1,1,1,1,1,1])
boards << Board.new([1,1,1,0,1,1,1,1,1,1,1,1,1,1,1])
boards <<  Board.new([1,1,1,1,0,1,1,1,1,1,1,1,1,1,1])

# Now we can call solve on each of those in turn.  While we're at it,
# lets time how long this takes using Ruby's 'benchmark' library:
require 'benchmark'

results = Benchmark.measure {
  boards.each do |board|
    board.solve
  end
}

# by my solution, there are 131448 solutions to those 4 board
# starting positions.

# Hmm... interesting that there are 4 boards that can be solved
# independently.  perhaps we could start up 4 different threads
# and see if we can get this to run any faster... but thats another
# topic...


# once you understand a working version of this, there are *all kinds*
# of applications for this technique.  Chess-playing computers
# use exactly this technique, as to many combinatorial games from
# tic tac toe to checkers.  You could look pretty smart and start
# reading books like
#
# http://www.amazon.com/Combinatorial-Theory-Graduate-Studies-Mathematics/dp/082185190X/ref=pd_sim_sbs_b_2
#
# When we start talking about data strutures like trees, and
# algorithms like sorting and searching, having this kind of
# stuff in your head will have those make a lot more sense.
#
# Finally, I'd bet backtracking like this occurs in sql databases
# all over the place, from query optimization to calculating
# result sets.