42 SILICON VALLEY Piscine 2017 Rush01 - sudoku2

sudoku2.py

# coding: utf-8
# Your code here!

def make_puzzle(args):
    puzzle = []
    row = []
    i = 0
    
    for c in args:
        row.append(c)
        
        if (i + 1) % 9 == 0:
            puzzle.append(row)
            row = []
        
        i += 1
    
    return puzzle

def make_workbd():
    digits = '123456789'
    workbd = []
    row = []
    c = 0
    r = 0
    
    while r < 9:
        while c < 9:
            row.append(digits)

            if (c + 1) % 9 == 0:
                workbd.append(row)
                row = []
                c = 0
                r += 1
                break
            else:
                c += 1
    
    return workbd

def print_workbd(isGrid):
    r = 0
    c = 0
    buf = ''
    
    while r < 9:       
        while c < 9:
            buf += my_workbd[r][c]
            
            if isGrid == True and (c == 2 or c == 5):
                buf += '|'

            c += 1
            
        buf += '\n'

        if isGrid == True and (r == 2 or r == 5):
            buf += '---+---+---\n'

        c = 0
        r += 1
    
    print(buf)

def update_workbd(workbd, r, c, d, isOW):
    try_num = workbd[r][c]
    buf = ''
    
    for i in try_num:
        if i == d:
            continue
        
        buf += i
    
    if isOW == True:
        workbd[r][c] = buf
    
    return buf

def search_number(num, val):
    for i in val:
        if i == num:
            return True
        
    return False

def get_box_range(val):
    if 0 <= val and val <= 2:
        return 0
    elif 3 <= val and val <= 5:
        return 3
    elif 6 <= val and val <= 8:
        return 6

def get_pos(r, c, isPeer):
    pos = []
    row = []
    col = []
    box = []
    sr = get_box_range(r)
    sc = get_box_range(c)
    
    #row
    i = 0
    while i < 9:
        if isPeer == True and (i == sc or i == sc + 1 or i == sc + 2):
            i += 1
            continue
        
        pos.append(r)
        pos.append(i)
        row.append(pos)
        pos = []
        i += 1
    
    #column
    i = 0
    while i < 9:
        if isPeer == True and (i == sr or i == sr + 1 or i == sr + 2):
            i += 1
            continue
        
        pos.append(i)
        pos.append(c)
        col.append(pos)
        pos = []
        i += 1

    #box
    x = sc
    y = sr
    while y < sr + 3:
        while x < sc + 3:
            if isPeer == True and x == c and y == r:
                x += 1
                continue

            pos.append(y)
            pos.append(x)
            box.append(pos)
            pos = []
            x += 1

        x = sc
        y += 1

    return row + col + box

def check_peer(workbd, r, c, d):
    for peer_pos in get_pos(r, c, True):
        if eliminate(workbd, peer_pos[0], peer_pos[1], d) is None:
            return None
    
    return workbd

def check_unit(workbd, r, c, d):
    psbl_pos = []
    for unit_pos in get_pos(r, c, False):
        y = unit_pos[0]
        x = unit_pos[1]

        if search_number(d, workbd[y][x]) == True:
            psbl_pos.append(unit_pos)

    l = len(psbl_pos)
    if l == 0:
        return None
    elif l == 1:
        y = psbl_pos[0][0]
        x = psbl_pos[0][1]

        if assign(workbd, y, x, d) is None:
            return None

    return workbd
        
def eliminate(workbd, r, c, d):
    cell = workbd[r][c]
    
    if search_number(d, cell) == False:
        return workbd
    
    cell = update_workbd(workbd, r, c, d, True)
    
    l = len(cell)
    if l == 0:
        return None
    elif l == 1:
        if check_peer(workbd, r, c, cell) is None:
              return None

    if check_unit(workbd, r, c, d) == None:
        return None
    return workbd

def assign(workbd, r, c, d):
    psbl_num = update_workbd(workbd, r, c, d, False)
    
    for try_num in psbl_num:
        if eliminate(workbd, r, c, try_num) is None:
            return None
    
    return workbd

def isAll1(workbd):
    r = 0
    c = 0
    
    while r < 9:
        while c < 9:
            if len(workbd[r][c]) != 1:
                return False
            
            c += 1
        c = 0
        r += 1
    
    return True

def findMinPos(psbl_pos, psbl_min):
    real_min = psbl_min[0]
    real_pos = 0
    
    for i in range(len(psbl_min)):
        m = psbl_min[i]
        
        if real_min > m:
            real_min = m
            real_pos = i

    return psbl_pos[real_pos]
    
def getMinPos(workbd):
    r = 0
    c = 0
    psbl_min = 0
    psbl_pos = []
    ret_min = []
    ret_pos = []
    
    while r < 9:
        while c < 9:
            psbl_min = len(workbd[r][c])
            
            if psbl_min > 1:
                ret_min.append(psbl_min)
                psbl_pos.append(r)
                psbl_pos.append(c)
                ret_pos.append(psbl_pos)
                psbl_pos = []
            
            c += 1
        
        c = 0
        r += 1
    
    return findMinPos(ret_pos, ret_min)
               
def explore(workbd):
    import copy
    
    if workbd is None:
        return None

    if isAll1(workbd) == True:
        global my_workbd
        my_workbd = workbd
        return workbd

    min_pos = getMinPos(workbd)
    r = min_pos[0]
    c = min_pos[1]

    for try_num in workbd[r][c]:       
        wbd_copy = copy.deepcopy(workbd)
        
        if assign(wbd_copy, r, c, try_num) is None:
            continue
        
        explore(wbd_copy)        

#42SV Piscine 2017 sample
#args = "9...7...." "2...9..53" ".6..124.." "84...1.9." "5.....8.." ".31..4..." "..37..68." ".9..5.741" "47......."

#easy
#args = '..3.2.6..' '9..3.5..1' '..18.64..' '..81.29..' '7.......8' '..67.82..' '..26.95..' '8..2.3..9' '..5.1.3..'

#hard
args = '4.....8.5' '.3.......' '...7.....' '.2.....6.' '....8.4..' '....1....' '...6.3.7.' '5..2.....' '1.4......'

my_puzzle = make_puzzle(args)
my_workbd = make_workbd()

r = 0
c = 0
while r < 9:
    while c < 9:
        d = my_puzzle[r][c]
        if d != '.':
            assign(my_workbd, r, c, d)
        c += 1
    
    c = 0
    r += 1

explore(my_workbd)

print_workbd(True)
print_workbd(False)