数独の超難問を解くpythonのプログラム

簡易なものを作成したもののここから先をどう作ったらいいのかアイデアが浮かばなかったのですが、

3箇所ぐらい設定可能な数値を全パターン入れてから簡易計算をかければ解けるのではと作成開始です。

 

 

データ作成ツール

 

リスト１

boxに数独のデータを設定

clearCheck　盤面の判定をする。クリア、未定、エラーを返す

putPoint　盤面のx,yの位置に置ける数字を判断する。確定したら置く、未定の時は置ける可能性のある数字を返す

 

 

リスト２

boardError 縦横と太枠のボックスの数値に同じものがあればTrue(エラーあり)を返す

recAttack 可能性のある数字を順次検索していく再帰関数（最大15回実施）

 

 

リスト３　

簡単な判別でクリアできればそれで終了

クリアできなければ再帰で解くロジックを呼び出す

最後に結果表示

 

リスト１のネットで探した難問（数学者が作成した問題）を解いてます。

最初130秒ぐらいかかっていたのですが無駄な検索を減らしていって12秒まで到達しました。

 

 

 

最初のアイデアだけで少しづつ増やしてみましたが実際作ってみると8つ選択しても解ける兆しが見えず。（バグはあるかも）

さらにそれをランダムパターンで100回繰り返して解こうとした時のロジックのかけらです。

考えが浮かばかければ超難問は今回もお蔵入りになるところでした。

 

 

 

#データ作成用ツール

d ="     7   "
d+="2 3   8 5"
d+="    8 7 3"
d+=" 9   2 7 "
d+="  184 6  "
d+=" 6   9 5 "
d+="    9 4 6"
d+="8 7   9 1"
d+="     4   "

box=[]
for y in range(9):
  line=[]
  for x in range(9):
    line+=[d[y*9+x]]
  box+=[line]
print(box)

 

 

#数独解答プログラム

