flag=False
def showBox(al,x,y,change):
if not flag: return
print('====showBox',x,y,change)
for ix in range(3*x,3*x+3):
for jx in range(3*y,3*y+3):
print(al[ix][jx],end=' ')
print()
def showRow(al,x,row,change):
if not flag: return
print('====showRow',x,row,change)
for ix in range(row[0],row[1]):
print(al[x][ix],end=' ')
print()
def showCol(al,y,col,change):
if not flag: return
print('====showCol',y,col,change)
for ix in range(col[0],col[1]):
print(al[ix][y],end=' ')
print()
def debug(al,change,q,loc):
if not flag: return
print(change,q[1][-1])
res=input(loc)
while res!='':
act=input('what to do: ')
if act[0]=='b':
x,y=int(act[1]),int(act[2])
showBox(al,x,y,change)
elif act[0]=='r':
x,r1,r2=int(act[1]),int(act[2]),int(act[3])
showRow(al,x,(r1,r2),change)
elif act[0]=='c':
y,c1,c2=int(act[1]),int(act[2]),int(act[3])
showCol(al,y,(c1,c2),change)
res=input('again')
def isempty1(x,y):
xx,yy=x//3+1,y//3+1
return xx//3!=1 and yy==4 or xx==4 and yy//3!=1
def isempty2(x,y):
xx,yy=x+1,y+1
return xx//3!=1 and yy==4 or xx==4 and yy//3!=1
def arrowWorkRow(al,p,row,col,delta,q,change):
x,y=p
bl=[10*[0],10*[0],10*[0]]
cl=[[],[],[]]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
for k in al[i][j]:
bl[i-3*x][k]+=1
for i in range(3):
for j in range(1,10):
if bl[i][j]>0 and bl[(i+1)%3][j]==0 and bl[(i+2)%3][j]==0:
cl[i].append(j)
dl=list(range(row,3*y))+list(range(3*y+3,row+9+delta))
for i in range(3):
for k in cl[i]:
for j in dl:
cell=al[x*3+i][j]
if k in cell:
if len(cell)==1: return False
else:
cell.remove(k)
if len(cell)==1:
q[1].append((cell,x*3+i,j))
debug(al,change,q,'arrowRow')
change[0]+=1
result=True
for iy in range(row//3,(row+9+delta)//3):
if iy==y: continue
result=result and findOneBox(al,x,iy,q,change)
return result
def arrowWorkCol(al,p,row,col,delta,q,change):
x,y=p
bl=[10*[0],10*[0],10*[0]]
cl=[[],[],[]]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
for k in al[i][j]:
bl[j-3*y][k]+=1
for i in range(3):
for j in range(1,10):
if bl[i][j]>0 and bl[(i+1)%3][j]==0 and bl[(i+2)%3][j]==0:
cl[i].append(j)
dl=list(range(col,3*x))+list(range(3*x+3,col+9+delta))
for i in range(3):
for k in cl[i]:
for j in dl:
cell=al[j][y*3+i]
if k in cell:
if len(cell)==1: return False
else:
cell.remove(k)
if len(cell)==1:
q[1].append((cell,j,y*3+i))
debug(al,change,q,'arrowCol '+str(k)+str(p))
change[0]+=1
result=True
for ix in range(col//3,(col+9+delta)//3):
if ix==x: continue
result=result and findOneBox(al,ix,y,q,change)
return result
def delArrow(al,p,row,col,delta,q,change):
result1=arrowWorkRow(al,p,row,col,delta,q,change)
result2=arrowWorkCol(al,p,row,col,delta,q,change)
return result1 and result2
def delTwoBox(al,x,y,q,change):
if (x,y) in [(2,2),(2,4),(4,2),(4,4)]:
return delArrow(al,(x,y),(y//3)*6,(x//3)*6,6,q,change)
elif x==3 or y==3:
return delArrow(al,(x,y),6,6,0,q,change)
else:
return delArrow(al,(x,y),(y//4)*12,(x//4)*12,0,q,change)
def delPairX(al,rl,q,change,msg,loc):
if rl[0][0]!=rl[1][0]: return False
if len(al[rl[0][1]][rl[0][2]])==2 and len(al[rl[1][1]][rl[1][2]])==2: return False
al[rl[0][1]][rl[0][2]]=rl[0][0][:]
al[rl[1][1]][rl[1][2]]=rl[0][0][:]
q[2].append(rl)
change[0]+=1
if flag: print(msg,rl,loc)
return True
def isPairX(al,rl):
if len(rl[0][0])==2 and rl[0][0]==rl[1][0]: return True
return False
def delPairBox(al,x,y,hp,q,change):
if flag: print('delPairBox',x,y,hp)
showBox(al,x,y,change)
e1,e2=hp[0][0][0]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
if i==hp[0][0][1] and j==hp[0][0][2]: continue
if i==hp[0][1][1] and j==hp[0][1][2]: continue
cell=al[i][j]
if e1 in cell:
if len(cell)==1: return False
else:
cell.remove(e1)
if len(cell)==1:
q[1].append((cell,i,j))
debug(al,change,q,'delPairBox '+str(hp))
change[0]+=1
if e2 in cell:
if len(cell)==1: return False
else:
cell.remove(e2)
if len(cell)==1:
q[1].append((cell,i,j))
debug(al,change,q,'delPairBox '+str(hp))
change[0]+=1
#if flag: showBox(al,x,y,change)
return True
def delPairRow(al,x,row,hp,q,change):
#if flag: print('delPairRow',x,row,hp)
e1,e2=hp[0][0][0]
for i in range(row[0],row[1]):
if i in [hp[0][0][2],hp[0][1][2]]: continue
cell=al[x][i]
if e1 in cell:
if len(cell)==1: return False
else:
cell.remove(e1)
if len(cell)==1:
q[1].append((cell,x,i))
debug(al,change,q,'delPairRow '+str(hp))
change[0]+=1
if e2 in cell:
if len(cell)==1: return False
else:
cell.remove(e2)
if len(cell)==1:
q[1].append((cell,x,i))
debug(al,change,q,'delPairRow '+str(hp))
change[0]+=1
#if flag: showRow(al,x,row,change)
return True
def delPairCol(al,y,col,hp,q,change):
#if flag: print('delPairCol',y,col,hp)
e1,e2=hp[0][0][0]
for i in range(col[0],col[1]):
if i in [hp[0][0][1],hp[0][1][1]]: continue
cell=al[i][y]
if e1 in cell:
if len(cell)==1: return False
else:
cell.remove(e1)
if len(cell)==1:
q[1].append((cell,i,y))
debug(al,change,q,'delPairCol '+str(hp))
change[0]+=1
if e2 in cell:
if len(cell)==1: return False
else:
cell.remove(e2)
if len(cell)==1:
q[1].append((cell,i,y))
debug(al,change,q,'delPairCol '+str(hp))
change[0]+=1
#if flag: showCol(al,y,col,change)
return True
def findNakedPairBox1(al,x,y,q,change):
rl=[]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
rl.append((al[i][j][:],i,j))
nakedPair=[]
n=len(rl)
for i in range(n-1):
for j in range(i+1,n):
if isPairX(al,(rl[i],rl[j])):
if not (rl[i],rl[j]) in nakedPair: nakedPair.append((rl[i],rl[j]))
return nakedPair
def findNakedPairBox(al,x,y,q,change):
nakedPair=findNakedPairBox1(al,x,y,q,change)
for pair in nakedPair:
if not pair in q[2]: q[2].append(pair)
if nakedPair: return delPairBox(al,x,y,nakedPair,q,change)
return True
def findNakedPairRow1(al,x,row,q,change):
rl=[]
for i in range(row[0],row[1]):
rl.append((al[x][i][:],x,i))
nakedPair=[]
n=len(rl)
for i in range(n-1):
for j in range(i+1,n):
if isPairX(al,(rl[i],rl[j])):
if not (rl[i],rl[j]) in nakedPair: nakedPair.append((rl[i],rl[j]))
return nakedPair
def findNakedPairRow(al,x,row,q,change):
nakedPair=findNakedPairRow1(al,x,row,q,change)
for pair in nakedPair:
if not pair in q[2]: q[2].append(pair)
if nakedPair: return delPairRow(al,x,row,nakedPair,q,change)
return True
def findNakedPairCol1(al,y,col,q,change):
rl=[]
for i in range(col[0],col[1]):
rl.append((al[i][y][:],i,y))
nakedPair=[]
n=len(rl)
for i in range(n-1):
for j in range(i+1,n):
if isPairX(al,(rl[i],rl[j])):
if not (rl[i],rl[j]) in nakedPair: nakedPair.append((rl[i],rl[j]))
return nakedPair
def findNakedPairCol(al,y,col,q,change):
nakedPair=findNakedPairCol1(al,y,col,q,change)
for pair in nakedPair:
if not pair in q[2]: q[2].append(pair)
if nakedPair: return delPairCol(al,y,col,nakedPair,q,change)
return True
def findHiddenPairBox(al,x,y,q,change):
bl=10*[0]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
for k in al[i][j]:
bl[k]+=1
sl=[]
hiddenPair=[]
for k in range(1,10):
if bl[k]==2:
sl.append(k)
if len(sl)<2: return True
rl=[]
n=len(sl)
for ix in range(n-1):
for jx in range(ix+1,n):
p1,p2=sl[ix],sl[jx]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
cell=al[i][j]
if p1 in cell and p2 in cell:
rl.append(([p1,p2],i,j))
if len(rl)<2: return True
n=len(rl)
for i in range(n-1):
for j in range(i+1,n):
newFound=delPairX(al,(rl[i],rl[j]),q,change,'BOX',(x,y))
if newFound:
if not (rl[i],rl[j]) in hiddenPair: hiddenPair.append((rl[i],rl[j]))
if hiddenPair: return delPairBox(al,x,y,hiddenPair,q,change)
return True
def findHiddenPairRow(al,x,row,q,change):
bl=10*[0]
for i in range(row[0],row[1]):
for k in al[x][i]:
bl[k]+=1
sl=[]
hiddenPair=[]
for k in range(1,10):
if bl[k]==2:
sl.append(k)
if len(sl)<2: return True
rl=[]
n=len(sl)
for ix in range(n-1):
for jx in range(ix+1,n):
p1,p2=sl[ix],sl[jx]
for i in range(row[0],row[1]):
cell=al[x][i]
if p1 in cell and p2 in cell:
rl.append(([p1,p2],x,i))
if len(rl)<2: return True
n=len(rl)
for i in range(n-1):
for j in range(i+1,n):
newFound=delPairX(al,[rl[i],rl[j]],q,change,'ROW',row)
if newFound:
if not (rl[i],rl[j]) in hiddenPair: hiddenPair.append((rl[i],rl[j]))
if hiddenPair: return delPairRow(al,x,row,hiddenPair,q,change)
return True
def findHiddenPairCol(al,y,col,q,change):
bl=10*[0]
for i in range(col[0],col[1]):
for k in al[i][y]:
bl[k]+=1
sl=[]
hiddenPair=[]
for k in range(1,10):
if bl[k]==2:
sl.append(k)
if len(sl)<2: return True
rl=[]
n=len(sl)
for ix in range(n-1):
for jx in range(ix+1,n):
p1,p2=sl[ix],sl[jx]
for i in range(col[0],col[1]):
cell=al[i][y]
if p1 in cell and p2 in cell:
rl.append(([p1,p2],i,y))
n=len(rl)
for i in range(n-1):
for j in range(i+1,n):
newFound=delPairX(al,[rl[i],rl[j]],q,change,'COL',(col[0],y))
if newFound:
if not (rl[i],rl[j]) in hiddenPair: hiddenPair.append((rl[i],rl[j]))
if hiddenPair: return delPairCol(al,y,col,hiddenPair,q,change)
return True
def findOneBox(al,x,y,q,change):
bl=10*[0]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
for k in al[i][j]:
bl[k]+=1
for k in range(1,10):
if bl[k]==1:
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
if k in al[i][j] and len(al[i][j])>1:
al[i][j]=[k]
q[1].append(([k],i,j))
debug(al,change,q,'oneBox')
change[0]+=1
return True
def findOneRow(al,x,row,q,change):
bl=10*[0]
for i in range(row[0],row[1]):
for k in al[x][i]:
bl[k]+=1
for k in range(1,10):
if bl[k]==1:
for i in range(row[0],row[1]):
if k in al[x][i] and len(al[x][i])>1:
showRow(al,x,row,change)
al[x][i]=[k]
q[1].append(([k],x,i))
debug(al,change,q,'oneRow')
change[0]+=1
return True
def findOneCol(al,y,col,q,change):
bl=10*[0]
for i in range(col[0],col[1]):
for k in al[i][y]:
bl[k]+=1
for k in range(1,10):
if bl[k]==1:
for i in range(col[0],col[1]):
if k in al[i][y] and len(al[i][y])>1:
al[i][y]=[k]
q[1].append(([k],i,y))
debug(al,change,q,'oneCol')
change[0]+=1
return True
def doRowWork(al,x,row,q,change):
result1=findOneRow(al,x,row,q,change)
result2=findNakedPairRow(al,x,row,q,change)
result3=findHiddenPairRow(al,x,row,q,change)
return result1 and result2 and result3
def doColWork(al,y,col,q,change):
result1=findOneCol(al,y,col,q,change)
result2=findNakedPairCol(al,y,col,q,change)
result3=findHiddenPairCol(al,y,col,q,change)
return result1 and result2 and result3
def delOneBox(al,x,y,k,q,change):
xx,yy=x//3*3,y//3*3
tl=[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)]
tl.remove((x%3,y%3))
for i,j in tl:
cell=al[xx+i][yy+j]
if k in cell:
if len(cell)==1: return False
else:
cell.remove(k)
if len(cell)==1:
q[1].append((cell,xx+i,yy+j))
debug(al,change,q,'pinned in Box by '+str([k])+str((x,y)))
change[0]+=1
return True
def findPairBox(al,q,change):
result=True
for x in range(7):
for y in range(7):
if not isempty2(x,y):
result=result and delTwoBox(al,x,y,q,change)
result=result and findOneBox(al,x,y,q,change)
result=result and findHiddenPairBox(al,x,y,q,change)
result=result and findNakedPairBox(al,x,y,q,change)
return result
def findPairLong(al,q,change):
result=True
for i in range(0,9):
result=result and doRowWork(al,i,(0,9),q,change)
result=result and doRowWork(al,i,(12,21),q,change)
result=result and doColWork(al,i,(0,9),q,change)
result=result and doColWork(al,i,(12,21),q,change)
for i in range(6,15):
result=result and doRowWork(al,i,(6,15),q,change)
result=result and doColWork(al,i,(6,15),q,change)
for i in range(12,21):
result=result and doRowWork(al,i,(0,9),q,change)
result=result and doRowWork(al,i,(12,21),q,change)
result=result and doColWork(al,i,(0,9),q,change)
result=result and doColWork(al,i,(12,21),q,change)
return result
def doFinalTouch(al,pair,pl,q,change):
n=len(pl)
#print(change,pair,pl)
for ix in range(n):
n1,n2=pl[ix]
cl=[ix]
for jx in range(n):
if ix==jx: continue
n3,n4=pl[jx]
if n1==n3 or n1==n4 or n2==n3 or n2==n4:
cl.append(jx)
if len(cl)==3: break
if len(cl)!=3: return True
x,y,z=cl
n1,n2=pl[x]
if n1[0]==n2[0] or n1[1]==n2[1]: return True
val=0
n3,n4=pl[y]
if n3[0]==n4[0]: val+=1 #horizontal
else: val+=2 #vertical
n5,n6=pl[z]
if n5[0]==n6[0]: val+=1 #horizontal
else: val+=2 #vertical
if val!=3: return True
if n1==n3 or n2==n3: na=n4
else: na=n3
if n1==n5 or n2==n5: nb=n6
else: nb=n5
#print('n=',n,'na=',na,'nb=',nb)
i1,j1=na[0],nb[1]
i2,j2=nb[0],na[1]
cell=al[i1][j1]
if len(cell)>1:
for el in pair:
if el in cell and len(cell)>1: cell.remove(el)
if len(cell)==1:
q[1].append((cell,i1,j1))
debug(al,change,q,'chained three pairs')
cell=al[i2][j2]
if len(cell)>1:
for el in pair:
if el in cell and len(cell)>1: cell.remove(el)
if len(cell)==1:
q[1].append((cell,i2,j2))
debug(al,change,q,'chained three pairs')
return True
def doPairChain(al,q,change):
pl=q[2][:]
q[2]=[]
chain={}
cl=[]
for one,two in pl:
if len(al[one[1]][one[2]])==1: continue
key=one[0][0]*10+one[0][1]
if not key in chain:
chain[key]=[((one[1],one[2]),(two[1],two[2]))]
else:
if not ((one[1],one[2]),(two[1],two[2])) in chain[key]:
chain[key].append(((one[1],one[2]),(two[1],two[2])))
for key,val in chain.items():
if len(val)>1: cl.append(([key//10,key%10],val))
result=True
for pair,pl in cl:
result=doFinalTouch(al,pair,pl,q,change)
return result
def solveOne(al,q,change):
saved=change[:]
result=True
while q[1] or q[2]:
if q[1]:
k,x,y=q[1].pop(0)
result=result and delOneBox(al,x,y,k[0],q,change)
result=result and delTwoBox(al,x//3,y//3,q,change)
elif q[2]:
result=result and doPairChain(al,q,change)
result=result and findPairLong(al,q,change)
result=result and findPairBox(al,q,change)
return result,q[1] or q[2] or saved!=change
def addOneQ(al,q):
for i in range(21):
x=i//3
for j in range(21):
y=j//3
if isempty2(x,y): continue
cell=al[i][j]
if len(cell)==1:
q[1].append((cell,i,j))
def fullCopy(al):
bl=[]
for r in al:
cl=[]
for el in r:
cl.append(el[:])
bl.append(cl)
return bl
def findTwo(al,x,y):
bl=10*[0]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
for k in al[i][j]:
bl[k]+=1
rl=[]
for k in range(1,10):
if bl[k]==2:
cl=[]
for i in range(3*x,3*x+3):
for j in range(3*y,3*y+3):
if k in al[i][j]:
cl.append((i,j))
rl.append((k,cl))
return rl
def findNextCase(al,runStack,q,change):
tryQ=[]
for x in range(7):
for y in range(7):
if isempty2(x,y): continue
rl=findTwo(al,x,y)
if len(rl)>0:
if (x,y) in [(2,2),(2,4),(4,2),(4,4)]:
tryQ.insert(0,rl[0])
tryQ.append(rl[0])
rl=tryQ.pop(0)
pos1,pos2=rl[1][0],rl[1][1]
bl=fullCopy(al)
qb=[[],q[1][:],q[2][:]]
al[pos1[0]][pos1[1]]=[rl[0]]
q[1].append(([rl[0]],pos1[0],pos1[1]))
bl[pos2[0]][pos2[1]]=[rl[0]]
qb[1].append(([rl[0]],pos2[0],pos2[1]))
runStack.append(qb)
runStack.append(bl)
change[0]+=1
print('save one canditate', qb[1][-1])
def allDone(al):
for row in al:
for el in row:
if len(el)>1: return False
return True
def solveAll(al,q):
runStack=[]
change=[0]
saved=[0]
result=True
while True:
good,progress=solveOne(al,q,change)
if allDone(al): return al,change
if not good:
if not runStack:
input('@@ THIS PUZZLE CANNOT BE SOLVED @@')
break
al=runStack.pop()
q=runStack.pop()
print('resotre one candidate',q[1][-1])
continue
if not progress:
findNextCase(al,runStack,q,change)
return al,change
def getSudoku():
name=input('file: ')
f=open(name,'r')
al=f.readlines()
f.close()
bl=[]
for x in al:
cl=[]
if x[-1]=='\n': x=x[:-1]
for y in list(x):
cl.append(int(y))
bl.append(cl)
al=[]
for x in range(21):
cl=[]
for y in range(21):
if isempty1(x,y):
cl.append([])
else:
if bl[x][y]==0: cl.append([1,2,3,4,5,6,7,8,9])
else: cl.append([bl[x][y]])
al.append(cl)
return al
def showSS(al):
for x in range(21):
for y in range(21):
if isempty1(x,y):
print(' ',end='')
else:
if len(al[x][y])>1: print(end=' .')
else: print('%3d' % al[x][y][0],end='')
if (y+1)%3==0: print(end=' ')
print()
if (x+1)%3==0: print()
al=getSudoku()
response=input('do you want detailed message? ')
flag=response=='yes'
showSS(al)
q=[[],[],[]]
addOneQ(al,q)
al,change=solveAll(al,q)
print()
print('--------------------------------',change,'-------------------------------')
showSS(al)
[sdk01.txt 파일]
000001600000008400000
007930050000020036900
060050007000600070080
010007006000900100050
042000780000083000610
900800010000010003004
500020070000050040007
030048200000004250030
001300000050000008400
000000000608000000000
000000003000400000000
000000000401000000000
005100000010000004900
070059100000005670030
900060050000020030007
800300010000050003002
039000570000037000650
020005003000100400090
040030001000200080010
002780090000010049200
000006200000008100000
[sdk02.txt 파일]
052000170000029000460
800504006000500602003
600000008000400000008
030050090000030020040
000208000000000106000
040010050000060050020
700000002000600000005
300701005000900405002
061000730090052000630
000000000306000000000
000000007010200000000
000000000405000000000
092000170080096000310
700103009000400309006
600000008000300000008
070090050000010030040
000302000000000504000
010080030000050020030
900000005000900000002
100507004000100208009
043000620000082000560
[s03.txt]
090000080000060000020
406302905000902403605
030060040000040070080
050000090000080000050
009040700000009010700
010000030000020000090
060050070000090050040
503106408709501702809
040000060030070000010
000000050000010000000
000000001080900000000
000000040000020000000
090000080070040000060
604801207104603904201
080060010000050010080
060000070000070000010
003020900000004090700
040000050000060000090
020010060000010080040
809206401000405601809
030000020000090000030
[s04.txt]
050000000000002000038
036870002000073900000
000409008000000107000
902010060000000040001
000096000000000090300
000507000000000070500
260000000000000000050
003040000000200006004
004000000030000000020
000000900084000000000
000000000000468000000
000000060007010000000
300000000000000200000
040000000040000070300
009100200000003009002
600800000000000000079
000004100000208040003
090007000000097380040
402080000000004020080
000035027000000801000
703040000000300000500
[s05.txt]
600020000000000003000
040000000000000009307
008031007000705000000
123000000000801000000
070000083000940305000
000007000000000040702
001006000000000000209
000010070080000800060
000708000000000502000
000000080000010000000
000000023900000000000
000000900035000000000
000000000000002300000
063000000000090008300
000120000000000000800
000008370000500000600
009000000000000093100
500067000000000560030
006901040000020050001
400000005000010900004
020030080000000001020
'자바·파이썬·자바스크립트 > 파이썬 프로그래밍' 카테고리의 다른 글
| kivy 시작하기 (파이썬으로 앱만들기) (0) | 2015.11.15 |
|---|---|
| knight-move (0) | 2015.07.02 |
| get_next (next_permutation) (0) | 2014.07.22 |
| 점프 투 파이썬 사이트 소개 (0) | 2013.10.17 |
| 확장된 애너그램 사전만들기 (0) | 2013.07.24 |