"""
Redelmeier's algorithm with the untried set organized as a queue.
The queue is implemented as an arry.
Prototype implementation
"""
from collections import defaultdict

nmax = 10
PRINT_SOLUTIONS = False

queuelength = nmax * 3 + 10 # polyomino plus neighbors plus safety buffer
Q = [0] * queuelength
occupied_or_adjacent = defaultdict(bool)
count = defaultdict(int)

for x in range(nmax):
    occupied_or_adjacent[x,-1] = occupied_or_adjacent[-x,0] = True
    # lower border and starting cell


polyomino = defaultdict(str)
    
def construct(stackbegin, stackend, n):
    """UNTRIED points are stored in Q[stackbegin] ... Q[stackend-1]."""
    count[n] += 1
    if PRINT_SOLUTIONS:
        polyomino[0,0]="S" # mark the start position
        print_grid(polyomino, text = f" {n=}, number {count[n]}")
        print()
    if n>=nmax:
        return
    for i in range(stackbegin, stackend):
        #print(f"{n=} {i=} {stackbegin}:{stackend} {Q[stackbegin:stackend]}",)
        #print_grid(occupied_or_adjacent)
        x,y = Q[i]
        # include cell (x,y):
        polyomino[x,y] = "X" # needed only for printing
        #occupied_or_adjacent[x,y] = "S" # helpful for debugging
        new_neighbors = [nbr for nbr in ((x-1,y),(x,y-1),(x+1,y),(x,y+1))
                         if not occupied_or_adjacent[nbr]]
        for k,nbr in enumerate(new_neighbors):
            occupied_or_adjacent[nbr]=True
            Q[stackend+k] = nbr
            
        # recursive call
        construct(i+1, stackend+len(new_neighbors), n+1)
        
        for nbr in new_neighbors:
            occupied_or_adjacent[nbr]=False # undo the mark; nbr become "unseen"
        polyomino[x,y] = " " # needed only for printing
        #occupied_or_adjacent[x,y] = True # reset the debugging marker

def print_grid(GRID, text=""):
    # print the pattern represented in the dictionary GRID
    xmin = min(x for x,y in GRID.keys())
    xmax = max(x for x,y in GRID.keys())
    ymin = min(y for x,y in GRID.keys())
    ymax = max(y for x,y in GRID.keys())
    pattern = [["." for _ in range(1+xmax-xmin)] for _ in range(1+ymax-ymin)]
    for (x,y),letter in GRID.items():
        if letter is False:
            letter = " "
        elif letter is True:
            letter = "X"
        pattern[ymax-y][x-xmin]=letter
    print("\n".join("".join(l) for l in pattern)+text + f",  {xmin}<=x<={xmax}, {ymin}<=y<={ymax}")

        
Q[0] = (0,0) # The starting square (0,0) is put on the queue
construct(0, 1, 0)
for i,val in sorted(count.items()):
    print(f"{i:2} {val:6}") # results