数独人工算法的python实现，人工算法python,目前只有两个解法，对一般

数独人工算法的python实现，人工算法python,目前只有两个解法，对一般

目前只有两个解法，对一般的数独题均能应付。从sudoku up2010上不同难度的个选了3个，其中困难的未解出，非常困难的解出一个。解题思路间代码注释部分。

sudoku.py

# _*_ coding = utf-8 _*_def gather_col_row(row, col, sudoku):    """收集二维数组sudoku(mxm)中元素(row, col)所在行的元素至rows中，所在列的元素至cols中"""    rows = []    cols = []    m    = len(sudoku)    for i in range(m):        rows.append(sudoku[row][i])        cols.append(sudoku[i][col])    return rows, colsdef gather_block(row, col, sudoku):    """收集二维数组sudoku(mxm)中元素(row, col)所在的宫中的元素的列表"""    blocks = []    i = row // 3    j = col // 3    for k in range(i*3, (i+1)*3):        blocks += sudoku[k][j*3 : (j+1)*3]    return blocksdef position(sudoku):    """返回sudoku中0所在的位置(row, col),即没有数的位置的列表，如[(2,3),(0,8)]"""    return [(row, col) for row in range(9) for col in range(9) if sudoku[row][col] == 0]def possible_dict(sudoku):    """以字典形式返回sudoku中所有0元素位置中可能放置的数字，键为(row,col)对，值为可能数的集合，如{(2, 3):{2,4,5}}"""    digits = {1, 2, 3, 4, 5, 6, 7, 8, 9}    ans = {}    for pos in position(sudoku):        row, col = pos        rows, cols = gather_col_row(row, col, sudoku)        blocks = gather_block(row, col, sudoku)        possible   = digits - set(rows) - set(cols) - set(blocks)        ans[pos] = possible    return ansdef possible_set(row, col, sudoku):    """以集合形式返回sudoku中(row, col)元素中可能放置的数字，如{2,4,5}"""    digits = {1, 2, 3, 4, 5, 6, 7, 8, 9}    rows, cols = gather_col_row(row, col, sudoku)    blocks = gather_block(row, col, sudoku)    possible_num   = digits - set(rows) - set(cols) - set(blocks)    return possible_numdef by_row_col(seq, row_or_col):    """按行或按列收集序列seq中的元素,row_or_col=0,按行，1，按列,用于解法二"""    row = list(set([i[row_or_col] for i in seq]))    ans = []    for r in row:        tmp = []        for s in seq:            if s[row_or_col] == r:                tmp.append(s)        ans.append(tmp)    return ansdef solve1(sudoku):    # 解法一：元素所在位置的行、列及块的交集中只有一个数的情况，也是最简单的情况    update = True    while update:        update = False        for k, v in possible_dict(sudoku).items():            if len(v) == 1:                sudoku[k[0]][k[1]] = list(v)[0]                update = True    return Nonedef unique(seq):    # 返回系列seq中只出现一次的数字和它的位置    # seq形如[((2,6),{9,5,6}),((2,7),{9,6}),((row,col),{possible_number})]    numbers = []    unique_num = []    for a in seq:       for i in a[1]:           numbers.append(i)    for num in numbers:       if numbers.count(num) == 1:           unique_num.append(num)    position = []    for unum in  unique_num:        for a in seq:            if unum in a[1]:                position.append(a[0])    return position, unique_numdef solve2(sudoku):    # 解法二：分别按照行、按列、按块，如果某个数仅出现一次，则该位置为该数    # 如(8,8):{8,9,2,7},(8,7):{8,9,2},(8,5):{8,2},(8,1):{8,9,2},则(8,8):{7}    update = True    while update:        update = False        pos = position(sudoku)        possible = possible_dict(sudoku)        # 按行        rows = by_row_col(pos, 0)        for row in rows:            pos_num = unique([(p, possible[p]) for p in row])            if pos_num[0]:                for i in range(0, len(pos_num), 2):   # pos_num中可能返回的数不止一个                    sudoku[pos_num[i][0][0]][pos_num[i][0][1]] = pos_num[i+1][0]                    update = True        # 按列        cols = by_row_col(pos, 1)        for col in cols:            pos_num = unique([(p, possible[p]) for p in col])            if pos_num[0]:                for i in range(0, len(pos_num), 2):   # pos_num中可能返回的数不止一个                    sudoku[pos_num[i][0][0]][pos_num[i][0][1]] = pos_num[i+1][0]                    update = True        solve1(sudoku)    return Noneif __name__ == "__main__":    """sudoku = [[0, 0, 2, 0, 4, 0, 8, 0, 0],              [9, 5, 0, 0, 0, 0, 0, 4, 1],              [0, 0, 0, 2, 0, 3, 0, 0, 0],              [0, 6, 0, 9, 0, 5, 0, 1, 0],              [7, 0, 0, 0, 0, 0, 0, 0, 4],              [0, 3, 0, 6, 0, 4, 0, 5, 0],              [0, 0, 0, 7, 0, 6, 0, 0, 0],              [4, 7, 0, 0, 0, 0, 0, 3, 5],              [0, 0, 6, 0, 3, 0, 1, 0, 0]]"""    sudokus = []    difficulty = []    f = open('sudoku.txt', 'r')    for line in f.readlines():        line = line.strip()        if line.startswith('#'):            difficulty.append(line[1:])        else:            numbers = line.split(',')            sudoku = []            for number in numbers:                tmp = []                for num in number:                    tmp.append(int(num))                sudoku.append(tmp)            sudokus.append(sudoku)    f.close()    cnt = 0    for sudoku in sudokus:        print(difficulty[cnt//3])        sdk = sudoku[:]        solve1(sudoku)        solve2(sudoku)        for i in range(9):            print(sudoku[i], "\t", sdk[i])        cnt += 1        input()

sudoku.txt

# very easy000010902,020460007,679200400,901000023,000103649,003972801,097051000,340807096,800000275607910000,000040670,301600024,004070006,726084090,030090247,503420010,010768539,000031400825000416,470152080,903060000,000720950,502801700,000043062,040000090,251370040,030204170# easy080000000,100300500,096102037,020930085,000008764,650700200,060870420,010005678,007060300904806057,050010000,008047900,400000000,076390080,890700004,561900008,300060592,209403000500019000,830600010,100030070,000041700,014300500,000200601,309578100,251090860,000062903# moderate060000009,700100030,050006000,005007000,000092054,100450600,400000763,200804910,003069042000500002,020000900,600902350,080206000,001008004,400100000,200030089,004829013,008061070530006094,012004070,490002065,960500000,001200480,080000000,300100700,000490501,100000008# difficult000000100,096200800,800000600,100082003,000140060,760050000,600400901,004020000,950001000700040080,010080204,000005000,079000800,030604007,040030020,800000010,000860700,007100090050031460,000090000,038060700,000000000,000100270,207500001,070000500,060020904,400800100# very difficult142000387,003040201,080132005,090000106,000520704,000004000,608200009,020000000,001070000041020000,000000007,080005200,610080000,000010460,000490050,006000000,437009106,102000090003279000,020501009,000080003,000060500,690003000,005000000,000000064,700600080,060920007