数独求解算法

Question

我想用 python 编写代码来解决数独难题。你们知道用于此目的的好算法吗？我在网上的某个地方读到了一种算法，该算法通过用所有可能的数字填充整个盒子，然后将已知值插入相应的盒子来解决这个问题。从已知值的行和列中，已知值被删除。如果你们知道更好的话比这个算法请帮我写一个。我也很困惑我应该如何从用户那里读取已知值。通过控制台一一输入数值确实很困难。除了使用 gui 之外，还有什么简单的方法吗？

Answer 1

这是我用 python 编写的数独解算器。它使用简单的回溯算法来解决难题。
为了简单起见，没有进行输入验证或奇特的输出。这是解决问题的最低限度代码。

算法

1. 查找给定单元格的所有合法值
2. 对于每个合法值，递归地尝试求解网格

解决方案

需要 9X9 网格，部分填充数字。值为 0 的单元格表示该单元格未填充。

代码

def findNextCellToFill(grid, i, j):
        for x in range(i,9):
                for y in range(j,9):
                        if grid[x][y] == 0:
                                return x,y
        for x in range(0,9):
                for y in range(0,9):
                        if grid[x][y] == 0:
                                return x,y
        return -1,-1

def isValid(grid, i, j, e):
        rowOk = all([e != grid[i][x] for x in range(9)])
        if rowOk:
                columnOk = all([e != grid[x][j] for x in range(9)])
                if columnOk:
                        # finding the top left x,y co-ordinates of the section containing the i,j cell
                        secTopX, secTopY = 3 *(i//3), 3 *(j//3) #floored quotient should be used here. 
                        for x in range(secTopX, secTopX+3):
                                for y in range(secTopY, secTopY+3):
                                        if grid[x][y] == e:
                                                return False
                        return True
        return False

def solveSudoku(grid, i=0, j=0):
        i,j = findNextCellToFill(grid, i, j)
        if i == -1:
                return True
        for e in range(1,10):
                if isValid(grid,i,j,e):
                        grid[i][j] = e
                        if solveSudoku(grid, i, j):
                                return True
                        # Undo the current cell for backtracking
                        grid[i][j] = 0
        return False

测试代码

>>> input = [[5,1,7,6,0,0,0,3,4],[2,8,9,0,0,4,0,0,0],[3,4,6,2,0,5,0,9,0],[6,0,2,0,0,0,0,1,0],[0,3,8,0,0,6,0,4,7],[0,0,0,0,0,0,0,0,0],[0,9,0,0,0,0,0,7,8],[7,0,3,4,0,0,5,6,0],[0,0,0,0,0,0,0,0,0]]
>>> solveSudoku(input)
True
>>> input
[[5, 1, 7, 6, 9, 8, 2, 3, 4], [2, 8, 9, 1, 3, 4, 7, 5, 6], [3, 4, 6, 2, 7, 5, 8, 9, 1], [6, 7, 2, 8, 4, 9, 3, 1, 5], [1, 3, 8, 5, 2, 6, 9, 4, 7], [9, 5, 4, 7, 1, 3, 6, 8, 2], [4, 9, 5, 3, 6, 2, 1, 7, 8], [7, 2, 3, 4, 8, 1, 5, 6, 9], [8, 6, 1, 9, 5, 7, 4, 2, 3]]

上面是非常基本的回溯算法，在很多地方都有解释。但我遇到的最有趣、最自然的数独解决策略是这个 来自此处

Answer 2

我还用 Python 编写了一个数独求解器。这也是一个回溯算法，但我也想分享我的实现。

回溯可以足够快，因为它在限制范围内移动并且明智地选择单元格。您可能还想查看我在此线程中关于优化算法的回答。但这里我将重点关注算法和代码本身。

该算法的要点是开始迭代网格并决定要做什么 - 填充单元格，或尝试同一单元格的另一个数字，或清空一个单元格并移回前一个单元格，等等。值得注意的是没有确定的方法可以知道解决这个难题需要多少步骤或迭代。因此，您实际上有两个选择 - 使用 while 循环或使用递归。它们都可以继续迭代，直到找到解决方案或直到证明缺乏解决方案。递归的优点是能够进行分支，一般支持更复杂的逻辑和算法，但缺点是实现起来比较困难，调试起来也比较棘手。对于回溯的实现，我使用了 while 循环，因为不需要分支，该算法以单线程线性方式进行搜索。

逻辑如下：

While True：（主要迭代）

1. 如果所有空白单元格都已迭代并且迭代的最后一个空白单元格没有任何剩余数字可供尝试 - 在此停止，因为没有解决方案。
2. 如果没有空白单元格，则验证网格。如果网格有效，则在此停止并返回解决方案。
3. 如果有空白单元格，请选择下一个单元格。如果该单元格至少有一个可能的数字，则分配它并继续下一个主迭代。
4. 如果当前单元格至少有一个剩余选择，并且没有空白单元格或所有空白单元格都已迭代，则分配剩余选择并继续下一次主迭代。
5. 如果以上都不成立，那么是时候回溯了。清空当前单元格并进入下面的循环。

While True：（回溯迭代）

1. 如果没有更多单元格可以回溯到 - 在此停止，因为有
   是没有解决办法。
2. 根据回溯历史选择上一个单元格。
3. 如果该单元格没有任何选择，则将该单元格清空并
   继续下一次回溯迭代。
4. 将下一个可用数字分配给当前单元格，从
   回溯并返回到主要迭代。

该算法的一些特点：

• 它以相同的顺序记录访问过的单元格，以便随时回溯

• 它都会记录每个单元格的选择记录，这样它就不会在同一个单元格中尝试相同的数字两次

• 单元格的可用选择始终在数独约束内（行、列和 3x3 象限）

• 此特定实现有几种不同的方法来根据输入参数选择下一个单元格和下一个数字（优化线程中的更多信息）

• 如果给定一个空白网格，那么它将生成一个有效的数独谜题（与优化参数“C”一起使用，以便每次生成随机网格时间）

• 如果给定一个已解决的网格，它会识别它并打印一条消息

完整的代码是：

import random, math, time

class Sudoku:
    def __init__( self, _g=[] ):
        self._input_grid = [] # store a copy of the original input grid for later use
        self.grid = [] # this is the main grid that will be iterated
        for i in _g: # copy the nested lists by value, otherwise Python keeps the reference for the nested lists
            self._input_grid.append( i[:] )
            self.grid.append( i[:] )

    self.empty_cells = set() # set of all currently empty cells (by index number from left to right, top to bottom)
    self.empty_cells_initial = set() # this will be used to compare against the current set of empty cells in order to determine if all cells have been iterated
    self.current_cell = None # used for iterating
    self.current_choice = 0 # used for iterating
    self.history = [] # list of visited cells for backtracking
    self.choices = {} # dictionary of sets of currently available digits for each cell
    self.nextCellWeights = {} # a dictionary that contains weights for all cells, used when making a choice of next cell
    self.nextCellWeights_1 = lambda x: None # the first function that will be called to assign weights
    self.nextCellWeights_2 = lambda x: None # the second function that will be called to assign weights
    self.nextChoiceWeights = {} # a dictionary that contains weights for all choices, used when selecting the next choice
    self.nextChoiceWeights_1 = lambda x: None # the first function that will be called to assign weights
    self.nextChoiceWeights_2 = lambda x: None # the second function that will be called to assign weights

    self.search_space = 1 # the number of possible combinations among the empty cells only, for information purpose only
    self.iterations = 0 # number of main iterations, for information purpose only
    self.iterations_backtrack = 0 # number of backtrack iterations, for information purpose only

    self.digit_heuristic = { 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 } # store the number of times each digit is used in order to choose the ones that are least/most used, parameter "3" and "4"
    self.centerWeights = {} # a dictionary of the distances for each cell from the center of the grid, calculated only once at the beginning

    # populate centerWeights by using Pythagorean theorem
    for id in range( 81 ):
        row = id // 9
        col = id % 9
        self.centerWeights[ id ] = int( round( 100 * math.sqrt( (row-4)**2 + (col-4)**2 ) ) )



    # for debugging purposes
    def dump( self, _custom_text, _file_object ):
        _custom_text += ", cell: {}, choice: {}, choices: {}, empty: {}, history: {}, grid: {}\n".format(
            self.current_cell, self.current_choice, self.choices, self.empty_cells, self.history, self.grid )
        _file_object.write( _custom_text )

    # to be called before each solve of the grid
    def reset( self ):
        self.grid = []
        for i in self._input_grid:
            self.grid.append( i[:] )

        self.empty_cells = set()
        self.empty_cells_initial = set()
        self.current_cell = None
        self.current_choice = 0
        self.history = []
        self.choices = {}

        self.nextCellWeights = {}
        self.nextCellWeights_1 = lambda x: None
        self.nextCellWeights_2 = lambda x: None
        self.nextChoiceWeights = {}
        self.nextChoiceWeights_1 = lambda x: None
        self.nextChoiceWeights_2 = lambda x: None

        self.search_space = 1
        self.iterations = 0
        self.iterations_backtrack = 0

        self.digit_heuristic = { 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }

    def validate( self ):
        # validate all rows
        for x in range(9):
            digit_count = { 0:1, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }
            for y in range(9):
                digit_count[ self.grid[ x ][ y ] ] += 1
            for i in digit_count:
                if digit_count[ i ] != 1:
                    return False

        # validate all columns
        for x in range(9):
            digit_count = { 0:1, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }
            for y in range(9):
                digit_count[ self.grid[ y ][ x ] ] += 1
            for i in digit_count:
                if digit_count[ i ] != 1:
                    return False

        # validate all 3x3 quadrants
        def validate_quadrant( _grid, from_row, to_row, from_col, to_col ):
            digit_count = { 0:1, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }
            for x in range( from_row, to_row + 1 ):
                for y in range( from_col, to_col + 1 ):
                    digit_count[ _grid[ x ][ y ] ] += 1
            for i in digit_count:
                if digit_count[ i ] != 1:
                    return False
            return True

        for x in range( 0, 7, 3 ):
            for y in range( 0, 7, 3 ):
                if not validate_quadrant( self.grid, x, x+2, y, y+2 ):
                    return False
        return True

    def setCell( self, _id, _value ):
        row = _id // 9
        col = _id % 9
        self.grid[ row ][ col ] = _value

    def getCell( self, _id ):
        row = _id // 9
        col = _id % 9
        return self.grid[ row ][ col ]

    # returns a set of IDs of all blank cells that are related to the given one, related means from the same row, column or quadrant
    def getRelatedBlankCells( self, _id ):
        result = set()
        row = _id // 9
        col = _id % 9

        for i in range( 9 ):
            if self.grid[ row ][ i ] == 0: result.add( row * 9 + i )
        for i in range( 9 ):
            if self.grid[ i ][ col ] == 0: result.add( i * 9 + col )
        for x in range( (row//3)*3, (row//3)*3 + 3 ):
            for y in range( (col//3)*3, (col//3)*3 + 3 ):
                if self.grid[ x ][ y ] == 0: result.add( x * 9 + y )

        return set( result ) # return by value

    # get the next cell to iterate
    def getNextCell( self ):
        self.nextCellWeights = {}
        for id in self.empty_cells:
            self.nextCellWeights[ id ] = 0

        self.nextCellWeights_1( 1000 ) # these two functions will always be called, but behind them will be a different weight function depending on the optimization parameters provided
        self.nextCellWeights_2( 1 )

        return min( self.nextCellWeights, key = self.nextCellWeights.get )

    def nextCellWeights_A( self, _factor ): # the first cell from left to right, from top to bottom
        for id in self.nextCellWeights:
            self.nextCellWeights[ id ] += id * _factor

    def nextCellWeights_B( self, _factor ): # the first cell from right to left, from bottom to top
        self.nextCellWeights_A( _factor * -1 )

    def nextCellWeights_C( self, _factor ): # a randomly chosen cell
        for id in self.nextCellWeights:
            self.nextCellWeights[ id ] += random.randint( 0, 999 ) * _factor

    def nextCellWeights_D( self, _factor ): # the closest cell to the center of the grid
        for id in self.nextCellWeights:
            self.nextCellWeights[ id ] += self.centerWeights[ id ] * _factor

    def nextCellWeights_E( self, _factor ): # the cell that currently has the fewest choices available
        for id in self.nextCellWeights:
            self.nextCellWeights[ id ] += len( self.getChoices( id ) ) * _factor

    def nextCellWeights_F( self, _factor ): # the cell that currently has the most choices available
        self.nextCellWeights_E( _factor * -1 )

    def nextCellWeights_G( self, _factor ): # the cell that has the fewest blank related cells
        for id in self.nextCellWeights:
            self.nextCellWeights[ id ] += len( self.getRelatedBlankCells( id ) ) * _factor

    def nextCellWeights_H( self, _factor ): # the cell that has the most blank related cells
        self.nextCellWeights_G( _factor * -1 )

    def nextCellWeights_I( self, _factor ): # the cell that is closest to all filled cells
        for id in self.nextCellWeights:
            weight = 0
            for check in range( 81 ):
                if self.getCell( check ) != 0:
                    weight += math.sqrt( ( id//9 - check//9 )**2 + ( id%9 - check%9 )**2 )

    def nextCellWeights_J( self, _factor ): # the cell that is furthest from all filled cells
        self.nextCellWeights_I( _factor * -1 )

    def nextCellWeights_K( self, _factor ): # the cell whose related blank cells have the fewest available choices
        for id in self.nextCellWeights:
            weight = 0
            for id_blank in self.getRelatedBlankCells( id ):
                weight += len( self.getChoices( id_blank ) )
            self.nextCellWeights[ id ] += weight * _factor

    def nextCellWeights_L( self, _factor ): # the cell whose related blank cells have the most available choices
        self.nextCellWeights_K( _factor * -1 )



    # for a given cell return a set of possible digits within the Sudoku restrictions
    def getChoices( self, _id ):
        available_choices = {1,2,3,4,5,6,7,8,9}
        row = _id // 9
        col = _id % 9

        # exclude digits from the same row
        for y in range( 0, 9 ):
            if self.grid[ row ][ y ] in available_choices:
                available_choices.remove( self.grid[ row ][ y ] )

        # exclude digits from the same column
        for x in range( 0, 9 ):
            if self.grid[ x ][ col ] in available_choices:
                available_choices.remove( self.grid[ x ][ col ] )

        # exclude digits from the same quadrant
        for x in range( (row//3)*3, (row//3)*3 + 3 ):
            for y in range( (col//3)*3, (col//3)*3 + 3 ):
                if self.grid[ x ][ y ] in available_choices:
                    available_choices.remove( self.grid[ x ][ y ] )

        if len( available_choices ) == 0: return set()
        else: return set( available_choices ) # return by value

    def nextChoice( self ):
        self.nextChoiceWeights = {}
        for i in self.choices[ self.current_cell ]:
            self.nextChoiceWeights[ i ] = 0

        self.nextChoiceWeights_1( 1000 )
        self.nextChoiceWeights_2( 1 )

        self.current_choice = min( self.nextChoiceWeights, key = self.nextChoiceWeights.get )
        self.setCell( self.current_cell, self.current_choice )
        self.choices[ self.current_cell ].remove( self.current_choice )

    def nextChoiceWeights_0( self, _factor ): # the lowest digit
        for i in self.nextChoiceWeights:
            self.nextChoiceWeights[ i ] += i * _factor

    def nextChoiceWeights_1( self, _factor ): # the highest digit
        self.nextChoiceWeights_0( _factor * -1 )

    def nextChoiceWeights_2( self, _factor ): # a randomly chosen digit
        for i in self.nextChoiceWeights:
            self.nextChoiceWeights[ i ] += random.randint( 0, 999 ) * _factor

    def nextChoiceWeights_3( self, _factor ): # heuristically, the least used digit across the board
        self.digit_heuristic = { 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }
        for id in range( 81 ):
            if self.getCell( id ) != 0: self.digit_heuristic[ self.getCell( id ) ] += 1
        for i in self.nextChoiceWeights:
            self.nextChoiceWeights[ i ] += self.digit_heuristic[ i ] * _factor

    def nextChoiceWeights_4( self, _factor ): # heuristically, the most used digit across the board
        self.nextChoiceWeights_3( _factor * -1 )

    def nextChoiceWeights_5( self, _factor ): # the digit that will cause related blank cells to have the least number of choices available
        cell_choices = {}
        for id in self.getRelatedBlankCells( self.current_cell ):
            cell_choices[ id ] = self.getChoices( id )

        for c in self.nextChoiceWeights:
            weight = 0
            for id in cell_choices:
                weight += len( cell_choices[ id ] )
                if c in cell_choices[ id ]: weight -= 1
            self.nextChoiceWeights[ c ] += weight * _factor

    def nextChoiceWeights_6( self, _factor ): # the digit that will cause related blank cells to have the most number of choices available
        self.nextChoiceWeights_5( _factor * -1 )

    def nextChoiceWeights_7( self, _factor ): # the digit that is the least common available choice among related blank cells
        cell_choices = {}
        for id in self.getRelatedBlankCells( self.current_cell ):
            cell_choices[ id ] = self.getChoices( id )

        for c in self.nextChoiceWeights:
            weight = 0
            for id in cell_choices:
                if c in cell_choices[ id ]: weight += 1
            self.nextChoiceWeights[ c ] += weight * _factor

    def nextChoiceWeights_8( self, _factor ): # the digit that is the most common available choice among related blank cells
        self.nextChoiceWeights_7( _factor * -1 )

    def nextChoiceWeights_9( self, _factor ): # the digit that is the least common available choice across the board
        cell_choices = {}
        for id in range( 81 ):
            if self.getCell( id ) == 0:
                cell_choices[ id ] = self.getChoices( id )

        for c in self.nextChoiceWeights:
            weight = 0
            for id in cell_choices:
                if c in cell_choices[ id ]: weight += 1
            self.nextChoiceWeights[ c ] += weight * _factor

    def nextChoiceWeights_a( self, _factor ): # the digit that is the most common available choice across the board
        self.nextChoiceWeights_9( _factor * -1 )



    # the main function to be called
    def solve( self, _nextCellMethod, _nextChoiceMethod, _start_time, _prefillSingleChoiceCells = False ):
        s = self
        s.reset()

        # initialize optimization functions based on the optimization parameters provided
        """
        A - the first cell from left to right, from top to bottom
        B - the first cell from right to left, from bottom to top
        C - a randomly chosen cell
        D - the closest cell to the center of the grid
        E - the cell that currently has the fewest choices available
        F - the cell that currently has the most choices available
        G - the cell that has the fewest blank related cells
        H - the cell that has the most blank related cells
        I - the cell that is closest to all filled cells
        J - the cell that is furthest from all filled cells
        K - the cell whose related blank cells have the fewest available choices
        L - the cell whose related blank cells have the most available choices
        """
        if _nextCellMethod[ 0 ] in "ABCDEFGHIJKLMN":
            s.nextCellWeights_1 = getattr( s, "nextCellWeights_" + _nextCellMethod[0] )
        elif _nextCellMethod[ 0 ] == " ":
            s.nextCellWeights_1 = lambda x: None
        else:
            print( "(A) Incorrect optimization parameters provided" )
            return False

        if len( _nextCellMethod ) > 1:
            if _nextCellMethod[ 1 ] in "ABCDEFGHIJKLMN":
                s.nextCellWeights_2 = getattr( s, "nextCellWeights_" + _nextCellMethod[1] )
            elif _nextCellMethod[ 1 ] == " ":
                s.nextCellWeights_2 = lambda x: None
            else:
                print( "(B) Incorrect optimization parameters provided" )
                return False
        else:
            s.nextCellWeights_2 = lambda x: None

        # initialize optimization functions based on the optimization parameters provided
        """
        0 - the lowest digit
        1 - the highest digit
        2 - a randomly chosen digit
        3 - heuristically, the least used digit across the board
        4 - heuristically, the most used digit across the board
        5 - the digit that will cause related blank cells to have the least number of choices available
        6 - the digit that will cause related blank cells to have the most number of choices available
        7 - the digit that is the least common available choice among related blank cells
        8 - the digit that is the most common available choice among related blank cells
        9 - the digit that is the least common available choice across the board
        a - the digit that is the most common available choice across the board
        """
        if _nextChoiceMethod[ 0 ] in "0123456789a":
            s.nextChoiceWeights_1 = getattr( s, "nextChoiceWeights_" + _nextChoiceMethod[0] )
        elif _nextChoiceMethod[ 0 ] == " ":
            s.nextChoiceWeights_1 = lambda x: None
        else:
            print( "(C) Incorrect optimization parameters provided" )
            return False

        if len( _nextChoiceMethod ) > 1:
            if _nextChoiceMethod[ 1 ] in "0123456789a":
                s.nextChoiceWeights_2 = getattr( s, "nextChoiceWeights_" + _nextChoiceMethod[1] )
            elif _nextChoiceMethod[ 1 ] == " ":
                s.nextChoiceWeights_2 = lambda x: None
            else:
                print( "(D) Incorrect optimization parameters provided" )
                return False
        else:
            s.nextChoiceWeights_2 = lambda x: None

        # fill in all cells that have single choices only, and keep doing it until there are no left, because as soon as one cell is filled this might bring the choices down to 1 for another cell
        if _prefillSingleChoiceCells == True:
            while True:
                next = False
                for id in range( 81 ):
                    if s.getCell( id ) == 0:
                        cell_choices = s.getChoices( id )
                        if len( cell_choices ) == 1:
                            c = cell_choices.pop()
                            s.setCell( id, c )
                            next = True
                if not next: break

        # initialize set of empty cells
        for x in range( 0, 9, 1 ):
            for y in range( 0, 9, 1 ):
                if s.grid[ x ][ y ] == 0:
                    s.empty_cells.add( 9*x + y )
        s.empty_cells_initial = set( s.empty_cells ) # copy by value

        # calculate search space
        for id in s.empty_cells:
            s.search_space *= len( s.getChoices( id ) )

        # initialize the iteration by choosing a first cell
        if len( s.empty_cells ) < 1:
            if s.validate():
                print( "Sudoku provided is valid!" )
                return True
            else:
                print( "Sudoku provided is not valid!" )
                return False
        else: s.current_cell = s.getNextCell()

        s.choices[ s.current_cell ] = s.getChoices( s.current_cell )
        if len( s.choices[ s.current_cell ] ) < 1:
            print( "(C) Sudoku cannot be solved!" )
            return False



        # start iterating the grid
        while True:
            #if time.time() - _start_time > 2.5: return False # used when doing mass tests and don't want to wait hours for an inefficient optimization to complete

            s.iterations += 1

            # if all empty cells and all possible digits have been exhausted, then the Sudoku cannot be solved
            if s.empty_cells == s.empty_cells_initial and len( s.choices[ s.current_cell ] ) < 1:
                print( "(A) Sudoku cannot be solved!" )
                return False

            # if there are no empty cells, it's time to validate the Sudoku
            if len( s.empty_cells ) < 1:
                if s.validate():
                    print( "Sudoku has been solved! " )
                    print( "search space is {}".format( self.search_space ) )
                    print( "empty cells: {}, iterations: {}, backtrack iterations: {}".format( len( self.empty_cells_initial ), self.iterations, self.iterations_backtrack ) )
                    for i in range(9):
                        print( self.grid[i] )
                    return True

            # if there are empty cells, then move to the next one
            if len( s.empty_cells ) > 0:

                s.current_cell = s.getNextCell() # get the next cell
                s.history.append( s.current_cell ) # add the cell to history
                s.empty_cells.remove( s.current_cell ) # remove the cell from the empty queue
                s.choices[ s.current_cell ] = s.getChoices( s.current_cell ) # get possible choices for the chosen cell

                if len( s.choices[ s.current_cell ] ) > 0: # if there is at least one available digit, then choose it and move to the next iteration, otherwise the iteration continues below with a backtrack
                    s.nextChoice()
                    continue

            # if all empty cells have been iterated or there are no empty cells, and there are still some remaining choices, then try another choice
            if len( s.choices[ s.current_cell ] ) > 0 and ( s.empty_cells == s.empty_cells_initial or len( s.empty_cells ) < 1 ): 
                s.nextChoice()
                continue

            # if none of the above, then we need to backtrack to a cell that was previously iterated
            # first, restore the current cell...
            s.history.remove( s.current_cell ) # ...by removing it from history
            s.empty_cells.add( s.current_cell ) # ...adding back to the empty queue
            del s.choices[ s.current_cell ] # ...scrapping all choices
            s.current_choice = 0
            s.setCell( s.current_cell, s.current_choice ) # ...and blanking out the cell

            # ...and then, backtrack to a previous cell
            while True:
                s.iterations_backtrack += 1

                if len( s.history ) < 1:
                    print( "(B) Sudoku cannot be solved!" )
                    return False

                s.current_cell = s.history[ -1 ] # after getting the previous cell, do not recalculate all possible choices because we will lose the information about has been tried so far

                if len( s.choices[ s.current_cell ] ) < 1: # backtrack until a cell is found that still has at least one unexplored choice...
                    s.history.remove( s.current_cell )
                    s.empty_cells.add( s.current_cell )
                    s.current_choice = 0
                    del s.choices[ s.current_cell ]
                    s.setCell( s.current_cell, s.current_choice )
                    continue

                # ...and when such cell is found, iterate it
                s.nextChoice()
                break # and break out from the backtrack iteration but will return to the main iteration

根据本文使用世界上最难的数独进行示例调用 http://www.telegraph.co.uk/news/science /science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html

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

mySudoku = Sudoku( hardest_sudoku )
start = time.time()
mySudoku.solve( "A", "0", time.time(), False )
print( "solved in {} seconds".format( time.time() - start ) )

示例输出为：

Sudoku has been solved!
search space is 9586591201964851200000000000000000000
empty cells: 60, iterations: 49559, backtrack iterations: 49498
[8, 1, 2, 7, 5, 3, 6, 4, 9]
[9, 4, 3, 6, 8, 2, 1, 7, 5]
[6, 7, 5, 4, 9, 1, 2, 8, 3]
[1, 5, 4, 2, 3, 7, 8, 9, 6]
[3, 6, 9, 8, 4, 5, 7, 2, 1]
[2, 8, 7, 1, 6, 9, 5, 3, 4]
[5, 2, 1, 9, 7, 4, 3, 6, 8]
[4, 3, 8, 5, 2, 6, 9, 1, 7]
[7, 9, 6, 3, 1, 8, 4, 5, 2]
solved in 1.1600663661956787 seconds

Answer 3

这是基于 hari 答案的更快的解决方案。基本区别在于，我们为未分配值的单元格保留一组可能的值。因此，当我们尝试新值时，我们只尝试有效值，并且还会传播此选择对数独其余部分的含义。在传播步骤中，我们从每个单元格的有效值集中删除已出现在行、列或同一块中的值。如果集合中只剩下一个数字，我们就知道该位置（单元格）必须具有该值。

此方法称为前向检查和前瞻 (http://ktiml. mff.cuni.cz/~bartak/constraints/propagation.html）。

下面的实现需要一次迭代（调用solve），而hari的实现需要487次。当然我的代码有点长。传播方法也不是最佳的。

import sys
from copy import deepcopy

def output(a):
    sys.stdout.write(str(a))

N = 9

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

def print_field(field):
    if not field:
        output("No solution")
        return
    for i in range(N):
        for j in range(N):
            cell = field[i][j]
            if cell == 0 or isinstance(cell, set):
                output('.')
            else:
                output(cell)
            if (j + 1) % 3 == 0 and j < 8:
                output(' |')

            if j != 8:
                output(' ')
        output('\n')
        if (i + 1) % 3 == 0 and i < 8:
            output("- - - + - - - + - - -\n")

def read(field):
    """ Read field into state (replace 0 with set of possible values) """

    state = deepcopy(field)
    for i in range(N):
        for j in range(N):
            cell = state[i][j]
            if cell == 0:
                state[i][j] = set(range(1,10))

    return state

state = read(field)


def done(state):
    """ Are we done? """

    for row in state:
        for cell in row:
            if isinstance(cell, set):
                return False
    return True


def propagate_step(state):
    """
    Propagate one step.

    @return:  A two-tuple that says whether the configuration
              is solvable and whether the propagation changed
              the state.
    """

            new_units = False

    # propagate row rule
    for i in range(N):
        row = state[i]
        values = set([x for x in row if not isinstance(x, set)])
        for j in range(N):
            if isinstance(state[i][j], set):
                state[i][j] -= values
                if len(state[i][j]) == 1:
                    val = state[i][j].pop()
                    state[i][j] = val
                    values.add(val)
                    new_units = True
                elif len(state[i][j]) == 0:
                    return False, None

    # propagate column rule
    for j in range(N):
        column = [state[x][j] for x in range(N)]
        values = set([x for x in column if not isinstance(x, set)])
        for i in range(N):
            if isinstance(state[i][j], set):
                state[i][j] -= values
                if len(state[i][j]) == 1:
                    val = state[i][j].pop()
                    state[i][j] = val
                    values.add(val)
                    new_units = True
                elif len(state[i][j]) == 0:
                    return False, None

    # propagate cell rule
    for x in range(3):
        for y in range(3):
            values = set()
            for i in range(3 * x, 3 * x + 3):
                for j in range(3 * y, 3 * y + 3):
                    cell = state[i][j]
                    if not isinstance(cell, set):
                        values.add(cell)
            for i in range(3 * x, 3 * x + 3):
                for j in range(3 * y, 3 * y + 3):
                    if isinstance(state[i][j], set):
                        state[i][j] -= values
                        if len(state[i][j]) == 1:
                            val = state[i][j].pop()
                            state[i][j] = val
                            values.add(val)
                            new_units = True
                        elif len(state[i][j]) == 0:
                            return False, None

    return True, new_units

def propagate(state):
    """ Propagate until we reach a fixpoint """
    while True:
        solvable, new_unit = propagate_step(state)
        if not solvable:
            return False
        if not new_unit:
            return True


def solve(state):
    """ Solve sudoku """

    solvable = propagate(state)

    if not solvable:
        return None

    if done(state):
        return state

    for i in range(N):
        for j in range(N):
            cell = state[i][j]
            if isinstance(cell, set):
                for value in cell:
                    new_state = deepcopy(state)
                    new_state[i][j] = value
                    solved = solve(new_state)
                    if solved is not None:
                        return solved
                return None

print_field(solve(state))

Answer 4

我写了一个简单的程序来解决简单的问题。它从一个文件中获取输入，该文件只是一个带有空格和数字的矩阵。解决这个问题的数据结构只是一个 9 x 9 的位掩码矩阵。位掩码将指定在某个位置上哪些数字仍然可能。填充文件中的数字将减少每个已知位置旁边的所有行/列中的数字。完成后，您将继续迭代矩阵并减少可能的数字。如果每个位置只剩下一个选项，那么您就完成了。但有些数独需要更多的工作。对于这些，你可以使用蛮力：尝试所有剩余的可能组合，直到找到一个有效的组合。

Answer 5

我知道我迟到了，但这是我的版本：

from time import perf_counter

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


def solve(bo):
    find = find_empty(bo)
    if not find:  # if find is None or False
        return True
    else:
        row, col = find

    for num in range(1, 10):
        if valid(bo, num, (row, col)):
            bo[row][col] = num

            if solve(bo):
                return True

            bo[row][col] = 0

    return False


def valid(bo, num, pos):

    # Check row
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # Check column
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # Check box
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x*3, box_x*3 + 3):
            if bo[i][j] == num and (i, j) != pos:
                return False

    return True


def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0:
            if i == 0:
                print(" ┎─────────────────────────┒")
            else:
                print(" ┠─────────────────────────┨")

        for j in range(len(bo[0])):
            if j % 3 == 0:
                print(" ┃ ", end=" ")

            if j == 8:
                print(bo[i][j], " ┃")
            else:
                print(bo[i][j], end=" ")

    print(" ┖─────────────────────────┚")


def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return i, j  # row, column

    return None

print('\n--------------------------------------\n')

print('× Unsolved Suduku :-')
print_board(board)

print('\n--------------------------------------\n')

t1 = perf_counter()
solve(board)
t2 = perf_counter()
print('× Solved Suduku :-')
print_board(board)

print('\n--------------------------------------\n')

print(f' TIME TAKEN = {round(t2-t1,3)} SECONDS')

print('\n--------------------------------------\n')

它使用回溯。但这不是我编码的，它是Tech With Tim's。该列表包含世界上最难的数独，通过实现计时功能，时间为：

===========================
[Finished in 2.838 seconds]
===========================

但对于一个简单的数独谜题，如：

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

结果是：

===========================
[Finished in 0.011 seconds]
===========================

我可以说相当快。

Answer 6

使用回溯实现相同算法的简短尝试：

def solve(sudoku):
    #using recursion and backtracking, here we go.
    empties = [(i,j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]
    predict = lambda i, j: set(range(1,10))-set([sudoku[i][j]])-set([sudoku[y+range(1,10,3)[i//3]][x+range(1,10,3)[j//3]] for y in (-1,0,1) for x in (-1,0,1)])-set(sudoku[i])-set(list(zip(*sudoku))[j])
    if len(empties)==0:return True
    gap = next(iter(empties))
    predictions = predict(*gap)
    for i in predictions:
        sudoku[gap[0]][gap[1]] = i
        if solve(sudoku):return True
        sudoku[gap[0]][gap[1]] = 0
    return False

Answer 7

解决数独难题有四个步骤：

1. 确定每个单元格的所有可能性（从行、列和方框中获取）
   并尝试建立一个可能的矩阵。
   2.检查双对，如果存在，则从该行/列/框中的所有单元格中删除这两个值，无论该对存在于何处
   如果任何单元格具有单一可能性，则分配该单元格
   再次运行步骤 1
2. 检查每个单元格的每行、每列和方框。如果单元格有一个不属于其他可能值的值，则将该值分配给该单元格。
   再次运行步骤 1
3. 如果数独仍未解出，那么我们需要开始以下假设，
   假设第一个可能的值并分配。然后运行步骤 1-3
   如果仍未解决，则对下一个可能的值执行此操作并以递归方式运行它。
4. 如果数独仍然没有解决，那么我们需要开始以下假设，
   假设第一个可能的值并分配。然后运行步骤 1-3

如果仍未解决，则对下一个可能的值执行此操作并以递归方式运行。

import math
import sys


def is_solved(l):
    for x, i in enumerate(l):
        for y, j in enumerate(i):
            if j == 0:
                # Incomplete
                return None
            for p in range(9):
                if p != x and j == l[p][y]:
                    # Error
                    print('horizontal issue detected!', (x, y))
                    return False
                if p != y and j == l[x][p]:
                    # Error
                    print('vertical issue detected!', (x, y))
                    return False
            i_n, j_n = get_box_start_coordinate(x, y)
            for (i, j) in [(i, j) for p in range(i_n, i_n + 3) for q in range(j_n, j_n + 3)
                           if (p, q) != (x, y) and j == l[p][q]]:
                    # Error
                print('box issue detected!', (x, y))
                return False
    # Solved
    return True


def is_valid(l):
    for x, i in enumerate(l):
        for y, j in enumerate(i):
            if j != 0:
                for p in range(9):
                    if p != x and j == l[p][y]:
                        # Error
                        print('horizontal issue detected!', (x, y))
                        return False
                    if p != y and j == l[x][p]:
                        # Error
                        print('vertical issue detected!', (x, y))
                        return False
                i_n, j_n = get_box_start_coordinate(x, y)
                for (i, j) in [(i, j) for p in range(i_n, i_n + 3) for q in range(j_n, j_n + 3)
                               if (p, q) != (x, y) and j == l[p][q]]:
                        # Error
                    print('box issue detected!', (x, y))
                    return False
    # Solved
    return True


def get_box_start_coordinate(x, y):
    return 3 * int(math.floor(x/3)), 3 * int(math.floor(y/3))


def get_horizontal(x, y, l):
    return [l[x][i] for i in range(9) if l[x][i] > 0]


def get_vertical(x, y, l):
    return [l[i][y] for i in range(9) if l[i][y] > 0]


def get_box(x, y, l):
    existing = []
    i_n, j_n = get_box_start_coordinate(x, y)
    for (i, j) in [(i, j) for i in range(i_n, i_n + 3) for j in range(j_n, j_n + 3)]:
        existing.append(l[i][j]) if l[i][j] > 0 else None
    return existing


def detect_and_simplify_double_pairs(l, pl):
    for (i, j) in [(i, j) for i in range(9) for j in range(9) if len(pl[i][j]) == 2]:
        temp_pair = pl[i][j]
        for p in (p for p in range(j+1, 9) if len(pl[i][p]) == 2 and len(set(pl[i][p]) & set(temp_pair)) == 2):
            for q in (q for q in range(9) if q != j and q != p):
                pl[i][q] = list(set(pl[i][q]) - set(temp_pair))
                if len(pl[i][q]) == 1:
                    l[i][q] = pl[i][q].pop()
                    return True
        for p in (p for p in range(i+1, 9) if len(pl[p][j]) == 2 and len(set(pl[p][j]) & set(temp_pair)) == 2):
            for q in (q for q in range(9) if q != i and p != q):
                pl[q][j] = list(set(pl[q][j]) - set(temp_pair))
                if len(pl[q][j]) == 1:
                    l[q][j] = pl[q][j].pop()
                    return True
        i_n, j_n = get_box_start_coordinate(i, j)
        for (a, b) in [(a, b) for a in range(i_n, i_n+3) for b in range(j_n, j_n+3)
                       if (a, b) != (i, j) and len(pl[a][b]) == 2 and len(set(pl[a][b]) & set(temp_pair)) == 2]:
            for (c, d) in [(c, d) for c in range(i_n, i_n+3) for d in range(j_n, j_n+3)
                           if (c, d) != (a, b) and (c, d) != (i, j)]:
                pl[c][d] = list(set(pl[c][d]) - set(temp_pair))
                if len(pl[c][d]) == 1:
                    l[c][d] = pl[c][d].pop()
                    return True
    return False


def update_unique_horizontal(x, y, l, pl):
    tl = pl[x][y]
    for i in (i for i in range(9) if i != y):
        tl = list(set(tl) - set(pl[x][i]))
    if len(tl) == 1:
        l[x][y] = tl.pop()
        return True
    return False


def update_unique_vertical(x, y, l, pl):
    tl = pl[x][y]
    for i in (i for i in range(9) if i != x):
        tl = list(set(tl) - set(pl[i][y]))
    if len(tl) == 1:
        l[x][y] = tl.pop()
        return True
    return False


def update_unique_box(x, y, l, pl):
    tl = pl[x][y]
    i_n, j_n = get_box_start_coordinate(x, y)
    for (i, j) in [(i, j) for i in range(i_n, i_n+3) for j in range(j_n, j_n+3) if (i, j) != (x, y)]:
        tl = list(set(tl) - set(pl[i][j]))
    if len(tl) == 1:
        l[x][y] = tl.pop()
        return True
    return False


def find_and_place_possibles(l):
    while True:
        pl = populate_possibles(l)
        if pl != False:
            return pl


def populate_possibles(l):
    pl = [[[]for j in i] for i in l]
    for (i, j) in [(i, j) for i in range(9) for j in range(9) if l[i][j] == 0]:
        p = list(set(range(1, 10)) - set(get_horizontal(i, j, l) +
                                         get_vertical(i, j, l) + get_box(i, j, l)))
        if len(p) == 1:
            l[i][j] = p.pop()
            return False
        else:
            pl[i][j] = p
    return pl


def find_and_remove_uniques(l, pl):
    for (i, j) in [(i, j) for i in range(9) for j in range(9) if l[i][j] == 0]:
        if update_unique_horizontal(i, j, l, pl) == True:
            return True
        if update_unique_vertical(i, j, l, pl) == True:
            return True
        if update_unique_box(i, j, l, pl) == True:
            return True
    return False


def try_with_possibilities(l):
    while True:
        improv = False
        pl = find_and_place_possibles(l)
        if detect_and_simplify_double_pairs(
                l, pl) == True:
            continue
        if find_and_remove_uniques(
                l, pl) == True:
            continue
        if improv == False:
            break
    return pl


def get_first_conflict(pl):
    for (x, y) in [(x, y) for x, i in enumerate(pl) for y, j in enumerate(i) if len(j) > 0]:
        return (x, y)


def get_deep_copy(l):
    new_list = [i[:] for i in l]
    return new_list


def run_assumption(l, pl):
    try:
        c = get_first_conflict(pl)
        fl = pl[c[0]
                ][c[1]]
        # print('Assumption Index : ', c)
        # print('Assumption List: ',  fl)
    except:
        return False
    for i in fl:
        new_list = get_deep_copy(l)
        new_list[c[0]][c[1]] = i
        new_pl = try_with_possibilities(new_list)
        is_done = is_solved(new_list)
        if is_done == True:
            l = new_list
            return new_list
        else:
            new_list = run_assumption(new_list, new_pl)
            if new_list != False and is_solved(new_list) == True:
                return new_list
    return False


if __name__ == "__main__":
    l = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 8, 0, 0, 0, 0, 4, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 6, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [2, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 2, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]
    # This puzzle copied from Hacked rank test case
    if is_valid(l) == False:
        print("Sorry! Invalid.")
        sys.exit()
    pl = try_with_possibilities(l)
    is_done = is_solved(l)
    if is_done == True:
        for i in l:
            print(i)
        print("Solved!!!")
        sys.exit()

    print("Unable to solve by traditional ways")
    print("Starting assumption based solving")
    new_list = run_assumption(l, pl)
    if new_list != False:
        is_done = is_solved(new_list)
        print('is solved ? - ', is_done)
        for i in new_list:
            print(i)
        if is_done == True:
            print("Solved!!! with assumptions.")
        sys.exit()
    print(l)
    print("Sorry! No Solution. Need to fix the valid function :(")
    sys.exit()

Answer 8

不会写完整的代码，但我很久以前就做了一个数独求解器。我发现它并不总能解决问题（人们在拥有报纸时所做的事情是不完整的！），但现在我想我知道该怎么做。

• 设置：对于每个方块，每个数字都有一组标志，显示允许的数字。
• 划掉：就像火车上的人在纸上求解一样，你可以迭代地划掉已知的数字。任何只剩下一个数字的方格都会触发另一次划掉。这要么会解决整个谜题，要么会耗尽触发器。这是我上次停顿的地方。
• 排列：只有9个！ = 362880 种排列 9 个数字的方法，可以在现代系统上轻松预先计算。所有行、列和 3x3 正方形都必须是这些排列之一。一旦你有了一堆数字，你就可以做你在划掉时所做的事情了。对于每行/列/3x3，您可以划掉 9 中的 1/9！如果有 1 个数字，则为排列；如果有 2 个数字，则为 1/(8*9)，依此类推。
• 交叉排列：现在你有一堆行和列，其中有一组潜在的排列。但还有另一个限制：一旦设置了一行，列和 3x3 的数量就会大大减少。您可以从此处进行树搜索以找到解决方案。

Answer 9

使用 google ortools - 以下将生成一个虚拟数独数组或解决一个候选数。该代码可能比所需的更详细，任何反馈都值得赞赏。

这个想法是解决一个约束编程问题，该问题涉及

1. 81 个变量的列表，整数范围在 1 到 9 之间。
2. 行向量的所有不同约束 列
3. 向量的所有不同约束 子
4. 矩阵的所有不同约束

此外，当尝试解决现有的数独，我们对已经分配值的变量添加额外的约束。

from ortools.constraint_solver import pywrapcp
import numpy as np

def sudoku_solver(candidate = None):
    solver = pywrapcp.Solver("Sudoku")

    variables = [solver.IntVar(1,9,f"x{i}") for i in range(81)]
    if len(candidate)>0:
        candidate = np.int64(candidate)
        for i in range(81):
            val = candidate[i]
            if val !=0:
                solver.Add(variables[i] == int(val))

    def set_constraints():
        for i in range(9):
            # All columns should be different
            q=[variables[j] for j in list(range(i,81,9))]
            solver.Add(solver.AllDifferent(q))

            #All rows should be different
            q2=[variables[j] for j in list(range(i*9,(i+1)*9))]
            solver.Add(solver.AllDifferent(q2))

            #All values in the sub-matrix should be different
            a = list(range(81))
            sub_blocks = a[3*i:3*(i+9):9] + a[3*i+1:3*(i+9)+1:9] + a[3*i+2:3*(i+9)+2:9]
            q3 = [variables[j] for j in sub_blocks]
            solver.Add(solver.AllDifferent(q3))
            
    set_constraints()
    db = solver.Phase(variables, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
    solver.NewSearch(db)    
    
    results_store =[]
    num_solutions =0
    total_solutions = 5
    while solver.NextSolution() and num_solutions<total_solutions:
        results = [j.Value() for j in variables]
        results_store.append(results)
        num_solutions +=1
        
    return results_store

解决以下数独

candidate = np.array([0, 2, 0, 4, 5, 6, 0, 8, 0, 0, 5, 6, 7, 8, 9, 0, 0, 3, 7, 0, 9, 0,
       2, 0, 4, 5, 6, 2, 0, 1, 5, 0, 4, 8, 9, 7, 5, 0, 4, 8, 0, 0, 0, 0,
       0, 3, 1, 0, 6, 4, 5, 9, 7, 0, 0, 0, 5, 0, 7, 8, 3, 1, 2, 8, 0, 7,
       0, 1, 0, 5, 0, 4, 9, 7, 8, 0, 3, 0, 0, 0, 5])


results_store = sudoku_solver(candidate)  

Answer 10

您好，我在博客中写过关于用 Python 从头开始​​编写数独求解器的文章，并且目前正在编写关于用 Julia（另一种高级但更快的语言）编写约束编程求解器的整个系列
您可以从文件中读取数独问题，这似乎比 gui 或 cli 方式更容易、更方便。它使用的总体思想是约束规划。我使用所有不同/唯一的约束，但我自己编码，而不是使用约束编程求解器。

如果有人感兴趣：

• 旧的Python版本： https://opensourc.es/blog/sudoku
• 新的 Julia 系列：https://opensourc.es/blog/constraint-solver-1

Answer 11

这是我前段时间用 Tensorflow 和 mnist 以及自动求解器做的一个项目。不过，求解器算法没有很好的记录:)

https://github.com/Sohrab82/Sudoku-Solver< /a>