人工智能之八数码难题

推荐阅读：

•  我的CSDN
•  我的博客园
•  QQ群：704621321

八数码难题：33的9个方格中有1到8的整数，并用0表示空白格。非0数字可以向与之相邻的空白格（即0的位置）移动，同时空白格向这个数字原来的位置移动。通过若干步的移动，将33方格中的数字排列在指定的位置。用prolog写代码，求解八数码难题。

题目中的意思我们用数学的方式表示出来：

初始状态为：
1 2 3
4 5 6
0 7 8

目标状态为：
2 3 0
1 4 5
7 8 6

对于这个问题我们来作如下分析：
（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个列表是否相同，用来判断状态转移是否到达最终目标

（3）用谓词swap(integer*,integer,integer, integer*)来实现0（即空格）和某个相邻数字的交换。Swap的第1个参数是交换前的列表，第4个参数是交换后的列表，第2、3个参数代表要交换的2个数的序号（即位置）。例如[0 1 2 3 4 5 6 7 8 ]中，序号1、 2的数0和1可以交换；序号1 、4的数0和3可以交换；因为没有空格，序号2、3的数1和2不能交换；因为不相邻，序号1、7的数0和6不能交换。

（4） 为了实现swap，要设计根据序号对列表进行取值、赋值的谓词。

（5）设计谓词findZeroPosition，找到列表中空格的序号（0的位置），已知空格序号后，其周围哪些位置的数可以交换就确定了。例如当空格序号为5时，空格可以和序号为2、4、6、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 ]中，序号1、2对应的数0和1可以交换，交换后1和0又可以交换，这种无尽交换没有价值，通过设置深度来淘汰这种交换。规则的右边move是左边move的下一个状态。右边的move之前，应该检测空格序号（0的位置），随后确定空格可以与哪些序号交换，然后调用swap进行交换，最后是对交换后的列表（即新状态）递归move。

（7）设置move递归的终止条件。写一条move规则判断是否已经到达最终目标，即判断move中的第1、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]).


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
 

文章来源: unity3d.blog.csdn.net，作者：爱上游戏开发，版权归原作者所有，如需转载，请联系作者。

原文链接：unity3d.blog.csdn.net/article/details/84338140