#nonrecursive_fork
SPLIT_LEFT=1
SPLIT_RIGHT=2


def run(board,next,dv):
    badmove=False
    covered=[]
    sawr=[]
    sawl=[]
    lastr=[]
    lastl=[]
    vergr,vergl=[],[]
    next_dvs=[]
    while board.isopen(next):
        now=next
        covered.append(now)
        rpos=add(now,dv+1)
        lpos=add(now,dv-1)
        if board.isopen(rpos):
            lastr.append(rpos)
        else:
            if lastr:
                if rpos in board.glob:
                    badmove=SPLIT_RIGHT
                    break
                else:
                    board.glob=glob(allneighbors,board,rpos,board.glob)
                sawr.append(lastr)
                lastr=[]
        if board.isopen(lpos):
            lastl.append(lpos)
        else:
            if lastl:
                if lpos in board.glob:
                    badmove=SPLIT_LEFT
                    break
                else:
                    board.glob=glob(allneighbors,board,lpos,board.glob)
                sawl.append(lastl)
                lastl=[]
        next=add(now,dv)
    if lastr:
        vergr=lastr
        next_dvs.append((dv+1)%4)
    if lastl:
        vergl=lastl
        next_dvs.append((dv-1)%4)
    return res,covered,sawr,sawl,vergr,vergl,next_dvs,now
    
SPLIT_BUMP=3
DEADEND=4
DONE=5
def move(board,pos,dv):
    next=add(pos,dv)
    back=add(pos,dv+2)
    next_dvs=[]
    board.vergr=[]
    board.vergl=[]
    badmove,covered,board.sawr,board.sawl,board.vergr,board.vergl,next_dvs,now=run(board,next,dv)
    if board.isopen(back):
        board.back=back
    else:
        board.back=None
    bump=next
    if (board.vergr) and (board.vergl):
        if bump in board.glob:
            badmove=SPLIT_BUMP
        next_dvs=[(dv+1)%4,(dv-1)%4]
    elif (not board.vergr and not board.vergl):
        badmove=DEADEND
        if board.curopen==len(covered):
            badmove=DONE
    elif board.vergr:
        next_dvs=[(dv+1)%4]
    else:
        next_dvs=[(dv-1)%4]
    return now,bump,covered,badmove,next_dvs
    
    
    board.set_many(covered)
    board.glob=glob(allneighbors,board,now,board.glob)
    #~ movedebug=False
    #~ if movedebug:
        #~ print '++++++++++++end of move'
        #~ print 'sawr',board.sawr
        #~ print 'sawl',board.sawl
        #~ print 'vergr',board.vergr
        #~ print 'vergl',board.vergl
        #~ print 'back:',board.back
        #~ board.show()
    
    

def pack(board):
    board.alleystore.append(board.alley)
    board.globstore.append(board.glob.copy())
    board.illegalstore.append(board.illegal)
    

def unpack(board):
    board.alley=board.alleystore.pop()
    board.glob=board.globstore.pop()
    board.illegal=board.illegalstore.pop()


def fork(board,origpos,origdv):
    thisdv=origdv
    thispos=origpos
    board.thisdvs=[[origdv]]
    while 1:
        thisdvs=board.thisdvs.pop()
        #continuations from same st.
        while thisdvs:
            thisdv=thisdvs.pop()
            pack(board)
            board.sol.append(thisdv)
            endpos,bump,covered,movebad,next_dvs=move(board,origpos,thisdv)
            board.endpos=endpos
            board.endposstore.append(endpos)
            board.set_many(covered)
            board.coverstore.append(covered)
            board.glob=glob(allneighbors,board,now,board.glob)
            if not movebad:
                checkres=check(board,thisdv)
                if checkres is True:
                    #deeper
                    break
            elif movebad=='done':
                return 'done'
            unpack(board)
            unc=board.coverstore.pop()
            board.unset_many(unc)
            board.sol.pop()
        if thisdvs:
            board.thisdvs.append(thisdvs)
        board.thisdvs.append(next_dvs)
    return