遞歸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上板（你實現一個發電機）。直到呼叫者用解決方案做任何事情。