时间戳

首页 > 解决方案 > 我的数独模拟器的验证功能有什么问题吗？

python - 我的数独模拟器的验证功能有什么问题吗？

问题描述

我最近正在使用 python 构建一个数独模拟器，我很困惑为什么我的验证函数不能按预期工作。我尝试使用另一种使用 3 个 for 循环的验证方法，它有效，所以我认为我的解决方法没有问题。基本上如果在同一行、列或对角线上有相同的数字，它将返回 False，否则返回 True

def validate1(grid, r, c, val):
    var = 0
    r_up = r-var
    r_down = r+var
    c_right = c+var
    c_left = c-var
    while(r_up>=0 or r_down<=8 or c_right<=8 or c_left>=0):
        if(r_up>=0):
            if(grid[r_up][c]==val):
                return False
        if(r_down<=8):
            #print("down" + str(grid[r_down][c]))
            if(grid[r_down][c]==val):
                return False
        if(c_right<=8):
            if(grid[r][c_right]==val):
                return False
        if(c_left>=0):
            if(grid[r][c_left]==val):
                return False
        if(r_up>=0 and c_right<=8):
            if(grid[r_up][c_right]==val):
                return False
        if(r_up>=0 and c_left>=0):
            if(grid[r_up][c_left]==val):
                return False
        if(r_down<=8 and c_right<=8):
            if(grid[r_down][c_right]==val):
                return False
        if(r_down<=8 and c_left>=0):
            if(grid[r_down][c_left]==val):
                return False
        var = var + 1
        r_up = r-var
        r_down = r+var
        c_right = c+var
        c_left = c-var
    return True

标签： pythonalgorithmvalidationsudoku

解决方案

我建议不要试图找出问题所在，而是让函数更简单（并且更 Pythonic）：

def validate1(grid,r,c,val):
    if val in grid[r] : return False
    if val in (row[c] for row in grid): return False
    if any(val in row[c//3*3:][:3] for row in grid[r//3*3:][:3]): return False
    return True

但是，像这样检查冲突并不是最快的方法。你可以做的是维护27组已使用的号码，对应于板上的专属组。每个位置映射到这些组中的 3 个（行、列、块），因此您可以快速将放置的数字添加到它们，并使用集合成员快速检查是否存在冲突的数字。这可以通过将数字与其组索引相结合来进一步改进，从而允许您使用一组 243 个 groupID-number 对来管理冲突。有了这个，您可以编写一个非常紧凑的数独求解器，带有回溯功能，可以蛮力解决问题：

def shortSudokuSolve(board):
    size    = len(board)
    block   = int(size**0.5)
    board   = [n for row in board for n in row ]      
    span    = { (n,p): { (g,n)  for g in (n>0)*[p//size, size+p%size, 2*size+p%size//block+p//size//block*block] }
                for p in range(size*size) for n in range(size+1) }
    empties = [i for i,n in enumerate(board) if n==0 ]
    used    = {gn for p,n in enumerate(board) for gn in span[n,p] if n}
    empty   = 0
    while empty>=0 and empty<len(empties):
        pos        = empties[empty]
        used      -= span[board[pos],pos]
        board[pos] = next((n for n in range(board[pos]+1,size+1) if not span[n,pos]&used),0)
        used      |= span[board[pos],pos]
        empty     += 1 if board[pos] else -1
    return [board[r:r+size] for r in range(0,size*size,size)]

推荐阅读