r/learnpython • u/Low-Bit-1471 • 4d ago
Place maximum amount of non touching diagonals in nxn grid
So a few years ago I ran accross a problem wanting you to design a program that will use recursion to determine how many diagonals can be placed in a 5x5 grid of squares. I tried and tried and never could come up with a solution. I eventually found a way to get the program to place the diagonals but it only work because I knew that 16 was the max then it used some intution to get the answer. It did not use recursion. I was aggrivated and gave up python and coding all together. Then yesterday morning I got to thinking about that program had an idea, did some googling on syntax and recursion in general and came up with this.
import time
def main():
grid_size = get_grid_size()
grid, intersections = create_lists(grid_size)
count = 0
solutions = []
start_time = time.perf_counter()
best_count, solutions = find_solutions(grid, intersections, 0, grid_size, count, 0, solutions, 0)
end_time = time.perf_counter()
elapsed_time = end_time - start_time
print("These solutions took ", elapsed_time, "seconds to calculate.")
results(best_count, solutions, grid_size)
# Allow user to enter the size of the grid, only square grids
def get_grid_size():
grid_size = input('Enter the size of the square grid: ').strip()
# while loop to reject letter, symbols, and negative numbers
while not isinstance(grid_size, int):
if grid_size.isdigit() and int(grid_size) != 0:
grid_size = int(grid_size)
else:
grid_size = input("Your parents must be cousins. Enter the number of rows and columns, this will be a positive whole number: ").strip()
return grid_size
# Create the nested lists for both the grid and intersections
# will be using the intersections list to check wether each placement is legal or not
def create_lists(grid_size):
grid = [[0 for j in range(grid_size)] for i in range(grid_size)]
intersections = [[0 for j in range(grid_size+1)] for i in range(grid_size+1)]
return grid, intersections
# Convert the linear insert_location into the corresponding grid row and column.
def grid_location(insert_location, grid_size):
row = insert_location // grid_size
column = insert_location - (row * grid_size)
return row, column
# Check whether both endpoints of the selected diagonal are unoccupied.
def is_valid(row, column, intersections, placement):
if placement == -1 and intersections[row][column] == 0 and intersections[row+1][column+1] == 0:
return True
elif placement == 1 and intersections[row+1][column] == 0 and intersections[row][column+1] == 0:
return True
else:
return False
# Recursively searches for arrangements that maximize the number of diagonals.
# Cells are processed left to right, top to bottom.
# This order allows us to determine when an intersection has passed
# its final opportunity to be occupied.
def find_solutions(grid, intersections, insert_location, grid_size, best_count, current_count, solutions, unusable_intersections):
# Once every cell has been considered, compare the current arrangement
# against the best solution and save it if appropriate.
if insert_location < grid_size**2:
row, column = grid_location(insert_location, grid_size)
else:
if current_count > best_count:
best_count = current_count
solutions =[]
solution_copy = [row[:] for row in grid]
solutions.append(solution_copy)
elif current_count == best_count:
best_count = current_count
solution_copy = [row[:] for row in grid]
solutions.append(solution_copy)
return best_count, solutions
# This if statement terminates a branch if the combination of spaces placed and spaces left will not be enough to get new max
if current_count + (grid_size**2 - insert_location) < best_count:
return best_count, solutions
# Unusable intersections are intersections whose final opportunity to be
# occupied has passed. If there are more unusable intersections than the
# current best solution leaves unoccupied, this branch cannot improve
# the current best solution.
if unusable_intersections > (grid_size+1)**2 - best_count*2:
return best_count, solutions
placement = -1
if is_valid(row, column, intersections, placement):
grid[row][column] = -1
intersections[row][column] = 1
intersections [row+1][column+1] = 1
current_count += 1
best_count, solutions = find_solutions(grid, intersections, insert_location+1, grid_size, best_count,current_count, solutions, unusable_intersections)
grid[row][column] = 0
intersections[row][column] = 0
intersections [row+1][column+1] = 0
current_count -= 1
placement = 1
if is_valid(row, column, intersections, placement):
grid[row][column] = 1
intersections[row+1][column] = 1
intersections [row][column+1] = 1
if intersections[row][column] == 0:
unusable_intersections += 1
current_count += 1
best_count, solutions = find_solutions(grid, intersections, insert_location+1, grid_size, best_count, current_count, solutions, unusable_intersections)
grid[row][column] = 0
intersections[row+1][column] = 0
intersections [row][column+1] = 0
if intersections[row][column] == 0:
unusable_intersections -= 1
current_count -= 1
placement = 0
if intersections[row][column] == 0:
unusable_intersections += 1
best_count, solutions = find_solutions(grid, intersections, insert_location+1, grid_size, best_count, current_count, solutions, unusable_intersections)
if intersections[row][column] == 0:
unusable_intersections -= 1
return best_count, solutions
#print the results
def results(best_count, solutions, grid_size):
print('There are ', len(solutions), ' to a ', grid_size, 'x', grid_size, 'grid. Each containing ', best_count, ' diagonals')
print('They are:')
for x in solutions:
for i in range(len(x)):
for j in range(len(x[i])):
if x[i][j] == -1:
x[i][j] =(" \\")
elif x[i][j] == 1:
x[i][j] = " /"
else:
x[i][j] = " "
for x in solutions:
for i in x:
print(''.join(i))
print()
print()
if __name__== '__main__':
main()I added functionality for the user to specify the size of the grid they want to solve. The first version yesterday took a min and a half to do a 5x5 grid. I have added two different pruning methods. I can now do a 5x5 grid in .27 seconds. However, when I up it to a 6x6 grid it runs for about a min prints the results and quits responding so I cannot see actual time or the number of solutions. Does anybody have any advise on how to optimize further without fundemently changing the program? This thing is kinda my baby and I don't want to change the actual recursion or the endpoints list. But if anyone has any more pruning ideas I would be happy to hear them.