# basic_valid_sudoku_gen.py ZZZ

# basic_valid_sudoku_gen.py -- ZZZ *generator 2 replacement now avails!

import random
import time

Lv1 = 36
Lv2 = 32
Lv3 = 29
Lv4 = 27

hints = 81-Lv4
def progress(z):
    sec=time.time()+1
    '''while sec-time.time() > 0:
        pass'''
    for i in range(9):
        print
        for ii in range(9):
            print z[i*9+ii],
    print
    print
def twodee(z):
    return [[z[ii*9+i] for i in range(9)] for ii in range(9)]
def shfl(z):
    z=zip(*z)
    z=[list(i) for i in z]
    z=list([z[i*3:i*3+3] for i in range(3)])
    #'''
    for i in range(3):
        random.shuffle(z[i])
    random.shuffle(z)
    #'''
    return sum(sum(z,[]),[])
def rcb(b,x,c):
    i,j=divmod(c, 9)
    ii, jj=i-i%3, j-j%3
    b=twodee(b)
    row = b[i]
    col = [r[j] for r in b]
    block = sum([r[jj:jj+3] for r in b[ii:ii+3]],[])
    if str(x) in row + col + block:
        return True
    return False
def rndplot(blank,mask):
    for z in blank:
        if mask.count('.') is hints: break
        mask=plot(z,mask)
    return mask
def plot(z,mask):
    new=mask[:]
    new[z]='.'
    rec=[new[:]]*81

    sq=[i for i in range(81) if mask[i] is '.'][::-1]
    c=0
    chk=0
    while c > -1:
        i=sq[c]
        bbb=rec[i][:]
        if bbb[i] is '.': number=1
        else: number=int(bbb[i])+1
        while number < 10:
            if not rcb(bbb,number,i):
                bbb[i]=str(number)
                rec[i]=bbb[:]
                for r in range(1,10):
                    if len(set(bbb[r*9:r*9+9])) is 1:
                        print "???"
                        return mask
                if c+1 is len(sq):
                    number=99
                    chk+=1
                    if chk > 1:
                        return mask
                break
            number+=1
        if number != 99:
            if number < 10:
                c+=1
                try: rec[sq[c]]=bbb[:]
                except: pass
            else:
                c-=1
    return new
def init():
    a='abcdefghxfexghcdabhdgxabefcbxaedgfchghdcfabxeecfhbxagdcfbaxehdgdgefchxbaxahbgdcef'
    #
    numbers=range(1,10)
    #random.shuffle(numbers)
    for i in range(9):
        a=a.replace(a[i],str(numbers[i]))
    solution=shfl(twodee(a))
    progress(solution)
    mask=solution[:]
    mask[:9]=['.']*9
    for i in range(9,9*9,9): mask[i]='.'
    c=str(numbers[0])
    mask=''.join(mask)
    mask=mask.replace(c,'.')
    mask=list(mask)
    blank=[i for i in range(81) if mask[i] is not '.'][::-1]
    random.shuffle(blank)
    mask=rndplot(blank,mask)
    progress(mask)
    print 81-hints, 'hints'
#
init()