时间戳

首页 > 解决方案 > 需要一些关于我在 Ocaml 中尝试解决此问题的 fold_neighbours 的反馈

ocaml - 需要一些关于我在 Ocaml 中尝试解决此问题的 fold_neighbours 的反馈

问题描述

该程序是使用递归和图形着色来读取和解决数独板的尝试。

type vertex = int * int 

module Vertex = Map.Make(struct
  type t = vertex
  let compare = Stdlib.compare
  end)

let ascii_digit c = Char.code c - Char.code '0'

let read_matrix chan = 
  let rec loop i j grid = 
    match input_char chan with 
    | exception End_of_file -> grid
    | '\n' -> loop (i+1) 0 grid
    | '0'..'9' as c ->
      loop i (j+1) @@
      Vertex.add (i,j) (ascii_digit c) grid
    | _ -> invalid_arg "invalid input" in
  loop 0 0 Vertex.empty

let matrix_from_file file =
  let chan = open_in file in
  let r = read_matrix chan in
  close_in chan;
  r

(*Print grid method*)
let print_vertex vertex = 
  let print_node (x,y) g  = 
    Printf.printf "\n(%d, %d) = " x y;
    print_int g
  in
  Vertex.iter print_node vertex

(*Print pretty sudoku*)
let print_board vertex = 
  let print_node (_x,_y) _grid =
    if _y = 0 then 
      Printf.printf "\n | ";
      print_int _grid;
      print_string " | "
  in 
  Vertex.iter print_node vertex

我试图实现这个 fold_neighbours 但我不能让它与我的（Map.Vertex）一起工作。我认为我的逻辑是正确的，但是会出现很多错误等。也许我应该将这些功能分解为单独的功能？

let fold_neighbours v gamma game =
  let in_quadrant (x1, y1) (x2, y2) = 
    x1/3 = x2/3 && y1/3 = y2/3 
  in 
  let is_neighbour v n = 
    in_quadrant v n || fst v = fst n || snd v = snd n
  in 
  let filter v gamma  = 
    if is_neighbour neigh v' then
      f v' g' a
    else 
      a
  in
  fold_vertices filter game

标签： ocamlbacktrackingsudokugraph-coloring

解决方案

这比你想象的要容易得多。为了使它更容易，让我们将任务分成简单的子任务，我们不会出错。首先，让我们定义什么是邻居。为了使事情可视化，让我们用指南针方向表示位置（如果您觉得更容易理解，我们可以只使用向上和向下）

let north (x,y) = (x+1,y) (* [north p] is to the north of [p] *)
let northeast (x,y) = (x+1,y+1) (* [north p] is to the north of [p] *)
...
let south (x,y) = (x-1,y) (* [north p] is to the north of [p] *)
...
let norhtwest (x,y) = (x-1,y+1) (* [north p] is to the north of [p] *)

现在，我们可以说邻居集合是，

let neighbors p = [
  north p;
  northeast p;
  ...
  northwest p;
]

我们可以编写一个函数，它接受一个顶点和游戏地图并折叠所有可用的邻居，

let fold_neighbors vertex map ~init ~f =
  let visit s v = match Vertex.find_opt v map with
    | None -> s
    | Some d -> f v d s in
  List.fold_left visit init (neighbors vertex)

请注意，我将f三个参数传递给访问函数，邻居坐标、游戏中顶点的值和状态。

最后一点。您可能会发现以这种声明性方式定义邻居列表不是程序化的。好吧，当然可以编写一个生成这八个顶点的函数。为此，我们将使用生成递归。通常很难推理，但为了学习，让我们尝试一下，这是我的看法，

let neighbors (x,y) =
  let rec gen i j =
    if i = 0 && j = 0 then gen (i+1) j
    else if i < 2 then (x+i,y+j) :: gen (i+1) j
    else if j < 1 then gen (-1) (j+1)
    else [] in
  gen (-1) (-1)

嗯，看起来很丑，但有效。能不能写得更好？试试看，用更好的版本更新我的答案！:)

推荐阅读