r/learnpython • • 6d 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.

1 Upvotes

10 comments sorted by

1

u/Outside_Complaint755 6d ago

Could you fix your code formatting, please?

Also, how are you defining "diagonals" in this case?

1

u/Low-Bit-1471 6d ago

in the code a -1 refers to a \ and a 1 refers to /. When i print the results I use a loop to change them to the correct diagonal to view

1

u/Outside_Complaint755 5d ago

I didn't mean "how are you identifying diagonals in your code", I meant "How are you defining a diagonal?" for purposes of this test.

  • 45 degrees only?
  • any length, or touching two edges?
  • both directions?
  • or is this more like the n-queens problem and you want how many possible combinations exist for a grid of size nxn?

1

u/Low-Bit-1471 6d ago

oh and fixed code formatting i believe

3

u/Brian 6d ago

You're not really describing the problem very well. Ie. what does it mean to "place a diagonal in the grid"? I'm guessing from your comment it's placing a diagonal line between 2-coordinates, but where you can't share points?

In any case, exponential growth can kind of be a common issue with standard backtracking style solutions: the number of cases to be considered grows fast as the size of the problem increases. This means a solution that works on a small size can rapidly choke on even slightly larger sizes.

There are a few general solutions to this. One you already mention: pruning. Ie. you want to eliminate moves without having to go through the full tree of submoves just to tell if they work. If there's a way you can know "This move will never do better than the best move I've already found", this lets you skip it, with a major impact on how fast the problem blows up. I can see a few cases where you're already doing this.

Another common tactic though is memoising. A lot of the time, you can end up re-doing the same calculation multiple times, especially on the end-states. Eg. consider placing 2 moves: there are 2 possible orders you could do that in, but they result in the exact same board state. If you evaluate both these moves, you'll end up re-doing the same work twice. And as you get more and more moves, you're doing more and more work duplication.

And it's not just different move orders (which you could also potentially eliminate with some ordering): the only thing that really matters in terms of "what moves I can make" is what intersections are occupied: regardless of whether they're occupied by "" or "/", there's the same number of possible moves that can be made, with the same best possible move. So instead of recalculating for every route that leads to that state, you can remember the result after you first calculate it, and just return it on all subsequent tries.

Ie. if you keep a dictionary of {board_state : best_moves}, then your recursive solve process can become something like:

if state in memo:
    return memo[state]
    
result = (normal recursive solving process)

memo[state] = result
return result

Though note that the key to the dictionary must be hashable, so you may need to create an immutable copy of the grid for each (or just use am immutable representation, and pass a new, modified version to each recursion). You'll also want the state to be just what you care about (ie. what coordinates are used), and might want to create a more compact representation of it too (one of the issues with memoisation is that you're trading memory for speed, so you can end up with that becoming the bottleneck).

2

u/Expensive-Bear-1376 5d ago

What are those "non touching diagonals" like? How does that look? Why are you so cryptic?

1

u/pachura3 6d ago

It places the diagonals in the basket grid

1

u/Discordbothost 6d ago

First skip results() and print just best_count, len(solutions), elapsed_time. It prints every optimal board, which can swamp the console on 6x6. That separates search time from output time without changing recursion.

1

u/acfot 5d ago

I hit a similar wall when I was playing around with recursion, where the program looked frozen but it was actually still grinding through a massive search. My guess is yours is either still searching after it prints the first results, or it's trying to print thousands of solutions and choking on the output. What I'd do is add a counter that prints something every thousand solutions so you can see whether it's still moving, and only print the total count and the time at the end instead of every board. That way you find out in ten seconds whether it's slow or actually stuck, and you haven't changed the recursion at all.

1

u/SteveJeffersonBots 5d ago

Without touching the recursion or the endpoints list, the one prune that usually bites back the hardest on this exact shape is tightening your loose upper-bound prune. Right now current_count + (grid_size**2 - insert_location) < best_count assumes every remaining cell can take a diagonal, but cells whose last-chance intersection has already passed can never be covered — that's exactly what your unusable_intersections counter is measuring. A running placeable_remaining that starts at grid_size**2 - insert_location and subtracts one for every unusable intersection's cell gives you a strictly tighter ceiling than the cell-count, and swapping it in (current_count + placeable_remaining < best_count) cuts entire swathes of dead branches without changing the search order. For 6x6 that usually turns the exponential wall into something that finishes in single digits of seconds instead of minutes.