递归Clojure中

Question

这个问题产生额外的空列表是关于本课程的练习：http://iloveponies.github.io/120-hour-epic-sax-marathon/sudoku.html

我实现的功能solve返回解决数独板，但除了它周围有很多空的列表。我所有的其他功能都正常工作，不会返回任何空列表。我无法弄清楚为什么会发生这种情况。

下面是相关代码：

(defn solve [board] 
    (if-let [point (find-empty-point board)] 
    (let [valid-values (valid-values-for board point)] 
     (for [value valid-values] 
     (solve (set-value-at board point value)))) 
    (if (valid-solution? board) 
     board))) 

(def sudoku-board 
    (board [[5 3 0 0 7 0 0 0 0] 
      [6 0 0 1 9 5 0 0 0] 
      [0 9 8 0 0 0 0 6 0] 
      [8 0 0 0 6 0 0 0 3] 
      [4 0 0 8 0 3 0 0 1] 
      [7 0 0 0 2 0 0 0 6] 
      [0 6 0 0 0 0 2 8 0] 
      [0 0 0 4 1 9 0 0 5] 
      [0 0 0 0 8 0 0 7 9]])) 

输出：

(solve sudoku-board) 
(((((())()) 
((((((() (())) (())) ((() (())) ((()))) ((()) ((())))))) 
(() ((((() (())) (())) ((() (())) ((()))) ((()) ((())))))) 
(((((() (())) (())) ((() (())) ((()))) ((()) ((()))))))) 
((()) (()))) 
(((((((() (())) (())) ((() (())) ((()))) ((()) ((())))))) 
(() ((((() (())) (())) ((() (())) ((()))) ((()) ((())))))) 
(((((() (())) (())) ((() (())) ((()))) ((()) ((()))))))) 

...

(((((((((((((((([[5 3 4 6 7 8 9 1 2] 
                [6 7 2 1 9 5 3 4 8] 
                [1 9 8 3 4 2 5 6 7] 
                [8 5 9 7 6 1 4 2 3] 
                [4 2 6 8 5 3 7 9 1] 
                [7 1 3 9 2 4 8 5 6] 
                [9 6 1 5 3 7 2 8 4] 
                [2 8 7 4 1 9 6 3 5] 
                [3 4 5 2 8 6 1 7 9]])))))))))) 

...

((((((((()) ((((((()) (()))))) (((((((()))) ((())))))))) ((((((()()) (())))) ((((()()) (()))))) (()))) 
        (((((((()())))) ((((()()))))) (()) (((((()())))) ((((()())))))) 
        ((((()))()) ((() (())) (()) (()))) 
        (((() (((())))) (()) (())) (((((()))))()))) 
        (((()) ((((((()) (()))))) (((((((()))) ((())))))))) (((((((((((((())))))))))))()))))) 
       ())))))) 
     ()))))) 
    ()))))) 

Answer 1

正如coredump所说，你需要更加小心地结合递归调用的结果。尤其要注意的是，您的“退货类型”不一致：在if-let的else分行中，您返回一个解决方案，但在then分行中返回由for生成的解决方案列表。

为了能够有意义地调用你的函数，它应该返回一个一致的类型：一系列解决方案。下面是改变返回值永远是一个列表的简单变化，并会确保所有Concat的的子列表，以避免引入嵌套的额外层次：

(defn solve [board] 
    (if-let [point (find-empty-point board)] 
    (let [valid-values (valid-values-for board point)] 
     (for [value valid-values 
      solution (solve (set-value-at board point value))] 
     solution)) 
    (if (valid-solution? board) 
     [board]))) 

Answer 2

for构造将列表理解的主体中计算的每个值累加为一个惰性序列。当你递归调用解决方案时，你正在计算嵌套序列中的这样的序列等。

你应该附加这些列表，以便将结果展平。

个人，但我不知道它是多么地道Clojure的，我也只是接受一个回调函数fn和执行doseq而不是for，使每个解决方案板，你只需要调用fn上板（你实现一个发电机）。直到呼叫者用解决方案做任何事情。