ImplementingKnightsTour.ptx

<section xml:id="graphs_implementing-knights-tour">
        <title>Implementing Knight's Tour</title>
        <p><idx>depth first search</idx><idx>DFS</idx>The search algorithm we will use to solve the knight's tour problem is
            called <term>depth first search</term> (<term>DFS</term>).  Whereas the
            breadth first search algorithm discussed in the previous section builds
            a search tree one level at a time, a depth first search creates a search
            tree by exploring one branch of the tree as deeply as possible. In this
            section we will look at two algorithms that implement a depth first
            search. The first algorithm we will look at directly solves the knight's
            tour problem by explicitly forbidding a node to be visited more than
            once. The second implementation is more general, but allows nodes to be
            visited more than once as the tree is constructed. The second version is
            used in subsequent sections to develop additional graph algorithms.</p>
        <p>The depth first exploration of the graph is exactly what we need in
            order to find a path that has exactly 63 edges. We will see that when
            the depth first search algorithm finds a dead end (a place in the graph
            where there are no more moves possible) it backs up the tree to the next
            deepest vertex that allows it to make a legal move.</p>
        <p>The <c>knightTour</c> function takes four parameters: <c>n</c>, the current
            depth in the search tree; <c>path</c>, a list of vertices visited up to
            this point; <c>u</c>, the vertex in the graph we wish to explore; and
            <c>limit</c> the number of nodes in the path. The <c>knightTour</c> function
            is recursive. When the <c>knightTour</c> function is called, it first
            checks the base case condition. If we have a path that contains 64
            vertices, we return from <c>knightTour</c> with a status of <c>True</c>,
            indicating that we have found a successful tour. If the path is not long
            enough we continue to explore one level deeper by choosing a new vertex
            to explore and calling <c>knightTour</c> recursively for that vertex.</p>
        <p>DFS also uses colors to keep track of which vertices in the graph have
            been visited. Unvisited vertices are colored white, and visited vertices
            are colored gray. If all neighbors of a particular vertex have been
            explored and we have not yet reached our goal length of 64 vertices, we
            have reached a dead end. When we reach a dead end we must backtrack.
            Backtracking happens when we return from <c>knightTour</c> with a status of
            <c>False</c>. In the breadth first search we used a queue to keep track of
            which vertex to visit next. Since depth first search is recursive, we
            are implicitly using a stack to help us with our backtracking. When we
            return from a call to <c>knightTour</c> with a status of <c>False</c>, in line 11,
            we remain inside the <c>while</c> loop and look at the next
            vertex in <c>nbrList</c>.</p>
        <p><term>Listing 3</term></p>
        <pre>from pythonds.graphs import Graph, Vertex
