Starting with the tic-tac-toe program of Figure 12.4, draw a directed acyclic graph in which every clause is a node and an arc from A to B indicates that it is important, either for correctness or efficiency, that A come before B in the program. (Do not draw any other arcs.) Any topological sort of your graph should constitute an equally efficient version of the program. (Is the existing program one of them?)

Figure 12.4:

Transcribed Image Text:

printsquare (N) :- o(N), write(' o '). printsquare (N) :- x(N), write(' x '). printsquare (N) :- empty (N), write(' printboard :- printsquare(1), printsquare (2), printsquare (3), nl, '). printsquare (4), printsquare(5), printsquare(6), nl, printsquare (7), printsquare(8), printsquare (9), nl. clear :- retractall (x(_)), retractall(o(_)). % main goal: play clear, repeat, getmove, respond. respond :- ordered_line (A, B, C), o(A), o(B), o(C), % shouldn't ever happen! printboard, write('You won.'), nl. :- makemove, printboard, done. respond