小智 25
这是我在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]]
以上是非常基本的回溯算法,在很多地方都有解释.但最有趣的和自然的,我碰到的数独解决策略的是这一个从这里
基于hari的答案,这是一个更快的解决方案.基本区别在于我们为没有分配值的单元格保留一组可能的值.因此,当我们尝试新值时,我们只尝试有效值,并且我们还传播了这个选择对其余数据的意义.在传播步骤中,我们从每个单元格的有效值集合中删除已经出现在行,列或同一块中的值.如果集合中只剩下一个数字,我们知道位置(单元格)必须具有该值.
这种方法称为前向检查并向前看(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))
我还用Python编写了Sudoku求解器。它也是一个回溯算法，但是我也想分享我的实现。
考虑到回溯在约束内移动并明智地选择了单元，回溯可以足够快。您可能还想在此线程中查看有关优化算法的答案。但是在这里，我将重点介绍算法和代码本身。
该算法的要点是开始迭代网格并决定要执行的操作-填充一个单元格，或者为同一单元格尝试另一个数字，或者清空一个单元格并移回上一个单元格，依此类推。没有确定性的方法来知道解决难题所需的步骤或迭代次数。因此，您确实有两个选择-使用while循环或使用递归。他们两个都可以继续迭代，直到找到解决方案或证明缺乏解决方案为止。递归的优点是它可以分支出来，并且通常支持更复杂的逻辑和算法，但是缺点是实现起来比较困难并且调试起来通常很棘手。在实现回溯的过程中，我使用了while循环，因为不需要分支，
逻辑如下：
虽然为True ：（主要迭代）
正确时：（回溯迭代）
该算法的一些特点：
它以相同顺序记录访问单元的记录，以便可以随时回溯
它会记录每个单元格的选择，以便它不会对同一单元格两次尝试相同的数字
单元的可用选项始终在数独约束内（行，列和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:
我写了一个简单的程序来解决简单的问题。它从一个文件中获取输入，该文件只是一个带有空格和数字的矩阵。解决它的数据结构只是一个 9 x 9 的位掩码矩阵。位掩码将指定在某个位置上哪些数字仍然是可能的。填写文件中的数字会减少每个已知位置旁边所有行/列中的数字。完成后，您将继续迭代矩阵并减少可能的数字。如果每个位置只剩下一个选项，您就完成了。但是有一些数独需要更多的工作。对于这些，您可以只使用蛮力：尝试所有剩余的可能组合，直到找到一种可行的组合。
| 归档时间： |
|
| 查看次数： |
86743 次 |
| 最近记录： |