def knightTour(n,path,u,limit):
        u.setColor('gray')
        path.append(u)
        if n &lt; limit:
            nbrList = list(u.getConnections())
            i = 0
            done = False
            while i &lt; len(nbrList) and not done:
                if nbrList[i].getColor() == 'white':
                    done = knightTour(n+1, path, nbrList[i], limit)
                i = i + 1
            if not done:  # prepare to backtrack
                path.pop()
                u.setColor('white')
        else:
            done = True
        return done</pre>
        <p>Let's look at a simple example of <c>knightTour</c> in action. You
            can refer to the figures below to follow the steps of the search. For
            this example we will assume that the call to the <c>getConnections</c>
            method on line 6 orders the nodes in
            alphabetical order. We begin by calling <c>knightTour(0,path,A,6)</c>.</p>
        <p><c>knightTour</c> starts with node A <xref ref="fig-kta"/>. The nodes adjacent to A are B and D.
            Since B is before D alphabetically, DFS selects B to expand next as
            shown in <xref ref="fig-ktb"/>. Exploring B happens when <c>knightTour</c> is
            called recursively. B is adjacent to C and D, so <c>knightTour</c> elects
            to explore C next. However, as you can see in <xref ref="fig-ktc"/> node C is
            a dead end with no adjacent white nodes. At this point we change the
            color of node C back to white. The call to <c>knightTour</c> returns a
            value of <c>False</c>. The return from the recursive call effectively
            backtracks the search to vertex B (see <xref ref="fig-ktd"/>). The next
            vertex on the list to explore is vertex D, so <c>knightTour</c> makes a
            recursive call moving to node D (see <xref ref="fig-kte"/>). From vertex D on,
            <c>knightTour</c> can continue to make recursive calls until we
            get to node C again (see <xref ref="fig-ktf"/>, <xref ref="fig-ktg"/>, and  <xref ref="fig-kth"/>).  However, this time when we get to node C the
            test <c>n &lt; limit</c> fails so we know that we have exhausted all the
            nodes in the graph. At this point we can return <c>True</c> to indicate
            that we have made a successful tour of the graph. When we return the
            list, <c>path</c> has the values <c>[A,B,D,E,F,C]</c>, which is the the order
            we need to traverse the graph to visit each node exactly once.</p>
        
        <figure align="center" xml:id="fig-kta">
            <caption>Start with node A.</caption>
                <image source="Graphs/ktdfsa.png" width="80%">
                <description><p>Graph with node 'fool' as the central node connected to four adjacent nodes labeled 'pool', 'foil', 'foul', and 'cool', each marked with the number '1'. Below the graph is a visual representation of a queue with the nodes 'pool', 'foil', 'foul', and 'cool' lined up in order.</p></description>
                </image>
            </figure>
        
        <figure align="center" xml:id="fig-ktb">
            <caption>Explore B.</caption>
                <image source="Graphs/ktdfsb.png" width="80%">
                <description><p>Graph with nodes A, B, C, D, E, and F, with node B highlighted, indicating exploration from node B to nodes A and E.</p></description>
                </image>
            </figure>

        <figure align="center" xml:id="fig-ktc">
            <caption>Node C is a dead end.</caption>
                <image source="Graphs/ktdfsc.png" width="80%">
                <description><p>Graph highlighting node C, showing no further connections, indicating that C is a dead end in the search process.</p></description>
                </image>
            </figure>
        
        <figure align="center" xml:id="fig-ktd">
            <caption>Backtrack to B.</caption>
                <image source="Graphs/ktdfsd.png" width="80%">
                <description><p>Graph with a backtrack path from node C to node B, illustrating the step of returning to node B to continue the search.</p></description>
                </image>
            </figure>
        
        <figure align="center" xml:id="fig-kte">
            <caption>Explore D.</caption>
                <image source="Graphs/ktdfse.png" width="80%">
                <description><p>Graph with node D highlighted, indicating the exploration is continuing from node D to nodes A and E.</p></description>
                </image>
            </figure>
        
        <figure align="center" xml:id="fig-ktf">
            <caption>Explore E.</caption>
                <image source="Graphs/ktdfsf.png" width="80%">
                <description><p>Graph focusing on node E, with exploration proceeding from node E to nodes B and D.</p></description>
                </image>
            </figure>
        
        <figure align="center" xml:id="fig-ktg">
            <caption>Explore F.</caption>
                <image source="Graphs/ktdfsg.png" width="80%">
                <description><p>Graph with node F highlighted, representing the search exploring potential paths from node F to node C.</p></description>
                </image>
            </figure>
        
        <figure align="center" xml:id="fig-kth">
            <caption>Finish.</caption>
                <image source="Graphs/ktdfsh.png" width="80%">
                <description><p>Final graph with all nodes no longer highlighted, representing the completion of the depth-first search process.</p></description>
                </image>
            </figure>
        <p><xref ref="fig-completeTour"/> shows you what a complete tour around an
            eight-by-eight board looks like. There are many possible tours; some are
            symmetric. With some modification you can make circular tours that start
            and end at the same square.</p>
        
        <figure align="center" xml:id="fig-completeTour">
            <caption>A Complete Tour of the Board.</caption>
                <image source="Graphs/completeTour.png" width="80%">
                <description><p>Image depicting a graph overlaid on an 8x8 chessboard grid representing a complete Knight's Tour. The nodes, numbered from 0 to 63, correspond to the squares of the chessboard. Lines crisscross the grid, mapping the knight's moves in a sequential path that visits each square exactly once. The complex web of lines indicates the knight's route, creating a Hamiltonian circuit where the start and end points are connected. Captioned 'Figure 11: A Complete Tour of the Board'.</p></description>
                </image>
            </figure>
      <reading-questions xml:id="rq-knights-tour-imp">
        <title>Reading Questions</title>
        
        

    <exercise label="KnightsTour">
        <statement>

            <p>True/False: The Knight's Tour Graph contains as many vertices as there are tiles on a chessboard.</p>

        </statement>
<choices>

            <choice correct="yes">
                <statement>
                    <p>True</p>
                </statement>
                <feedback>
                    <p>You are correct!</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>False</p>
                </statement>
                <feedback>
                    <p>No; remember the implementation of Matrix graphs.</p>
                </feedback>
            </choice>
</choices>

    </exercise>

<exercise label="clickKnight">
    <statement><p>What line denotes the base case of the Knight's Tour function?</p></statement>
<feedback><p>Remember, the base case is usually the first comparison in the function!</p></feedback>
<areas>
<cline><area>def knightTour(n,path,u,limit):</area>:</cline>
<cline><area>u.setColor('gray')</area>:</cline>
<cline><area>path.append(u)</area>:</cline>
<cline><area correct="yes">if n &lt; limit:</area>:</cline>
<cline>    <area>nbrList = list(u.getConnections())</area>:</cline>
<cline>    <area>i = 0</area>:</cline>
<cline>    <area>done = False</area>:</cline>
<cline>    <area>while i &lt; len(nbrList) and not done:</area>:</cline>
<cline>        <area>if nbrList[i].getColor() == 'white':</area>:</cline>
<cline>            <area>done = knightTour(n+1, path, nbrList[i], limit)</area>:</cline>
<cline>        <area>i = i + 1</area>:</cline>
<cline>    <area>if not done:  # prepare to backtrack</area>:</cline>
<cline>        <area>path.pop()</area>:</cline>
<cline>        <area>u.setColor('white')</area>:</cline>
<cline><area>else:</area>:</cline>
<cline>    <area>done = True</area>:</cline>
<cline><area>return done</area>:</cline>
</areas></exercise>        </reading-questions>  
    <conclusion><p>
        <!-- extra space before the progress bar -->
    </p></conclusion> 
    </section>