import copy,time,random,sys
#初級
#box=[['7', ' ', '1', ' ', ' ', ' ', '6', ' ', '8'], [' ', ' ', ' ', '2', '1', ' ', '7', ' ', ' '], ['3', '9', ' ', ' ', ' ', '8', ' ', ' ', '4'], [' ', ' ', '3', ' ', '8', ' ', ' ', '1', ' '], [' ', '6', ' ', '9', ' ', '1', ' ', '4', ' '], [' ', '1', ' ', ' ', '4', ' ', '8', ' ', ' '], ['9', ' ', ' ', '6', ' ', ' ', ' ', '8', '1'], [' ', ' ', '6', ' ', '3', '9', ' ', ' ', ' '], ['1', ' ', '2', ' ', ' ', ' ', '9', ' ', '3']]
#中級
#box=[[' ', ' ', ' ', '1', ' ', ' ', ' ', '4', ' '], [' ', ' ', ' ', '7', '3', ' ', ' ', '2', ' '], [' ', ' ', '7', ' ', ' ', '5', '6', ' ', ' '], ['4', ' ', ' ', ' ', ' ', '6', ' ', ' ', '9'], [' ', ' ', '6', ' ', '1', ' ', '7', ' ', ' '], ['5', ' ', ' ', '9', ' ', ' ', ' ', ' ', '1'], [' ', ' ', '9', '3', ' ', ' ', '8', ' ', ' '], [' ', '2', ' ', ' ', '8', '7', ' ', ' ', ' '], [' ', '4', ' ', ' ', ' ', '9', ' ', ' ', ' ']]
#box=[[' ', ' ', '9', ' ', ' ', ' ', '3', ' ', ' '], ['8', ' ', ' ', '5', '3', '9', ' ', ' ', '7'], ['6', ' ', ' ', ' ', '1', ' ', ' ', ' ', '9'], [' ', ' ', ' ', '3', '9', '8', ' ', ' ', ' '], [' ', '8', ' ', '4', ' ', '2', ' ', '1', ' '], [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '], ['4', '2', ' ', ' ', ' ', ' ', ' ', '3', '1'], [' ', '5', ' ', ' ', '2', ' ', ' ', '8', ' '], [' ', ' ', ' ', '6', ' ', '5', ' ', ' ', ' ']]
#上級
#box=[[' ', ' ', ' ', ' ', ' ', '7', ' ', ' ', ' '], ['2', ' ', '3', ' ', ' ', ' ', '8', ' ', '5'], [' ', ' ', ' ', ' ', '8', ' ', '7', ' ', '3'], [' ', '9', ' ', ' ', ' ', '2', ' ', '7', ' '], [' ', ' ', '1', '8', '4', ' ', '6', ' ', ' '], [' ', '6', ' ', ' ', ' ', '9', ' ', '5', ' '], [' ', ' ', ' ', ' ', '9', ' ', '4', ' ', '6'], ['8', ' ', '7', ' ', ' ', ' ', '9', ' ', '1'], [' ', ' ', ' ', ' ', ' ', '4', ' ', ' ', ' ']]
#超難問
#box=[[' ', ' ', '3', ' ', '5', '4', ' ', ' ', ' '], [' ', '1', ' ', '8', ' ', '9', ' ', '3', ' '], [' ', ' ', '2', ' ', '1', ' ', '4', ' ', '5'], ['4', '9', ' ', ' ', ' ', ' ', ' ', '8', ' '], ['7', ' ', '1', ' ', '3', ' ', '5', ' ', '4'], [' ', '2', ' ', ' ', ' ', ' ', ' ', '6', '9'], ['1', ' ', '9', ' ', '4', ' ', '8', ' ', ' '], [' ', '5', ' ', '7', ' ', '3', ' ', '4', ' '], [' ', ' ', ' ', '1', '8', ' ', '9', ' ', ' ']]
#box=[[' ', '9', ' ', ' ', ' ', ' ', ' ', '1', ' '], ['4', ' ', ' ', '2', ' ', '9', ' ', ' ', '3'], [' ', '3', ' ', ' ', '6', ' ', ' ', '8', ' '], [' ', ' ', ' ', '9', ' ', '6', ' ', ' ', ' '], ['8', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '7'], ['6', '4', ' ', ' ', '8', ' ', ' ', '3', '1'], [' ', '6', ' ', '1', ' ', '5', ' ', '2', ' '], ['3', ' ', '1', ' ', ' ', ' ', '7', ' ', '5'], [' ', ' ', ' ', '3', ' ', '4', ' ', ' ', ' ']]
#ネットで探した難問
box=[[' ', ' ', '5', '3', ' ', ' ', ' ', ' ', ' '], ['8', ' ', ' ', ' ', ' ', ' ', ' ', '2', ' '], [' ', '7', ' ', ' ', '1', ' ', '5', ' ', ' '], ['4', ' ', ' ', ' ', ' ', '5', '3', ' ', ' '], [' ', '1', ' ', ' ', '7', ' ', ' ', ' ', '6'], [' ', ' ', '3', '2', ' ', ' ', ' ', '8', ' '], [' ', '6', ' ', '5', ' ', ' ', ' ', ' ', '9'], [' ', ' ', '4', ' ', ' ', ' ', ' ', '3', ' '], [' ', ' ', ' ', ' ', ' ', '9', '7', ' ', ' ']]
def clearCheck(bo):
  ck=1 # 1 ok 0 notyet -1 error
  a=[]
  for x in range(3):
    for y in range(3):
      a+=["".join(sorted([bo[y//3*3+ly][x//3*3+lx] for lx in range(3) for ly in range(3)]))]
  for x in range(9):a+=["".join(sorted([bo[y][x] for y in range(9)]))]
  for y in range(9):a+=["".join(sorted(bo[y]))]
  for i in a:
    if i=="123456789":pass
    elif i[0]!=" ":return -1
    else:ck=0
  return ck
def putPoint(bo,x,y):
  global cTurn,ppErr
  a=set([bo[y][x] for y in range(9)]+bo[y]+[bo[y//3*3+ly][x//3*3+lx] for lx in range(3) for ly in range(3)])
  b=[i for i in "123456789" if not(i in a)]
  if b==[]:ppErr=1
  if len(b)==1:
    bo[y][x]=b[0]
    cTurn+=1
  return (len(b),x,y,b)

def boardError(bo):
  for y in range(9):
    for i in "123456789":
      if bo[y].count(i)>1:return True
  for x in range(9):
    a=[bo[y][x] for y in range(9)]
    for i in "123456789":
      if a.count(i)>1:return True    
  for x in range(3):
    for y in range(3):
      a=[bo[y*3+ly][x*3+lx] for lx in range(3) for ly in range(3)]
      for i in "123456789":
        if a.count(i)>1:return True
  return False  

def recAttack(bo,rn):
  global box,last,ppErr
  if rn==15:return
  ppErr=0
  _,px1,py1,loop1=last[rn]
  for p1 in loop1:
    wk=copy.deepcopy(bo)
    wk[py1][px1]=p1
    if boardError(wk):continue
    for i in range(10):
      cTurn=0
      ppErr=0
      [putPoint(wk,x,y) for y in range(9) for x in range(9) if wk[y][x]==" "]
      if ppErr==1:break
      if cTurn==0:break
    cc=clearCheck(wk)
    if cc==1:
      box=copy.deepcopy(wk)
      return  
    if ppErr==0:recAttack(wk,rn+1)
  return

t1=time.time()
[putPoint(box,x,y) for i in range(10) for y in range(9) for x in range(9) if box[y][x]==" "]
last=[putPoint(box,x,y) for y in range(9) for x in range(9) if box[y][x]==" "]
cTurn=0
ppErr=0
if last!=[]:
  last.sort()
  last=last[::-1]
  recAttack(box,0)

for y in range(9):print(box[y])
print(time.time()-t1)