以下为《9x9数独算法》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

9x9数独算法

/

开源中国

发表于 2014-08-21 10:45:42

#1.?先遍历一遍，找出所有“只有一个候选数字”的格子,?清除行，列，块数据??

#2.?填满这些数字，重复第一步??

#3.?如果没有“只有一个候选数字”的格子，那就找最少候选的那个格子??

#　　先尝试这个格子的其中一个候选，再尝试剩余的候选数字?

# sdks 给出了数独源

#这个算法也可以用来做生成数独，然后取出几个?

比如你给定数独为?

******************************1??

#?嘿嘿，这解可多了，机器别跑死了。 ?

# -*- coding:utf-8 -*-

'''

构造法

首先生成9x9x9的三维数组，每个值为[1,2,3,4,5,6,7,8,9]

1，然后确定有独一的值，清除行，列，块当中的值 clean(data)函数

继续1

然后找到唯一值，即行、列或块当中只出现一次的值，设置当前值，然后执行1，clean_help(data)函数

最后如果没有唯一值那就找最少候选的那个格子先尝试这个格子的其中一个候选，再尝试剩余的候选数字

'''

#1. 先遍历一遍，找出所有“只有一个候选数字”的格子, 清除行，列，块数据

#2. 填满这些数字，重复第一步

#3. 如果没有“只有一个候选数字”的格子，那就找最少候选的那个格子

#　　先尝试这个格子的其中一个候选，再尝试剩余的候选数字

from copy import deepcopy

# 移除数组中指定的值

def rm(s, n):

i = 0

try:

s.remove(n)

i = i + 1

except:

pass

return i

# 根据行，列坐标，返回行，列，块数组

def find(fbs, i, j):

block = []

br = i / 3 * 3

bc = j / 3 * 3

for l in range(0, 3):

r = br + l

for k in range(0, 3):

c = bc + k

block.append(fbs[r][c])

return {"row":fbs[i],"column":[fbs[a][j] for a in range(0, 9)],"block":block}

# 打印

def pnt(dbss):

print"============"

for i in range(0, 9):

print dbss[i],"n"

# 生成9×9×9的三维数组

base = [[[i for i in range(1, 10)] for a in range(1, 10)] for b in range(1, 10)]

sudo1 = [

[0,8,1, 0,9,0, 0,0,0],

[0,0,0, 1,0,7, 0,5,0],

[0,7,5, 0,4,0, 0,0,1],

[0,0,0, 0,3,4, 2,0,0],

[5,0,0, 7,0,1, 0,0,0],

[0,0,0, 0,0,2, 1,0,9],

[0,0,6, 0,8,0, 0,0,4],

[8,0,7, 6,0,0, 5,0,0],

[0,0,3, 0,0,0, 6,0,8]

]

# 此数独没有解出来。ps:这个数独是错误的，无解。DLX算法也不行。

sudo2 = [

[ 8, 0, 0, 0, 0, 0, 0, 0, 0 ],

[ 0, 0, 3, 6, 0, 0, 0, 0, 0 ],

[ 0, 7, 0, 0, 9, 0, 2, 0, 0 ],

[ 0, 5, 0, 0, 0, 7, 0, 0, 0 ],

[ 0, 0, 0, 0, 4, 5, 7, 0, 0 ],

[ 0, 0, 0, 1, 0, 6, 0, 3, 0 ],

[ 0, 0, 1, 0, 0, 0, 0, 6, 8 ],

[ 0, 0, 8, 5, 0, 0, 0, 1, 0 ],

[ 0, 9, 0, 0, 0, 0, 4, 0, 0 ]

]

# 此数独有解，但死循环

sudo3 = [

[0, 0, 0, 0, 1, 0, 0, 0, 0],

[0, 0, 0, 2, 0, 3, 0, 0, 0],

[0, 0, 4, 0, 0, 0, 5, 0, 0],

[0, 6, 0, 0, 0, 0, 0, 7, 0],

[8, 0, 0, 0, 5, 0, 0, 0, 9],

[0, 7, 0, 0, 0, 0, 0, 6, 0],

[0, 0, 5, 0, 0, 0, 4, 0, 0],

[0, 0, 0, 3, 0, 2, 0, 0, 0],

[0, 0, 0, 0, 9, 0, 0, 0, 0]

]

sudo4 = [

[0, 0, 0, 0, 1, 0, 8, 7, 0],

[0, 2, 0, 0, 9, 0, 0, 0, 0],

[0, 0, 0, 5, 0, 0, 0, 0, 0],

[2, 0, 0, 0, 6, 8, 0, 9, 0],

[0, 0, 8, 0, 7, 0, 3, 0, 0],

[0, 9, 7, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 4, 6, 3, 0],

[0, 8, 0, 0, 5, 0, 0, 0, 0],

[0, 7, 1, 3, 0, 0, 9, 0, 0]

]

