基于最小剩余值(MRV)的回溯搜索(BTS)算法求解sudoku

Question

Intro

我编写了这段代码来解决数独问题，作为人工智能课程分配(现在关闭)的一部分。程序工作正常，我对代码很满意。请让我知道我是否有理由感到高兴，或者说执行工作是否会好得多。

这是一个纯粹的代码评审问题，所以不要拘泥于任何事情。

问题

输入

输入是一个代表sudoku板的81个字符串，其数字按行排列.空空格由零表示。

000000000302540000050301070000000004409006005023054790000000050700810000080060009

输出

程序必须将解决的sudoku板以与输入相同的字符串表示形式输出到文本文件output.txt。

148697523372548961956321478567983214419276385823154796691432857735819642284765139

算法

该算法基于回溯搜索 (glorified )算法，同时还引入了一种启发式算法，将sudoku作为约束满意度问题( CSP )来改进结果。启发式最小剩余值倾向于先对那些有最少可用选项的变量进行赋值。(从直觉上看，这就像是试图先解决更困难的问题，这样，如果事情不顺利，我们就可以更快地回溯。)

算法(来自艾玛) :-

function RECURSIVE-BACKTRACKING(assignment, csp) returns a solution, or failure
    if assignment is complete then return assignment
    var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp)
    for each value in ORDER-DOMAIN-VALUES(var , assignment, csp) do
        if value is consistent with assignment according to CONSTRAINTS[csp] then
            add {var = value} to assignment
            result ← RECURSIVE-BACKTRACKING(assignment, csp)
            if result != failure then return result
            remove {var = value} from assignment
    return failure

码

以下是供评审的代码：-

import sys
import numpy as np
from functools import reduce

# Instructions:
# Linux>> python3 driver_3.py <soduku_str>
# Windows py3\> python driver_3.py <soduku_str>

# Inputs
print("input was:", sys.argv)
soduku_str=sys.argv[1]

def str2arr(soduku_str):
    "Converts soduku_str to 2d array"
    return np.array([int(s) for s in list(soduku_str)]).reshape((9,9))

soduku = str2arr(soduku_str)

slices = [slice(0,3), slice(3,6), slice(6,9)]
s1,s2,s3 = slices
allgrids=[(si,sj) for si in [s1,s2,s3] for sj in [s1,s2,s3]] # Makes 2d slices for grids

def var2grid(var):
    "Returns the grid slice (3x3) to which the variable's coordinates belong "
    row,col = var
    grid = ( slices[int(row/3)], slices[int(col/3)] )
    return grid

FULLDOMAIN = np.array(range(1,10)) #All possible values (1-9)


# Constraints
def unique_rows(soduku):
    for row in soduku:
        if not np.array_equal(np.unique(row),np.array(range(1,10))) :
            return False
    return True
def unique_columns(soduku):
    for row in soduku.T: #transpose soduku to get columns
        if not np.array_equal(np.unique(row),np.array(range(1,10))) :
            return False
    return True

def unique_grids(soduku):
    for grid in allgrids: 
        if not np.array_equal(np.unique(soduku[grid]),np.array(range(1,10))) :
            return False
    return True

def  isComplete(soduku):
    if 0 in soduku:
        return False
    else:
        return True


def checkCorrect(soduku):
    if unique_columns(soduku):
        if unique_rows(soduku):
            if unique_grids(soduku):
                return True
    return False


# Search
def getDomain(var, soduku):
    "Gets the remaining legal values (available domain) for an unfilled box `var` in `soduku`"
    row,col = var
    #ravail = np.setdiff1d(FULLDOMAIN, soduku[row,:])
    #cavail = np.setdiff1d(FULLDOMAIN, soduku[:,col])
    #gavail = np.setdiff1d(FULLDOMAIN, soduku[var2grid(var)])
    #avail_d = reduce(np.intersect1d, (ravail,cavail,gavail))
    used_d = reduce(np.union1d, (soduku[row,:], soduku[:,col], soduku[var2grid(var)]))
    avail_d = np.setdiff1d(FULLDOMAIN, used_d)
    #print(var, avail_d)
    return avail_d

def selectMRVvar(vars, soduku):
    """
    Returns the unfilled box `var` with minimum remaining [legal] values (MRV) 
    and the corresponding values (available domain)
    """
    #Could this be improved?
    avail_domains = [getDomain(var,soduku) for var in vars]
    avail_sizes = [len(avail_d) for avail_d in avail_domains]
    index = np.argmin(avail_sizes)
    return vars[index], avail_domains[index]

def BT(soduku):
    "Backtracking search to solve soduku"
    # If soduku is complete return it.
    if isComplete(soduku):
        return soduku
    # Select the MRV variable to fill
    vars = [tuple(e) for e in np.transpose(np.where(soduku==0))]
    var, avail_d = selectMRVvar(vars, soduku)
    # Fill in a value and solve further (recursively), 
    # backtracking an assignment when stuck
    for value in avail_d:
        soduku[var] = value
        result = BT(soduku)
        if np.any(result):
            return result
        else:
            soduku[var] = 0
    return False


# Solve
print("solved:\n", BT(soduku))
print("correct:", checkCorrect(soduku))


# Output
with open('output.txt','w') as f:
    output_str = np.array2string(soduku.ravel(), max_line_width=90, separator='').strip('[]') + ' Solved with BTS'
    f.write(output_str)

Answer 1

你的阿尔法不错，我有几个造型挑剔的人。

1. 使用if__name__ == '__main__' --这将确保当您导入此脚本时，根行不会被执行。
2. 阅读PEP8 Python
   • 函数和变量应该是snake_case

3. 以@DJHenjin正确的状态直接返回，您不需要嵌套的if语句。def checkCorrect(soduku)：if unique_columns(soduku)：if unique_rows(soduku)：if unique_grids(soduku)：返回真返回False (Soduku)可以重写为def check_correct(soduku)：返回unique_columns(soduku)和unique_rows(soduku)和unique_grids(soduku)
4. 您可以使用np.array_equal(np.unique(soduku网格)，或any使其更漂亮，def unique_grids(soduku)：对于所有网格中的网格:如果没有，则为all np.array(范围(1，10))：返回假返回True可以重写为def unique_grid(sudoku)：返回all(np.array_equal(np.unique(soduku网格)，Np.array(范围(1，10))用于all_grids中的网格)与其他unique_*相同
5. 删除无用的注释#如果soduku是完整的，返回它。如果is_complete( soduku )：返回soduku，代码是非常自我解释的，而这个注释只会增加噪音。