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

Question

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 2x2 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.

Answer 1

To avoid blowing up your stack, a more robust approach is to devise an encoding for your partial solutions (partially filled in board), and implement the backtracking yourself. That will require a lot less memory than relying on python's stack.

Google's Peter Norvig has written an illuminating article describing how he used such techniques to build an efficient backtracking sudoku solver. It uses a technique he calls "constraint propagation" to limit the space of options, so that the solution can be quickly found via brute force backtracking search (that is, without checking every possible grid of numbers, but only pursuing partial grids that might still lead to a solution). I think you will find it extremely applicable, not only for the general ideas but also for the specifics: Your problem, as you have approached it, is extremely close to a sudoku solver.

Answer 2

There's a way to set custom value for Python recursion limit (which is 1000 by default):

import sys
sys.setrecursionlimit(10000000)

You can add those lines before recursive call and if the problem remains, you have to review your implementation for other possible bugs.