только что начал с некоторого кода на Python, и я пытался сделать решение судоку, используя алгоритм обратного отслеживания, опубликованный здесь
Итак, у меня есть это прямо сейчас:
SUDOKU= [[0, 6, 0, 1, 0, 4, 0, 5, 0],
[0, 0, 8, 3, 0, 5, 6, 0, 0],
[2, 0, 0, 0, 0, 0, 0, 0, 1],
[8, 0, 0, 4, 0, 7, 0, 0, 6],
[0, 0, 6, 0, 0, 0, 3, 0, 0],
[7, 0, 0, 9, 0, 1, 0, 0, 4],
[5, 0, 0, 0, 0, 0, 0, 0, 2],
[0, 0, 7, 2, 0, 6, 9, 0, 9],
[0, 4, 0, 5, 0, 8, 2, 7, 0]]
sublist = []
def validate(value, y, x, sudoku):
# check linea
for idx in range(0,9):
if sudoku[y][idx] == value:
return False
for idy in range(0, 9):
if sudoku[idy][x] == value:
return False
return True
def validate_square(value, y, x, sudoku):
if y < 3 and x < 3:
aux_list = [aux_list[0:3] for aux_list in sudoku[0:3]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
elif y < 3 and (x >= 3 and x < 6):
aux_list = [aux_list[3:6] for aux_list in sudoku[0:3]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
elif y < 3 and (x >= 6 and x < 9):
aux_list = [aux_list[6:9] for aux_list in sudoku[0:3]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
elif (y >= 3 and y < 6) and x < 3:
aux_list = [aux_list[0:3] for aux_list in sudoku[3:6]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
elif (y >= 3 and y < 6) and (x >= 3 and x < 6):
aux_list = [aux_list[3:6] for aux_list in sudoku[3:6]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
elif (y >= 3 and y <6) and (x >= 6 and x < 9):
aux_list = [aux_list[6:9] for aux_list in sudoku[3:6]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
elif (y >= 6 and y < 9) and x < 3:
aux_list = [aux_list[0:3] for aux_list in sudoku[6:9]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
elif (y >= 6 and y < 9) and (x >= 3 and x < 6):
aux_list = [aux_list[3:6] for aux_list in sudoku[6:9]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
elif (y >= 6 and y < 9) and (x >= 6 and x < 9):
aux_list = [aux_list[6:9] for aux_list in sudoku[6:9]]
if value in [j for i in aux_list for j in i]:
return False
else:
return True
else:
return True
def auto_complete(sudoku):
for idy in range(0,9):
for idx in range(0,9):
if sudoku[idy][idx] == 0:
for attempt in range(1, 10):
if validate(attempt, idy, idx, sudoku) == True and validate_square(attempt, idy, idx, sudoku) == True:
sudoku[idy][idx] = attempt
if __name__ == "__main__":
auto_complete(SUDOKU)
for i in SUDOKU:
print(i)
Вот решение, которое я получаю с ним:
[9, 6, 3, 1, 8, 4, 7, 5, 0]
[4, 7, 8, 3, 9, 5, 6, 2, 0]
[2, 5, 0, 7, 6, 0, 8, 9, 1]
[8, 9, 5, 4, 3, 7, 1, 0, 6]
[1, 2, 6, 8, 5, 0, 3, 0, 7]
[7, 3, 0, 9, 2, 1, 5, 8, 4]
[5, 8, 9, 0, 7, 3, 4, 6, 2]
[3, 1, 7, 2, 4, 6, 9, 0, 9]
[6, 4, 0, 5, 1, 8, 2, 7, 3]
А это ожидаемое решение (правильное решение): Судоку
На данный моменту меня есть алгоритм, который может частично выполнять возврат, но когда дело доходит до значения, которое не соответствует его ячейке (нарушения строки, строки, квадрата), оно просто оставляет его пустым, из поста википедии я понимаю, что я должен перейти на позицию назад (вычесть 1к idx, может быть?) добавьте 1 к этой ячейке и переоцените это значение.
Я совершенно потерян, так что любые предложения о том, как улучшить этот код питонскими способами?
Кроме того, есть списокперечисляет лучший способ структурировать данные судоку?Похоже, они работают немного иначе, чем массивы (откуда я, а не эксперт)
Спасибо всем за чтение!