How to get rid of maximum recursion depth error or better solve this?

Problem: We have a square grid of 5 rows and 4 columns. We need to use these numbers to fill the grid; 1,2,3,4,5,6,7,8,9,10,12,18,20,21,24,27,30,35,36,40. We need to fill the grid in such a way that every horizontal and vertical neighbors should divide other without remainder. For example, 12 and 3 can be neighbors because 12 % 3 == 0, but 5 and 12 can’t. Grid 2×2 is given to be 10.

I tried to solve problem using a list of sets. Each set represent possible values for each grid. When every set has only one element, problem is solved. Here are the functions I use to try to solve this problem (I added whole thing just in case, but I think my problem is in solve function.);

class CannotSolveError(Exception):
    pass

def suitable_neighbor(a,b):
    "return True if a and b can be neighbors."
    return (a > b) and (a % b == 0) or (b % a == 0)

def equalize_tables(table1, table2):
    "Make two tables equal, by changing first one in-place"
    for i in range(len(table1)):
        table1[i] = table2[i]


def remove_possibility(table, row, column, value):
    """Remove possibilities that can't be neighbors with value in rowxcolumn grid."""

    index = ((row - 1) * num_cols) + column - 1

    if len(table[index]) == 1:
        return # This is a solved grid, do nothing.

    remaining_possibilities = set(
        filter(lambda x: suitable_neighbor(x, value), table[index])
                                )

    if not remaining_possibilities:
        raise ValueError("Invalid move")

    if len(remaining_possibilities) == 1:
        "Only one possibility remains, try to put it!"
        copy_table = table[:]
        try:
            "Try it on copy"
            put(copy_table, row, column, remaining_possibilities.pop())
        except ValueError:
            "Cannot put, re-raise and do nothing.."
            raise
        else:
            "Putting is successfull, update original table"
            equalize_tables(table, copy_table)
    else:
        table[index] = remaining_possibilities


def put(table, row, column, value):
    """Put a value on a grid, modifies given table. use with care!"""

    index = ((row - 1) * num_cols) + column - 1

    "Is this move possible?"
    if value not in table[index]:
        raise ValueError("Cannot put %d on %dx%d" % (value, row, column))

    "Remove possibilities from left neighbor"
    if column > 1:
        remove_possibility(table, row, column - 1, value)

    "Remove possibilities from right neighbor"
    if column < num_cols:
        remove_possibility(table, row, column + 1, value)

    "Remove possibilities from upper neighbor"
    if row > 1:
        remove_possibility(table, row - 1, column, value)

    "Remove possibilities from lower neighbor"
    if row < num_rows:
        remove_possibility(table, row + 1, column, value)

    "Remove this value from every other set."
    for i in range(num_rows * num_cols):
        if i == index:
            continue

        table[i].discard(value)

    "Put one-item set in place. Have to do this last."
    table[index] = set([value])



def solve(table):
    "Try to solve the table by trying possible values on grids."

    to_try = [(i,len(table[i])) for i in range(num_rows * num_cols) if len(table[i]) > 1]

    "Grid with least remaining possibilities will be tried first."
    to_try.sort(key = lambda x: x[1])

    for index, _ in to_try:
        for value in table[index]:
            row = index / num_cols + 1
            column = index % num_cols + 1
            copy_table = table[:]
            put(copy_table, row, column, value)
            try:
                solve(copy_table)
                equalize_tables(table, copy_table)
                return
            except CannotSolveError:
                continue
            except ValueError:
                continue
    raise CannotSolveError

I think this algorithm should solve the problem. But I am exceding maximum recursion depth. Any ideas how to work around this, or how should I solve this problem better in Python?

This is not a homework question. I am working on this by myself.

Best answer

it’s a rainy day here, so i wrote a solution. i can post if you want, but perhaps you would rather find it yourself?

here are some hints:

  • your code doesn’t seem to start with 10 at (2,2)
  • when trying a new value, you could add it to any empty space. the best space to try is one that has lots of neighbours, because that lets you test and reject bad values quickly.
  • assumed above, or a different way of saying the same thing – my search was over values. so i chose a location for “next move” and tried each value there. the opposite would be to search over locations (chose a “next value” and search with that value at each location), but that is not as efficient (see above).
  • when backtracking and re-trying, always follow the same pattern of locations. for example, (2,2) is 10 then (2,3) might be 40, then you might find nothing fits (2,4). so you backtrack and remove 40 and try a different number at (2,3). but the second number you try (after 10 and something at (2,2)) is always at (2,3). if you aren’t careful in this way you can end up testing many duplicate combinations. sorry not sure this is very clear. basically – choose a “path” that you fill and stick to it when searching and backtracking. since this path is chosen to maximise the number of neighbours (point above) i constructed it as i went on, but kept a cache of the path locations that i used when backtracking. this is easier to explain by showing the code…
  • for the table i used an array of arrays. when copying i re-used columns that were not changed. this should reduce memory use (i don’t know if it is important).
  • the search only needs to recurse 40 times (once for each value) so the stack is plenty big enough.
  • a simple search, in python, that tries each value in turn, backtracking on failure, runs ~4 minutes on my laptop (assuming you use the hints above) (without the printing a slightly modified version takes just 8 seconds).
  • i found it was useful to have a python function that, given a grid and a position, returns a list (well, a generator, with yield) of the coordinates of neighbours. that made writing other functions, like the one that tests whether a move is ok, simpler.

