我想在 python 中编写代码来解决数独难题。你们对为此目的的好算法有什么想法吗？我在网上的某个地方读到了一种算法，它通过用所有可能的数字填充整个盒子来解决它，然后将已知值插入到相应的盒子中。从已知值的行和列中删除已知值。如果你们知道更好算法比这个请帮我写一个。我也很困惑我应该如何从用户那里读取已知值。通过控制台逐一输入值真的很难。除了使用gui之外，还有什么简单的方法吗？
问问题
144102 次
11 回答
33
这是我在 python 中的数独求解器。它使用简单的回溯算法来解决这个难题。为简单起见，没有进行输入验证或花哨的输出。这是解决问题的最少代码。
算法
- 查找给定单元格的所有合法值
- 对于每个合法值，递归地去并尝试解决网格
解决方案
它需要部分填充数字的 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]]
于 2013-11-29T06:20:28.143 回答
9
我还用 Python 写了一个数独求解器。它也是一种回溯算法，但我也想分享我的实现。
回溯可以足够快，因为它在约束范围内移动并且明智地选择单元格。您可能还想查看我在此线程中关于优化算法的答案。但在这里我将重点介绍算法和代码本身。
该算法的要点是开始迭代网格并决定要做什么 - 填充一个单元格，或者为同一个单元格尝试另一个数字，或者空白一个单元格并移回前一个单元格，等等。重要的是要注意没有确定的方法可以知道解决难题需要多少步骤或迭代。因此，您确实有两个选择 - 使用 while 循环或使用递归。它们都可以继续迭代，直到找到解决方案或证明没有解决方案。递归的优点是可以分支出来，一般支持更复杂的逻辑和算法，缺点是实现起来比较困难，调试起来也比较麻烦。对于回溯的实现，我使用了一个 while 循环，因为不需要分支，
逻辑是这样的：
虽然为真：（主要迭代）
- 如果所有空白单元格都已被迭代并且最后一个空白单元格迭代没有任何剩余的数字要尝试 - 在这里停止，因为没有解决方案。
- 如果没有空白单元格验证网格。如果网格有效，请在此处停止并返回解决方案。
- 如果有空白单元格，请选择下一个单元格。如果该单元格至少有一个可能的数字，则分配它并继续下一个主迭代。
- 如果当前单元格至少有一个剩余选择，并且没有空白单元格或所有空白单元格都已迭代，则分配剩余选择并继续下一次主迭代。
- 如果以上都不是真的，那么是时候回溯了。清空当前单元格并进入下面的循环。
虽然为真：（回溯迭代）
- 如果没有更多的单元格可以回溯 - 在这里停止，因为没有解决方案。
- 根据回溯历史选择上一个单元格。
- 如果该单元格没有任何选择，则将该单元格清空并继续下一次回溯迭代。
- 将下一个可用数字分配给当前单元格，退出回溯并返回主迭代。
算法的一些特点：
它以相同的顺序记录访问过的单元格，以便随时回溯
它会记录每个单元格的选择记录，这样它就不会为同一个单元格尝试相同的数字两次
单元格的可用选项始终在数独约束（行、列和 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
于 2018-01-13T10:33:03.207 回答
9
这是基于哈里的答案的更快的解决方案。基本区别在于，我们为未分配值的单元格保留一组可能值。因此，当我们尝试一个新值时，我们只尝试有效值，并且我们还会传播这个选择对其余数独的意义。在传播步骤中，我们从每个单元格的有效值集中删除已经出现在行、列或同一块中的值。如果集合中只剩下一个数字，我们知道位置（单元格）必须具有该值。
这种方法称为前向检查和前瞻 ( http://ktiml.mff.cuni.cz/~bartak/constraints/propagation.html )。
下面的实现需要一次迭代（求解调用），而 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))
于 2016-02-19T08:04:32.487 回答
5
我写了一个简单的程序来解决简单的问题。它从一个文件中获取输入，该文件只是一个带有空格和数字的矩阵。解决它的数据结构只是一个 9 x 9 的位掩码矩阵。位掩码将指定在某个位置上哪些数字仍然是可能的。从文件中填写数字将减少每个已知位置旁边的所有行/列中的数字。完成后，您将继续迭代矩阵并减少可能的数字。如果每个位置只剩下一个选项，那么您就完成了。但是有些数独需要更多的工作。对于这些，您可以只使用蛮力：尝试所有剩余的可能组合，直到找到一个有效的组合。
于 2009-11-08T18:16:35.547 回答
3
我知道我迟到了，但这是我的版本：
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 的. 该列表包含世界上最难的数独，通过实现计时功能，时间为：
===========================
[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]
===========================
我可以说相当快。
于 2019-09-10T18:48:27.210 回答
2
解决数独难题有四个步骤：
- 确定每个单元格的所有可能性（从行、列和框中获取）并尝试开发一个可能的矩阵。2.检查双对，如果存在，则从该行/列/框中的所有单元格中删除这两个值，无论该对是否存在如果任何单元格具有单一可能性，则再次分配该运行步骤 1
- 检查每个单元格的每一行、每一列和每一框。如果单元格具有一个不属于其他可能值的值，则将该值分配给该单元格。再次运行第 1 步
- 如果数独仍未解出，那么我们需要开始下面的假设，假设第一个可能的值并赋值。然后运行第 1-3 步，如果仍未解决，则执行下一个可能的值并递归运行。
- 如果数独仍未解出，那么我们需要开始下面的假设，假设第一个可能的值并赋值。然后运行步骤 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()
于 2019-10-08T08:52:54.700 回答
1
不会写完整的代码，但我很久以前做过数独求解器。我发现它并不总是能解决它（人们在拥有报纸时所做的事情是不完整的！），但现在我想我知道该怎么做了。
- 设置：对于每个方块，为每个数字设置一组标志，显示允许的数字。
- 划掉：就像火车上的人在纸上解决问题一样，您可以迭代划掉已知数字。任何只剩下一个数字的方块都会触发另一个划线。这将导致解决整个难题，或者将耗尽触发器。这是我上次停顿的地方。
- 排列：只有9个！= 362880 种排列 9 个数字的方法，在现代系统上很容易预先计算。所有的行、列和 3x3 正方形都必须是这些排列之一。一旦你有一堆数字，你就可以做你所做的划线。对于每一行/列/3x3，您可以划掉 9 个中的 1/9！如果您有一个数字，则排列，如果您有 2，则为 1/(8*9)，依此类推。
- 交叉排列：现在您有一堆行和列，其中包含一组潜在的排列。但是还有另一个限制：一旦你设置了一行，列和 3x3 可能会大大减少。您可以从此处进行树搜索以找到解决方案。
于 2016-02-19T08:26:59.213 回答
1
使用谷歌或工具 - 以下将生成一个虚拟数独数组或将解决一个候选者。代码可能比要求的更详细，感谢任何反馈。
这个想法是解决一个约束规划问题，包括
- 整数范围在 1 到 9 之间的 81 个变量的列表。
- 行向量的所有不同约束
- 列向量的所有不同约束
- 子矩阵的所有不同约束
此外，在尝试解决现有数独时，我们会在已经赋值的变量上添加额外的约束。
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)
于 2019-11-19T13:41:51.467 回答
1
嗨，我已经写了一篇关于在 Python 中从头开始编写数独求解器的博客，目前正在编写一个关于在 Julia（另一种高级但更快的语言）中编写约束编程求解器的整个系列您可以从文件中读取数独问题，这似乎更容易比 gui 或 cli 方式更方便。它使用的一般思想是约束规划。我使用了所有不同/唯一的约束，但我自己编写了代码，而不是使用约束编程求解器。
如果有人感兴趣：
- 旧 Python 版本：https ://opensourcec.es/blog/sudoku
- 新的 Julia 系列：https ://opensourcec.es/blog/constraint-solver-1
于 2019-10-06T19:47:36.513 回答
1
使用回溯实现相同算法的简短尝试：
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
于 2019-09-27T18:10:35.827 回答
0
这是我前段时间用 Tensorflow 和 mnist 和自动求解器做的一个项目。求解器算法虽然没有很好的文档记录:)
于 2021-04-24T12:39:31.817 回答