Hello, the problem consists of a knight that can move 3 squares in L. The function must receive the number of moves to make, and return the number of valid moves, for example if there are 2 moves, I can go first from 0 to 6, or from 0 to 4, there I already made a move in which there are two valid possibilities, so I have another move left, first starting from 6, 6 to 0, 6 to 7 or 6 to 1 which makes 3 more valid moves, and finally starting from 4 I can go from 4 to 3, 4 to 9 or 4 to 0 which are another 3 valid movements, and I already spent my two movements then there for the case of starting from 0, that case then I will have 8 valid movements in total, then I will have to evaluate the case of 1, until I reach 9 and add all those movements that in total should be 44.
The proposed program is:
chessBoard = [[1,2,3],[4,5,6], [7,8,9], [None, 0, None]]
def countMatrizElements(matriz):
counter = 0
for row in range(len(matriz)):
for col in range (len(matriz[row])):
if matriz[row][col] != None:
counter = counter + 1
return counter
def horseValidMovementsAux(board, movements, startpoint):
if movements == 0:
return 0
for row in range(len(board)):
for col in range (len(board[row])):
if(board[row][col] == startpoint):
if(row==0 and col == 0):
return 2+horseValidMovementsAux(board,movements-1,board[row+1][col+2])+horseValidMovementsAux(board,movements-1,board[row+2][col+1])
elif(row==1 and col == 0):
return 3+horseValidMovementsAux(board,movements-1,board[row+1][col+2])+horseValidMovementsAux(board,movements-1,board[row-1][col+2])+horseValidMovementsAux(board,movements-1,board[row+2][col+1])
elif(row==2 and col == 0):
return 2+horseValidMovementsAux(board,movements-1,board[row-1][col+2])+horseValidMovementsAux(board,movements-1,board[row-2][col+1])
elif(row== 3 and col == 1):
return 2+horseValidMovementsAux(board,movements-1,board[row-2][col+1])+horseValidMovementsAux(board,movements-1,board[row-2][col-1])
elif(row==0 and col == 1):
return 2+horseValidMovementsAux(board,movements-1,board[row+2][col+1])+horseValidMovementsAux(board,movements-1,board[row+2][col-1])
elif(row==1 and col == 1):
return 0
elif(row==2 and col == 1):
return 2+horseValidMovementsAux(board,movements-1,board[row-2][col+1])+horseValidMovementsAux(board,movements-1,board[row-2][col-1])
elif(row==0 and col == 2):
return 2+horseValidMovementsAux(board,movements-1,board[row+2][col-1])+horseValidMovementsAux(board,movements-1,board[row+1][col-2])
elif(row==1 and col == 2):
return 3+horseValidMovementsAux(board,movements-1,board[row+2][col-1])+horseValidMovementsAux(board,movements-1,board[row-1][col-2])+horseValidMovementsAux(board,movements-1,board[row+1][col-2])
elif(row==2 and col == 2):
return 2+horseValidMovementsAux(board,movements-1,board[row-2][col-1])+horseValidMovementsAux(board,movements-1,board[row-1][col-2])
def horseValidMovements(board, movements):
countingMovements = 0
for startPosition in range(countMatrizElements(board)):
countingMovements = countingMovements + horseValidMovementsAux(board, movements, startPosition)
return countingMovements
print(horseValidMovements(chessBoard, 1))
That calling with 1 move gives me a total of 20 possibilities, which is correct. But when I call with 2 moves it gives me 66, which is wrong, because with 2 moves it is supposed to give 46.
Analyzing the program step by step I find this:
Enter 2 moves startposition is 0
when I call the recursive function I pass 2 moves and the square 0
Enter the for that will look for where my element is. find it in row 3 column 1
Add 2, subtract a move, making 2 moves now only have 1 move left, first call the box in row 1 with column 0, that is, 4, and also call the box in row 1 with column 2 , that is box 6.
now when you call element 4 it will be in row 1 with column 0
what will happen here is that it will add 3, and it will call the others, but since now its movements are 1, when subtracting in the call they will be 0 and they will activate the base case, causing it not to add more and finally return its sum
The same for the case of box 6, which is in row 1 column 2
will add 3 and make its calls that will activate the base case.
In total with the sums we would have 2+3+3 = 8 The expected would be: 0 can go to 4 or 6, those are 2 possible moves, from 4 to 3 to 9 or 0, those are 3 moves and from 6 it can go to 1, 7 or 0 which is another 3 moves, that will add up to 8, which agrees with the result of the program.
What is causing it to not give the total result of 46 and instead more possible moves than that?
I'm not sure I have understood the conditions of the problem correctly. In this case, I await your comments to clarify and correct.
Solution
First I'll create a cell-indexed dictionary on the board. The value is the cells that can be reached from there:
I will make a recursive function that executes all valid moves from a starting point in a given number of steps (1, 2, ....)
The number of moves from that starting position is equal to the length of the associated list. To this are added the movements from each of the positions in the associated list, a process that is repeated recursively until the total number of steps is completed.
I also build a function that loops through each starting cell, computes the moves and totals them, giving the final result:
To test, I will calculate the moves in one step and in two steps:
To validate the result I have printed each accounted movement, in format:
The result for one step is:
and for two steps (I have separated the lines manually for clarity):
And the final result is 66.