In Python, and do not use slicing and The only functions you may use are: print, str, int, float, bool, len, list, range, abs, round, and pow

ORIGINAL CODE :

import random; from array import array

class Cell: def __init__(self, x, y): self.x = x; self.y = y;

class GFG: #### CHANGE HERE #### # Dimensions of a square chessboard N = 4 possible_knight_movements = 3

# Move pattern on basis of the change of # x coordinates and y coordinates respectively cx = [1, 1, 2, 2, -1, -1, -2, -2] cy = [2, -2, 1, -1, 2, -2, 1, -1] #### CHANGE HERE #### # This function should restrict the knight to remain within # the chessboard, adjust accordingly for a non-square chessboard def limits(self, x, y): return ((x >= 0 and y >= 0) and (x

# Checks whether a square is valid and # empty or not def isempty(self, a, x, y): return (self.limits(x, y)) and (a[y * self.N + x]

# Picks next square using Warnsdorff's heuristic. # Returns false if it is not possible to pick # next square. def next_move(self, a, cell): min_deg_idx = -1 min_deg = (self.N + 1)

# Try all adjacent nodes of (x, y) # in Warndorff's graph based on the possible moves. # Starts from a random adjacent node and finds the one # with minimum degree. start = random.randint(0,self.possible_knight_movements - 1); for count in range(self.possible_knight_movements): i = (start + count) % self.possible_knight_movements nx = cell.x + self.cx[i] ny = cell.y + self.cy[i] c = self.get_degree(a, nx, ny) if ((self.isempty(a, nx, ny)) and (c)

# If we could not find a next cell if (min_deg_idx == -1): return None

# Store coordinates of next point nx = cell.x + self.cx[min_deg_idx] ny = cell.y + self.cy[min_deg_idx]

# Mark next move a[ny * self.N + nx] = a[(cell.y) * self.N + (cell.x)] + 1

# Update next point cell.x = nx cell.y = ny

return cell # Displays the chessboard with all the # legal knight's moves def print_tour(self, a): for i in range(self.N): for j in range(self.N): print("\t", (a[j * self.N + i]), end="") print(' ') # Checks its neighbouring squares. # If the knight ends on a square that is one # knight's move from the beginning square, # then tour is closed def neighbour(self, x, y, xx, yy): for i in range(self.possible_knight_movements): if (((x + self.cx[i]) == xx) and ((y + self.cy[i]) == yy)): return True

return False # Generates the legal moves using Warnsdorff's # heuristics. Returns false if not possible def find_closed_tour(self, initial_x,initial_y): # Filling up the chessboard matrix with -1's a = [-1] * (self.N*self.N)

# Initial position sx = initial_x sy = initial_y

# Current points are same as initial points cell = Cell(sx, sy)

a[cell.y * self.N + cell.x] = 1 # Mark first move.

# Keep picking next points using # Warnsdorff's heuristic #### CHANGE HERE #### for i in range(64 - 1): ret = self.next_move(a, cell) if (ret == None): return False

# Check if tour is closed (Can end # at starting point) if (not self.neighbour(ret.x, ret.y, sx, sy)): return False

self.print_tour(a) return True

# Driver Code to run your tour not_closed = True # While we don't have a solution, try to find one. while(not_closed): solution = GFG() current_tour = solution.find_closed_tour(0,1) if(current_tour): not_closed = False

Problem 2 (50pts) The Kangaroo Cross Puzzle In the second problem for this homework, there is code that has been adapted into Python 3 in your template file based on the code found here e. By default, the code successfully implements Warnsdorff's algorithm to solve the Knight's Tour Problem. The goal is to adapt this code to work with the irregular board shape that was given to you below: 4 5 6 8 9. 10 11 12 There are three comments labeled "#### CHANGE HERE ####" that give hints about where in the code a change should be made. Understanding the original code that works for the 8 by 8 board is key to making the proper changes and making the program work for our irregular board shape. The input for your program will take the initial and initial y coordinate for the closed tour. The output is a successful closed tour that gets printed at the end. Recommended Approach: 1. Run the program as it is originally on the 8 by 8 board to inspect firsthand its input and output 2. Then, try to have your board start at different locations by giving it a different input. (In the comments at the top of Problem 2 the coordinates for a board configuration for a 4 by 4 are listed. This could be expanded to represent the board configuration for the 8 by 8 as you are testing different inputs for the starting square). 3. After you are comfortable successfully running the program with different inputs, then start to analyze Problem 2 function by function. 4. There is not a solution for all square board configurations, but there is for a 6x6, so you can experiment with that configuration too (Note there is no solution for an NxN board when Nis 2,4 or odd). 5. There are three major changes that need to be made to get the problem to work for our irregular board shape. The "#### CHANGE HERE ####" comments are a guide to where those changes should be made. 6. When you run the program, you should eventually see your closed tour printed as output. Thus, there is no reason to use a WebCAT submission if you are not able to see the output of a successful closed tour. Problem 2 (50pts) The Kangaroo Cross Puzzle In the second problem for this homework, there is code that has been adapted into Python 3 in your template file based on the code found here e. By default, the code successfully implements Warnsdorff's algorithm to solve the Knight's Tour Problem. The goal is to adapt this code to work with the irregular board shape that was given to you below: 4 5 6 8 9. 10 11 12 There are three comments labeled "#### CHANGE HERE ####" that give hints about where in the code a change should be made. Understanding the original code that works for the 8 by 8 board is key to making the proper changes and making the program work for our irregular board shape. The input for your program will take the initial and initial y coordinate for the closed tour. The output is a successful closed tour that gets printed at the end. Recommended Approach: 1. Run the program as it is originally on the 8 by 8 board to inspect firsthand its input and output 2. Then, try to have your board start at different locations by giving it a different input. (In the comments at the top of Problem 2 the coordinates for a board configuration for a 4 by 4 are listed. This could be expanded to represent the board configuration for the 8 by 8 as you are testing different inputs for the starting square). 3. After you are comfortable successfully running the program with different inputs, then start to analyze Problem 2 function by function. 4. There is not a solution for all square board configurations, but there is for a 6x6, so you can experiment with that configuration too (Note there is no solution for an NxN board when Nis 2,4 or odd). 5. There are three major changes that need to be made to get the problem to work for our irregular board shape. The "#### CHANGE HERE ####" comments are a guide to where those changes should be made. 6. When you run the program, you should eventually see your closed tour printed as output. Thus, there is no reason to use a WebCAT submission if you are not able to see the output of a successful closed tour