How to get rid of a recursion depth error or is it better to solve this problem?

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 so that each horizontal and vertical neighbors should divide without a trace. For example, 12 and 3 can be neighbors because 12 % 3 == 0 , but 5 and 12 cannot. The 2x2 grid is set to 10 .

I tried to solve the problem using a list of sets. Each set represents the possible values ​​for each grid. When each set has only one element, the problem is resolved. Here are the functions that I use to try to solve this problem (I added the whole thing just in case, but I think my problem is solving the 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 exceed the maximum recursion depth. Any ideas how to get around this, or how best to solve this problem in Python?

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

Answer 1

It's a rainy day here, so I wrote a solution. I can send if you want, but maybe you will soon find it yourself?

Here are some tips:

• your code doesn't seem to start at 10 in (2,2)

• when trying a new value, you can add it to any empty space. the best place to look is one that has many neighbors because it allows you to quickly test and reject bad values.

• suggested above, or another way of saying the same thing - my search was above the values. so I chose a place for the “next move” and tried every value there. on the contrary, there would be a search in places (I chose the "next value" and a search with this value in each place), but this is not so effective (see above).

• when backtracking and retrying, the same layout always follows. for example, (2.2) is 10, then (2.3) can be 40, then you can find nothing suitable (2.4). so you step back and remove 40 and try a different number (2,3). but the second number you try (after 10 and something in (2.2)) is always in (2,3). if you are not so careful, you can end up testing many duplicate combinations. Sorry, not sure if this is very clear. basically - select the "path" that you fill in and stick to it when searching and backtracking. since this path was chosen to maximize the number of neighbors (the point above), I built it as I continued, but kept the cache of the paths that I used in the backtracking. it's easier to explain by showing the code ...

• For the table, I used an array of arrays. when copying, I reused columns that were not changed. this should reduce memory usage (I don't know if this is important).

• the search requires only 40x repetition (once for each value), so the stack is quite large.

• A simple search in python, which in turn tries each value, returning with an error, works on my laptop for ~ 4 minutes (provided that you use the prompts above) (without printing, a slightly modified version takes only 8 seconds).

• I found it useful to have a python function that, given the grid and position, returns a list (well, a generator, with yield ) of neighbors' coordinates. which made recording of other functions, such as those that check whether the movement is in order, easier.

anyway, if you need a code or solution (I changed my code to print everything, and there was only one), just ask and I will send a message. Of course, he may have a mistake: o)

Decision

I changed this a bit and now it prints out the solution (2,2) = 10 and then searches for all the solutions (which still work 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)) 

starts by choosing a square where it will add the next number using next_xy() . he selects the location of as many existing numbers as possible so that he can test and reject the numbers efficiently (the position is saved in xy_moves , so it does not need to be re-detected if we go back). for each value, it checks to see if the value works at that position with move_ok . if so, it calculates a new grid (with added value) and a new list of values ​​(with deletion of the used value) and recurses. recursion ends when there are no added values.

and here is the result (each internal 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 

[removed incorrect comment about recursion and generators]

Update

he completed a global search - if you do not fix (2,2) at the beginning, there seem to be only 12 solutions (3 different solutions if you ignore simple symmetries).

update 2

final code, including finding all solutions without symmetrical duplicates

Answer 2

To avoid breaking your stack, a more reliable approach is to develop an encoding for your partial solutions (partially filled on the board) and implement returns. This will require much less memory than relying on the python stack.

Google Peter Norvig wrote an illustrative article describing how he used such methods to build an effective sudoku solver rollback. He uses a technique that he calls “constraint propagation” to limit the space of options, so that a solution can be quickly found by brute force brute force search (i.e., without checking the entire possible grid of numbers, but only to perform partial grids that can lead to a solution). I think you will find it extremely applicable not only for general ideas, but also for specifics: your problem, since you are close to it, is very close to the sudoku solver.

Answer 3

There is a way to set a custom value for the Python recursion limit (the default is 1000):

 import sys sys.setrecursionlimit(10000000) 

You can add these lines before the recursive call, and if the problem remains, you should look at your implementation for other possible errors.