anyway, if you want the code or the solution (i changed my code to print all and there was just one) just ask and i will post. of course, it may have a bug too :o)

solution

i tweaked this some, and it now prints out the (2,2)=10 solution and then searches for all solutions (which is still running for me):

#!/usr/bin/python3

nx, ny = 4, 5
values = [1,2,3,4,5,6,7,8,9,10,12,18,20,21,24,27,30,35,36,40]
# grid[x][y] so it is a list of columns (prints misleadingly!)
grid = [[0 for _ in range(ny)] for _ in range(nx)]
# cache these to avoid re-calculating
xy_moves = {}
debug = False

def neighbours(grid, x, y):
    'coordinates of vertical/horizontal neighbours'
    for (xx, yy) in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
        if xx > -1 and xx < nx and yy > -1 and yy < ny:
            yield xx, yy

def filled_neighbours(grid, x, y):
    'filter "neighbours" to give only filled cells'
    return filter(lambda xy: grid[xy[0]][xy[1]], neighbours(grid, x, y))

def count_neighbours(grid, x, y):
    'use this to find most-constrained location'
    return sum(1 for _ in filled_neighbours(grid, x, y))

def next_xy(grid, depth):
    '''given a certain depth in the search, where should we move next?  
       choose a place with lots of neighbours so that we have good 
       constraints (and so can reject bad moves)'''
    if depth not in xy_moves:
        best, x, y = 0, nx // 2, ny // 2 # default to centre
        for xx in range(nx):
            for yy in range(ny):
                if not grid[xx][yy]:
                    count = count_neighbours(grid, xx, yy)
                    if count > best:
                        best, x, y = count, xx, yy
        xy_moves[depth] = (x, y)
        if debug: print('next move for %d is %d,%d' % (depth, x, y))
    return xy_moves[depth]

def drop_value(value, values):
    'remove value from the values'
    return [v for v in values if v != value]

def copy_grid(grid, x, y, value):
    'copy grid, replacing the value at x,y'
    return [[value if j == y else grid[i][j] for j in range(ny)]
            if x == i else grid[i]
            for i in range(nx)]

def move_ok(grid, x, y, value):
    'are all neighbours multiples?'
    for (xx, yy) in filled_neighbours(grid, x, y):
        g = grid[xx][yy]
        if (g > value and g % value) or (g < value and value % g):
            if debug: 
                print('fail: %d at %d,%d in %s' % (value, x, y, grid))
            return False
    return True

def search(grid, values, depth=0):
    'search over all values, backtracking on failure'
    if values:
        (x, y) = next_xy(grid, depth)
        for value in values:
            if move_ok(grid, x, y, value):
                if debug: print('add %d to %d,%d' % (value, x, y))
                for result in search(copy_grid(grid, x, y, value),
                                     drop_value(value, values), 
                                     depth+1):
                    yield result
    else:
        yield grid


# run the search, knowing that (2,2) (which is (1,1) for zero-indexing)
# has the value 10.
for result in search(copy_grid(grid, 1, 1, 10), drop_value(10, values)):
    print(result)

# how many solutions in total?
#xy_moves = {} # reset cache
#for (n, solution) in enumerate(search(grid, values)):
#    print('%d: %s' % (n, solution))

it starts by choosing the square where it will add the next number using next_xy(). it chooses a place near as many existing numbers as possible so that it can test and reject numbers efficiently (the position is saved in xy_moves so that it doesn’t need to be re-found if we backtrack). for each value it checks to see if putting the value at that position works using move_ok. if so, it calculates a new grid (with the value added) and a new list of values (with the used value removed) and recurses. recursion finishes when there are no values left to add.

and here is the result (each inner list is a column):

> time ./grid.py 
[[4, 20, 5, 35, 7], [40, 10, 30, 1, 21], [8, 2, 6, 18, 3], [24, 12, 36, 9, 27]]
real    0m5.909s

[deleted incorrect comment about recursion and generators]

update

it finished the global search – if you don’t fix (2,2) at the start there seem to be 12 solutions in total (3 distinct solutions if you ignore simple symmetries).

update 2

final code, including search for all solutions without symmetrical duplicates