使用Python编写程序求解数独游戏答案

问题描述：数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

解题建议：遇到问题后，最好先手工推导和模拟一下，把思路理清楚，然后再动手写代码。

参考代码：

import random

def init():
    # 初始状态，每个格内都是1-9之间的数字
    grids = {(r, c):list(range(1,10))\
             for r in range(9) for c in range(9)}
    # 根据文件中的位置和数字设置数独游戏初始状态
    with open('values.txt') as fp:
        for line in fp:
            line = line.strip()
            if line == '0':
                break
            row, col, value = map(int, line.split(','))
            grids[(row,col)] = value
    return grids

def eachGrid(grids, row, col, value):
    tempValue = grids[(row,col)]
    # 删除不可能的数字
    if isinstance(tempValue, list):
        if value in tempValue:
            tempValue.remove(value)
        # 如果格内只有一个数字，就拿出来填充
        if len(tempValue) == 1:
            grids[(row,col)] = tempValue[0]

def solve(oldGrids):
    grids = oldGrids.copy()
    for r in range(9):
        for c in range(9):
            value = grids[(r,c)]
            if isinstance(value, int):
                # 处理同一列
                for rr in range(9):
                    eachGrid(grids, rr, c, value)
                # 处理同一行
                for cc in range(9):
                    eachGrid(grids, r, cc, value)
                # 处理小九宫格内的数字
                rowStart = r//3 * 3
                colStart = c//3 * 3
                for rr in range(rowStart, rowStart+3):
                    for cc in range(colStart, colStart+3):
                        eachGrid(grids, rr, cc, value)
            elif isinstance(value, list) and len(value)==1:
                # 当前格内只有一个数了，拿出来填充
                grids[(r,c)] = value[0]
    return grids

def output(grids):
    '''输出grids中的内容'''
    for row in range(9):
        for col in range(9):
            value = grids[(row,col)]
            if isinstance(value, int):
                print(grids[(row,col)], end=' ')
            else:
                print(' ', end=' ')
        print()

def check(grids):
    '''检查grids是否满足数独游戏要求'''
    for rc in range(9):
        row = {grids[(rc,c)] for c in range(9)}
        if len(row) != 9:
            return False
        col = {grids[(r,rc)] for r in range(9)}
        if len(col) != 9:
            return False
    for row in range(0,9,3):
        for col in range(0,9,3):
            value = {grids[(r,c)]\
                     for r in range(row,row+3)\
                     for c in range(col,col+3)}
            if len(value) != 9:
                return False
    return True

def main(oldGrids):
    grids = oldGrids.copy()
    steps = 0
    while True:
        steps += 1
        grids = solve(grids)
        if steps > 20:
            try:
                position = [(r,c)\
                            for r in range(9) for c in range(9)\
                            if isinstance(grids[(r,c)],list)][0]
                grids[position] = random.choice(grids[position])
            except:
                grids = oldGrids.copy()
                steps = 0
                continue
       
        if all({isinstance(grids[(r,c)], int)\
                for r in range(9) for c in range(9)}):
            if check(grids):
                return grids
            else:
                # 当前选择无效，恢复原状，选择下一个
                grids = oldGrids.copy()
                steps = 0
               
grids = init()
output(grids)
result = main(grids)
print('='*30)
output(result)
print(check(result))

代码中使用的文本文件values.txt中内容格式，以第一行为例，0,2,9表示第0行第2列的初始数字为9：

运行结果一：

运行结果二：

运行结果三：

运行结果四：