论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2014-11-15 06:29 |只看该作者 |倒序浏览

業餘時間用python寫了個求解數獨的小程序。
方法很直接，就是根據每個空可能出現的數字來逐個試填，直到找到解。
有興趣可以看看……

CS群：329355400
点击链接加入群【Computer Science】：http://jq.qq.com/?_wv=1027&k=STufuA

#!/usr/bin/python
#
# Useage: ./sudoku.py
#
# import packages
import array
import numpy
# define functions
def init_possible_element( s, p_list, i, j):
p_list[i][j] = range(1,10)
for k in range(1,10):
if k != j and s[i][k] != 0 and s[i][k] in p_list[i][j]:
p_list[i][j].remove(s[i][k])
if k != i and s[k][j] != 0 and s[k][j] in p_list[i][j]:
p_list[i][j].remove(s[k][j])
for ki in range((i-1)/3*3+1, (i-1)/3*3+4):
for kj in range((j-1)/3*3+1, (j-1)/3*3+4):
if (ki != i or kj != j) and s[ki][kj] != 0 and s[ki][kj] in p_list[i][j]:
p_list[i][j].remove(s[ki][kj])
return 0
def init_possible_list( s, p_list):
empty_box = 0
for i in range(1,10):
for j in range(1,10):
if s[i][j] == 0:
empty_box += 1
else:
p_list[i][j] = s[i][j]
for k in range(1,10):
if k != j and s[i][k] == 0 and s[i][j] in p_list[i][k]:
p_list[i][k].remove(s[i][j])
if k != i and s[k][j] == 0 and s[i][j] in p_list[k][j]:
p_list[k][j].remove(s[i][j])
for ki in range((i-1)/3*3+1, (i-1)/3*3+4):
for kj in range((j-1)/3*3+1, (j-1)/3*3+4):
if (ki != i or kj != j) and s[ki][kj] == 0 and s[i][j] in p_list[ki][kj]:
p_list[ki][kj].remove(s[i][j])
return empty_box
def update_possible_list( s, p_list, i, j, flag):
if flag != 0: # s[i][j] turn back to zero, it original value now is in flag
init_possible_element(s, p_list, i, j)
for k in range(1,10):
if k != j and s[i][k] == 0:
init_possible_element(s, p_list, i, k)
if k != i and s[k][j] == 0:
init_possible_element(s, p_list, k, j)
for ki in range((i-1)/3*3+1, (i-1)/3*3+4):
for kj in range((j-1)/3*3+1, (j-1)/3*3+4):
if ki != i and kj != j and s[ki][kj] == 0:
init_possible_element(s, p_list, ki, kj)
else: # set s[i][j] a value in possible list
for k in range(1,10):
if k != j and s[i][k] == 0 and s[i][j] in p_list[i][k]:
p_list[i][k].remove(s[i][j])
if k != i and s[k][j] == 0 and s[i][j] in p_list[k][j]:
p_list[k][j].remove(s[i][j])
for ki in range((i-1)/3*3+1, (i-1)/3*3+4):
for kj in range((j-1)/3*3+1, (j-1)/3*3+4):
if (ki != i or kj != j) and s[ki][kj] == 0 and s[i][j] in p_list[ki][kj]:
p_list[ki][kj].remove(s[i][j])
return 0
def find_min_posibble( p_list ):
min_p = 9
min_i = 0
min_j = 0
for i in range(1,10):
for j in range(1,10):
if s[i][j] == 0 and len(p_list[i][j]) < min_p:
min_p = len(p_list[i][j])
(min_i, min_j) = (i, j)
return (min_i, min_j, min_p)
def solve_sudoku( s, p_list, empty_box ):
if empty_box == 0:
for i in range(1,10):
for j in range(1,9):
print s[i][j],
print s[i][9]
return 0
(i, j, p) = find_min_posibble(p_list)
if p == 0:
return 1
for t in range(0, p):
s[i][j] = p_list[i][j][t]
update_possible_list( s, p_list, i, j, 0)
try_failed = solve_sudoku( s, p_list, empty_box-1 )
if try_failed == 1:
flag = s[i][j]
s[i][j] = 0
update_possible_list( s, p_list, i, j, flag)
else:
return 0
return 1
####################################################################################################
# keep current sudoku status
s = numpy.zeros([10,10], int)
# initial status
s[1][4] = 3
s[1][7] = 6
s[2][2] = 2
s[2][7] = 4
s[2][8] = 7
s[3][2] = 7
s[3][3] = 6
s[3][4] = 4
s[4][1] = 3
s[4][2] = 1
s[4][6] = 9
s[4][8] = 6
s[5][4] = 2
s[5][6] = 6
s[6][2] = 8
s[6][4] = 5
s[6][8] = 2
s[6][9] = 7
s[7][6] = 1
s[7][7] = 5
s[7][8] = 3
s[8][2] = 4
s[8][3] = 1
s[8][8] = 8
s[9][3] = 9
s[9][6] = 4
p_list = [[range(1,10) for i in range(0,10)] for j in range(0,10)]
empty_box = init_possible_list(s, p_list)
solve_sudoku( s, p_list, empty_box )