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

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], [4,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]
                 ]

alias Move = Array(Int32)
alias Solution = Array(Move)

class Board
  getter :pegs
  @@solution_count = 0
  @pegs : Array(Int32)

  def initialize(@pegs)
  end

  def self.solution_count
    @@solution_count
  end

  def self.solutions
    @@solutions
  end

  def legal_move?(move)
    @pegs[move[0]] == 1 && @pegs[move[1]] == 1 && @pegs[move[2]] == 0
  end

  def valid_moves
    POSSIBLE_MOVES.select { |m| legal_move?(m) }
  end

  def solved?
    @pegs.sum == 1
  end

  def solve(moves = [] of Move) : Array(Solution)
    if solved?
      @@solution_count = @@solution_count + 1
      [moves]
    else
      valid_moves.flat_map { |move|
        new_board = @pegs.dup
        new_board[move[0]] = 0
        new_board[move[1]] = 0
        new_board[move[2]] = 1
        Board.new(new_board).solve(moves + [move]) as Array(Solution)
      }
    end
  end

  def to_s(io)
    io << "Board["
    @pegs.each { |p| io << p }
    io << "]"
  end
end

boards = [] of Board
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])

require "benchmark"

results = Benchmark.measure {
  boards.each do |board|
    puts "Solutions for #{board}"
    board.solve
    # .each { |solution| p solution }
  end
}

puts "Benchmark: #{results}"
puts "There were #{Board.solution_count} solutions"