Я сделал простой класс Судоку (на Python). Его основными атрибутами являются следующие:
def __init__(self, it: iter = None):
self.grid = [[None for _ in range(9)] for _ in range(9)]
self.usedInRow = [[False for _ in range(10)] for _ in range(9)]
self.usedInCol = [[False for _ in range(10)] for _ in range(9)]
self.usedInBox = [[False for _ in range(10)] for _ in range(9)]
def writeCell(self, pos: tuple, val: int) -> bool: [...]
def eraseCell(self, pos: tuple): [...]
self.grid отслеживает фактические цифры в судоку. self.usedInRow, self.usedInCol и self.usedInBox - это логические массивы, которые отслеживают, какие числа были использованы в каждой строке / столбце / квадрате. writeCell - это метод, который пытается записать число в пустую ячейку и возвращает, успешно ли оно выполнено (согласно правилам судоку). Наконец, eraseCell заменяет содержимое ячейки на None.
Внутри класса я написал метод решателя с рекурсивным отслеживанием. При реализации решателя я пробовал разные подходы для выбора ячейки для заполнения следующей. Первое, что я попробовал, было просто начать с (0, 0) и увеличивать позиции слева направо и сверху вниз (с колонками как «маленькой» единицей и строками как «большой» единицей).
Но это недостаточно обобщенно (если по какой-то причине решатель начал решать с позиции, отличной от (0, 0), каждую пустую ячейку до того, как она будет пропущена). Поэтому я добавил участника, чтобы отслеживать пустые ячейки:
def __init__(self, it: iter = None):
[...]
self.emptyCells = [(i, j) for i in range(9) for j in range(9)]
Я изменил методы writeCell и eraseCell для обеспечения правильной записи. На этом этапе решатель выглядит примерно так:
def solve(self) -> bool:
[...]
def _solve() -> bool:
if not self.emptyCells: return True
pos = self.emptyCells[0]
for n in range(1, 10):
if self.writeCell(pos, n):
if _solve(): return True
self.eraseCell(pos)
else: return False
success = _solve()
[...]
return success
В этот момент я подумал, что, возможно, было бы лучше, если бы член self.emptyCells был set вместо list: я не хотел дубликатов, не нуждался в индексированном доступе (я думал, что это не имеет значения порядок, в котором были заполнены ячейки), и требуется быстрое удаление. Поэтому я изменил атрибут self.emptyCells
self.emptyCells = set((i, j) for i in range(9) for j in range(9))
и методы, которые ссылались на него (например, я использовал .discard() вместо .remove() в writeCell). Метод решателя теперь выглядел так:
def solve(self) -> bool:
[...]
def _solve() -> bool:
if not self.emptyCells: return True
pos = self.emptyCells.pop() # Get arbitrary position
for n in range(1, 10):
if self.writeCell(pos, n):
if _solve(): return True
self.eraseCell(pos)
else:
self.emptyCells.add(pos) # Backtrack
return False
success = _solve()
[...]
return success
К моему удивлению, второй подход (с использованием набора) занял около одной минуты, чтобы решить пустое судоку, в то время как первый подход (с использованием списка) занял около двух секунд. Это почему? Влияет ли произвольно выбранная позиция, присвоенная set.pop(), на эффективность алгоритма по сравнению с заполнением ячеек по порядку?
Полный код
Использование списка
import queue
import threading
import colorama
colorama.init() # For ANSI escape codes
class Sudoku:
@staticmethod
def isSudoku(S: iter):
return len(S) == 9 \
and all(len(row) == 9 for row in S) \
and all(num in range(1, 10) for row in S for num in row)
def __init__(self, it: iter = None):
self.grid = [[None for _ in range(9)] for _ in range(9)]
self.usedInRow = [[False for _ in range(10)] for _ in range(9)]
self.usedInCol = [[False for _ in range(10)] for _ in range(9)]
self.usedInBox = [[False for _ in range(10)] for _ in range(9)]
self.emptyCells = [(i, j) for i in range(9) for j in range(9)]
if it is not None:
for i in range(9):
for j, num in zip(range(9), it):
if num is not None:
if not self.writeCell((i, j), num): raise ValueError("Invalid Sudoku")
def __iter__(self):
return iter(self.grid)
def __len__(self):
return 9
def __str__(self):
def numsToStr(row):
for num in row: yield num if num is not None else ' '
def rowsBlock(i):
yield ''
for row in self.grid[3 * i:3 * (i + 1)]:
yield '|{} {} {}|{} {} {}|{} {} {}|'.format(*numsToStr(row))
yield ''
def blocks():
yield ''
for i in range(3): yield '\n'.join(rowsBlock(i))
yield ''
return ('-' * 19).join(blocks())
def __getitem__(self, key: tuple):
if not len(key) == 2: raise TypeError("Two indices needed")
r, c = key
return self.grid[r][c]
def __setitem__(self, key: tuple, value: int):
if not len(key) == 2: raise TypeError("Two indices needed")
self.eraseCell(key)
self.writeCell(key, value)
def _canWrite(self, r: int, c: int, b: int, val: int) -> bool:
if self.usedInRow[r][val] or self.usedInCol[c][val] or self.usedInBox[b][val] \
or self.grid[r][c] is not None: return False
self.usedInRow[r][val] = self.usedInCol[c][val] = self.usedInBox[b][val] = True
return True
def writeCell(self, pos: tuple, val: int) -> bool:
if val is None: return True # Ignore writing none
r, c = pos
b = 3*(r//3) + c//3
if not self._canWrite(r, c, b, val): return False
# noinspection PyTypeChecker
self.grid[r][c] = val
self.emptyCells.remove(pos)
return True
def eraseCell(self, pos: tuple):
r, c = pos
b = 3*(r//3) + c//3
val = self.grid[r][c] # Get old value for reference
if val is None: return # If there wasn't anything in the first place
self.grid[r][c] = None # Actually erase
self.emptyCells.append(pos)
# noinspection PyTypeChecker
self.usedInRow[r][val] = self.usedInCol[c][val] = self.usedInBox[b][val] = False
def solve(self) -> bool:
printQueue = queue.PriorityQueue()
def printer():
while True:
priority, item = printQueue.get()
if item is StopAsyncIteration:
break
print(item)
print('\x1b[13A', end='')
printQueue.task_done()
printThread = threading.Thread(target=printer, name="PrintThread")
printThread.start()
def _solve() -> bool:
if not self.emptyCells: return True
pos = self.emptyCells[0]
for n in range(1, 10):
if self.writeCell(pos, n):
if _solve(): return True
printQueue.put((1, self))
self.eraseCell(pos)
else:
return False
success = _solve()
printQueue.put((0, StopAsyncIteration))
printThread.join()
return success
Использование набора
Меняются только следующие вещи.
_solve() внутренний метод:
def _solve():
if not self.emptyCells: return True
pos = self.emptyCells.pop()
for n in range(1, 10):
if self.writeCell(pos, n):
if _solve(): return True
printQueue.put((1, self))
self.eraseCell(pos)
else:
self.emptyCells.add(pos)
return False
eraseCell и writeCell:
def writeCell(self, pos: tuple, val: int):
if val is None: return True # Ignore writing none
r, c = pos
b = 3*(r//3) + c//3
if not self._canWrite(r, c, b, val): return False
# noinspection PyTypeChecker
self.grid[r][c] = val
self.emptyCells.discard(pos)
return True
def eraseCell(self, pos: tuple):
r, c = pos
b = 3*(r//3) + c//3
val = self.grid[r][c] # Get old value for reference
if val is None: return # If there wasn't anything in the first place
self.grid[r][c] = None # Actually erase
self.emptyCells.add(pos)
# noinspection PyTypeChecker
self.usedInRow[r][val] = self.usedInCol[c][val] = self.usedInBox[b][val] = False
Примечание
Причина, по которой я не возвращаю pos в версию списка, а также почему я получаю pos как self.emptyCells[0] вместо self.emptyCells.pop(0) - потому что writeCell и eraseCell уже заботятся о что: если writeCell удастся написать (ранее пустую) ячейку, то она вызовет self.emptyCells.remove(pos) - и вот еще одна причина, по которой я не появляюсь в списке: в противном случае я бы remove нашел бы несуществующий элемент в список, и придется поймать ValueError.
После этого, если происходит возврат (т. Е. Рекурсивный вызов _solve() возвращает False), eraseCell вернет pos в список. Таким образом, если цикл for «не работает», т. Е. Введена ветвь else, последний eraseCell уже вернет pos назад.
С другой стороны, при использовании set невозможно получить доступ к элементу, не удалив его из набора (насколько мне известно). Таким образом, я вынужден pop из него и положить его обратно вручную. Вот почему remove используется вместо *1093* в set -версии writeCell, так как pos, возможно, уже был вытолкнут solve_.
Альтернативой может быть сохранение pos = self.emptyCells.pop() и add прямо (self.emptyCells.add(pos)), а затем переход к solve_. Тогда я мог бы изменить discard на remove.
Пример использования
sudoku = Sudoku()
sudoku.solve()
print(sudoku)
Результаты профилирования
Я профилировал обе версии, но не нашел никакого очевидного виновника, то есть пропорции совокупного времени, затраченного каждым методом, были очень похожи, хотя фактическое абсолютное время, которое они взяли, было только увеличено в версии set с уважение к версии списка.
Обновление - pos насчитывает
Я добавилмассив для отслеживания того, сколько раз каждый pos был выбран для исследования, и я распечатал его в конце решения. Вот результаты.
Список версий:
[[ 1 1 1 1 1 1 1 1 1]
[ 1 1 1 1 145 671 7169 9869 7606]
[ 774 1115 645 7 2066 1240 451 463 554]
[ 511 466 504 424 554 422 358 502 566]
[ 545 224 507 539 578 404 487 357 574]
[ 421 421 452 436 465 406 326 621 483]
[ 436 519 284 462 545 534 410 563 730]
[ 433 561 311 397 365 254 308 708 384]
[ 445 559 558 413 513 572 564 511 686]]
Установить версию (насколько я могу судить, результаты согласованы):
[[ 19895 1 91239 66620 1 1 76794 1 1]
[ 1 1 77617 43061 95435 1 1 49617 77772]
[ 54441 1 1 96081 79660 1 1 1 89575]
[101233 1 1 85645 55172 1 1 1 54613]
[ 1 1 71512 61978 5531 1 76794 82692 74311]
[ 96268 1 57136 92052 1 1 86104 91911 1]
[ 1 98119 95706 10680 1 97232 67210 1 39094]
[ 53447 1 1 1 89846 1 1 88072 1]
[ 74468 19103 1 39934 75698 1 1 90778 53260]]