Алгоритм решения судоку
Я хочу написать код в python, чтобы решить загадку sudoku. У вас, ребята, есть представление о хорошем алгоритме для этой цели. Я читал где-то в сети об алгоритме, который решает его, заполняя все поле всеми возможными числами, а затем вставляет известные значения в соответствующие поля. Из строки и coloumn известных значений известное значение удаляется. Если вы, ребята, знаете лучше алгоритм, чем это, пожалуйста, помогите мне написать один. Также я смущен тем, что я должен читать известные значения от пользователя. Очень сложно вводить значения один за другим через консоль. Любой простой способ для этого, кроме использования gui?
Ответы
Ответ 1
Вот мой решатель судоку на питоне. Для решения головоломки используется простой алгоритм возврата.
Для простоты никакие входные проверки или причудливый вывод не делаются. Это минимальный код, который решает проблему.
Алгоритм
- Найти все допустимые значения для данной ячейки
- Для каждого допустимого значения, идите рекурсивно и попытайтесь решить сетку
Решение
Требуется сетка 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]]
Вышеприведенный алгоритм является базовым алгоритмом возврата, который объясняется во многих местах. Но самая интересная и естественная из стратегий решения судоку, с которыми я столкнулся, это эта из здесь
Ответ 2
Вот гораздо более быстрое решение, основанное на хари ответе. Основное отличие состоит в том, что мы сохраняем набор возможных значений для ячеек, которым не присвоено значение. Поэтому, когда мы пробуем новое значение, мы пробуем только допустимые значения и также распространяем, что этот выбор означает для остальной части судоку. На этапе распространения мы удаляем из набора допустимых значений для каждой ячейки значения, которые уже появляются в строке, столбце или в том же блоке. Если в наборе осталось только одно число, мы знаем, что позиция (ячейка) должна иметь это значение.
Этот метод известен как прямая проверка и взгляд в будущее (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))
Ответ 3
Я также написал решатель судоку на Python. Это тоже алгоритм возврата, но я также хотел поделиться своей реализацией.
Откат может быть достаточно быстрым, учитывая, что он движется в пределах ограничений и выбирает ячейки с умом. Вы также можете проверить мой ответ в этой теме об оптимизации алгоритма. Но здесь я остановлюсь на алгоритме и самом коде.
Суть алгоритма состоит в том, чтобы начать итерацию сетки и принимать решения о том, что делать - заполнить ячейку, или попробовать другую цифру для той же ячейки, или очистить ячейку и вернуться к предыдущей ячейке и т.д. Важно отметить что не существует детерминированного способа узнать, сколько шагов или итераций вам потребуется для решения головоломки. Поэтому у вас действительно есть два варианта - использовать цикл while или использовать рекурсию. Оба они могут продолжать итерацию до тех пор, пока не будет найдено решение или пока не будет доказано отсутствие решения. Преимущество рекурсии заключается в том, что она способна к ветвлению и, как правило, поддерживает более сложные логики и алгоритмы, но недостатком является то, что ее сложнее реализовать и зачастую сложно отладить. Для моей реализации обратного отслеживания я использовал цикл while, поскольку разветвление не требуется, алгоритм ищет однопоточный линейный метод.
Логика выглядит так:
Пока True: (основные итерации)
- Если все пустые ячейки были повторены, а последняя пустая ячейка повторена и не имеет оставшихся цифр, которые нужно попробовать - остановитесь здесь, потому что нет решения.
- Если пустых ячеек нет, проверьте сетку. Если сетка действительна, остановитесь здесь и верните решение.
- Если есть пустые ячейки, выберите следующую ячейку. Если в этой ячейке имеется хотя бы возможная цифра, назначьте ее и переходите к следующей основной итерации.
- Если для текущей ячейки есть хотя бы один оставшийся выбор, и пустых ячеек нет, или все пустые ячейки были повторены, назначьте оставшийся выбор и переходите к следующей основной итерации.
- Если ничего из вышеперечисленного не соответствует действительности, то пришло время отказаться. Очистите текущую ячейку и войдите в нижеследующий цикл.
В то время как 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:
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 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
Ответ 4
Я написал простую программу, которая разрешила простые. Он взял свой вклад из файла, который был просто матрицей с пробелами и числами. Датструктура для решения этой проблемы была всего лишь 9 на 9 матрицей битовой маски. Бит-маска будет указывать, какие числа все еще возможны в определенной позиции. Заполнение чисел из файла приведет к уменьшению числа во всех строках/столбцах рядом с каждым известным местоположением. Когда это будет сделано, вы продолжаете итерацию по матрице и уменьшаете возможные числа. Если в каждом месте осталось только один параметр, все будет сделано. Но есть некоторые судоку, которые нуждаются в дополнительной работе. Для этих целей вы можете просто использовать грубую силу: попробуйте все оставшиеся возможные комбинации, пока не найдете тот, который работает.
Ответ 5
Не буду писать полный код, но я давно решил sudoku solver. Я обнаружил, что это не всегда разрешало это (люди, которые делают, когда у них есть газета, являются неполными!), Но теперь думаю, что я знаю, как это сделать.
- Настройка: для каждого квадрата, есть набор флагов для каждого номера, показывающий разрешенные номера.
- Пересечение: точно так же, как люди на поезде решают его на бумаге, вы можете итеративно вычеркивать известные цифры. Любой квадрат слева с одним номером вызовет еще один переход. Это либо приведет к решению всей головоломки, либо закончится триггерами. Именно здесь я остановился в прошлый раз.
- Перестановки: всего 9!= 362880 способов организовать 9 номеров, легко вычисленных в современной системе. Все строки, столбцы и квадраты 3x3 должны быть одной из этих перестановок. Как только у вас есть куча чисел, вы можете делать то, что вы сделали с переходом. Для каждой строки/столбца/3x3 вы можете вычеркнуть 1/9 из 9! перестановки, если у вас есть один номер, 1/(8 * 9), если у вас есть 2 и т.д.
- Перекрестные перестановки: теперь у вас есть куча строк и столбцов с наборами потенциальных перестановок. Но есть еще одно ограничение: после того, как вы установите строку, столбцы и 3x3s значительно сократятся, какими они могут быть. Вы можете выполнить поиск дерева здесь, чтобы найти решение.
Ответ 6
Я знаю, что опоздал, но это моя версия:
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_board(board)
print('\n--------------------------------------\n')
solve(board)
print_board(board)
Он использует возврат. Но я не закодирован, это Технология с Тимом. Этот список содержит самое сложное судоку мира, и благодаря реализации функции времени, время:
===========================
[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]
===========================
Довольно быстро я могу сказать.
Ответ 7
короткая попытка достичь того же алгоритма с помощью обратного отслеживания:
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
Ответ 8
Привет, я писал о написании решателя судоку с нуля на Python и в настоящее время пишу целую серию статей о написании решателя зависимостей в Julia (еще один высокоуровневый, но более быстрый язык)
Вы можете прочитать проблему судоку из файла, который кажется более удобным, чем графический или графический. Общая идея: я использую это программирование с ограничениями и использую все разные/уникальные ограничения, но я сам кодировал его вместо использования решателя программирования с ограничениями.
Если кому-то интересно:
Ответ 9
Есть четыре шага, чтобы решить головоломку судоку:
- Определите все возможности для каждой ячейки (получение из строки, столбца и поля)
и попытаться разработать возможную матрицу.
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()
