Write the function knightsTour(rows, cols) that takes a… Write the function knightsTour(rows, cols) that takes a non-negative int n and returns a 2d list of a knight’s tour on a rows-by-cols board, or None if this does not exist. Following these instructions, knightsTour(4, 5) should return a legal 4×5 knight’s tour, such as this one: [ 1, 14, 5, 18, 7] [10, 19 8 13 4] [15 2, 11, 6, 17] [20 9, 16 3, 12]… Show moreRequirements:1) It is possible for some dimensions that there is a legal knight’s tour, only not one starting at the top-left corner. You will have to account for that in your solution.2) Must use recursion meaningfully when solving the problem ( can use for/while loops)Test case:def testKnightsTour(): print(‘Testing knightsTour()….’, end=”) def checkDims(rows, cols, ok=True): T = knightsTour(rows, cols) s = f’knightsTour({rows},{cols})’ if (not ok): if (T is not None): raise Exception(f'{s} should return None’) return True if (T is None): raise Exception(f'{s} must return a {rows}x{cols}’ +’ 2d list (not None)’) if ((rows != len(T)) or (cols != (len(T[0])))): raise Exception(f'{s} must return a {rows}x{cols} 2d list’) d = dict() for r in range(rows): for c in range(cols): d[ T[r][c] ] = (r,c) if (sorted(d.keys()) != list(range(1, rows*cols+1))): raise Exception(f'{s} should contain numbers’ +’ from 1 to {rows*cols}’) prevRow, prevCol = d[1] for step in range(2, rows*cols+1): row,col = d[step] distance = abs(prevRow – row) + abs(prevCol – col) if (distance != 3): raise Exception(f'{s}: from {step-1} to {step}’ +’ is not a legal move’) prevRow, prevCol = row,col return True assert(checkDims(4, 3)) assert(checkDims(4, 4, ok=False)) assert(checkDims(4, 5)) assert(checkDims(3, 4)) assert(checkDims(3, 6, ok=False)) assert(checkDims(3, 7)) assert(checkDims(5, 5)) print(‘Passed!’)Computer ScienceEngineering & TechnologyPython Programming CS 152
