网上看到一个python写的数独,很好玩,分享给大家。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
import random
import itertools
from copy import deepcopy
def make_board(m = 3 ):
numbers = list ( range ( 1 , m * * 2 + 1 ))
board = None
while board is None :
board = attempt_board(m, numbers)
return board
def attempt_board(m, numbers):
n = m * * 2
board = [[ None for _ in range (n)] for _ in range (n)]
for i, j in itertools.product( range (n), repeat = 2 ):
i0, j0 = i - i % m, j - j % m
random.shuffle(numbers)
for x in numbers:
if (x not in board[i]) and all (row[j] ! = x for row in board) and all (x not in row[j0:j0 + m] for row in board[i0:i]):
board[i][j] = x
break
else :
return None
return board
def print_board(board, m = 3 ):
numbers = list ( range ( 1 , m * * 2 + 1 ))
omit = 5
challange = deepcopy(board)
for i, j in itertools.product( range (omit), range (m * * 2 )):
x = random.choice(numbers) - 1
challange[x][j] = None
spacer = "++---+---+---++---+---+---++---+---+---++"
print (spacer.replace( '-' , '=' ))
for i, line in enumerate (challange):
print ( "|| {0} | {1} | {2} || {3} | {4} | {5} || {6} | {7} | {8} ||" . format ( * (cell or ' ' for cell in line)))
if (i + 1 ) % 3 = = 0 :
print (spacer.replace( '-' , '=' ))
else :
print (spacer)
return challange
def print_answer(board):
spacer = "++---+---+---++---+---+---++---+---+---++"
print (spacer.replace( '-' , '=' ))
for i, line in enumerate (board):
print ( "|| {0} | {1} | {2} || {3} | {4} | {5} || {6} | {7} | {8} ||" . format ( * (cell or ' ' for cell in line)))
if (i + 1 ) % 3 = = 0 :
print (spacer.replace( '-' , '=' ))
else :
print (spacer)
def is_full(challange, m = 3 ):
for i, j in itertools.product( range (m * * 2 ), repeat = 2 ):
if challange[i][j] is None :
return False
return True
def cal_candidate(challange, x, y, m = 3 ):
candidate = range ( 1 , m * * 2 + 1 )
for i in range (m * * 2 ):
if challange[x][i] in candidate:
candidate.remove(challange[x][i])
if challange[i][y] in candidate:
candidate.remove(challange[i][y])
for i, j in itertools.product( range (m), repeat = 2 ):
x0, y0 = x - x % m, y - y % m
if challange[x0 + i][y0 + j] in candidate:
candidate.remove(challange[x0 + i][y0 + j])
return candidate
def least_candidate(challange, m = 3 ):
least, x, y = m * * 2 , - 1 , - 1
for i, j in itertools.product( range (m * * 2 ), repeat = 2 ):
if not challange[i][j]:
num = len (cal_candidate(challange, i, j))
if num < least:
least = num
x, y = i, j
return x, y
def solving_soduku(challange, m = 3 ):
if is_full(challange):
return challange
x, y = least_candidate(challange)
id = x * (m * * 2 ) + y
result = try_candidate(challange, id )
return result
def try_candidate(challange, id , m = 3 ):
if is_full(challange):
return challange
x = id / (m * * 2 )
y = id % (m * * 2 )
while challange[x][y]:
id = ( id + 1 ) % m * * 4
x = id / (m * * 2 )
y = id % (m * * 2 )
candidate = cal_candidate(challange, x, y)
if len (candidate) = = 0 :
return False
for i in range ( len (candidate)):
challange[x][y] = candidate[i]
result_r = try_candidate(challange, ( id + 1 ) % m * * 4 )
if not result_r:
pass
else :
return challange
challange[x][y] = None
return False
#Board = make_board()
#print Board
#challange = print_board(Board)
#print_answer(Board)
#result = solving_soduku(challange)
#print_answer(result)
testing = [[ 8 , None , None , None , None , None , None , None , None ],
[ None , None , 3 , 6 , None , None , None , None , None ],
[ None , 7 , None , None , 9 , None , 2 , None , None ],
[ None , 5 , None , None , None , 7 , None , None , None ],
[ None , None , None , None , 4 , 6 , 7 , None , None ],
[ None , None , None , 1 , None , None , None , 3 , None ],
[ None , None , 1 , None , None , None , None , 6 , 8 ],
[ None , None , 8 , 5 , None , None , None , 1 , None ],
[ None , 9 , None , None , None , None , 4 , None , None ]]
result = solving_soduku(testing)
print_answer(result)
|
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/Pnfy__Shan/article/details/54970361