digits-puzzle-heuristics.py

# we can dramatically reduce the possible answers space
# using a simple heuristic instead of straightforward permutation generation
# here we have 360 variants instead of 40K using the bruteforce approach

LEN = 8

def generate_possible_positions(digit):
  start = 0
  while start + digit + 1 < LEN:
    yield (start, start + digit + 1)
    start += 1

def check_positions_interlapping(*limitations):
    s = set()
    for l in limitations:
        s = s.union(set(l))
    return len(s) == LEN

def build_number_string(fours_variant, threes_variant, twos_variant, ones_variant):
    arr = [0]*8
    arr[fours_variant[0]] = arr[fours_variant[1]] = 4
    arr[threes_variant[0]] = arr[threes_variant[1]] = 3
    arr[twos_variant[0]] = arr[twos_variant[1]] = 2
    arr[ones_variant[0]] = arr[ones_variant[1]] = 1
    return ''.join(map(str, arr))


def solve():
    for fours_variant in generate_possible_positions(4):
        for threes_variant in generate_possible_positions(3):
            for twos_variant in generate_possible_positions(2):
                for ones_variant in generate_possible_positions(1):
                    print(fours_variant, threes_variant, twos_variant, ones_variant,
                        check_positions_interlapping(fours_variant, threes_variant, twos_variant, ones_variant),
                        build_number_string(fours_variant, threes_variant, twos_variant, ones_variant))

solve()