birthday2.py

BDAYSD = { 13: {5:1, 7:1}, 14:{7:1 , 8:1}, 15:{5:1,8:1}, 17:{6:1,8:1}, 18:{6:1}, 19:{5:1} }
BDAYSM = { 5: {13:1, 15:1, 19:1}, 6: {17:1, 18:1}, 7: {13:1, 14:1}, 8:{14:1, 15:1, 17:1} } 

def removeObvious(status = False):
    
    if not status:  
        b = {a: {d: BDAYSD[a][d] for d in BDAYSD[a] if BDAYSD[a][d] == 1} for a in BDAYSD }  
        for d in b:
            if len(b[d]) == 1:
                for m1 in b[d]:
                    print "Removing obvious day: ({}/{})".format(d, m1)
                    BDAYSD[d][m1] = 0
                    BDAYSM[m1][d] = 0
        m = {a: {d: BDAYSM[a][d] for d in BDAYSM[a] if BDAYSM[a][d] == 1} for a in BDAYSM }
        for n in m:
            if len(m[n]) == 1:
                print "Removing obvious month: {}".format(n)
                for d in m[n]:
                    BDAYSM[n][d] = 0
                    BDAYSD[d][n] = 0
    else:
        b = {a: {d: BDAYSD[a][d] for d in BDAYSD[a] if BDAYSD[a][d] == 1} for a in BDAYSD }
        for d in b:
            if len(b[d]) > 1:
                for m1 in b[d]:
                    print "Removing non-obvious day: ({}/{})".format(d, m1)
                    BDAYSD[d][m1] = 0
                    BDAYSM[m1][d] = 0
        m = {a: {d: BDAYSM[a][d] for d in BDAYSM[a] if BDAYSM[a][d] == 1} for a in BDAYSM }
        for n in m:
            if len(m[n]) > 1:
                print "Removing non-obvious month: {}".format(n)
                for d in m[n]:
                    BDAYSM[n][d] = 0
                    BDAYSD[d][n] = 0

    differenceFound = False
    for d in b:
        for m1 in b[d]: 
            if BDAYSD[d][m1] != b[d][m1]:
                differenceFound = True

    return differenceFound

def removeMonth(month):
    print "Removing month: {}".format(month)
    b = {a: {d: BDAYSD[a][d] for d in BDAYSD[a] if BDAYSD[a][d] == 1} for a in BDAYSD }
    m = {a: {d: BDAYSM[a][d] for d in BDAYSM[a] if BDAYSM[a][d] == 1} for a in BDAYSM }    
    for d in m[month]:
        BDAYSM[month][d] = 0
        BDAYSD[d][month] = 0
    #showTables()
    showPossibleDates()

def showPossibleDates():
    hasPossibleDate = False
    m = {a: {d: BDAYSM[a][d] for d in BDAYSM[a] if BDAYSM[a][d] == 1} for a in BDAYSM } 
    for m1 in sorted(m):
        for d in m[m1]:
            if BDAYSM[m1][d] != 0:
                if hasPossibleDate:
                    print ", ({}/{})".format( d, m1), 
                else:
                    print "Possible dates: ({}/{})".format( d, m1), 
                
                hasPossibleDate = True
               
    if not hasPossibleDate:
        print "no possible date found."
    else:
        print "."

def showTables():          
    print "Days   TBL:  ", BDAYSD
    print "Months TBL:  ", BDAYSM


def step(stepNbr, status = False):
    print ">>> Step {}".format(stepNbr)
    if not status:
        if not removeObvious():
            print "No more obvious changes."
    else:
        if not removeObvious(status):
            print "done"
    #showTables()
    showPossibleDates()

step("1")
print "=========\nForce removal of month: 5 (May)\n=========="
removeMonth(5)
print "=========\nStart KNOWING phase \n=========="
step("2a", True)
step("3a", True)

http://pythonfiddle.com/birthday/