解决数独的算法
我想用Python写一段代码来解决数独问题。你们有没有什么好的算法推荐？我在网上看到过一种算法，它是先把整个数独的格子填上所有可能的数字，然后再把已知的数字放到对应的格子里。接着，根据已知数字所在的行和列，把这些已知数字去掉。如果你们知道比这个更好的算法，请帮我写一个。另外，我对如何从用户那里读取已知数字感到困惑。通过控制台一个一个输入数字真的很麻烦，有没有比用图形界面更简单的方法？
11 个回答
9
这里有一个更快的解决方案，基于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))
11
我也用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
34
这是我用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]]