12. Heuristic Search¶
This text has focused on the interaction of algorithms with data structures. Many of the algorithms presented in this text deal with search and how to organize data so searching can be done efficiently. Many problems involve searching for an answer among many possible solutions, not all of which are correct. Sometimes, there are so many possibilities, no algorithm can be written that will efficiently find a correct solution amongst all the possible solutions. In these cases, we may be able to use a rule of thumb, most often called a heuristic in computer science, to eliminate some of these possibilities from our search space. If the heuristic does not eliminate possible solutions, it may at least help us order the possible solutions so we look at better possible solutions first, whatever better might mean.
In chapter 7 depth first search of a graph was presented. Sometimes search spaces for graphs or other problems grow to such an enormous size, it is impossible to blindly search for a goal node. This is where a heuristic can come in handy. This chapter uses searching a maze, which is really just a type of graph, as an example to illustrate several search algorithms that are related to depth first or breadth first search. Several applications of these search algorithms are also presented or discussed.
Heuristic search is often covered in texts on Artificial Intelligence :cite:`AIIlluminated`. As problems in AI are better understood, algorithms arise that become more commonplace over time. The heuristic algorithms presented in this chapter are covered in more detail in an AI text, but as data sizes grow, heuristic search will become more and more necessary in all sorts of applications. AI techniques may be useful in many search problems and so are covered in this chapter to provide an introduction to search algorithms designed to deal with large or infinite search spaces.
12.1. Searching Mazes¶
You can write your own maze search code that interacts with a front-end that is provided here. You can download the front-end code by clicking here. The front-end code requires the tile20.gif file. It also requires at least one maze file. The file maze3.txt was used in the text to demonstrate the various search algorithms. Here are three maze files for downloading.
Of course, you can write your own maze file as well. The format requires the number of rows on the first line, followed by the number of columns on the second line. Then the rest of the maze on the following lines must have an opening at the top for the entrance and an opening at the bottom for the exit.
The program is written as a front-end. Your challenge is to provide a back-end that supports the given search types. The architecture for your back-end is described at the top of the front-end code. The front-end is written to support five types of search, depth-first, bread-first, hill climbing, best-first, and a-star. If you wish to see a demonstration of these search types without writing your own back-end code first, you can download the search.fas file which is a compiled CLISP back-end. You must have CLISP installed on your system to run this back-end code.
Here is the front-end code for your reference.
1import turtle
2import subprocess
3import tkinter
4import sys
5import time
6
7# The following program will animate a search algorithm written in a language of
8# your choice. The only requirement is that the programming language is able to
9# write to standard output and read from standard input following the architecture
10# outlined below. The program that you write is the back-end communicating to this
11# front-end code. A compiled lisp program serves as a back-end for demonstration
12# purposes and can be downloaded from the text website. This front-end
13# program and the back-end program communicate through pipes (both input and output)
14# according to this architecture. When a command is sent to the back-end it is indicated
15# with a right arrow indicating something is written to the back-end program's
16# standard input. When the back-end program sends something to this front-end
17# it is indicated with a left arrow. That means it is written to the standard
18# output of the back-end program.
19
20# front-end back-end
21# dfs ---------> # A search type is selected, the back-end program must read
22# maze.txt ----> # The filename is passed to the back-end program
23# <----------- 0 10 # these are the row column pairs of visited locations
24# ... # repeating until the search is complete
25# <----------- done # Then done is printed by the back-end
26# <----------- 31 22 # Finally the path is printed in reverse order
27# ... # All locations are printed
28# <----------- eof # EOF is printed back to be sent back to this application.
29
30# If you wish to implement your own back-end you must alter the line of code below
31# that looks like this:
32#
33# proc = subprocess.Popen(["clisp","search.fas"],stdout=subprocess.PIPE, \
34# stdin=subprocess.PIPE,universal_newlines=True)
35#
36# You must replace clisp with the program that starts your program running. If you
37# have written your back-end with python 3.x then replace clisp with python3.
38# The search.fas should be replaced by any command-line arguments to your program. If
39# you have written your program in python, then the argument should be the name of your
40# program which must be in the same directory as this front-end code and the mazes you
41# with to search.
42#
43# Output that you want to print for debugging purposes can be written to standard error
44# instead of standard output. In this way standard output can be used to communicate
45# with the front-end while you still see output printed to the terminal window for
46# debugging purposes. In python, standard error can be written to as follows:
47#
48# import sys
49# sys.stderr.write('Your text goes here.\n')
50#
51# This architecture must be adhered to strictly for this program to work. The search
52# types supported by the front-end code are: dfs, bfs, hill, best, astar. Here
53# is sample Lisp code that will handle this interaction from the front-end code.
54
55#(defun processCommand ()
56 #(let ((searchTtype "")
57 #(filename "")
58 #(path nil))
59
60
61 #(setf searchType (read-line))
62 #(format *error-output* "Lisp says - Search Type is ~S~%" searchType)
63 #(setf filename (read-line))
64
65
66 #(cond ((equal searchType "dfs") (setf path (dfsMaze filename)))
67 #((equal searchType "bfs") (setf path (bfsMaze filename))))
68
69 #(format t "done~%")
70 #(printPath path)
71 #(format t "eof~%")))
72
73#(processCommand)
74
75
76class MazeAnimateApplication(tkinter.Frame):
77 def __init__(self, master=None):
78 super().__init__(master)
79 self.pack()
80 self.buildWindow()
81 self.running = False
82
83 def buildWindow(self):
84
85 self.master.title("Maze Search Animation")
86
87 bar = tkinter.Menu(self.master)
88 fileMenu = tkinter.Menu(bar,tearoff=0)
89
90 def run():
91 if self.running:
92 return
93
94 try:
95 self.running = True
96 screen = theTurtle.getscreen()
97 screen.clear()
98 screen.tracer(0)
99 screen.setworldcoordinates(0,800,1300,0)
100 self.screen = screen
101 screen.register_shape("tile20.gif")
102 file = open(self.filename.get(),"r")
103
104 firstLine = file.readline()
105 rows = int(firstLine)
106 secondLine = file.readline()
107 cols = int(secondLine)
108
109 if cols > 65 or rows > 40:
110 tkinter.messagebox.showwarning("Information", \
111 "Maximum allowed rows is 40 and the maximum allowed columns are 65")
112 self.running = False
113 return
114
115 screen.register_shape("tile20.gif")
116
117 screen.tracer(0)
118 for i in range(rows):
119 line = file.readline()
120 for j in range(cols):
121 if line[j] == "*":
122 tile = turtle.RawTurtle(canvas)
123 tile.penup()
124 tile.shape("tile20.gif")
125 tile.goto(j*20+10,i*20+10)
126
127 screen.update()
128
129 proc = subprocess.Popen(["clisp","search.fas"],stdout=subprocess.PIPE, \
130 stdin=subprocess.PIPE,universal_newlines=True)
131 fromLisp = proc.stdout
132 toLisp = proc.stdin
133 print(self.rbSelection())
134 toLisp.write(self.rbSelection()+"\n")
135 print(self.filename.get())
136 toLisp.flush()
137 toLisp.write(self.filename.get()+"\n")
138 toLisp.flush()
139
140 t = turtle.RawTurtle(canvas)
141 t.penup()
142 t.shape("circle")
143 t.color("blue")
144
145 line = fromLisp.readline().strip()
146 screen.tracer(1)
147
148 while line != "done" and self.running:
149 # process line of currently inspected node
150 lst = line.split()
151 row = int(lst[0])
152 col = int(lst[1])
153 length = int(lst[2])
154 t.goto(col*20+10,row*20+10+5)
155 #t.dot(10)
156 t.write(str(length),align="center",font=("Arial", 10, "bold"))
157
158 # read the next line
159 line = fromLisp.readline().strip()
160
161 t.color("red")
162 line = fromLisp.readline().strip()
163
164 while line != "eof" and self.running:
165
166 # process line of final path node
167 lst = line.split()
168 row = int(lst[0])
169 col = int(lst[1])
170 length = int(lst[2])
171 t.goto(col*20+10,row*20+10+5)
172 t.write(str(length),align="center",font=("Arial", 10, "bold"))
173 #t.dot(10)
174
175 # read the next line
176 line = fromLisp.readline().strip()
177
178 proc.kill()
179 t.ht()
180 self.running = False
181
182
183 except Exception as ex:
184 tkinter.messagebox.showwarning("Alert",str(ex))
185 tb = sys.exc_info()[2]
186 self.running = False
187 raise ex
188
189
190
191 def stop():
192 self.running = False
193
194 fileMenu.add_command(label="Exit",command=self.master.quit)
195
196 bar.add_cascade(label="File",menu=fileMenu)
197
198 self.master.config(menu=bar)
199
200 canvas = tkinter.Canvas(self,width=1300,height=800)
201 canvas.pack(side=tkinter.LEFT)
202
203 theTurtle = turtle.RawTurtle(canvas)
204 theTurtle.ht()
205
206 sideBar = tkinter.Frame(self,padx=5,pady=5, relief=tkinter.RAISED, \
207 borderwidth="5pt")
208 sideBar.pack(side=tkinter.RIGHT, fill=tkinter.BOTH)
209
210 self.filename = tkinter.StringVar()
211 self.filename.set("maze.txt")
212
213 selectLabel = tkinter.Label(sideBar,text="Select File")
214 selectLabel.pack()
215
216 fileEntryBox = tkinter.Entry(sideBar,textvariable=self.filename)
217 fileEntryBox.pack()
218
219 selectLabel = tkinter.Label(sideBar,text="Select Search")
220 selectLabel.pack()
221
222 RadioButtonBox = tkinter.Frame(sideBar,relief=tkinter.SUNKEN, \
223 borderwidth="5pt",padx=5,pady=5)
224 RadioButtonBox.pack()
225
226 self.searchType = tkinter.IntVar()
227
228 rb1 = tkinter.Radiobutton(RadioButtonBox, text = "Depth First", \
229 variable=self.searchType, value=0, command=self.rbSelection)
230 rb1.grid(sticky="w",column=0,row=0)
231
232 rb2 = tkinter.Radiobutton(RadioButtonBox, text = "Breadth First", \
233 variable=self.searchType, value=1, command=self.rbSelection)
234 rb2.grid(sticky="w",column=0,row=1)
235
236 rb3 = tkinter.Radiobutton(RadioButtonBox, text = "Hill Climbing", \
237 variable=self.searchType, value=2, command=self.rbSelection)
238 rb3.grid(sticky="w",column=0,row=2)
239
240 rb4 = tkinter.Radiobutton(RadioButtonBox, text = "Best First", \
241 variable=self.searchType, value=3, command=self.rbSelection)
242 rb4.grid(sticky="w",column=0,row=3)
243
244 rb5 = tkinter.Radiobutton(RadioButtonBox, text = "A Star", \
245 variable=self.searchType, value=4, command=self.rbSelection)
246 rb5.grid(sticky="w",column=0,row=4)
247
248 sb = tkinter.Button(sideBar,text="Start",command=run)
249 sb.pack()
250
251 kb = tkinter.Button(sideBar,text="Stop",command=stop)
252 kb.pack()
253
254 def rbSelection(self):
255 if self.searchType.get() == 0:
256 self.master.title("DFS Search")
257 return "dfs"
258 elif self.searchType.get() == 1:
259 self.master.title("BFS Search")
260 return "bfs"
261 elif self.searchType.get() == 2:
262 self.master.title("Hill Climbing Search")
263 return "hill"
264 elif self.searchType.get() == 3:
265 self.master.title("Best First Search")
266 return "best"
267 elif self.searchType.get() == 4:
268 self.master.title("A* Search")
269 return "astar"
270
271def main():
272 root = tkinter.Tk()
273 animApp = MazeAnimateApplication(root)
274
275 animApp.mainloop()
276 print("Program Execution Completed.")
277
278if __name__ == "__main__":
279 main()
280
281
12.2. N-Queens Problem¶
The N-Queens problem from the text can be solved using a depth first search with forward checking. A front-end program is provided so you can visualize the search for a solution. You can download the front-end code here.
The program is written as a front-end. Your challenge is to write the back-end code for this program. The architecture for your back-end is described at the top of the front-end code.
If you wish to visualize how this program works without writing your own back-end, you can download the qsearch.fas file here. This file requires CLISP be installed to run. The qsearch.fas file must be placed in the same directory as the front-end queensanimate.py program to run.
Here is the front-end code for your reference.
1import turtle
2import subprocess
3import tkinter
4import sys
5import time
6
7# The following program will animate the n-queens algorithm. This front-end
8# program and a back-end program communicate through pipes (both input and output)
9# according to this architecture. When a command is sent to the back-end it is indicated
10# with a right arrow indicating something is written to the back-end program's
11# standard input. When the back-end program sends something to this front-end program
12# it is indicated with a left arrow. That means it is written to the standard
13# output of the back-end program.
14
15# Each state in the search consists of the currently placed queens (up to the current
16# row) and the remaining available locations above the row the last queen was placed in.
17# The architecture below repeats this state information over and over until the search
18# has found a solution.
19
20# front-end back-end
21# 8 ---------> # A size is specified to the back-end program
22# <----------- 0 10 # these are the row column pairs of possibly assigned queen locations
23# ... # repeating until the search is complete
24# <----------- and # The and is printed between the assigned and remaining locations
25# <----------- 1 2 # next comes the remaining locations
26# ... # repeating until done
27# <----------- done # Then done is printed after each state is completely enumerated
28# ... # These states repeat until the search has concluded.
29# <----------- eof # EOF is printed back to inidicate the end of the animation.
30
31# If you wish to implement your own backend you must alter the line of code below
32# that looks like this:
33#
34# proc = subprocess.Popen(["clisp","qsearch.fas"],stdout=subprocess.PIPE, \
35# stdin=subprocess.PIPE,universal_newlines=True)
36#
37# You must replace clisp with the program that starts your program running. If you
38# have written your back-end with python 3.x then replace clisp with python3.
39# The qsearch.fas should be replaced by any command-line arguments to your program. If
40# you have written your program in python, then the argument should be the name of your
41# program which must be in the same directory as this front-end code.
42#
43# Output that you want to print for debugging purposes can be written to standard error
44# instead of standard output. In this way standard output can be used to communicate
45# with the front-end while you still see output printed to the terminal window for
46# debugging purposes. In python, standard error can be written to as follows:
47#
48# import sys
49# sys.stderr.write('Your text goes here.\n')
50#
51# This architecture must be adhered to strictly for this program to work. Here
52# is sample Lisp code that will handle this interaction.
53
54#(defun queens-search (size)
55 #(print-state (dfs (initialize size) #'(lambda (state) (eq (list-length
56 # (first state)) size))))
57 #(format t "eof~%"))
58
59#(defun processCommand ()
60 #(let ((size 8))
61
62
63 #(setf size (parse-integer (read-line)))
64 #(format *error-output* "Lisp says - Size is ~D~%" size)
65
66 #(queens-search size)))
67
68
69#(processCommand)
70
71
72
73class QueensAnimateApplication(tkinter.Frame):
74 def __init__(self, master=None):
75 super().__init__(master)
76 self.pack()
77 self.buildWindow()
78 self.running = False
79
80 def buildWindow(self):
81
82 self.master.title("Queens Search Animation")
83
84 bar = tkinter.Menu(self.master)
85 fileMenu = tkinter.Menu(bar,tearoff=0)
86
87 def run():
88 if self.running:
89 return
90
91 try:
92 colors = ["red", "black"]
93 colorIndex = 0
94 self.running = True
95 screen = theTurtle.getscreen()
96 screen.clear()
97 screen.tracer(0)
98 self.screen = screen
99 size = int(self.sizevar.get())
100 cellWidth = 800/size
101 screen.setworldcoordinates(0,800,800,0)
102
103 for i in range(size):
104 for j in range(size):
105 theTurtle.penup()
106 theTurtle.goto(j*cellWidth,i*cellWidth)
107 theTurtle.pendown()
108 theTurtle.color("black")
109 theTurtle.fillcolor(colors[colorIndex])
110 colorIndex=(colorIndex+1)%2
111 theTurtle.begin_fill()
112 theTurtle.goto(j*cellWidth+cellWidth,i*cellWidth)
113 theTurtle.goto(j*cellWidth+cellWidth,i*cellWidth+cellWidth)
114 theTurtle.goto(j*cellWidth,i*cellWidth+cellWidth)
115 theTurtle.goto(j*cellWidth,i*cellWidth)
116 theTurtle.end_fill()
117 if (size % 2 == 0):
118 colorIndex = (colorIndex+1)%2
119
120 screen.update()
121
122 matrix = []
123 screen.tracer(0)
124 for i in range(size):
125 row = []
126 for j in range(size):
127 t = turtle.RawTurtle(canvas)
128 t.penup()
129 t.color("yellow")
130 t.goto(j*cellWidth+cellWidth/2,i*cellWidth+cellWidth/2)
131 t.width(cellWidth)
132 t.shape("circle")
133 t.ht()
134 row.append(t)
135 matrix.append(row)
136
137 screen.update()
138
139 proc = subprocess.Popen(["clisp","qsearch.fas"],stdout=subprocess.PIPE, \
140 stdin=subprocess.PIPE,universal_newlines=True)
141 fromLisp = proc.stdout
142 toLisp = proc.stdin
143 toLisp.write(str(size)+"\n")
144 toLisp.flush()
145
146 line = fromLisp.readline().strip()
147
148 while line != "eof" and self.running:
149 # process line of currently inspected node
150 for row in matrix:
151 for cell in row:
152 cell.ht()
153
154 while line != "and":
155
156 lst = line.split()
157 row = int(lst[0])
158 col = int(lst[1])
159 matrix[row][col].color("yellow")
160 matrix[row][col].st()
161
162 # read the next line
163 line = fromLisp.readline().strip()
164
165 line = fromLisp.readline().strip()
166
167 while line != "done":
168
169 lst = line.split()
170 row = int(lst[0])
171 col = int(lst[1])
172 matrix[row][col].color("blue")
173 matrix[row][col].st()
174
175 # read the next line
176 line = fromLisp.readline().strip()
177
178 screen.update()
179 #time.sleep(1)
180 # read the next line
181 line = fromLisp.readline().strip()
182
183
184 proc.kill()
185 self.running = False
186
187
188 except Exception as ex:
189 tkinter.messagebox.showwarning("Alert",str(ex))
190 tb = sys.exc_info()[2]
191 self.running = False
192 raise ex
193
194
195
196 def stop():
197 self.running = False
198
199 fileMenu.add_command(label="Exit",command=self.master.quit)
200
201 bar.add_cascade(label="File",menu=fileMenu)
202
203 self.master.config(menu=bar)
204
205 canvas = tkinter.Canvas(self,width=800,height=800)
206 canvas.pack(side=tkinter.LEFT)
207
208 theTurtle = turtle.RawTurtle(canvas)
209 theTurtle.ht()
210
211 sideBar = tkinter.Frame(self,padx=5,pady=5, relief=tkinter.RAISED, \
212 borderwidth="5pt")
213 sideBar.pack(side=tkinter.RIGHT, fill=tkinter.BOTH)
214
215 self.sizevar = tkinter.StringVar()
216 self.sizevar.set("8")
217
218 selectLabel = tkinter.Label(sideBar,text="Problem Size")
219 selectLabel.pack()
220
221 sizeEntryBox = tkinter.Entry(sideBar,textvariable=self.sizevar)
222 sizeEntryBox.pack()
223
224 sb = tkinter.Button(sideBar,text="Start",command=run)
225 sb.pack()
226
227 kb = tkinter.Button(sideBar,text="Stop",command=stop)
228 kb.pack()
229
230def main():
231 root = tkinter.Tk()
232 animApp = QueensAnimateApplication(root)
233
234 animApp.mainloop()
235 print("Program Execution Completed.")
236
237if __name__ == "__main__":
238 main()
239
240
12.3. Connect Four¶
The connect four game presented in the text, like the other two program presented here, is written as a front-end/back-end pair. The front-end code can be downloaded here. The front-end requires the redchecker.gif and the blackchecker files be in the same directory.
Your challenge is to write the back-end code for this program that beats the author’s back-end code. The architecture for your back-end is described at the top of the front-end code.
If you wish to run this program works without writing your own back-end, you can download the c4.fas file here. This file requires CLISP be installed to run. The c4.fas file must be placed in the same directory as the front-end c4.py program to run.
Here is the front-end code for your reference.
1import turtle
2import subprocess
3import tkinter
4import sys
5import time
6
7# The following program will play connect four. This front-end
8# program and a back-end program communicate through pipes (both input and output)
9# according to this architecture. When a command is sent it is indicated
10# with a right arrow indicating something is written to the other program's
11# standard input. When the other program sends something to this Python Program
12# it is indicated with a left arrow. That means it is written to the standard
13# output of the other program.
14
15# front-end back-end
16# 0 -----------> # New Game is initiated by the front-end code
17# <----------- 0 # Back-end code says OK.
18# 2 M ---------> # Human Move followed by Move Value M which is 0-6.
19# # Move Value M will be on separate line.
20# <----------- 0 # Back-end code says OK.
21# 1 -----------> # Computer Move is indicated to back-end code.
22# <--------- 0 M # Status OK and Move Value M which is 0-6.
23# 3 -----------> # Game Over?
24# <--------- Val # Val is 0=Not Over, 1=Computer Won, 2=Human Won, 3=Tie.
25
26# If you wish to implement your own back-end you must alter the line of code below
27# that looks like this:
28#
29# proc = subprocess.Popen(["clisp","c4.fas"],stdout=subprocess.PIPE, \
30# stdin=subprocess.PIPE,universal_newlines=True)
31#
32# You must replace clisp with the program that starts your program running. If you
33# have written your back-end with python 3.x then replace clisp with python3.
34# The c4.fas should be replaced by any command-line arguments to your program. If
35# you have written your program in python, then the argument should be the name of your
36# program which must be in the same directory as this front-end code.
37#
38# Output that you want to print for debugging purposes can be written to standard error
39# instead of standard output. In this way standard output can be used to communicate
40# with the front-end while you still see output printed to the terminal window for
41# debugging purposes. In python, standard error can be written to as follows:
42#
43# import sys
44# sys.stderr.write('Your text goes here.\n')
45#
46# This architecture must be adhered to strictly for this program to work. Here
47# is sample Lisp code that will handle this interaction. However, the other
48# program may be written in any programming language, including Python.
49
50#(defun play ()
51 #(let ((gameBoard (make-hash-table :size 10))
52 #(memo (make-hash-table :size 27 :test #'equalp))
53 #(lastMove nil))
54
55 #(do () (nil nil)
56 #;(printBoard gameBoard)
57 #(let ((msgId (read)))
58 #(cond ((equal msgId 2) ;; Human turn to call human turn function
59 #(setf lastMove (humanTurn gameBoard)))
60
61 #((equal msgId 0) ;; New Game message
62 #(progn
63 #(setf gameBoard (make-hash-table :size 10))
64 #(setf memo (make-hash-table :size 27 :test #'equalp))
65 #(format t "0~%")))
66 #;; Return a 0 to indicate the computer is ready
67
68 #((equal msgId 1) ;; Computer Turn message
69 #(setf lastMove (computerTurn gameBoard)))
70
71 #((equal msgId 3) ;; Get Game Status
72
73 #(cond ((equal (evalBoard gameBoard lastMove) 1) (format t "1~%"))
74 #;; The Computer Won
75
76 #((equal (evalBoard gameBoard lastMove) -1) (format t "2~%"))
77 #;; The Human Won
78
79 #((fullBoard gameBoard) (format t "3~%"))
80 #;; It's a draw
81
82 #(t (format t "0~%"))))
83 #;; The game is not over yet.
84
85 #(t (format t "-1~%")))))))
86
87Computer = 1
88Human = -1
89
90class Tile(turtle.RawTurtle):
91 def __init__(self,canvas,row,col,app):
92 super().__init__(canvas)
93 self.val = 0
94 self.row = row
95 self.col = col
96 self.tttApplication = app
97 self.penup()
98 self.ht()
99 self.goto(col*100+50,row*100+50)
100
101 def setShape(self,horc,screen):
102 self.val = horc
103
104 if horc == Computer:
105 self.shape("blackchecker.gif")
106 else:
107 self.shape("redchecker.gif")
108
109 self.drop(screen)
110
111 def getOwner(self):
112 return self.val
113
114 def clicked(self):
115 print(self.row,self.col)
116
117 def drop(self,screen):
118 self.goto(self.col*100+50,0)
119 screen.tracer(1)
120 self.speed(5)
121 self.st()
122 self.goto(self.col*100+50,self.row*100+55)
123 self.goto(self.col*100+50,self.row*100+45)
124 self.goto(self.col*100+50,self.row*100+50)
125 screen.tracer(0)
126
127class Connect4Application(tkinter.Frame):
128 def __init__(self, master=None):
129 super().__init__(master)
130 self.pack()
131 self.buildWindow()
132 self.running = False
133
134 def buildWindow(self):
135
136 self.master.title("Connect Four")
137
138 bar = tkinter.Menu(self.master)
139 fileMenu = tkinter.Menu(bar,tearoff=0)
140
141 fileMenu.add_command(label="Exit",command=self.master.quit)
142
143 bar.add_cascade(label="File",menu=fileMenu)
144
145 self.master.config(menu=bar)
146
147 canvas = tkinter.Canvas(self,width=700,height=600)
148 canvas.pack(side=tkinter.LEFT)
149
150 theTurtle = turtle.RawTurtle(canvas)
151 theTurtle.ht()
152 screen = theTurtle.getscreen()
153 screen.setworldcoordinates(0,600,700,0)
154 screen.register_shape("blackchecker.gif")
155 screen.register_shape("redchecker.gif")
156 screen.tracer(0)
157 screen.bgcolor("yellow")
158
159 theTurtle.width(5)
160 for k in range(6):
161 theTurtle.penup()
162 theTurtle.goto(k*100+100,0)
163 theTurtle.pendown()
164 theTurtle.goto(k*100+100,600)
165
166 theTurtle.ht()
167
168 screen.update()
169
170 def checkStatus():
171 toOther.write("3\n")
172 toOther.flush()
173
174 status = int(fromOther.readline().strip())
175
176 if status == 1:
177 tkinter.messagebox.showinfo("Game Over", "I Won!!!!!")
178 elif status == 2:
179 tkinter.messagebox.showinfo("Game Over", "You Won!!!!!")
180 elif status == 3:
181 tkinter.messagebox.showinfo("Game Over", "It's a tie.")
182
183 #print("Status is ", status)
184 return status
185
186 def ComputerTurn():
187 toOther.write("1\n")
188 toOther.flush()
189 status = int(fromOther.readline().strip())
190 #print("Computer Turn Other Status = ", status)
191 if status == 0:
192 move = int(fromOther.readline())
193 #print("Move is", move)
194 row = move // 7
195 col = move % 7
196
197 matrix[row][col].setShape(Computer,screen)
198 screen.update()
199
200 def HumanTurn(x,y):
201 if self.running:
202 return
203
204 #status = checkStatus()
205
206 #if status != 0:
207 #return
208
209 self.running = True
210 col = int(x) // 100
211
212 row = 5
213 while row >= 0 and matrix[row][col].isvisible():
214 row = row - 1
215
216 if row < 0:
217 #Then we clicked in a column that was already full.
218 self.running = True
219 return
220
221 val = row * 7 + col
222
223 # Do the Human Turn
224 toOther.write("2\n")
225 toOther.flush()
226 toOther.write(str(val) + "\n")
227 toOther.flush()
228
229 status = fromOther.readline().strip()
230 #print("Status is ",status)
231
232 matrix[row][col].setShape(Human,screen)
233 screen.update()
234
235 # Check the status of the game
236 status = checkStatus()
237
238 if status == 0:
239 # Do a Computer Turn
240 ComputerTurn()
241 checkStatus()
242
243 self.running = False
244
245
246 matrix = []
247
248 for i in range(6):
249 row = []
250 for j in range(7):
251 t = Tile(canvas,i,j,self)
252 row.append(t)
253 matrix.append(row)
254
255 screen.update()
256 screen.onclick(HumanTurn)
257
258 sideBar = tkinter.Frame(self,padx=5,pady=5, relief=tkinter.RAISED,borderwidth="5pt")
259 sideBar.pack(side=tkinter.RIGHT, fill=tkinter.BOTH)
260
261 def NewGame():
262 toOther.write("0\n")
263 toOther.flush()
264 status = int(fromOther.readline().strip())
265
266 for row in matrix:
267 for token in row:
268 token.ht()
269
270 screen.update()
271
272 kb = tkinter.Button(sideBar,text="Pass",command=ComputerTurn)
273 kb.pack()
274
275 ng = tkinter.Button(sideBar,text="New Game",command=NewGame)
276 ng.pack()
277
278
279 proc = subprocess.Popen(["clisp","c4.fas"],stdout=subprocess.PIPE, \
280 stdin=subprocess.PIPE,universal_newlines=True)
281 fromOther = proc.stdout
282 toOther = proc.stdin
283
284 # To write to the other program you should use commands like this
285 # toOther.write(val+"\n")
286 # Don't forget to flush the buffer
287 # toOther.flush()
288
289 # To read from the other program you write
290 # line = fromOther.readline().strip()
291
292
293
294def main():
295 root = tkinter.Tk()
296 animApp = Connect4Application(root)
297
298 animApp.mainloop()
299 print("Program Execution Completed.")
300
301if __name__ == "__main__":
302 main()
303
304
12.4. Figures from Text¶
Fig. 1: Depth First Search of a Maze¶
Fig. 2: Breadth First Search of a Maze¶
Fig. 3: Hill Climbing Search of a Maze¶
Fig. 4: A Closed 12 x 12 Knight’s Tour¶
Fig. 5: A 25-Queens Solution¶
Fig. 6: Best First Search of a Maze¶
Fig. 7: A-Star Search of a Maze¶
Fig. 8: The Connect Four Game¶