sudo5 = [

[0,0,2,4,5,0,7,0,0]

,[0,4,0,0,0,8,0,3,0]

,[8,0,1,0,0,3,5,0,6]

,[0,5,3,0,0,0,0,0,4]

,[7,0,0,0,0,0,0,0,2]

,[2,0,0,0,0,0,6,7,0]

,[3,0,6,5,0,0,1,0,7]

,[0,2,0,1,0,0,0,5,0]

,[0,0,7,0,2,9,4,0,0]

]

# 初始化填充base

def inits(b, s):

for i in range(0, 9):

sudo = s[i]

for j in range(0, 9):

num = sudo[j]

if num != 0:

b[i][j] = [num]

finds = find(b, i, j)

for f in finds:

ff = finds[f]

for fff in ff:

if len(fff) > 1:

rm(fff, num)

return b

# 根据独一值，清除行，列，块值

def clean(clean_data):

flag = True

while flag:

# 退出条件

rms = 0

for i in range(0, 9):

for j in range(0, 9):

num = clean_data[i][j]

if len(num) == 1:

# 根据独一值清除行，列，块

finds = find(clean_data, i, j)

for f1 in finds:

f2 = finds[f1]

for f3 in f2:

if len(f3) > 1:

rms += rm(f3, num[0])

if rms == 0:

flag = False

return clean_data

# 找到唯一值，并清除行列块

def clean_help(data):

while True:

# 退出条件

flag = True

for i in range(0, 9):

for j in range(0, 9):

brk = 0

cur = data[i][j]

if len(cur) > 1:

finds = find(data, i, j)

for f in finds:

a = [0] * 9

f1 = finds[f]

for f2 in f1:

for f3 in f2:

a[f3 - 1] += 1

for m in cur:

# 找到了唯一值，并进行设置，清除数独，退出当前循环

if a[m - 1] == 1:

flag = False

brk = 1

data[i][j] = [m]

clean(data)

break

if brk == 1:

break

# 当没有唯一值是退出循环

if flag:

break

return data

# 读取数独源

def readSdks(i):

sudokus = open("sdks","r")

if i < 0 or i > 125:

print"Not found sudoku data"

return

sdk = sudokus.readlines()[i].replace("n","")

sdks = [sdk[j:j + 9] for j in range(0, 81, 9)]

#print sdks

ret = [[int(sk[l]) for l in range(0, 9)] for sk in sdks]

sudokus.close()

return ret

# 验证数独

def isOk(data):

for i in range(0, 9):

for j in range(0, 9):

finds = find(data, i, j)

for f in finds:

a = [0] * 9

ff = finds[f]

for fff in ff:

if len(fff) > 1:

return False

a[fff[0] - 1] += 1

for ia in a:

if ia > 1 or ia == 0:

return False

print"ok"

return True

# 找到数独当中最小候选对象元祖

#([], x, y) 数组为候选可能值，x为行坐标，y为列坐标

def small(data):

ret_sm = ([0] * 9, -1, -1)

for i in range(0, 9):

for j in range(0, 9):

if len(data[i][j]) > 1 and len(data[i][j]) < len(ret_sm[0]):

ret_sm = (data[i][j], i, j)

return ret_sm

# 最后数独完成操作 设置候选值

def done(data):

if isOk(data):

pnt(data)

return

sm_tuple = small(data)

#print sm_tuple

if sm_tuple[1] == -1:

#print"no solve"

return

# 设置候选值

for sm in sm_tuple[0]:

#pnt(data)

# 复制数独源，上次的结果不然还存在，就不能求多解了

copy_data = deepcopy(data)

# 设置候选值

copy_data[sm_tuple[1]][sm_tuple[2]] = [sm]

# 然后执行清除操作

copy_data = clean_help(clean(copy_data))

if isOk(copy_data):

#print"in done"

pnt(copy_data)

return

# 如果没有完成，继续设置候选值

done(copy_data)

def main():

for i in range(0, 120):

print"The %d index"% i

#readSdks(1)

sudokuData = readSdks(i)

base = [[[j for j in range(1, 10)] for a in range(1, 10)] for b in range(1, 10)]

init_data = inits(base, sudokuData)

#print"init:"

#pnt(init_data)

clean_data = clean(init_data)

#print"clean:"

#pnt(clean_data)

only_data = clean_help(clean_data)

#print"only:"

#pnt(only_data)

done(only_data)

if __name__ =="__main__":

main()

以上为《9x9数独算法》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。