KnightsTourAnalysis.ptx

<section xml:id="graphs_knights-tour-analysis">
        <title>Knight's Tour Analysis</title>
        <p>There is one last interesting topic regarding the knight's tour problem,
            then we will move on to the general version of the depth first search.
            The topic is performance. In particular, <c>knightTour</c> is very
            sensitive to the method you use to select the next vertex to visit. For
            example, on a five-by-five board you can produce a path in about 1.5
            seconds on a reasonably fast computer. But what happens if you try an
            eight-by-eight board? In this case, depending on the speed of your
            computer, you may have to wait up to a half hour to get the results! The
            reason for this is that the knight's tour problem as we have implemented
            it so far is an exponential algorithm of size <m>O(k^N)</m>, where N
            is the number of squares on the chess board, and k is a small constant.
            <xref ref="fig-8array"/> can help us visualize why this is so. The root of
            the tree represents the starting point of the search. From there the
            algorithm generates and checks each of the possible moves the knight can
            make. As we have noted before the number of moves possible depends on
            the position of the knight on the board. In the corners there are only
            two legal moves, on the squares adjacent to the corners there are three
            and in the middle of the board there are eight. <xref ref="fig-nummoves"/>
            shows the number of moves possible for each position on a board. At the
            next level of the tree there are once again between 2 and 8 possible
            next moves from the position we are currently exploring. The number of
            possible positions to examine corresponds to the number of nodes in the
            search tree.</p>
        
        <figure align="center" xml:id="fig-8array">
            <caption>A Search Tree for the Knight's Tour.</caption>
                <image source="Graphs/8arrayTree.png" width="80%">
                <description><p>Image of a search tree representing the possible sequences of moves for a Knight's Tour on a chessboard. The tree structure fans out from a single root node at the top, branching out to successive levels that represent each move of the knight. Each node represents a position on the chessboard, with the links between them representing legal moves of the knight. The breadth of the tree at each level indicates the growing complexity of the tour as more moves are made. The tree is a visual representation of the decision process in computing the tour, with the expansive spread of nodes illustrating the many possible paths the knight can take.</p></description>
                </image>
            </figure>
        
        <figure align="center" xml:id="fig-nummoves">
            <caption>Number of Possible Moves for Each Square.</caption>
                <image source="Graphs/moveCount.png" width="80%">
                <description><p>Diagram showing an 8x8 chessboard grid, each square labeled with a number indicating the total possible moves a knight can make from that position. The numbers range from '2' on the corners, up to '8' in the central squares, with varying numbers like '3', '4', and '6' on other squares based on their position. The layout demonstrates the accessibility of each square for a knight, with central squares being the most accessible. This visualization aids in understanding the knight's range of movement on a standard chessboard.</p></description>
                </image>
            </figure>
        <p>We have already seen that the number of nodes in a binary tree of height
            N is <m>2^{N+1}-1</m>. For a tree with nodes that may have up to
            eight children instead of two the number of nodes is much larger.
            Because the branching factor of each node is variable, we could estimate
            the number of nodes using an average branching factor. The important
            thing to note is that this algorithm is exponential:
            <m>k^{N+1}-1</m>, where <m>k</m> is the average branching factor
            for the board. Let's look at how rapidly this grows! For a board that is
            5x5 the tree will be 25 levels deep, or N = 24 counting the first level
            as level 0. The average branching factor is <m>k = 3.8</m> So the
            number of nodes in the search tree is <m>3.8^{25}-1</m> or
            <m>3.12 \times 10^{14}</m>. For a 6x6 board, <m>k = 4.4</m>, there
            are <m>1.5
                \times 10^{23}</m> nodes, and for a regular 8x8 chess board,
            <m>k = 5.25</m>, there are <m>1.3 \times 10^{46}</m>. Of course,
            since there are multiple solutions to the problem we won't have to
            explore every single node, but the fractional part of the nodes we do
            have to explore is just a constant multiplier which does not change the
            exponential nature of the problem. We will leave it as an exercise for
            you to see if you can express <m>k</m> as a function of the board
            size.</p>
        <p>Luckily there is a way to speed up the eight-by-eight case so that it
            runs in under one second. In the listing below we show the code that
            speeds up the <c>knightTour</c>. This function (see <xref ref="graphs_lst-avail"/>), called <c>orderbyAvail</c>
            will be used in place of the call to <c>u.getConnections</c> in the code previously
            shown above. The critical line in the
            <c>orderByAvail</c> function is line 10. This line ensures that we
            select the vertex to go next that has the fewest available moves. You
            might think this is really counter productive; why not select the node
            that has the most available moves? You can try that approach easily by
            running the program yourself and inserting the line
            <c>resList.reverse()</c> right after the sort.</p>
        <p>The problem with using the vertex with the most available moves as your
            next vertex on the path is that it tends to have the knight visit the
            middle squares early on in the tour. When this happens it is easy for
            the knight to get stranded on one side of the board where it cannot
            reach unvisited squares on the other side of the board. On the other
            hand, visiting the squares with the fewest available moves first pushes
            the knight to visit the squares around the edges of the board first.
            This ensures that the knight will visit the hard-to-reach corners early
            and can use the middle squares to hop across the board only when
            necessary. Utilizing this kind of knowledge to speed up an algorithm is
            called a heuristic. Humans use heuristics every day to help make
            decisions, heuristic searches are often used in the field of artificial
            intelligence. This particular heuristic is called Warnsdorff's
            algorithm, named after H. C. Warnsdorff who published his idea in 1823.</p>
        <p>The visualization in <xref ref="graphs_knighttour-figvideo"/> depicts the full process of a Knight's Tour solution.
            It portrays the visitation of every spot on the chess board and an analysis
            on all neighboring locations, and finishes by showing the final solution wherein
            all locations on the chess board have been visited. The Warnsdorff heuristic is used
            in this visualization, so all neighbors with less moves are prioritized over neighbors
            with more moves. The individual components of the visualization are indicated by color
            and shape, which is described below.</p>
        <p><ul>
            <li>
                <p>The currently focused point on the chess board is a black circle.</p>
            </li>
            <li>
                <p>Neighbors of that point that are being examined are higlighted in blue hexagon.</p>
            </li>
            <li>
                <p>Distant neighbors are orange or brown triangles.</p>
                <p><ul>
                    <li>
                        <p>Triangles are orange if the spot on the chess board <em>has not been</em> visited yet.</p>
                    </li>
                    <li>
                        <p>Triangles are brown if the spot on the chess board <em>has already been</em> visited.</p>
                    </li>
                </ul></p>
            </li>
        </ul></p>
 
        <figure xml:id="graphs_knighttour-figvideo">
            <caption>Knights tour visualization</caption>
            <video label="graphs_knighttour-video" source="Graphs/knights_tour_vis.webm" width="80%" preview="Graphs/kt_vis_thumb.png" />
        </figure>

        <listing xml:id="graphs_lst-avail" names="lst_avail">
            <caption>Implementation of <c>orderByAvail</c></caption>
            <program language="python" label="graphs_lst-avail-prog"><input>
