python语言解杀手数独

杀手数独(Killer Sudoku)是一种数学智力游戏，它结合了数独(Sudoku)和数和(Kakuro)的玩法。虚线框之和表示虚线框内所有数字之和。

在这个网址有例题。杀手数独 - 游玩、打印并分享免费的在线杀手数独解谜游戏

我用python篇写了一段代码，用于解杀手数独，解了两个难度为困难++的杀手数独，结果如下

#10045

gsdict={"00,01":8,

"02,11,12,13,22":21,

"03,04":5,

"05,14,15":20,

"06,16":13,

"07,17":10,

"08,18,28":15,

"10,20,21":18,

"23,33":6,

"24,34,44,54,64":26,

"25,35,36,45":23,

"26,27":7,

"30,31,32":13,

"37,46,47":19,

"38,48":8,

"40,50":5,

"41,42,51":22,

"43,52,53,63":28,

"55,65":11,

"56,57,58":9,

"60,70,80":16,

"61,62":11,

"66,75,76,77,86":15,

"67,68,78":17,

"71,81":9,

"72,82":9,

"73,74,83":19,

"84,85":8,

"87,88":14}

结果：

[5, 3, 6, 4, 1, 8, 7, 9, 2]

[8, 7, 4, 2, 3, 9, 6, 1, 5]

[9, 1, 2, 5, 7, 6, 3, 4, 8]

[2, 8, 3, 1, 4, 5, 9, 6, 7]

[4, 6, 7, 9, 2, 3, 5, 8, 1]

[1, 9, 5, 6, 8, 7, 4, 2, 3]

[3, 2, 9, 8, 5, 4, 1, 7, 6]

[6, 5, 8, 7, 9, 1, 2, 3, 4]

[7, 4, 1, 3, 6, 2, 8, 5, 9]

#7382

gsdict={"00,01":15,

"02,03,04,13":22,

"05,14,15,25":20,

"06,16":9,

"07,17":5,

"08,18,27,28":24,

"10,20":10,

"11,12,21,22,32,42":30,

"23,24":5,

"26,35,36":19,

"30,31":8,

"33,43":15,

"34,44,54":14,

"37,38":6,

"40,41":5,

"45,55":8,

"46,56,66,67,76,77":22,

"47,48":11,

"50,51":17,

"52,53,62":14,

"57,58":11,

"60,61,70,80":17,

"63,73,74,83":10,

"64,65":17,

"68,78":12,

"71,81":10,

"72,82":12,

"75,84,85,86":26,

"87,88":11

}

结果：

[8, 7, 2, 6, 5, 1, 4, 3, 9]

[4, 3, 1, 9, 7, 8, 5, 2, 6]

[6, 5, 9, 2, 3, 4, 7, 1, 8]

[2, 6, 7, 8, 4, 3, 9, 5, 1]

[1, 4, 5, 7, 9, 2, 6, 8, 3]

[9, 8, 3, 5, 1, 6, 2, 7, 4]

[5, 2, 6, 1, 8, 9, 3, 4, 7]

[3, 9, 8, 4, 2, 7, 1, 6, 5]

[7, 1, 4, 3, 6, 5, 8, 9, 2]

原代码如下（采用递归算法，所需时间较长)：

m="""000000000

000000000

000000000

000000000

000000000

000000000

000000000

000000000

000000000""".split()

#10045

gsdict={"00,01":8,

"02,11,12,13,22":21,

"03,04":5,

"05,14,15":20,

"06,16":13,

"07,17":10,

"08,18,28":15,

"10,20,21":18,

"23,33":6,

"24,34,44,54,64":26,

"25,35,36,45":23,

"26,27":7,

"30,31,32":13,

"37,46,47":19,

"38,48":8,

"40,50":5,

"41,42,51":22,

"43,52,53,63":28,

"55,65":11,

"56,57,58":9,

"60,70,80":16,

"61,62":11,

"66,75,76,77,86":15,

"67,68,78":17,

"71,81":9,

"72,82":9,

"73,74,83":19,

"84,85":8,

"87,88":14

}

def solve_sudo(board):

global njsq

for i in range(0,9):

for j in range(0,9):

if board[i][j]==0:

njsq+=1

if njsq%1000000==0:

print("*"*30)

for x in board:

print(x)

rset=set(board[i])

rset|=set([board[k][j] for k in range(9)])

r=i//3*3

c=j//3*3

rset|=set([board[k][l] for k in range(r,r+3) for l in range(c,c+3)])

for num in sorted(set(range(1,10))-rset):

board[i][j]=num

gs=[x for x in gsdict.keys() if f'{i}{j}' in x]

if gs:

nsum=gsdict[gs[0]]

cells=[board[int(x[0])][int(x[1])] for x in gs[0].split(",")]

if all(cells):

if sum(cells)!=nsum:

board[i][j]=0

continue

if solve_sudo(board):

return True

else:

board[i][j]=0

return False

return True

ks=[]

for x in gsdict.keys():

for y in x.split(","):

ks.append(y)

if len(set(ks))!=81:

print("公式有错，单元格不全")

exit()

if sum(list(gsdict.values()))!=405:

print("数字和有错，不为405")

exit()

njsq=0

board=[[int(x) for x in m[i]] for i in range(9)]

if solve_sudo(board):

print("数独已解：")

for x in board:

print(x)

else:

print("数独无解。")