Allison Schinagle CS265 Assignment 2: Knight's Tour https://en.wikipedia.org/wiki/Knight%27s_tour knight.py is the version I submitted by the due date. knightstour4.py is the version I keep changing little things in past the due date. knightstour.py, knightstour2.py, knightstour3.py, and knightstour5.py all don't work, except for knightstour5.py, where I try to implement some of the ideas I wanted to implement, which I talk about below. avg_attepmts.py runs knightstour4.py a bunch of times and calculates the average number of attempts it takes to find a knight's tour, and the standard deviation. For dimensions 9 or less, I found valid knights tours on the following sized boards: 3x4 4x5 5x5 6x6 7x7 8x8* 9x9 3x7 4x6 5x6 6x7 7x8 8x9 3x8 4x7 5x7 6x8 7x9 3x9 4x8 5x8 6x9 4x9 5x9 * a normal chess board First, input is validated; I wish I had written something like "rows = checkarg(sys.argv[1])" etc. because within my valid_input() function, I attempt to cast sys.argv[1] etc. to int anyway, so if that's successful I should just be able to return the value. Then command line arguments are assigned to more readable names. Then an open knight's tour is attempted. First step is to create a board using create_board(rows, cols). I chose to represent the board as a dictionary mapping tuples representing positions on a board to values (initialized to None) representing potential positions for the knight. Tuples are immutable, positions on a board are immutable, so that's perfect. I chose this representation to make it easier to check if None was still in the board at the end of an attempt at a knight's tour; if so, the tour was not completed. If I had chosen to represent the board as a two-dimensional array, which I tried to do the first three times I tried to write this, I would have had to flatten the array and then check for None, or something. When I tried that, I still couldn't get the tour to work. The knight's position is initialized to the tuple (0, 0). I used a list at first, since I figured, I'll want to change the knight's position, but I use a tuple and assign knight_pos a completely new tuple when it moves instead, so that I don't have to cast knight_pos to a tuple every time I want to access board[knight_pos]. Then we start a loop to move the knight a bunch of times. The loop will run either exactly as many times as there are moves to complete a knight's tour, or until there are no more possible moves. I would like to create a more opaque board object so that I wouldn't have to pass around rows and cols along with the board. Instead of passing knight to a move function and returning either its new position or "fail!" (which is how I tried to do it the first three times I tried writing this) I generate a list of possible moves, so I can use that within the knight-moving-loop to check if there are no more possible moves, and if there are, pick one and move the knight using that move. Generating possible moves. The position being tested must have both the x and y coordinates greater than or equal to zero and less than rows or columns, respectively. Also, the position being tested must not have been visited previously by the knight. The board is printed when a complete knight's tour is found or when all attempts have been exhausted. Here's where I think the dictionary representation of the board makes my life easier: in checking whether the knight has visited every position on the board. I don't even have to look at keys or positions; just the values that represent whether the position has been visited or not. avg_attempts.py runs knightstour4.py a whole bunch of times and calculates the average number of attempts it takes to find a successful knights tour, and the standard deviation. Here are some stats returned when knightstour4.py was run 100 times, rounded to two decimals: avg number of attempts to board size complete tour standard deviation 1x1 1.00 0.00 3x4 4.00 3.48 3x7 206.20 199.87 3x8 144.28 162.43 3x9 320.45 243.07 4x5 274.41 219.17 4x6 422.04 291.90 4x7 487.64 231.30 4x8 5015.27 2788.28 4x9 41156.08 26089.68 5x5 384.43 390.04 5x6 6422.71 5660.11 5x7 9399.24 9901.42 6x6 10837.56 11197.45 6x7 23868.42 21158.42 7x7 55510.21 51710.01 One thing that's interesting to note is that the standard deviations are usually very close to the averages, for each board size. For running this program on the boards with higher dimensions and more attempts, I would do this: python knightstour4.py 8 8 10000000; spd-say "done" so that I wouldn't have to keep checking my terminal every five seconds, and could go off and do other things. (Let's be real though, I would go back and check the terminal every five seconds anyway.)