Find solutions for the n-box problem

boxes.py

#!/usr/bin/env python3
""" Find solutions for the n-box problem. Solutions are represented as
    a list of box indices for each integer. Partial sums are cached and
    passed around. """
from copy import copy
from sys import argv,stderr
import random

n_boxes = int(argv[1])

def box_numbers(solution, box):
    """ compute the numbers in an a box for a particular solution """
    for n,b in enumerate(solution):
        if b == box:
            yield n+1

def print_sol(solution, sums):
    """ pretty printer """
    print("%d:"%len(solution))
    for b in range(n_boxes):
        # print("\t%d: %s (sums: %s)" % (b, list(box_numbers(solution, b)), sums[b]))
        print("\t%d: %s" % (b, list(box_numbers(solution, b))))
    print("Max attainable length: %d" % max_attainable_length(sums))
    print()

def max_attainable_length(sums):
    """ return a bound on the length obtainable by deepening a particular solution """
    try:
        return min(set.intersection(*[set(s) for s in sums]))-1
    except ValueError:
        return 1e10 # when the intersection is empty, for pypy compatibility

def deepen(solution, sums):
    """ Find deeper solutions from a starting solution """
    new_number = len(solution) + 1 # starts at 1
    for box in range(n_boxes):
        if new_number not in sums[box]:
            new_solution = solution + [box]
            new_sums = copy(sums)
            new_sums[box] = new_sums[box] + [new_number+n for n in box_numbers(solution, box)]
            yield (new_solution, new_sums)

if __name__ == '__main__':
    max_length = 0
    tries = 0
    to_search = [([], [[] for _ in range(n_boxes)])]
    while to_search:
        if tries % 1e4 == 0:
            to_search = [(s,ss) for s,ss in to_search if max_attainable_length(ss) > max_length] # prune
            best_sol_length = max(len(s) for s,ss in to_search)
            print("\r Max length: %d. Already tried %.2g solutions. %d solutions in the pipeline. Currently exploring solutions of length %d  " %
                    (max_length, tries, len(to_search), best_sol_length), file=stderr, end="")
        # solution, sums = to_search.pop(0) # BFS
        solution, sums = to_search.pop() # DFS
        # solution, sums = to_search.pop(random.randrange(0,len(to_search))) # RFS

        if max_attainable_length(sums) > max_length:
            for new_solution, new_sums in deepen(solution, sums):
                if len(new_solution) > max_length:
                    print()
                    print_sol(new_solution, new_sums)
                    max_length = len(new_solution)
                if max_attainable_length(new_sums) > max_length:
                    to_search.append((new_solution, new_sums))
        tries += 1
    print()
    print("Done. Explored a total of %d solutions" % tries)