An example from "What Computer Scientists Know: Thinking Recursively, Part 2. In this example we are going to explore how we use our newfound knowledge of recursion to search through all the solutions of a simple puzzle using recursive backtracking.

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. 

Crystal solution as promised: https://gist.github.com/bjmllr/1054fceba5f399274fedcdac99917e40

I seem to have accidentally fixed whatever was causing the program to report an extra 30k or so solutions in the course of adding the ability to print out all the solutions. I tried using tuples for moves and booleans for pegs, but neither seemed to affect the benchmark, perhaps LLVM was already doing those optimizations for us. BItArray might have been a more efficient peg representation.