Как правильно реализовать логику для решения?
Задача:
Есть несколько уровней сложности судоку, мы можем оценить сложность судоку, основываясь на том, сколько ячеек дано из 81 ячейки игры.
Простые судоку обычно имеют более 32 заданий.
Судоку среднего размера имеет около 30–32 ответов.
В сложном судоку около 28–30 ответов.
Очень сложная судоку имеет менее 28 заданий
Примечание: минимальное количество данных, необходимых для создания уникальной (без множественных решений) игры судоку, составляет 17.
Сложная игра-судоку означает, что в начале ни в одной ячейке не будет ни одного кандидата, что требует угадывания и проб и ошибок. У очень жесткого будет несколько слоев из нескольких кандидатов на любую пустую ячейку.
Задача: Напишите функцию, которая решает головоломки судоку любой сложности. Функция принимает сетку судоку и должна возвращать массив 9x9 с правильным ответом на головоломку.
Или это должно вызывать ошибку в случаях: недопустимая сетка (не 9x9, ячейка со значениями не в диапазоне 1 ~ 9); несколько решений для одной и той же головоломки или головоломка неразрешима.
В общем я набросал код, и как я и думал, на моменте, когда я рассчитал кандидатов для каждой ячейки начались проблемы. Не приходит в голову мысль, как перебрать различные варианты подстановок имеющихся вариантов.
Код:
solution = [[3, 4, 6, 1, 2, 7, 9, 5, 8],
[7, 8, 5, 6, 9, 4, 1, 3, 2],
[2, 1, 9, 3, 8, 5, 4, 6, 7],
[4, 6, 2, 5, 3, 1, 8, 7, 9],
[9, 3, 1, 2, 7, 8, 6, 4, 5],
[8, 5, 7, 9, 4, 6, 2, 1, 3],
[5, 9, 8, 4, 1, 3, 7, 2, 6],
[6, 2, 4, 7, 5, 9, 3, 8, 1],
[1, 7, 3, 8, 6, 2, 5, 9, 4]]
puzzle = [[0, 0, 6, 1, 0, 0, 0, 0, 8],
[0, 8, 0, 0, 9, 0, 0, 3, 0],
[2, 0, 0, 0, 0, 5, 4, 0, 0],
[4, 0, 0, 0, 0, 1, 8, 0, 0],
[0, 3, 0, 0, 7, 0, 0, 4, 0],
[0, 0, 7, 9, 0, 0, 0, 0, 3],
[0, 0, 8, 4, 0, 0, 0, 0, 6],
[0, 2, 0, 0, 5, 0, 0, 8, 0],
[1, 0, 0, 0, 0, 2, 5, 0, 0]]
def solver():
transposed = [list(i) for i in zip(*puzzle)]
candidates = dict()
keys = [(0, 3), (3, 6), (6, 9)]
row_point = None
col_point = None
for x in range(len(puzzle)):
for y in range(len(puzzle[0])):
candidates['canFor{}_{}'.format(x, y)] = list()
for x in range(len(puzzle)):
if x < 3:
row_point = keys[0]
elif x < 6:
row_point = keys[1]
elif x < 9:
row_point = keys[2]
for y in range(len(puzzle[0])):
if y < 3:
col_point = keys[0]
elif y < 6:
col_point = keys[1]
elif y < 9:
col_point = keys[2]
if puzzle[x][y] == 0:
for z in range(1, 10):
if z not in puzzle[x] and z not in transposed[y] \
and z not in [puzzle[row][col] for col in range(*col_point) for row in range(*row_point)]:
candidates['canFor{}_{}'.format(x, y)].append(z)
print(candidates)
solver()
Ответы (3 шт):
Автор решения: Zhihar
→ Ссылка
Немного занимаюсь судоку :)))
Держите код, который решает судоку, а также ищет кратчайший путь для решения (требующий минимальных ветвлений)
Код не оптимальный, на C++ я его переписывал и ускорял где-то в 100.000 раз (правда там добавлял еще несколько правил для чистки судоку от лишних вариантов и выбора правильного хода при ветвлении, что приводило к решению судоку за минимально возможное кол-во ходов)
Но текущий код позволяет решать ЛЮБЫЕ судоку, только чуть менее эффективно :) (судоку, заявленную как одну из самых сложных в мире он решает на питоне за 0,5 сек)
На счет сложных судоку - то я генерировал как-то судоку в котором только изначально открыто только 19 цифр и требуется 3 ветвления для решения по самому кратчайшему пути)
import copy
import time
c_zipped_combinations = [
[
[2],
],
[
[2, 4],
[6],
],
[
[2, 4, 8],
[6, 10, 12],
[14],
],
[
[2, 4, 8, 16],
[6, 10, 18, 12, 20, 24],
[14, 22, 26, 28],
[30],
],
[
[2, 4, 8, 16, 32],
[6, 10, 18, 34, 12, 20, 36, 24, 40, 48],
[14, 22, 38, 26, 42, 50, 28, 44, 52, 56],
[30, 46, 54, 58, 60],
[62],
],
[
[2, 4, 8, 16, 32, 64],
[6, 10, 18, 34, 66, 12, 20, 36, 68, 24, 40, 72, 48, 80, 96],
[14, 22, 38, 70, 26, 42, 74, 50, 82, 98, 28, 44, 76, 52, 84, 100, 56, 88, 104, 112],
[30, 46, 78, 54, 86, 102, 58, 90, 106, 114, 60, 92, 108, 116, 120],
[62, 94, 110, 118, 122, 124],
[126],
],
[
[2, 4, 8, 16, 32, 64, 128],
[6, 10, 18, 34, 66, 130, 12, 20, 36, 68, 132, 24, 40, 72, 136, 48, 80, 144, 96, 160, 192],
[14, 22, 38, 70, 134, 26, 42, 74, 138, 50, 82, 146, 98, 162, 194, 28, 44, 76, 140, 52, 84, 148, 100, 164, 196, 56, 88, 152, 104, 168, 200, 112, 176, 208, 224],
[30, 46, 78, 142, 54, 86, 150, 102, 166, 198, 58, 90, 154, 106, 170, 202, 114, 178, 210, 226, 60, 92, 156, 108, 172, 204, 116, 180, 212, 228, 120, 184, 216, 232, 240],
[62, 94, 158, 110, 174, 206, 118, 182, 214, 230, 122, 186, 218, 234, 242, 124, 188, 220, 236, 244, 248],
[126, 190, 222, 238, 246, 250, 252],
[254],
],
[
[2, 4, 8, 16, 32, 64, 128, 256],
[6, 10, 18, 34, 66, 130, 258, 12, 20, 36, 68, 132, 260, 24, 40, 72, 136, 264, 48, 80, 144, 272, 96, 160, 288, 192, 320, 384],
[14, 22, 38, 70, 134, 262, 26, 42, 74, 138, 266, 50, 82, 146, 274, 98, 162, 290, 194, 322, 386, 28, 44, 76, 140, 268, 52, 84, 148, 276, 100, 164, 292, 196, 324, 388, 56, 88, 152, 280, 104, 168, 296, 200, 328, 392, 112, 176, 304, 208, 336, 400, 224, 352, 416, 448],
[30, 46, 78, 142, 270, 54, 86, 150, 278, 102, 166, 294, 198, 326, 390, 58, 90, 154, 282, 106, 170, 298, 202, 330, 394, 114, 178, 306, 210, 338, 402, 226, 354, 418, 450, 60, 92, 156, 284, 108, 172, 300, 204, 332, 396, 116, 180, 308, 212, 340, 404, 228, 356, 420, 452, 120, 184, 312, 216, 344, 408, 232, 360, 424, 456, 240, 368, 432, 464, 480],
[62, 94, 158, 286, 110, 174, 302, 206, 334, 398, 118, 182, 310, 214, 342, 406, 230, 358, 422, 454, 122, 186, 314, 218, 346, 410, 234, 362, 426, 458, 242, 370, 434, 466, 482, 124, 188, 316, 220, 348, 412, 236, 364, 428, 460, 244, 372, 436, 468, 484, 248, 376, 440, 472, 488, 496],
[126, 190, 318, 222, 350, 414, 238, 366, 430, 462, 246, 374, 438, 470, 486, 250, 378, 442, 474, 490, 498, 252, 380, 444, 476, 492, 500, 504],
[254, 382, 446, 478, 494, 502, 506, 508],
[510],
],
[
[2, 4, 8, 16, 32, 64, 128, 256, 512],
[6, 10, 18, 34, 66, 130, 258, 514, 12, 20, 36, 68, 132, 260, 516, 24, 40, 72, 136, 264, 520, 48, 80, 144, 272, 528, 96, 160, 288, 544, 192, 320, 576, 384, 640, 768],
[14, 22, 38, 70, 134, 262, 518, 26, 42, 74, 138, 266, 522, 50, 82, 146, 274, 530, 98, 162, 290, 546, 194, 322, 578, 386, 642, 770, 28, 44, 76, 140, 268, 524, 52, 84, 148, 276, 532, 100, 164, 292, 548, 196, 324, 580, 388, 644, 772, 56, 88, 152, 280, 536, 104, 168, 296, 552, 200, 328, 584, 392, 648, 776, 112, 176, 304, 560, 208, 336, 592, 400, 656, 784, 224, 352, 608, 416, 672, 800, 448, 704, 832, 896],
[30, 46, 78, 142, 270, 526, 54, 86, 150, 278, 534, 102, 166, 294, 550, 198, 326, 582, 390, 646, 774, 58, 90, 154, 282, 538, 106, 170, 298, 554, 202, 330, 586, 394, 650, 778, 114, 178, 306, 562, 210, 338, 594, 402, 658, 786, 226, 354, 610, 418, 674, 802, 450, 706, 834, 898, 60, 92, 156, 284, 540, 108, 172, 300, 556, 204, 332, 588, 396, 652, 780, 116, 180, 308, 564, 212, 340, 596, 404, 660, 788, 228, 356, 612, 420, 676, 804, 452, 708, 836, 900, 120, 184, 312, 568, 216, 344, 600, 408, 664, 792, 232, 360, 616, 424, 680, 808, 456, 712, 840, 904, 240, 368, 624, 432, 688, 816, 464, 720, 848, 912, 480, 736, 864, 928, 960],
[62, 94, 158, 286, 542, 110, 174, 302, 558, 206, 334, 590, 398, 654, 782, 118, 182, 310, 566, 214, 342, 598, 406, 662, 790, 230, 358, 614, 422, 678, 806, 454, 710, 838, 902, 122, 186, 314, 570, 218, 346, 602, 410, 666, 794, 234, 362, 618, 426, 682, 810, 458, 714, 842, 906, 242, 370, 626, 434, 690, 818, 466, 722, 850, 914, 482, 738, 866, 930, 962, 124, 188, 316, 572, 220, 348, 604, 412, 668, 796, 236, 364, 620, 428, 684, 812, 460, 716, 844, 908, 244, 372, 628, 436, 692, 820, 468, 724, 852, 916, 484, 740, 868, 932, 964, 248, 376, 632, 440, 696, 824, 472, 728, 856, 920, 488, 744, 872, 936, 968, 496, 752, 880, 944, 976, 992],
[126, 190, 318, 574, 222, 350, 606, 414, 670, 798, 238, 366, 622, 430, 686, 814, 462, 718, 846, 910, 246, 374, 630, 438, 694, 822, 470, 726, 854, 918, 486, 742, 870, 934, 966, 250, 378, 634, 442, 698, 826, 474, 730, 858, 922, 490, 746, 874, 938, 970, 498, 754, 882, 946, 978, 994, 252, 380, 636, 444, 700, 828, 476, 732, 860, 924, 492, 748, 876, 940, 972, 500, 756, 884, 948, 980, 996, 504, 760, 888, 952, 984, 1000, 1008],
[254, 382, 638, 446, 702, 830, 478, 734, 862, 926, 494, 750, 878, 942, 974, 502, 758, 886, 950, 982, 998, 506, 762, 890, 954, 986, 1002, 1010, 508, 764, 892, 956, 988, 1004, 1012, 1016],
[510, 766, 894, 958, 990, 1006, 1014, 1018, 1020],
[1022],
],
]
# определить константы
c_sudoku_size = 81
c_sudoku_all_variants = 0b1111111110
# получить позицию клетки в судоку
def getPos2(
i, # позиция клетки по x
j # позиция клетки по y
):
return i + j * 9
def getPos4(
i, # позиция блока по x
j, # позиция блока по y
m, # позиция клетки в блоке по x
n # позиция клетки в блоке по y
):
return getPos2(i * 3 + m, j * 3 + n)
# подсчитать кол - во вариантов в клетке
def countCageVariants(
cell # варианты клетки
):
# ПОЯСНЕНИЯ:
# доступные варианты кодируются соответствующим битом (1 - 1 бит, 2 - 2 бит, ...)
# таким образом подсчёт кол-ва вариантов сводится к подсчёту кол-ва установленных бит
amount = 0
for variant in range(1, 10):
amount += (cell >> variant) & 1
return amount
# подсчитать кол-во всех вариантов в судоку
def countSudokuVariants(
sudoku # судоку
):
count = 0
for pos in range(0, c_sudoku_size):
count += countCageVariants(sudoku[pos])
return count
# определить все варианты для списка клеток
def getViewVariants(
view # отображение
):
# ПОЯСНЕНИЯ:
# поскольку варианты клетки кодируются соответствующими битами, то варианты для нескольких клеток соответствую логическому ИЛИ по вариантам всех клеток
total_variants = 0
for i in range(0, 9):
total_variants |= view[i]
return total_variants
# проверить судоку на корректность (отсутствуют поля без вариантов)
def isCorrent(
sudoku # судоку
):
# ПОЯСНЕНИЯ:
# если хотя бы в одной из клеток судоку нет вариантов - судоку считается некорректной
for pos in range(0, c_sudoku_size):
if sudoku[pos] == 0:
return False
return True
# проверить судоку на завершённость (каждое поле содержит по 1 варианту)
def isCompleted(
sudoku # судоку
):
# ПОЯСНЕНИЯ:
# если хотя бы в одной из клеток судоку отличное от 1 вариантов - судоку считается незавершённой
for pos in range(0, c_sudoku_size):
if countCageVariants(sudoku[pos]) != 1:
return False
return True
# откинуть варианты в одной клетке
def clearCageVariants(
sudoku, # судоку
pos, # позиция клетки
variants # варианты, которые требуется удалить из клетки
):
# ПОЯСНЕНИЯ:
# доступные варианты кодируются соответствующим битом (1 - 1 бит, 2 - 2 бит, ...)
# таким образом откидывание вариантов в клетке сводится к скидываются битов в клетке, установленных в variants
sudoku[pos] = (sudoku[pos] | variants) ^ variants
# получить список клеток (отображение) из судоку
def getViewFromRow(
sudoku, # судоку
row, # ряд, который трубуется перенести из судоку в отображение
view # отображение
):
for i in range(0, 9):
view[i] = sudoku[getPos2(i, row)]
def getViewFromColumn(
sudoku, # судоку
column, # колонка, которую требуется перенести из судоку в отображение
view # отображение
):
for i in range(0, 9):
view[i] = sudoku[getPos2(column, i)]
def getViewFromCell(
sudoku, # судоку
block, # блок, который требуется перенести из судоку в отображение
view # отображение
):
for i in range(0, 9):
view[i] = sudoku[getPos4(block % 3, block // 3, i % 3, i // 3)]
# установить список клеток (отображение) в судоку
def setViewToRow(
sudoku, # судоку
row, # ряд судоку, в который трубуется перенести из отображения
view # отображение
):
for i in range(0, 9):
sudoku[getPos2(i, row)] = view[i]
def setViewToColumn(
sudoku, # судоку
column, # колонка судоку, в который трубуется перенести из отображения
view # отображение
):
for i in range(0, 9):
sudoku[getPos2(column, i)] = view[i]
def setViewToCell(
sudoku, # судоку
block, # block судоку, в который трубуется перенести из отображения
view # отображение
):
for i in range(0, 9):
sudoku[getPos4(block % 3, block // 3, i % 3, i // 3)] = view[i]
# проверить входит ли множество вариантов src в множество вариантов dst
def _issubset(
src, # исходные варианты
dst # конечные варианты
):
# ПОЯСНЕНИЯ:
# доступные варианты кодируются соответствующим битом (1 - 1 бит, 2 - 2 бит, ...)
# таким образом определение входит ли множество вариантов src в множество вариантов сводится к проверке установлены ли в dst биты, установленные в src
#
# если в src установлены только биты, установленные в dst, то src | dst не изменит dst (не будут установлены дополнительные биты)
return (src | dst) == dst
# проверить пересекаются ли множества вариантов src и dst
def _isunintersectedsets(
src, # исходные варианты
dst # конечные варианты
):
# ПОЯСНЕНИЯ:
# доступные варианты кодируются соответствующим битом (1 - 1 бит, 2 - 2 бит, ...)
# таким образом определение входит ли множество вариантов src в множество вариантов сводится к проверке установлены ли в dst биты, установленные в src
#
# если в src установлены только биты, не установленные в dst, то src & dst не должно содержать установленных бит
return (src & dst) == 0
# распаковать варианты
def unzip_variants(
numbers, # номера вариантов
variants # варианты
):
# ПОЯСНЕНИЯ:
# numbers: номера вариантов кодируются соответствующим битом (1 установленный бит в variants - 1 бит, 2 установленный бит в variants - 2 бит, ...)
# variants: доступные варианты кодируются соответствующим битом (1 - 1 бит, 2 - 2 бит, ...)
#
# требуется оставить установленными только те биты в variants, номера которых указаны в numbers
unzipped_variants = 0
pos = 0
for index in range(1, 10):
pos += (variants >> index) & 1
unzipped_variants |= (((variants >> index) & 1) * # текущий бит из variants
((numbers >> pos) & 1)) << index # стоит ли этот бит устанавливать - нет(0), да(1)
# ПОЯСНЕНИЕ: полный код
# for (int variants_index = 1 variants_index <= 9 variants_index++)
# {
# if (variants & (1 << variants_index))
# {
# pos += 1
#
# if (numbers & (1 << pos))
# unzipped_variants |= (1 << variants_index)
# }
# }
return unzipped_variants
# удалить лишние варианты
def dropViewVariant(
view # отображение
):
# определить все варианты для списка клеток
total_variants = getViewVariants(view)
# подсчитать кол-во всех вариантов
total_variants_amount = countCageVariants(total_variants)
# ПОЯСНЕНИЯ:
# чтобы откинуть лишние варианты в клетке требуется определить, что эти варианты встречаются в других клетках
# например, если варианты {1, 2} встречаются в двух клетках, то в остальных клетках они уже встречаться не могут
# ПОЯСНЕНИЯ:
# требуется перебирать не все варианты, а только рамером до total_variants_amount / 2, потому что все варианты размером больше были проанализированы размерами меньше
# перебрать все возможные сочетания вариантов
excluded_variants = 0
for variants_amount in range(1, total_variants_amount // 2 + 1):
# ПОЯСНЕНИЯ:
# для ускорения поиска сочетаний, все возможные сочетания вариантов предварительно вычислены и занесены в таблицу
# сочетания вариантов представляют собой номера вариантов и кодируются соответствующим битом (1 установленный бит в variants - 1 бит, 2 установленный бит в variants - 2 бит, ...)
# получить упакованные варианты для заданного кол-ва чисел
combinations = c_zipped_combinations[total_variants_amount - 1][variants_amount - 1]
# перебрать все сочетания для заданного кол-ва вариантов
for zipped_variants in combinations:
# ПОЯСНЕНИЯ:
# если некоторые варианты на предыдущих этапах уже были откинуты, то последующие сочетания с ними уже не требуется рассматривать
# например, если варианты {1, 2} были откинуты, то сочетание {1, 2, 5} уже не требуется анализировать
# не рассматривать исключённые варианты
if not _isunintersectedsets(zipped_variants, excluded_variants):
continue
# распаковать варианты, т.е. преобразовать номера вариантов в варианты
variants = unzip_variants(zipped_variants, total_variants)
# определить кол-во совпадений для заданного сочетания вариантов
total_count = 0
for pos in range(0, 9):
if _issubset(view[pos], variants):
total_count += 1
# если возможно удалить варианты, но удаление приведёт к удаление всех вариантов в какой-либо клетке - выйти
if total_count > variants_amount:
return False
# если возможно удалить варианты - удалить указанные варианты из всех клеток, которые имеют дополнительные варианты, кроме найденных
if total_count == variants_amount:
# исключить найденные варианты из списка возможных вариантов для следующих поисков
excluded_variants |= zipped_variants
# идалить найденные варианты из клеток
for pos in range(0, 9):
if not _issubset(view[pos], variants):
clearCageVariants(view, pos, variants)
return True
def dropVariants(
sudoku # судоку
):
view = list(range(9))
while True:
# сохранить копию судоку
old_sudoku = copy.copy(sudoku)
# удалить лишние варианты, но если удаление приведёт к удаление всех вариантов в какой-либо клетке - выйти, не продолжая дальнейший анализ
for i in range(0, 9):
getViewFromRow(sudoku, i, view)
if dropViewVariant(view) is False:
return False
setViewToRow(sudoku, i, view)
for i in range(0, 9):
getViewFromColumn(sudoku, i, view)
if dropViewVariant(view) is False:
return False
setViewToColumn(sudoku, i, view)
for i in range(0, 9):
getViewFromCell(sudoku, i, view)
if dropViewVariant(view) is False:
return False
setViewToCell(sudoku, i, view)
# если старый и новый варианты совпадают - выйти
if old_sudoku == sudoku:
break
return True
# заполнить судоку
def fillSudoku(
sudoku, # судоку
values # список значений
):
for j in range(0, 9):
for i in range(0, 9):
sudoku[getPos2(i, j)] = c_sudoku_all_variants if values[j][i] == ' ' else (1 << int(values[j][i]))
# перевести варианты клетки в строку
def variants2string(
variants # варианты
):
for variant in range(1, 10):
if variants & (1 << variant):
return str(variant)
return " "
# отобразить судоку
def showSudoku(
sudoku # судоку
):
for j in range(0, 9):
if j % 3 == 0:
print("-------------")
for i in range(0, 9):
if i % 3 == 0:
print("|", end="")
# получить значение поля
cell = sudoku[getPos2(i, j)]
# подсчитать кол-во вариантов
variants_amount = countCageVariants(cell)
print(variants2string(cell) if variants_amount == 1 else " ", end="")
print("|")
print("-------------")
# отобразить варианты в клетках судоку
def showVariants(
sudoku # судоку
):
for j in range(0, 9):
for i in range(0, 9):
# получить значение поля
cell = sudoku[getPos2(i, j)]
# подсчитать кол-во вариантов
variants_amount = countCageVariants(cell)
# сформировать перечень вариантов
variants = ""
for value in range(1, 10):
if cell & (1 << value):
variants += str(value)
else:
variants += "=" if variants_amount == 1 else " "
print("[" + variants + "]", end="")
if i % 3 == 2:
print(" ", end="")
print()
if j % 3 == 2:
print()
# решить судоку и найти путь решения
def CalculateVariant(
sudoku, # судоку
moves,
best_moves
):
# если текущий вариант превышает лучший вариант, не искать дальнейшее решение
if len(best_moves[0]) > 0 and len(moves) >= len(best_moves[0]):
return False
# удалить лишние варианты и если удаление лишних вариантов привело к некорректности судоку - не продолжать решать судоку
if dropVariants(sudoku) is False:
return False
# найти ближайшую клетку, содержащую два варианта
pos = -1
for i in range(0, c_sudoku_size):
if countCageVariants(sudoku[i]) == 2:
pos = i
break
# если клетка не найдена - не продолжать решать судоку
if pos == -1:
print(len(best_moves[0]), ("NO", "YES")[isCompleted(sudoku)], moves)
if isCompleted(sudoku) is True:
best_moves[0] = copy.copy(moves)
return True
else:
return False
# перебрать варианты в выбранной клетке
for i in range(1, 10):
if sudoku[pos] & (1 << i):
# продублировать судоку и установить в клетку выбранный вариант
new_sudoku = copy.copy(sudoku)
new_sudoku[pos] = 1 << i
# добавить выбранный ход в список
moves.append((pos, i))
# если выбранный вариант приводит к успеху сбора субоку, не рассматривать последующие варианты
res = CalculateVariant(new_sudoku, moves, best_moves)
# убрать выбранный ход из списка
moves.pop()
if res:
return True
return False
# решить судоку и найти все пути решения
def CalculateAllVariants(
sudoku, # судоку
moves,
best_moves
):
# если текущий вариант превышает лучший вариант, не искать дальнейшее решение
if len(best_moves[0]) > 0 and len(moves) >= len(best_moves[0]):
return False
# удалить лишние варианты и если удаление лишних вариантов привело к некорректности судоку - не продолжать решать судоку
if dropVariants(sudoku) is False:
return False
# найти все выборы из заданного кол-ва вариантов в одной клетке
positions = []
for i in range(0, c_sudoku_size):
if 2 <= countCageVariants(sudoku[i]) <= 3:
positions.append(i)
# если ни одна клетка не найдена - не продолжать решать судоку
if len(positions) == 0:
if isCompleted(sudoku) is True:
best_moves[0] = copy.copy(moves)
return True
else:
return False
# перебрать все клетки
res = False
for pos in positions:
# перебрать варианты в клетке
for i in range(1, 10):
if sudoku[pos] & (1 << i):
# продублировать судоку и установить в клетку выбранный вариант
new_sudoku = copy.copy(sudoku)
new_sudoku[pos] = 1 << i
# добавить выбранный ход в список
moves.append((pos, i))
# если выбранный вариант приводит к успеху сбора субоку, не рассматривать последующие варианты
local_res = False
if len(moves) < 4:
local_res = CalculateAllVariants(new_sudoku, moves, best_moves)
else:
local_res = CalculateVariant(new_sudoku, moves, best_moves)
# убрать выбранный ход из списка
moves.pop()
if local_res is True:
res = True
break
return res
sudoku = list(range(81))
#fillSudoku(sudoku, [
# "1 7 9 ",
# " 3 2 8",
# " 96 5 ",
# " 53 9 ",
# " 1 8 2",
# "6 4 ",
# "3 1 ",
# " 4 7",
# " 7 3 ",
#])
fillSudoku(sudoku, [
" 12",
" 3",
" 23 4 ",
" 18 5",
" 6 7 8 ",
" 9 ",
" 85 ",
"9 4 5 ",
"47 6 ",
])
moves = list()
best_moves = list(range(1))
best_moves[0] = []
tic = time.time()
#CalculateAllVariants(sudoku, moves, best_moves)
CalculateVariant(sudoku, moves, best_moves)
print(time.time() - tic)
print(f"[" + str(len(best_moves[0])) + "]", end=" ")
for move in best_moves[0]:
print("(" + str(move[0]) + ", " + str(move[1]) + ")", end=" ")
sudoku[move[0]] = 1 << move[1];
print("\n")
dropVariants(sudoku)
showSudoku(sudoku)
Автор решения: Zhihar
→ Ссылка
В один ответ не влезает
Вот менее оптимизированный код (он работает где-то в 10 раз медленнее и судоку решает за 6 секунд), зато более понятный для разбора
import copy
import itertools
import time
# получить позицию
def getPos2(i, j):
return i + j * 9
def getPos4(i, j, m, n):
return getPos2(i * 3 + m, j * 3 + n)
# установить в поле значение
def fillSudoku(values):
return [[int(x), ] if x != " " else list(range(1, 10)) for x in "".join(values)]
# напечатать судоку
def printSudoku(sudoku):
for j in range(0, 9):
if j % 3 == 0:
print("-" * 13)
for i in range(0, 9):
if i % 3 == 0:
print("|" , end="")
print(str(sudoku[getPos2(i, j)][0]) if len(sudoku[getPos2(i, j)]) == 1 else " ", end="")
print("|")
print("-" * 13)
# напечатать варианты
def printVariants(sudoku):
print(*[
"[" + "".join(
[str(obj) if obj in sudoku[pos] else "=" if len(sudoku[pos]) == 1 else " "
for obj in range(1, 10)]) + "]" +
("\n\n" if (pos + 1) % 27 == 0 else "\n" if (pos + 1) % 9 == 0 else " " if (pos + 1) % 3 == 0 else ""
)
for pos in range(len(sudoku))
], sep="")
# подсчитать все варианты выбора в судоку
def countAllVariants(sudoku):
count = 0
for i in sudoku:
count += len(i)
return count
# проверить судоку на корректность
def isCorrent(sudoku):
for i in sudoku:
if len(i) == 0:
return False
return True
# проверить судоку на завершённость
def isCompleted(sudoku):
for i in sudoku:
if len(i) != 1:
return False
return True
# откинуть варианты в одной ячейке
def clearVariants(sudoku, pos, variants):
sudoku[pos] = [value for value in sudoku[pos] if value not in variants]
# получить список ячеек
def getViewFromRow(sudoku, row):
return [sudoku[getPos2(i, row)] for i in range(0, 9)]
def getViewFromColumn(sudoku, column):
return [sudoku[getPos2(column, i)] for i in range(0, 9)]
def getViewFromCell(sudoku, cell):
return [sudoku[getPos4(cell % 3, cell // 3, i % 3, i // 3)] for i in range(0, 9)]
# установить список ячеек
def setViewToRow(sudoku, row, view):
for i in range(0, 9):
sudoku[getPos2(i, row)] = view[i]
def setViewToColumn(sudoku, column, view):
for i in range(0, 9):
sudoku[getPos2(column, i)] = view[i]
def setViewToCell(sudoku, cell, view):
for i in range(0, 9):
sudoku[getPos4(cell % 3, cell // 3, i % 3, i // 3)] = view[i]
# откинуть лишние варианты
def dropViewVariant(view):
# собрать все возможные варианты
total_variants = set()
for i in view:
total_variants.update(i)
# перебрать все возможные варианты чисел
for size in range(1, len(total_variants)):
# вычислить варианты для заданного кол-ва чисел
local_variants = list(itertools.combinations(total_variants, size))
# перебрать все варианты для заданного кол-ва чисел
for variants in local_variants:
# проверить кол-во вариантов для заданного кол-ва чисел
total_count = 0
for obj in view:
if set(obj).issubset(variants):
total_count += 1
# если возможно сократить - сократить все поля, кроме первых size полей
if total_count >= size:
count = 0
for pos in range(0, len(view)):
if set(view[pos]).issubset(variants) and count < size:
count += 1
else:
clearVariants(view, pos, variants)
def dropVariants(sudoku):
while True:
# сохранить старый вариант
old_sudoku = copy.deepcopy(sudoku)
# откинуть варианты
for i in range(0, 9):
view = getViewFromRow(sudoku, i)
dropViewVariant(view)
setViewToRow(sudoku, i, view)
for i in range(0, 9):
view = getViewFromColumn(sudoku, i)
dropViewVariant(view)
setViewToColumn(sudoku, i, view)
for i in range(0, 9):
view = getViewFromCell(sudoku, i)
dropViewVariant(view)
setViewToCell(sudoku, i, view)
# если старый и новый варианты совпадают - выйти
if sudoku == old_sudoku:
break
# решить судоку и найти путь решения
def CalculateVariant(sudoku, moves=[]):
global global__best_moves
# если кол-во ходов превышает лучшее кол-во ходов - не рассматривать дальше
if global__best_moves != [] and len(moves) >= len(global__best_moves):
return False
# откинуть лишние варианты
dropVariants(sudoku)
# print(f"кол-во вариантов: {countAllVariants(sudoku)}, ошибки: {('НЕТ', 'ДА')[not isCorrent(sudoku)]}")
# если удаление лишних вариантов привело к некорректности судоку - не продолжать решать судоку
if not isCorrent(sudoku):
return False
# найти ближайший выбор из двух вариантов в одной клетке
pos = -1
for i in range(len(sudoku)):
if len(sudoku[i]) == 2:
pos = i
break
# если варианты не найдены - не продолжать решать судоку
if pos == -1:
if isCompleted(sudoku) and (global__best_moves == [] or len(moves) < len(global__best_moves)):
global__best_moves = moves
print(len(global__best_moves), ("NO", "YES")[isCompleted(sudoku)], moves)
return isCompleted(sudoku)
# перебрать варианты
for obj in sudoku[pos]:
new_sudoku = copy.deepcopy(sudoku)
new_sudoku[pos] = [obj, ]
new_moves = copy.deepcopy(moves)
new_moves.append((pos, obj))
if CalculateVariant(new_sudoku, new_moves):
return True
return False
# решить судоку и найти все пути решения
def CalculateAllVariants(sudoku, moves):
global global__best_moves
if global__best_moves != [] and len(moves) >= len(global__best_moves):
return False
# откинуть лишние варианты
dropVariants(sudoku)
# print(f"кол-во вариантов: {countAllVariants(sudoku)}, ошибки: {('НЕТ', 'ДА')[not isCorrent(sudoku)]}")
# если удаление лишних вариантов привело к некорректности судоку - не продолжать решать судоку
if not isCorrent(sudoku):
return False
# найти все выборы из двух вариантов в одной клетке
positions = []
for i in range(len(sudoku)):
if 2 <= len(sudoku[i]) <= 4:
positions.append(i)
# если варианты не найдены - не продолжать решать судоку
if len(positions) == 0:
if isCompleted(sudoku) and (global__best_moves == [] or len(moves) < len(global__best_moves)):
global__best_moves = moves
print(len(global__best_moves), ("NO", "YES")[isCompleted(sudoku)], moves)
return isCompleted(sudoku)
# перебрать варианты
res = False
for pos in positions:
for obj in sudoku[pos]:
new_sudoku = copy.deepcopy(sudoku)
new_sudoku[pos] = [obj, ]
new_moves = copy.deepcopy(moves)
new_moves.append((pos, obj))
if len(moves) < 4:
if CalculateAllVariants(new_sudoku, new_moves):
res = True
break
else:
if CalculateVariant(new_sudoku, new_moves):
res = True
break
return res
# создать пустое поле судоку
sudoku = fillSudoku([
"1 7 9 ",
" 3 2 8",
" 96 5 ",
" 53 9 ",
" 1 8 2",
"6 4 ",
"3 1 ",
" 4 7",
" 7 3 ",
])
global__best_moves = []
CalculateVariant(sudoku)
print("best moves:", global__best_moves)
for move in global__best_moves:
sudoku[move[0]] = [move[1],]
dropVariants(sudoku)
printSudoku(sudoku)
Автор решения: Stanislav Volodarskiy
→ Ссылка
Примитивный решатель судоку перебирает клетки с нулями. В каждую такую клетку пытается вписать разные цифры и сразу проверяет строку, столбец и блок с этой клеткой. Если успех, то переходим к следующей клетке. Если не успех, то возвращаемся к предыдущей клетке.
Примитивный он так как проверка новых цифр медленная и порядок перебора клеток не лучший: следует начинать с клеток в которых мало подходящих вариантов.
Зато просто:
def solve(field):
def is_valid_set(seq):
s = set()
for v in seq:
if v != 0:
if v in s:
return False
s.add(v)
return True
def is_valid_row(i):
return is_valid_set(field[i][j] for j in range(9))
def is_valid_col(j):
return is_valid_set(field[i][j] for i in range(9))
def is_valid_block(ii, jj):
return is_valid_set(field[i][j] for i in range(ii, ii + 3) for j in range(jj, jj + 3))
def solve(k):
if k == 81:
yield field
return
i = k // 9
j = k % 9
if field[i][j] == 0:
for v in range(1, 10):
field[i][j] = v
if is_valid_row(i) and is_valid_col(j) and is_valid_block(i - i % 3, j - j % 3):
yield from solve(k + 1)
field[i][j] = 0
else:
yield from solve(k + 1)
return solve(0)
puzzle = [
[0, 0, 6, 1, 0, 0, 0, 0, 8],
[0, 8, 0, 0, 9, 0, 0, 3, 0],
[2, 0, 0, 0, 0, 5, 4, 0, 0],
[4, 0, 0, 0, 0, 1, 8, 0, 0],
[0, 3, 0, 0, 7, 0, 0, 4, 0],
[0, 0, 7, 9, 0, 0, 0, 0, 3],
[0, 0, 8, 4, 0, 0, 0, 0, 6],
[0, 2, 0, 0, 5, 0, 0, 8, 0],
[1, 0, 0, 0, 0, 2, 5, 0, 0]
]
for f in solve(puzzle):
for row in f:
print(''.join(map(str, row)))
print()
$ python primitive-sudoku-solver.py 346127958 785694132 219385467 462531879 931278645 857946213 598413726 624759381 173862594