Два дня go, мне дали проблему судоку, которую я пытался решить с помощью Python 3. Мне сообщили, что решение существует, но я не уверен, существует ли несколько решений.
Проблема в следующем: сетка судоку размером 9x9 полностью пуста. Однако он содержит цветные поля , и внутри этих полей сумма должна быть квадратным числом . Помимо этого, применяются нормальные правила судоку .
Проблема здесь в том, что не решает головоломку судоку, а скорее генерирует жизнеспособную головоломку, которая удовлетворяет правилам цветные коробки .
Моя стратегия
Используя массивы numpy, я разделил сетку на 81 индекс, который можно переставить в сетку 9x9.
import numpy as np
print(np.array([i for i in range(81)]).reshape((9, 9)))
->
[[ 0 1 2 3 4 5 6 7 8]
[ 9 10 11 12 13 14 15 16 17]
[18 19 20 21 22 23 24 25 26]
[27 28 29 30 31 32 33 34 35]
[36 37 38 39 40 41 42 43 44]
[45 46 47 48 49 50 51 52 53]
[54 55 56 57 58 59 60 61 62]
[63 64 65 66 67 68 69 70 71]
[72 73 74 75 76 77 78 79 80]]
Вот список, содержащий все блоки индексов.
boxes = [[44, 43, 42, 53],[46, 47, 38],[61, 60],[69, 70],[71, 62],
[0, 9, 18],[1, 10, 11, 20],[2, 3, 12],[4, 13, 14],[5, 6],
[7, 8],[17, 26, 35],[21, 22, 23],[15, 16, 24, 25, 34],
[27, 36, 37],[19, 28, 29],[45, 54],[55, 56],[63, 64, 65],
[72, 73, 74],[57, 66, 75 ],[58, 59, 67, 68],[76, 77],[78, 79, 80]]
Как видно из рисунка или из приведенного выше массива, ящики сгруппированы в блоки 2, 3, 4 или 5 (8 двойок, 12 тройок, 3 четверки, 1 пятерка). Я также заметил, что ящик может содержать несколько чисел без нарушения каких-либо правил судоку, но возможно только 2 числа из одного. Учитывая эту информацию, наибольшим возможным квадратом будет 36, как 9 + 9 + 8 + 7 + 6 = 39, и, таким образом, никакая сумма блока не может достичь 49. Узнать, содержит ли сумма списка квадратное число Я сделал следующую функцию:
def isSquare(array):
if np.sum(array) in [i**2 for i in range(1,7)]:
return True
else:
return False
Чтобы выяснить, содержит ли список правильное количество дубликатов, то есть более одного дубликата только одного числа, я сделал следующую функцию :
def twice(array):
counter = [0]*9
for i in range(len(array)):
counter[array[i]-1]+=1
if 3 in counter:
return False
if counter.count(2)>1:
return False
return True
Теперь, учитывая цифры 1-9, существуют ограниченные способы решения списка, если список должен суммироваться в квадратное число. Используя itertools , я мог бы найти решения, разделив их на массив, где индекс 0 содержит блоки двойок, индекс 1 содержит блоки тройок и т. Д.
from itertools combinations_with_replacement
solutions = []
for k in range(2, 6):
solutions.append([list(i) for i in combinations_with_replacement(np.arange(1, 10), k) if
isSquare(i) and twice(i)])
Однако любая перестановка этих списков является реальным решением «квадратной задачи». При повторном использовании itertools общее количество возможных ящиков (без правил судоку) составляет 8782.
from itertools import permutations
def find_squares():
solutions = []
for k in range(2, 6):
solutions.append([list(i) for i in combinations_with_replacement(np.arange(1, 10), k) if
isSquare(i) and twice(i)])
s = []
for item in solutions:
d=[]
for arr in item:
for k in permutations(arr):
d.append(list(k))
s.append(d)
return s # 4-dimensional array, max 2 of each
solutions = find_squares()
total = sum([len(i) for i in solutions])
print(total)
-> 8782
Этого должно быть достаточно для реализации функциональности, которая решает, является ли доска легальной, то есть строки, столбцы и поля содержат только одну из цифр 1-9. Моя реализация:
def legal_row(arr):
for k in range(len(arr)):
values = []
for i in range(len(arr[k])):
if (arr[k][i] != 0):
if (arr[k][i] in values):
return False
else:
values.append(arr[k][i])
return True
def legal_column(arr):
return legal_row(np.array(arr, dtype=int).T)
def legal_box(arr):
return legal_row(arr.reshape(3,3,3,3).swapaxes(1,2).reshape(9,9))
def legal(arr):
return (legal_row(arr) and legal_column(arr) and legal_box(arr))
Трудности со временем выполнения
Простой подход заключается в проверке каждой комбинации каждого блока. Я сделал это и создал несколько жизнеспособных проблем, однако из-за сложности моего алгоритма это занимает слишком много времени.
Вместо этого я попытался рандомизировать некоторые свойства: порядок блоков и порядок решений. Используя это, я ограничил количество попыток и проверил, является ли решение жизнеспособным:
attempts = 1000
correct = 0
possibleBoards = []
for i in range(1, attempts+1):
board = np.zeros((9, 9), dtype=int)
score = 0
shapes = boxes
np.random.shuffle(shapes)
for block in shapes:
new_board = board
new_1d = board.reshape(81)
all_sols = solutions[len(block)-2]
np.random.shuffle(all_sols)
for sols in all_sols:
#print(len(sols))
new_1d[block] = sols
new_board = new_1d.reshape((9, 9))
if legal(new_board):
board = new_board
score+=1
break
confirm = board.reshape(81)
#solve(board) # Using my solve function, not important here
# Note that without it, correct would always be 0 as the middle of the puzzle has no boxes
confirm = board.reshape(81)
if (i%1000==0 or i==1):
print("Attempt",i)
if 0 not in confirm:
correct+=1
print(correct)
possibleBoards.append(board)
В приведенном выше коде переменная оценка указывает, сколько блоков алгоритм может найти во время попытки. Правильная переменная указывает, сколько из созданных досок судоку может быть завершено. Если вас интересует, насколько хорошо это было сделано в 700 попытках, вот некоторые stats (Это историческая диаграмма, ось X представляет баллы, а ось Y представляет, сколько из каждого балла присутствовало во время этих 700 попыток).
Что мне нужно помочь с
Я изо всех сил пытаюсь найти реальный способ найти решение этой проблемы, которое на самом деле может работать в ограниченное количество времени. Я был бы очень признателен за любые советы относительно того, как сделать часть моего кода быстрее или лучше, любые идеи о другом подходе к проблеме, любые решения проблемы или некоторые полезные советы по Python / Numpy, относящиеся к этой проблеме.