ナイト巡回問題

3×4の盤面でのナイト巡回問題
お気楽 OCaml プログラミング入門

次のノードがわかる問題の全探索は
ぱっとできるようになった気がする

# 隣接リストバージョン
$adjList = [
  [5, 7],
  [6, 8],
  [3, 7],
  [2, 8, 10],
  [9, 11],
  [0, 6, 10],
  [1, 5, 11],
  [0, 2],
  [1, 3, 9],
  [4, 8],
  [3, 5],
  [4, 6]
]

def knightTour(acc = [0])
  return [] if acc != acc.uniq
  return [acc] if acc.length == $adjList.length

  # 今のポジション
  curPos = acc[-1]

  # 次の候補
  nextNodes = $adjList[curPos]

  # 深さ優先探索
  nextNodes.reduce([]) do |acc2, cur|
    acc2 + knightTour([*acc, cur])
  end
end

#隣接行列バージョン
adjMat = [
  [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
  [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
  [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
  [0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
]
def knightTour2(acc = [0])
  return [] if acc != acc.uniq
  return [acc] if acc.length == $adjMat.length

  # 今のポジション
  curPos = acc[-1]

  # 次の候補
  nextNodes = $adjMat.each_index.select { |i| $adjMat[curPos][i] == 1 }

  # 深さ優先探索
  nextNodes.reduce([]) do |acc2, cur|
    acc2 + knightTour2([*acc, cur])
  end
end