推薦閱讀：web
八數碼難題：33的9個方格中有1到8的整數，並用0表示空白格。非0數字能夠向與之相鄰的空白格（即0的位置）移動，同時空白格向這個數字原來的位置移動。經過若干步的移動，將33方格中的數字排列在指定的位置。用prolog寫代碼，求解八數碼難題。app
題目中的意思咱們用數學的方式表示出來：svg
初始狀態爲：
1 2 3
4 5 6
0 7 8編碼
目標狀態爲：
2 3 0
1 4 5
7 8 6.net
對於這個問題咱們來做以下分析：
（1）能夠用列表來表達一個八數碼狀態，例如[0 1 2 3 4 5 6 7 8 ]表示的數碼狀態是：0 1 2 是第一行，3 4 5是第二行，6 7 8是第三行。33的方格序號（即位置）按照行編碼，因此列表[0 1 2 3 4 5 6 7 8 ]中數的序號分別是1 2 3 4 5 6 7 8 9。用謂詞write_array_list(integer)輸出列表形式的狀態爲3*3形式，即每輸出3個數就換行。設計
（2）用謂詞list_same(integer*,integer*)來比較2個列表是否相同，用來判斷狀態轉移是否到達最終目標code
（3）用謂詞swap(integer*,integer,integer, integer*)來實現0（即空格）和某個相鄰數字的交換。Swap的第1個參數是交換前的列表，第4個參數是交換後的列表，第二、3個參數表明要交換的2個數的序號（即位置）。例如[0 1 2 3 4 5 6 7 8 ]中，序號一、 2的數0和1能夠交換；序號1 、4的數0和3能夠交換；由於沒有空格，序號二、3的數1和2不能交換；由於不相鄰，序號一、7的數0和6不能交換。xml
（4） 爲了實現swap，要設計根據序號對列表進行取值、賦值的謂詞。blog
（5）設計謂詞findZeroPosition，找到列表中空格的序號（0的位置），已知空格序號後，其周圍哪些位置的數能夠交換就肯定了。例如當空格序號爲5時，空格能夠和序號爲二、四、六、8的數進行交換。遞歸
（6）核心規則是move(linelist,linelist,integer):-…swap…move ….
規則左邊的move第1個參數爲列表表達的當前狀態，第2個參數爲列表表達的目標狀態，第3個參數是深度，move規則每遞歸1次，深度減1，要求深度大於等於0。設置深度是爲了不無心義的狀態轉移，例如在[0 1 2 3 4 5 6 7 8 ]中，序號一、2對應的數0和1能夠交換，交換後1和0又能夠交換，這種無盡交換沒有價值，經過設置深度來淘汰這種交換。規則的右邊move是左邊move的下一個狀態。右邊的move以前，應該檢測空格序號（0的位置），隨後肯定空格能夠與哪些序號交換，而後調用swap進行交換，最後是對交換後的列表（即新狀態）遞歸move。
（7）設置move遞歸的終止條件。寫一條move規則判斷是否已經到達最終目標，即判斷move中的第一、2個參數表明的列表是否相等。
move(linelist,linelist,integer)
（8）到達目標後設計輸出狀態序列的輸出。
代碼實現以下：
DOMAINS
integerlist=integer*
PREDICATES
write_array_list(integerlist)%輸出序列
list_same(integerlist,integerlist)%比較兩個狀態是否相等
nondeterm findZeroPosition(integerlist,integer)%找出0的位置
swap(integerlist,integer,integer,integerlist)%交換兩個位置的值，併成爲一個新的表
get(integerlist,integer,integer)%得到要交換的位置的值
set(integerlist,integer,integer,integerlist)%給要交換的位置復賦值
nondeterm move(integerlist,integerlist,integer,integerlist)%與0位置交換，併成爲新的表
nondeterm value(integer,integer)%獲取能夠與0交換的位置
compareSL(integerlist,integerlist)%判斷當前狀態是否在狀態序列中
append(integerlist,integerlist,integerlist)%將兩個表合成一個新的表
writeSL(integerlist)%輸出狀態序列
CLAUSES
append([], List, List).
append([X|L1], List2, [X|L3]) :-
append(L1, List2, L3).
writeSL([]):-!.
writeSL([X1,X2,X3,X4,X5,X6,X7,X8,X9|SL]):-write(X1),write(""),write(X2),write(""),write(X3),write(""),nl,
write(X4),write(""),write(X5),write(""),write(X6),write(""),nl,
write(X7),write(""),write(X8),write(""),write(X9),write(""),nl,nl,writeSL(SL).
compareSL(L,[]).
compareSL([X1,X2,X3,X4,X5,X6,X7,X8,X9],[Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8,Y9|_]):-X1=Y1,X2=Y2,X3=Y3,X4=Y4,X5=Y5,X6=Y6,X7=Y7,X8=Y8,X9=Y9,!,fail.
compareSL(L,[X1,X2,X3,X4,X5,X6,X7,X8,X9|SL]):-compareSL(L,SL).
write_array_list([]).%輸出列表
write_array_list([X,Y,Z|L]):-write(X),write(""),write(Y),write(""),write(Z),nl,write_array_list(L).
list_same([],[]):-!.
list_same([X|L1],[Y|L2]):-X=Y,list_same(L1,L2).%比較列表是否相同
findZeroPosition([0|L],X):-X=1,!.
findZeroPosition([H|L],X):-findZeroPosition(L,X1),X=X1+1.
value(1,2).value(1,4).
value(2,1).value(2,3).value(2,5).
value(3,2).value(3,6).
value(4,1).value(4,5).value(4,7).
value(5,2).value(5,4).value(5,6).value(5,8).
value(6,3).value(6,5).value(6,9).
value(7,4).value(7,8).
value(8,5).value(8,7).value(8,9).
value(9,6).value(9,8).
swap(L1,X,Y,L2):-get(L1,X,X1),get(L1,Y,Y1),set(L1,X,Y1,L22),set(L22,Y,X1,L2).
get([X|_],1,X):-!.
get([X|Y],A,B):-A1=A-1,get(Y,A1,B).
set([X|Y],1,B,[B|Y]):-!.
set([X|L1],A,B,[X|L2]):-A1=A-1,set(L1,A1,B,L2).
move(L1,L2,X,SL):-list_same(L1,L2),
writeSL(SL),!.
move(L1,L2,X,SL):- X>=0,
findZeroPosition(L1,ZERO),
value(ZERO,Y),
swap(L1,ZERO,Y,L11),
compareSL(L11,SL),append(SL,L11,SL2),
X1=X-1,
move(L11,L2,X1,SL2).
GOAL
move([1,2,3,4,5,6,0,7,8],[2,3,0,1,4,5,7,8,6],7,[1,2,3,4,5,6,0,7,8]).