I am not looking for a detailed review of this code as I am aware it is very inefficient. The main reason for posting this is to see if there is a better way to achieve my goal (I am certain there must be)
I have created code to find the fewest number of dice rolls that would permit someone to move from the first to last square on a snakes and ladders board. The player wins if they land on or go beyond the final square on the board. They start off the board at position -1.
My approach uses recursion so is OK for small boards. The moment the board reaches a size of 30+ it takes far too long to generate the solution.
Is there a better way to solve this problem
"""Module works out fastest way to traverse a snakes and ladders board""" def roll_dice(position, roll_number, number_squares, snakes, ladders, list_moves=[]): """Roll the dice and then work out if the player can climb a ladder / has won""" if position in ladders: position = ladders[position] if position >= number_squares -1: list_moves.append(roll_number) return for i in range(1, 7): #For each position roll the dice 6 times if position + i in snakes: continue # Forbid a dice-roll that lands on a snake roll_dice(position + i, roll_number + 1, number_squares, snakes, ladders) return list_moves def minimum_moves(number_squares, snakes={}, ladders={}): """Returns the minimum number of moves starting from position 0 for a board of size n snakes and ladders are both dictionaries containing the starting point as the key and end point as the value""" # Initialise board # The player starts off the board at position -1 list_moves = roll_dice(-1, 0, number_squares, snakes, ladders) print(f"Board is traversable in {min(list_moves)} moves") if __name__ == "__main__": NUMBER_SQUARES = 25 SNAKES = {21:0, 19:9, 14: 2, 18:5} LADDERS = {2: 21, 4:9, 10:20, 17:23} minimum_moves(NUMBER_SQUARES, SNAKES, LADDERS)
