列表如圖中的序言

Question

我試圖從矩陣中的一個元素生成所有可能的'方法'到另一個元素，主條件說矩陣中的元素可以與其他元素相連只有當元素共享至少一個角落時，矩陣

[[1,2,3] 
[5,4,6] 
[8,9,7]] 

1只能用2,4,5連接，但4用所有元素連接。是否有可能將該列表表示爲圖形而不使用吸引？或者，也許我可以找到任何更簡單的方法來做到這一點

---

感謝您的所有答案。 好吧，我提出:-) 現在有謂詞我產生了所有'邊緣'，但我不能在任何地方使用它們，我無法弄清楚，如何使用這種模式([row:R1,column:C1,value:V1], [row:R2,column:C2,value:V2])將每個單元格的累加器（列表）信息添加到累加器（列表）信息。

Answer 1

的有限集合枚舉可以使用Prolog回溯：

adjacent_pos((R,C), (Ra,Ca)) :- 
    (R > 1, Ra is R-1 ; Ra is R ; Ra is R+1), 
    (C > 1, Ca is C-1 ; Ca is C ; Ca is C+1), 
    once(Ra \= R ; Ca \= C). 

使用配對NTH1/3，我們可以接入小區：

cell(Mat, (R,C), Cell) :- 
    nth1(R, Mat, Row), 
    nth1(C, Row, Cell). 

所以，在矩陣不同元件的N×M個：

adjacent(Mat, Elem, Adj) :- 
    cell(Mat, Pe, Elem), 
    adjacent_pos(Pe, Pa), 
    cell(Mat, Pa, Adj). 

簡單的測試：

test :- 
    M = [[1,2,3], 
     [5,4,6], 
     [8,9,7]], 
    findall(A, adjacent(M,1,A), L1), writeln(L1), 
    findall(A, adjacent(M,4,A), L4), writeln(L4). 

收率：

?- test. 
[2,5,4] 
[1,2,3,5,6,8,9,7] 
true. 

請注意，測試R > 1 a nd C > 1可以避免，要求nth1/3失敗'帶外'測試。對於上限也是如此，實際上省略了，另外的好處是我們不限於預定義的矩陣大小。

Answer 2

下面是一個（很長但很簡單）的解決方案。

首先，它有助於有一個輔助謂詞在一個矩陣來檢索Row,Col位置的元素列表，如清單：

get_matrix_entry_nth0(RowInd, ColInd, Matrix, Entry) :- 
    nth0(RowInd, Matrix, Row), 
    nth0(ColInd, Row, Entry). 

其次，它也可以幫助使用此謂詞相對於定義的條目由和Col的方向而言索引的，如：

up_left_entry(R-C, Matrix, E) :- 
    PrevR is R - 1, 
    PrevC is C - 1, 
    get_matrix_entry_nth0(PrevR, PrevC, Matrix, E). 

up_entry(R-C, Matrix, E) :- 
    PrevR is R - 1, 
    get_matrix_entry_nth0(PrevR, C, Matrix, E). 

up_right_entry(R-C, Matrix, E) :- 
    PrevR is R - 1, 
    NextC is C + 1, 
    get_matrix_entry_nth0(PrevR, NextC, Matrix, E). 

right_entry(R-C, Matrix, E) :- 
    NextC is C + 1, 
    get_matrix_entry_nth0(R, NextC, Matrix, E). 

down_right_entry(R-C, Matrix, E) :-  
    NextR is R + 1, 
    NextC is C + 1, 
    get_matrix_entry_nth0(NextR, NextC, Matrix, E). 

down_entry(R-C, Matrix, E) :- 
    NextR is R + 1, 
    get_matrix_entry_nth0(NextR, C, Matrix, E). 

down_left_entry(R-C, Matrix, E) :-  
    NextR is R + 1, 
    PrevC is C - 1, 
    get_matrix_entry_nth0(NextR, PrevC, Matrix, E). 

left_entry(R-C, Matrix, E) :- 
    PrevC is C - 1, 
    get_matrix_entry_nth0(R, PrevC, Matrix, E). 

有了這些輔助謂詞，該解決方案是相當簡單：

matrix_path([R|Rs], P) :- 
    % determine rows, cols 
    length([R|Rs], Rows), 
    length(R, Cols), 
    % defer to matrix_path/4 to compute all paths starting with 0,0 
    matrix_path(0-0, Rows-Cols, [R|Rs], P). 

matrix_path/2是程序的入口點。該單子句謂詞預先確定給定矩陣中的行數和列數，並將處理推遲到從0,0（左上角）元素開始計算的matrix_path/4。

matrix_path(R-C, Rows-Cols, Matrix, P) :- 
    C >= Cols, !, 
    % end of column, proceed to next row 
    NextRow is R + 1, 
    NextRow < Rows, 
    matrix_path(NextRow-0, Rows-Cols, Matrix, P). 

matrix_path/4的第一個子句檢查是否已超過列數;如果是這樣，一個切口（!）用於排除下面的條款，並重新開始下一行中的計算和復位的列索引爲0

matrix_path(R-C, _, Matrix, adj(S, T)) :- 
    % get this entry 
    get_matrix_entry_nth0(R, C, Matrix, S), 
    % get each adjacent entry 
    ( up_left_entry(R-C, Matrix, T) 
    ; up_entry(R-C, Matrix, T) 
    ; up_right_entry(R-C, Matrix, T) 
    ; right_entry(R-C, Matrix, T) 
    ; down_right_entry(R-C, Matrix, T) 
    ; down_entry(R-C, Matrix, T) 
    ; down_left_entry(R-C, Matrix, T) 
    ; left_entry(R-C, Matrix, T) 
    ). 

的matrix_path/4第二條款只是試圖檢索來自給定條目的所有可能的「路徑」。有些可能會失敗（比如查找頂部行），但是Prolog會回溯到找到所有可行的解決方案。

matrix_path(R-C, Rows-Cols, Matrix, P) :- 
    % get the entry for the next column in this row 
    NextC is C + 1, 
    matrix_path(R-NextC, Rows-Cols, Matrix, P). 

的matrix_path/4最後子句簡單地移動相對於所述項目中的相同行中的下一列處理。

運行一個簡單的例子：

?- matrix_path([[1,2],[3,4]], P). 
P = adj(1, 2) ; 
P = adj(1, 4) ; 
P = adj(1, 3) ; 
P = adj(2, 4) ; 
P = adj(2, 3) ; 
P = adj(2, 1) ; 
P = adj(3, 1) ; 
P = adj(3, 2) ; 
P = adj(3, 4) ; 
P = adj(4, 1) ; 
P = adj(4, 2) ; 
P = adj(4, 3) ; 
false. 

請注意，如果你馬上要所有相鄰的一對無回溯，包裹中的呼叫findall/2，像這樣：

?- findall(P, matrix_path([[1,2],[3,4]], P), Ps). 
Ps = [adj(1, 2), adj(1, 4), adj(1, 3), adj(2, 4), adj(2, 3), adj(2, 1), adj(3, 1), adj(3, 2), adj(..., ...)|...].