递归在 Clojure 中产生额外的空列表

Question

这个问题是关于本类(class)的练习: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 分支中，您返回一个解决方案，但在 然后 分支返回由 for 生成的解决方案列表。

为了能够有意义地调用您的函数，它应该返回一个一致的类型:一个解决方案列表。这是一个简单的更改，将返回值更改为始终是一个列表，并确保连接所有子列表以避免引入额外的嵌套级别:

(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])))