数独求解器：减少+蛮力 [英] Sudoku solver: reduction + brute force

问题描述

受最近关于LinuxJournal和ASPN配方的一些读物的启发，我决定改进我的旧python hack ......新代码是一个组合

of（ 2）减少方法和蛮力，它比

ASPN程序快得多。如果有人有兴趣，我将代码附在
http://agolb.blogspot.com/2006/01/su...in-python.html

解决方案

前写道：

灵感来自最近关于LinuxJournal和ASPN配方的一些读物，我决定改进我的旧python hack ...新代码是一个组合< （2）减少方法和蛮力，它比ASPN程序快得多。如果有人有兴趣，我将代码附在
http://agolb.blogspot.com/2006/01/su...in-python.html

我建议尝试


输入="""

0,0,0,0,9,6,8,0,0

0,0,1,0,0,0,0,7,0

0,2,0,0,0,0,0,0,3

0,3,0,0,0,8,0,0,6

0,0,4,0,2,0,3,0,0

6,0,0,5,0,0,0,8,0

9,0,0,0,0,0,0,5,0

0,7,0,0,0,0,1,0,0

0,0,5,9,4,0,0,0,0"""你的程序似乎花了太长时间来解决它。


我认为困难的部分不是解决，而是创造*困难*

数独网格。

但是为了让我的自我超越已知的宇宙，这里是我的解算器

（这合理地解决了提到的网格快速）。我认为

唯一的区别是在开始树状搜索之前使用3而不是2规则简化

。


#########

＃如果需要复制品：

＃这是一个pulbic域，无论你想做什么都可以用它做什么

#ie最可能没有什么

#########

类DeadEnd（例外）：

传递

类数独（对象）：


def __init __（self，* args）：

self.changed = True

self.possible = []

if len（args）！= 81：

引发ValueError，需要81个数字

for i in args：

if i == 0：

self.possible.append（range（1,10））

否则：

self.possible.append（[i]）


def __getitem __（self，（x，y））：

返回self.possible [9 * x + y]


def __setitem __（self，（x，y），what）：

self.possible [9 * x + y] =什么


def copy（self）：

result = sudoku（*（81 * [1]） ）

for i in range（9）：

for j in range（9）：

result [i，j] = list（自我[i，j]）

返回结果


def solve（self）：

for i in range（9） ：

for j in range（9）：

if len（self [i，j]）！= 1：

返回False

返回True


def试验（个体经营）：

for i，j in（（i，j）for ln in范围（2,10）

for i in range（9）j in range（9）

if len（self [i，j]）== ln） ：

for self [i，j]：

new = self.copy（）

new [i，j] = [ k]

收益率新

def clean1（self，x，y）：

self.changed = False
if len（self [x，y]）== 1：

返回

remove = set（）

for self.regions（x，y）中的位置：

缺失=设置（范围（1,10））
$ x $ b表示xx，yy在某些地方：

如果xx == x和yy == y：

继续

如果len（self [xx，yy]）== 1：

remove.add（self [xx，yy] [0]）

missing- = set（self [xx，yy]）
如果缺少
：

a = missing.pop（）

self [x，y] = [a]

self.changed = True

for a remove：

试试：

self [x，y] .remove（a）

if not not self [x，y ]：

加注DeadEnd

self.changed = True
除了Valu之外的
错误：

通过


def clean3（self，out1，out2）：
（b1，o2）
（（ out1，out2），（out2，out1））：

remove = set（范围（1,10））

代表x，y代表o1：

remove- = set（self [x，y]）

for x，y in o2：

for n in remove：

尝试：

self [x，y] .remove（n）

如果不是自我[x，y]：

提高DeadEnd

self.changed = True

除了ValueError：

通过


@staticmethod
def region（x，y）：

return（（（xx，y）xx在范围内（9）），

（（x， yy）for yy in range（9）），

（（xx，yy）xx在范围内（3 *（x // 3），3 *（x // 3）+3）

for yy in range（3 *（y // 3），3 *（y // 3）+3）））

@staticmethod

def out（）：

for i in range（3）：

for j in range（3）：

for k在范围（3）中：

out1 = [（a + 3 * i，b + 3 * j）a范围内（3）

如果a不是k for b in range（3）]

