#python #numpy #sudoku
#python #numpy #судоку
Вопрос:
Я попытался оптимизировать этот код, и мой окончательный код был таким, как показано ниже
import numpy as np
sudoku = np.array([[0, 9, 0, 0, 5, 0, 6, 0, 8],
[0, 0, 0, 7, 1, 0, 3, 5, 0],
[2, 1, 0, 0, 0, 0, 7, 0, 4],
[0, 0, 1, 5, 0, 0, 0, 0, 6],
[6, 3, 0, 2, 0, 8, 0, 4, 5],
[7, 0, 0, 0, 0, 4, 9, 0, 0],
[9, 0, 3, 0, 0, 0, 0, 2, 1],
[0, 4, 8, 0, 2, 7, 0, 0, 0],
[5, 0, 6, 0, 8, 0, 0, 3, 0]])
#Checking if the number (n) can be placed there (row, col)
def check(sudoku, row, col, n):
# Row check
if np.sum(sudoku[row,:] == n) != 0: return False;
# Col check
if np.sum(sudoku[:,col] == n) != 0: return False;
# Sqr check
row0, col0 = (row//3)*3, (col//3)*3
if np.sum(sudoku[row0:row0 3,col0:col0 3] == n) != 0: return False;
return True
def solve_sudoku(sudoku):
rows, cols = np.where(sudoku == 0)
for row in rows:
for col in cols:
for num in range(1, 10):
if check(sudoku, row, col, num):
sudoku[row, col] = num
solve_sudoku(sudoku)
sudoku[row, col] = 0
return
print(sudoku)
return sudoku
solved = solve_sudoku(sudoku)
Моя проблема в том, что, несмотря на то, что решение успешно напечатано, как показано ниже, переменная solved является просто нетипичной и ничего не хранит.
[[3 9 7 4 5 2 6 1 8]
[8 6 4 7 1 9 3 5 2]
[2 1 5 8 3 6 7 9 4]
[4 8 1 5 9 3 2 7 6]
[6 3 9 2 7 8 1 4 5]
[7 5 2 1 6 4 9 8 3]
[9 7 3 6 4 5 8 2 1]
[1 4 8 3 2 7 5 6 9]
[5 2 6 9 8 1 4 3 7]]
TL; DR Функция выводит решение, но ничего не возвращает. Что я должен сделать, чтобы сохранить распечатанное решение?
Комментарии:
1. Вам нужно использовать результат вашего рекурсивного вызова
solve_sudokuи проверить, завершена ли игра на этом этапе.
Ответ №1:
Рассмотрим этот код:
if check(sudoku, row, col, num):
sudoku[row, col] = num
solve_sudoku(sudoku)
sudoku[row, col] = 0 # undo this move
Если судоку разрешимо, solve_sudoku(sudoku) вызов в конечном итоге найдет решение. Когда вы получите свое решение, вам следует немедленно прекратить отслеживание с помощью return . В противном случае следующая строка sudoku[row, col] = 0 отменит найденное вами решение, и дальнейшие итерации продолжат попытки следующих возможных чисел. Поскольку у Sudoku есть только одно решение, проверка дополнительных чисел после нахождения решения не требуется. Вы можете просто вернуть истинное значение, чтобы завершить рекурсию.
Например, вы можете написать код, подобный этому:
if solve_sudoku(sudoku):
return True
или
if solve_sudoku(sudoku):
return sudoku
Это предотвращает sudoku[row, col] = 0 удаление решения и в конечном итоге возвращает решенную сетку исходному вызывающему после развертывания стека рекурсивных вызовов.
Ответ №2:
Проблема здесь, в вашем коде:
solve_sudoku(sudoku)
sudoku[row, col] = 0
return
В первой строке вы повторяетесь, но игнорируете возвращаемое значение, которое отбрасывает любое возвращаемое значение из этого вызова и все рекурсии ниже него.
В последней строке вы возвращаете значение по умолчанию на None . Любое из этих действий нарушает непрерывность возвращаемых значений рекурсии.
Ответ №3:
print(sudoku) Вызов происходит, когда solve_sudoku вызывается с полностью заполненным массивом судоку (без каких-либо оставшихся нулей), а не в рекурсивном вызове верхнего уровня.
Каждый раз, когда solve_sudoku вызывается неполный массив судоку, вы проверяете каждое число от одного до десяти в самой верхней левой ячейке, заполненной нулем, и если число может быть помещено в ячейку, вы помещаете его туда, пытаетесь решить остальную часть сетки, а затем возвращаете ячейке значение нуля. Как только вы сделаете это для каждого числа от одного до десяти, вы вернетесь None , вот почему вы видите None возврат из solve_sudoku вызова верхнего уровня.
Ответ №4:
Через несколько часов я придумал это решение. решаемая задача сохраняет решение сейчас.
import numpy as np
sudoku = np.array([[0, 9, 0, 0, 5, 0, 6, 0, 8],
[0, 0, 0, 7, 1, 0, 3, 5, 0],
[2, 1, 0, 0, 0, 0, 7, 0, 4],
[0, 0, 1, 5, 0, 0, 0, 0, 6],
[6, 3, 0, 2, 0, 8, 0, 4, 5],
[7, 0, 0, 0, 0, 4, 9, 0, 0],
[9, 0, 3, 0, 0, 0, 0, 2, 1],
[0, 4, 8, 0, 2, 7, 0, 0, 0],
[5, 0, 6, 0, 8, 0, 0, 3, 0]])
solved = np.zeros_like(sudoku)
def check(arg, row, col, n):
if np.sum(arg[row,:] == n) != 0: return False;
if np.sum(arg[:,col] == n) != 0: return False;
row0, col0 = (row//3)*3, (col//3)*3
if np.sum(arg[row0:row0 3,col0:col0 3] == n) != 0: return False;
return True
def solve_sudoku(arg):
global solved
rows, cols = np.where(arg == 0)
for row in rows:
for col in cols:
for num in range(1, 10):
if check(arg, row, col, num):
arg[row, col] = num
solve_sudoku(arg)
arg[row, col] = 0
return
solved = arg.copy()
solve_sudoku(sudoku)
Я не знаю, является ли это лучшим способом оптимизации кода, отзывы приветствуются.
Комментарии:
1. Это плохая идея использовать глобальное состояние подобным образом. Он хрупкий (изменения имени переменной нарушают функцию), он не возвращается, в большой кодовой базе было бы кошмаром, если бы произошла ошибка, чтобы выяснить, какие функции, связанные с глобальным состоянием, что и когда сделали. Лучше вернуть решение в стек вызовов, чтобы все изменения состояния были полностью внутренними для функции.
Ответ №5:
def check(grid, num, x, y):
for i in range(9):
if grid[i][y] == num:
return False
for j in range(9):
if grid[x][j] == num:
return False
x0 = (x//3) * 3
y0 = (y//3) * 3
for i in range(3):
for j in range(3):
if grid[x0 i][y0 j] == num:
return False
return True
def solve(grid):
for i in range(9 1):
if i==9:
return True
for j in range(9):
if grid[i][j] == 0:
for num in range(1,10):
if check(grid, num, i, j):
grid[i][j] = num
if solve(grid):
return True
grid[i][j] = 0
return False
Это должно сработать для вас. Он не возвращает массив, но изменяет его. Так что, если вы пройдете
solve(sudoku_grid)
а затем выведите sudoku_grid, это даст вам решаемый результат