ナイト巡回問題

お気楽 OCaml プログラミング入門

ナイト巡回問題を解く。
ナイトの動けるマスをリストとして作っちゃえば深さ優先探索でできる。
だからこの前のやつの終了条件を少しいじればおk

/*
３行４列盤
 */

let adjacent = [
  [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],
];

let depth_first_search = start => {
  /* auxは 通ってきた道のり:list(int) と 現在地:int を受け取る */
  let rec aux = (curPos, pathList) =>
    switch (List.length(pathList) == List.length(adjacent) - 1) {
    | true => [List.rev([curPos, ...pathList])]
    | _ =>
      curPos
      |> List.nth(adjacent)  /* 現在地からつながっているとこ取り出す */
      |> List.fold_left(
           /* それぞれについて探索 & 合成して返す */
           (acc, el) =>
             List.mem(el, pathList) ?
               acc : acc @ aux(el, [curPos, ...pathList]),
           [],
         )
    };
  aux(start, []);
};

let test4 = depth_first_search(0);