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?