-
Notifications
You must be signed in to change notification settings - Fork 3
/
breadth.py
68 lines (60 loc) · 1.47 KB
/
breadth.py
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
#!/usr/bin/env python
# encoding: utf-8
"""
breadth.py
Created by Andrew Lenox on 2010-09-25.
Copyright (c) 2010 __MyCompanyName__. All rights reserved.
"""
import sys
import os
import towers
from collections import deque
from copy import deepcopy
from copy import copy
def prune_children(children, open_states, closed):
for child in children[:]:
if open_states:
for state in open_states:
if child.equal(state):
children.remove(child)
if closed:
for state in closed:
if child.equal(state):
children.remove(child)
return children
def breadth_first_search():
"""non recursive depth first search on a game state"""
start = towers.towers()
print "starting state:"
start.toString()
print ""
open_states = deque([start])
closed = list()
while open_states:
X = open_states.popleft()
if X.solved():
return X
else:
X.generateMoves
moves = X.validMoves
#generate children of X
children = []
for move in moves:
Y = deepcopy(X)
Y.move(move)
children.append(Y)
#put X on closed
closed.append(X)
#discard children of X if already on open or closed
children = prune_children(children, open_states, closed)
#put remaining children on left end of open
open_states.extend(children)
def main():
solved = breadth_first_search()
print "End state:"
solved.toString()
print "Complete! solved in %d steps!" % solved.steps
print "Steps used to complete are as follows:"
print solved.path
if __name__ == '__main__':
main()