python sudoku puzzle? проверка головоломки до и после

Question

Я написал решение Sudoku для очень простых проблем Sudoku в Python. Как это работает, проверяя каждый пустой квадрат, и если есть только одно возможное число, которое является законным, замените пустой квадрат на это число. Как только он прошел всю головоломку, если еще есть еще несколько пустых квадратов, он снова называет себя новой головоломкой. В той части, где у меня возникают проблемы, я хочу, чтобы решатель проверял в конце каждого вызова, если головоломка такая же, как и в начале вызова, и если она не изменилась, это означает, что все оставшиеся пустые квадраты имеют более одного возможного значения, и поэтому решатель должен вернуть False, чтобы указать, что решатель не способен решить эту конкретную загадку. Однако, когда я попытался реализовать это, Solver только проходит головоломку один раз и возвращает False. Вот мой код:

def Solver(puzzle): 

    oldpuzzle = puzzle 
    count = 0 

    for row in range(9): 

     for col in range(9): 
      if puzzle[row][col] == '0': 
       possible, numpossible = getPossible(puzzle, row, col) 

       if numpossible == 1: 
        puzzle[row][col] = possible[0] 
     count += puzzle[row].count('0') 

    if count > 0: 
     if oldpuzzle == puzzle: 
      return False 
     else: 
      Solver(puzzle) 
    else: 
     return True 

Функция getPossible() возвращает список возможных значений и длину списка.

Вот главная() функция:

def main():
 

puzzle = [ 
['0','2','0','1','7','8','0','3','0'], 
['0','4','0','3','0','2','0','9','0'], 
['1','0','0','0','0','0','0','0','6'], 
['0','0','8','6','0','3','5','0','0'], 
['3','0','0','0','0','0','0','0','4'], 
['0','0','6','7','0','9','2','0','0'], 
['9','0','0','0','0','0','0','0','2'], 
['0','8','0','9','0','1','0','6','0'], 
['0','1','0','4','3','6','0','5','0'] 
] 

if Solver(puzzle): 
    print "Solved!" 
    for row in puzzle: 
     print ' '.join(row) 
else: 
    print "Failed!" 

Как я могу получить программу, чтобы правильно сравнить состояние головоломки до и после того, как цикл?

Answer 1

Ваша проблема в том, что линия:

oldpuzzle = puzzle 

Делает ссылку на puzzle под названием oldpuzzelне копию, чтобы они всегда одинаковы - вам необходимо либо скопировать puzzle в oldpuzzle с copy.copy или более просто установить флаг:

def Solver(puzzle): 
    Changed = False 

и в:

  if numpossible == 1: 
       Changed = True 

Затем проверьте изменение, если оно вернёт его.

Answer 2

Вы устанавливаете ссылку на puzzle в oldpuzzle, следовательно, если вы делаете какие-либо изменения в puzzle, она будет отражать в oldpuzzle, а также. и puzzle всегда будет oldpuzzle.

Я не думаю, что вам нужно установить головоломку на старую головоломку (или вам нужно сохранить полную головоломку в начале).

Согласно логике, количество ячеек 0 никогда не увеличится, а ячейка, отмеченная ненулевым ранее, никогда не станет отмеченной 0.

Следовательно, вы можете просто сохранить счет 0 s в начале, а затем в конце проверить, изменилось ли число 0 s, если оно имеет хорошее, в противном случае возвращает False.

Пример кода -

def Solver(puzzle): 

    oldcount = sum(1 for row in puzzle for cell in row if cell == '0') 
    count = 0 

    for row in range(9): 

     for col in range(9): 
      if puzzle[row][col] == '0': 
       possible, numpossible = getPossible(puzzle, row, col) 

       if numpossible == 1: 
        puzzle[row][col] = possible[0] 
     count += puzzle[row].count('0') 

    if count > 0: 
     if oldcount == count: 
      return False 
     else: 
      Solver(puzzle) 
    else: 
     return True 

Answer 3

Проблема заключается в том, что if oldpuzzle == puzzle всегда будет верно, потому что, когда oldpuzzle создается она не станет копией списка головоломки, а дубликат. Это означает, что если вы измените puzzle, то oldpuzzle также изменится.

list1 = [1, 2, 3] 
list2 = list1 
list1[0] = 4 
print(list2) 
# this will print [4, 2, 3] 

Один из способов сделать oldpuzzle копию из puzzle является использование библиотеки копирования. В этом случае требуется сделать глубокую копию puzzle, потому что это список со списком в нем. Один из способов сделать это - использовать deep copy function from the copy library. Таким образом, функция будет выглядеть примерно так:

from copy import deepcopy # at the top of the document 

def Solver(puzzle): 

    oldpuzzle = deepcopy(puzzle) 
    count = 0 

    # ... and then the rest