スニーカーの靴紐の通し方についての問題（Ruby）

問題：
スニーカーに靴紐を通すのに、左右に6個づつ、計12個の穴があるとします。色いろな通し方がありますが、左右の穴に交互に紐を通していった場合、紐が交差してできる点の数の最大値はいくらになるでしょうか。なお、一番上の穴から通し始めて、最後も一番上の穴で終わるようにします。

Ruby で解いてみました。２重の深さ優先探索で求めています。

class ShoeString
  def initialize(left, right)
    @left = left
    @right = right
  end
  attr_reader :left, :right
end

def left_set(left, right, pattern)
  if pattern.size == 10
    @patterns << pattern + [ShoeString.new(left.last, 1)]
  else
    ((2..6).to_a - right).each do |hole_r|
      right_set(left, right + [hole_r], pattern + [ShoeString.new(left.last, hole_r)])
    end
  end
end

def right_set(left, right, pattern)
  ((1..6).to_a - left).each do |hole_l|
    left_set(left + [hole_l], right, pattern + [ShoeString.new(hole_l, right.last)])
  end
end

@patterns = []
left_set([1], [], [])

def cross?(a, b)
  return false if a.left == b.left
  a, b = b, a if a.left > b.left
  a.right > b.right
end

max = 0
@patterns.each do |pa|
  counter = 0
  pa.combination(2) {|a, b| counter += 1 if cross?(a, b)}
  max = counter if max < counter
end
puts max    #=>45

これを実行すると 45が最大値になります。結構ありますね。

なお最大値を与えるパターンのひとつは以下です。

[#<ShoeString:0x00556c44c322a0 @left=1, @right=6>, #<ShoeString:0x00556c44c32188 @left=2, @right=6>,
 #<ShoeString:0x00556c44cb2ec8 @left=2, @right=5>, #<ShoeString:0x00556c44cb2db0 @left=3, @right=5>,
 #<ShoeString:0x00556c44cba920 @left=3, @right=4>, #<ShoeString:0x00556c44cba808 @left=4, @right=4>,
 #<ShoeString:0x00556c44cb9f98 @left=4, @right=3>, #<ShoeString:0x00556c44cb9e80 @left=5, @right=3>,
 #<ShoeString:0x00556c44cb9d68 @left=5, @right=2>, #<ShoeString:0x00556c44cb9c50 @left=6, @right=2>,
 #<ShoeString:0x00556c44cb9bd8 @left=6, @right=1>]