out2 = [（k + 3 * i，n）n为范围（9），如果n // 3！= j]

收益率out1，out2

为范围内的k（3）：

out1 = [（a + 3 * i，b + 3 * j）范围内（3）
b b范围内的b b（b）如果b不是k则为b]

out2 = [（n，k + 3 * j）n范围内（9）如果n // 3！= i]

收益率out1，out2


def clean_all（个体经营）：

而self.changed：

self.changed = False

for x in range（9）：

for y in range（9）：

self.clean1（x，y）

for out1，out2 in self.outs（）：

self.clean3（out1，out2 ）


def __repr __（自我）：

result =""

for x in range（9）：

为y在范围内（9）：

如果len（self [x，y]）== 1：

haf = self [x ，y] [0]

其他：

haf = self [x，y]

结果+ = str（haf）+''' '

结果+ =''\ n''

返回结果



来自collection import deque


类升（物件）：


def __init __（self，* iterables）：

self.iters = de que（iter（x）for x in iterables）


def __iter __（self）：

而self.iters：

it = self.iters.popleft（）

试试：

result = it.next（）

除了StopIteration：

继续

self.iters.append（it）

收益率结果


def append（self，what）：

self.iters.append（iter（what））


def solve（me）：

tree =升（[我在你的树上给你
：

试试：

you.clean_all（）

除了DeadEnd：

继续

if youolved（）：

返回你

tree.append（you.trials（ ））


######

输入=（

0,0,0,0 ，9,6,8,0,0，

0,0,1,0,0,0,0,7,0，

0,2,0 ，0,0,0,0,0,3，

0,3,0,0,0,8,0,0,6，

0,0 ，4,0,2,0,3,0,0，

6,0,0,5,0,0,0,8,0，

9 ，0,0,0,0,0,0,5,0，

0,7,0,0,0,0,1,0,0，

0,0,5,9,4,0,0,0,0）


result = solve（sudoku（* inpu） t））

打印结果

前写道：

灵感来自LinuxJournal上最近的一些读物和一个ASPN配方，我决定改造我的旧python hack ...新代码是（2）减少方法和蛮力的组合，它比
快得多
ASPN计划。如果有人有兴趣，我将代码附在
http://agolb.blogspot.com/2006/01/su...in-python.html

我建议尝试


输入="""

0,0,0,0,9,6,8,0,0

0,0,1,0,0,0,0,7,0

0,2,0,0,0,0,0,0,3

0,3,0,0,0,8,0,0,6

0,0,4,0,2,0,3,0,0

6,0,0,5,0,0,0,8,0

9,0,0,0,0,0,0,5,0

0,7,0,0,0,0,1,0,0

0,0,5,9,4,0,0,0,0"""你的程序似乎花了太长时间来解决它。


我认为困难的部分不是解决，而是创造*困难*

数独网格。

但是为了让我的自我超越已知的宇宙，这里是我的解算器

（这合理地解决了提到的网格快速）。我认为

唯一的区别是在开始树状搜索之前使用3而不是2规则简化

。


#########

＃如果需要复制品：

＃这是一个pulbic域，无论你想做什么都可以用它做什么

#ie最可能没有什么

#########

类DeadEnd（例外）：

传递

类数独（对象）：


def __init __（self，* args）：

self.changed = True

self.possible = []

if len（args）！= 81：

引发ValueError，需要81个数字

for i in args：

if i == 0：

self.possible.append（range（1,10））

否则：

self.possible.append（[i]）


def __getitem __（self，（x，y））：

返回self.possible [9 * x + y]


def __setitem __（self，（x，y），what）：

self.possible [9 * x + y] =什么


def copy（self）：

result = sudoku（*（81 * [1]） ）

for i in range（9）：

for j in range（9）：

result [i，j] = list（自我[i，j]）

返回结果


def solve（self）：

for i in range（9） ：

for j in range（9）：

if len（self [i，j]）！= 1：

返回False

返回True


def试验（个体经营）：

for i，j in（（i，j）for ln in范围（2,10）

for i in range（9）j in range（9）

if len（self [i，j]）== ln） ：

for self [i，j]：

new = self.copy（）

new [i，j] = [ k]

收益率新

def clean1（self，x，y）：

self.changed = False
if len（self [x，y]）== 1：

返回

remove = set（）

for self.regions（x，y）中的位置：

缺失=设置（范围（1,10））
$ x $ b表示xx，yy在某些地方：

如果xx == x和yy == y：

继续

如果len（self [xx，yy]）== 1：

remove.add（self [xx，yy] [0]）

missing- = set（self [xx，yy]）
如果缺少
：

a = missing.pop（）

self [x，y] = [a]

self.changed = True

for a remove：

试试：

self [x，y] .remove（a）

if not not self [x，y ]：

加注DeadEnd

self.changed = True
除了Valu之外的
错误：

通过


def clean3（self，out1，out2）：
（b1，o2）
（（ out1，out2），（out2，out1））：

remove = set（范围（1,10））

代表x，y代表o1：

remove- = set（self [x，y]）

for x，y in o2：

for n in remove：

尝试：

self [x，y] .remove（n）

如果不是自我[x，y]：

提高DeadEnd

self.changed = True

除了ValueError：

通过


@staticmethod
def region（x，y）：

return（（（xx，y）xx在范围内（9）），

（（x， yy）for yy in range（9）），

（（xx，yy）xx在范围内（3 *（x // 3），3 *（x // 3）+3）

for yy in range（3 *（y // 3），3 *（y // 3）+3）））

@staticmethod

def out（）：

for i in range（3）：

for j in range（3）：

for k在范围（3）中：

out1 = [（a + 3 * i，b + 3 * j）a范围内（3）

如果a不是k for b in range（3）]

out2 = [（k + 3 * i，n）n为范围（9），如果n // 3！= j]

收益率out1，out2

为范围内的k（3）：

out1 = [（a + 3 * i，b + 3 * j）范围内（3）
b b范围内的b b（b）如果b不是k则为b]

out2 = [（n，k + 3 * j）n范围内（9）如果n // 3！= i]

收益率out1，out2


def clean_all（个体经营）：

而self.changed：

self.changed = False

for x in range（9）：

for y in range（9）：

self.clean1（x，y）

for out1，out2 in self.outs（）：

self.clean3（out1，out2 ）


def __repr __（自我）：

result =""

for x in range（9）：

为y在范围内（9）：

如果len（self [x，y]）== 1：

haf = self [x ，y] [0]

其他：

haf = self [x，y]

结果+ = str（haf）+''' '

结果+ =''\ n''

返回结果



来自collection import deque


类升（物件）：


def __init __（self，* iterables）：

self.iters = de que（iter（x）for x in iterables）


def __iter __（self）：

而self.iters：

it = self.iters.popleft（）

试试：

result = it.next（）

除了StopIteration：

继续

self.iters.append（it）

收益率结果


def append（self，what）：

self.iters.append（iter（what））


def solve（me）：

tree =升（[我在你的树上给你
：

试试：

you.clean_all（）

除了DeadEnd：

继续

if youolved（）：

返回你

tree.append（you.trials（ ））


######

输入=（

0,0,0,0 ，9,6,8,0,0，

0,0,1,0,0,0,0,7,0，

0,2,0 ，0,0,0,0,0,3，

0,3,0,0,0,8,0,0,6，

0,0 ，4,0,2,0,3,0,0，

6,0,0,5,0,0,0,8,0，

9 ，0,0,0,0,0,0,5,0，

0,7,0,0,0,0,1,0,0，

0,0,5,9,4,0,0,0,0）


result = solve（sudoku（* inpu） t））

打印结果

此主题还有更多内容：

http ：//groups.google.com/group/comp....52dab14e8ecabb


享受，

Bas

Inspired by some recent readings on LinuxJournal and an ASPN recipe, I
decided to revamp my old python hack... The new code is a combination
of (2) reduction methods and brute force and it is quite faster than
the
ASPN program. If anyone is interested I attached the code in
http://agolb.blogspot.com/2006/01/su...in-python.html

解决方案

ago wrote:

Inspired by some recent readings on LinuxJournal and an ASPN recipe, I
decided to revamp my old python hack... The new code is a combination
of (2) reduction methods and brute force and it is quite faster than
the
ASPN program. If anyone is interested I attached the code in
http://agolb.blogspot.com/2006/01/su...in-python.html

I suggest trying

input="""
0,0,0,0,9,6,8,0,0
0,0,1,0,0,0,0,7,0
0,2,0,0,0,0,0,0,3
0,3,0,0,0,8,0,0,6
0,0,4,0,2,0,3,0,0
6,0,0,5,0,0,0,8,0
9,0,0,0,0,0,0,5,0
0,7,0,0,0,0,1,0,0
0,0,5,9,4,0,0,0,0"""

your program seems to take too long to solve it.

I think the hard part is not to solve, but rather to create *difficult*
sudoku grids.
But to inflate my ego beyond the known universe, here is my solver
(that solves the avove mentioned grid reasonably fast). I suppose the
only difference is that is uses 3, rather than 2, rules to simplify
before starting tree-like search.

#########
#if a copyryght is needed:
#this is pulbic domain, do with it whatever you want
#i.e. most probably nothing
#########

class DeadEnd(Exception):
pass

class sudoku(object):

def __init__(self,*args):
self.changed=True
self.possible=[]
if len(args) != 81:
raise ValueError, "need 81 numbers"
for i in args:
if i==0:
self.possible.append(range(1,10))
else:
self.possible.append([i])

def __getitem__(self,(x,y)):
return self.possible[9*x+y]

def __setitem__(self,(x,y),what):
self.possible[9*x+y]=what

def copy(self):
result=sudoku(*(81*[1]))
for i in range(9):
for j in range(9):
result[i,j]=list(self[i,j])
return result

def solved(self):
for i in range(9):
for j in range(9):
if len(self[i,j]) != 1:
return False
return True

def trials(self):
for i,j in ((i,j) for ln in range(2,10)
for i in range(9) for j in range(9)
if len(self[i,j])==ln):
for k in self[i,j]:
new=self.copy()
new[i,j]=[k]
yield new

def clean1(self,x,y):
self.changed=False
if len(self[x,y]) == 1:
return
remove=set()
for places in self.regions(x,y):
missing=set(range(1,10))
for xx,yy in places:
if xx==x and yy==y:
continue
if len(self[xx,yy])==1:
remove.add(self[xx,yy][0])
missing-=set(self[xx,yy])
if missing:
a=missing.pop()
self[x,y]=[a]
self.changed=True
for a in remove:
try:
self[x,y].remove(a)
if not self[x,y]:
raise DeadEnd
self.changed=True
except ValueError:
pass

def clean3(self,out1,out2):
for (o1, o2) in ((out1,out2), (out2,out1)):
remove=set(range(1,10))
for x,y in o1:
remove-=set(self[x,y])
for x,y in o2:
for n in remove:
try:
self[x,y].remove(n)
if not self[x,y]:
raise DeadEnd
self.changed=True
except ValueError:
pass

@staticmethod
def regions(x,y):
return (((xx,y) for xx in range(9)),
((x,yy) for yy in range(9)),
((xx,yy) for xx in range(3*(x//3),3*(x//3)+3)
for yy in range(3*(y//3),3*(y//3)+3)))
@staticmethod
def outs():
for i in range(3):
for j in range(3):
for k in range(3):
out1=[(a+3*i,b+3*j) for a in range(3)
if a is not k for b in range(3)]
out2=[(k+3*i,n) for n in range(9) if n//3!=j]
yield out1, out2
for k in range(3):
out1=[(a+3*i,b+3*j) for a in range(3)
for b in range(3) if b is not k]
out2=[(n,k+3*j) for n in range(9) if n//3!=i]
yield out1, out2

def clean_all(self):
while self.changed:
self.changed=False
for x in range(9):
for y in range(9):
self.clean1(x,y)
for out1,out2 in self.outs():
self.clean3(out1,out2)

def __repr__(self):
result=""
for x in range(9):
for y in range(9):
if len(self[x,y])==1:
haf=self[x,y][0]
else:
haf=self[x,y]
result+=str(haf)+'' ''
result+=''\n''
return result


from collections import deque

class liter(object):

def __init__(self, *iterables):
self.iters=deque(iter(x) for x in iterables)

def __iter__(self):
while self.iters:
it=self.iters.popleft()
try:
result=it.next()
except StopIteration:
continue
self.iters.append(it)
yield result

def append(self,what):
self.iters.append(iter(what))

def solve(me):
tree=liter([me])
for you in tree:
try:
you.clean_all()
except DeadEnd:
continue
if you.solved():
return you
tree.append(you.trials())

######

input=(
0,0,0,0,9,6,8,0,0,
0,0,1,0,0,0,0,7,0,
0,2,0,0,0,0,0,0,3,
0,3,0,0,0,8,0,0,6,
0,0,4,0,2,0,3,0,0,
6,0,0,5,0,0,0,8,0,
9,0,0,0,0,0,0,5,0,
0,7,0,0,0,0,1,0,0,
0,0,5,9,4,0,0,0,0)

result=solve(sudoku(*input))
print result

ago wrote:

Inspired by some recent readings on LinuxJournal and an ASPN recipe, I
decided to revamp my old python hack... The new code is a combination
of (2) reduction methods and brute force and it is quite faster than
the
ASPN program. If anyone is interested I attached the code in
http://agolb.blogspot.com/2006/01/su...in-python.html

I suggest trying

input="""
0,0,0,0,9,6,8,0,0
0,0,1,0,0,0,0,7,0
0,2,0,0,0,0,0,0,3
0,3,0,0,0,8,0,0,6
0,0,4,0,2,0,3,0,0
6,0,0,5,0,0,0,8,0
9,0,0,0,0,0,0,5,0
0,7,0,0,0,0,1,0,0
0,0,5,9,4,0,0,0,0"""

your program seems to take too long to solve it.

I think the hard part is not to solve, but rather to create *difficult*
sudoku grids.
But to inflate my ego beyond the known universe, here is my solver
(that solves the avove mentioned grid reasonably fast). I suppose the
only difference is that is uses 3, rather than 2, rules to simplify
before starting tree-like search.

#########
#if a copyryght is needed:
#this is pulbic domain, do with it whatever you want
#i.e. most probably nothing
#########

class DeadEnd(Exception):
pass

class sudoku(object):

def __init__(self,*args):
self.changed=True
self.possible=[]
if len(args) != 81:
raise ValueError, "need 81 numbers"
for i in args:
if i==0:
self.possible.append(range(1,10))
else:
self.possible.append([i])

def __getitem__(self,(x,y)):
return self.possible[9*x+y]

def __setitem__(self,(x,y),what):
self.possible[9*x+y]=what

def copy(self):
result=sudoku(*(81*[1]))
for i in range(9):
for j in range(9):
result[i,j]=list(self[i,j])
return result

def solved(self):
for i in range(9):
for j in range(9):
if len(self[i,j]) != 1:
return False
return True

def trials(self):
for i,j in ((i,j) for ln in range(2,10)
for i in range(9) for j in range(9)
if len(self[i,j])==ln):
for k in self[i,j]:
new=self.copy()
new[i,j]=[k]
yield new

def clean1(self,x,y):
self.changed=False
if len(self[x,y]) == 1:
return
remove=set()
for places in self.regions(x,y):
missing=set(range(1,10))
for xx,yy in places:
if xx==x and yy==y:
continue
if len(self[xx,yy])==1:
remove.add(self[xx,yy][0])
missing-=set(self[xx,yy])
if missing:
a=missing.pop()
self[x,y]=[a]
self.changed=True
for a in remove:
try:
self[x,y].remove(a)
if not self[x,y]:
raise DeadEnd
self.changed=True
except ValueError:
pass

def clean3(self,out1,out2):
for (o1, o2) in ((out1,out2), (out2,out1)):
remove=set(range(1,10))
for x,y in o1:
remove-=set(self[x,y])
for x,y in o2:
for n in remove:
try:
self[x,y].remove(n)
if not self[x,y]:
raise DeadEnd
self.changed=True
except ValueError:
pass

@staticmethod
def regions(x,y):
return (((xx,y) for xx in range(9)),
((x,yy) for yy in range(9)),
((xx,yy) for xx in range(3*(x//3),3*(x//3)+3)
for yy in range(3*(y//3),3*(y//3)+3)))
@staticmethod
def outs():
for i in range(3):
for j in range(3):
for k in range(3):
out1=[(a+3*i,b+3*j) for a in range(3)
if a is not k for b in range(3)]
out2=[(k+3*i,n) for n in range(9) if n//3!=j]
yield out1, out2
for k in range(3):
out1=[(a+3*i,b+3*j) for a in range(3)
for b in range(3) if b is not k]
out2=[(n,k+3*j) for n in range(9) if n//3!=i]
yield out1, out2

def clean_all(self):
while self.changed:
self.changed=False
for x in range(9):
for y in range(9):
self.clean1(x,y)
for out1,out2 in self.outs():
self.clean3(out1,out2)

def __repr__(self):
result=""
for x in range(9):
for y in range(9):
if len(self[x,y])==1:
haf=self[x,y][0]
else:
haf=self[x,y]
result+=str(haf)+'' ''
result+=''\n''
return result


from collections import deque

class liter(object):

def __init__(self, *iterables):
self.iters=deque(iter(x) for x in iterables)

def __iter__(self):
while self.iters:
it=self.iters.popleft()
try:
result=it.next()
except StopIteration:
continue
self.iters.append(it)
yield result

def append(self,what):
self.iters.append(iter(what))

def solve(me):
tree=liter([me])
for you in tree:
try:
you.clean_all()
except DeadEnd:
continue
if you.solved():
return you
tree.append(you.trials())

######

input=(
0,0,0,0,9,6,8,0,0,
0,0,1,0,0,0,0,7,0,
0,2,0,0,0,0,0,0,3,
0,3,0,0,0,8,0,0,6,
0,0,4,0,2,0,3,0,0,
6,0,0,5,0,0,0,8,0,
9,0,0,0,0,0,0,5,0,
0,7,0,0,0,0,1,0,0,
0,0,5,9,4,0,0,0,0)

result=solve(sudoku(*input))
print result

There is more in this thread:

http://groups.google.com/group/comp....52dab14e8ecabb

Enjoy,
Bas

这篇关于数独求解器：减少+蛮力的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！