def orderByAvail(n):
    resList = []
    for v in n.getConnections():
        if v.getColor() == 'white':
            c = 0
            for w in v.getConnections():
                if w.getColor() == 'white':
                    c = c + 1
            resList.append((c,v))
    resList.sort(key=lambda x: x[0])
    return [y[1] for y in resList]
            </input></program>
        </listing>
        <reading-questions xml:id="rq-knights-tour-impl">
           <title>Reading Question</title>
           
            
       

    <exercise label="knightO">
        <statement>

            <p>What is the big O of the Knight's Tour function?</p>

        </statement>
<choices>

            <choice correct="yes">
                <statement>
                    <p><m>O(k^n)</m></p>
                </statement>
                <feedback>
                    <p>You are correct! K is a small constant, and N is the total number of vertices (or spaces on a chessboard).</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p><m>O(n)</m></p>
                </statement>
                <feedback>
                    <p>No, the Knight's Tour is not linear.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p><m>O(n^2)</m></p>
                </statement>
                <feedback>
                    <p>No, the Knight's Tour does not have a nested loop that iterates through all values twice.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p><m>O(n!)</m></p>
                </statement>
                <feedback>
                    <p>No, the input is not processed in a fashion indicative of a factorial.</p>
                </feedback>
            </choice>
</choices>

    </exercise>
</reading-questions>
<conclusion><p>
    <!-- extra space before the progress bar -->
</p></conclusion>
    </section>