Brute Force Sudoku рекурсии в Python

Question

Я пытался реализовать грубой силы подход к решению головоломки судоку с помощью Python, как описано в следующей ссылке: http://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Brute-force_algorithm

Я знаю, есть и другие темы, с тем же вопросом. Я прочитал их все и все еще испытываю проблемы.

Вот мой код рекурсии:

def recurse(x, k, grid): 
    if x > 8: 
     for line in grid: 
      print line 
     raw_input() 
    if grid[x][k] == '0': 
     for number in '123456789': 
      if clear(number, x, k, grid): 
       grid[x] = grid[x][0:k] + number + grid[x][k+1:]   
       k += 1 
       if k > 8: 
        x += 1 
        k = 0 
       recurse(x, k, grid) 
       k -= 1 
       if k < 0: 
        x -= 1 
        k = 8 
    else: 
     k += 1 
     if k > 8: 
      x += 1 
      k = 0 
     recurse(x, k, grid) 

В основном я держу судоку в массиве 9x9 слотов, где сетка [х] получает доступ к XTH линии всей судоку и сетки [х] [K ] обращается к k-му числу в x-й строке.

Существует функция, называемая «ясность», которая определяет, может ли определенное число входить в этот слот или нет. Я тестировал его много раз, и он работает правильно. Проблема здесь в том, что значение «х» никогда не превышает 8, что означает, что Судоку никогда не доходит до конца. Рекурсия останавливается, прежде чем все слоты будут заполнены правильно. Я довольно неопытен в написании рекурсивных методов, поэтому, пожалуйста, несите меня.

Я полагал, что если число помещается в слот, то этот номер помещается в этот слот, а затем увеличивается. Если k выше 8, значит, это конец строки, поэтому мы переходим к следующей строке. Затем функция recurse вызывается снова. Если функция рекурсии завершается без возможности повторного вызова, то это означает, что в этом слоте нет номера, поэтому нам нужно вернуться. В этом случае k уменьшается.

Так в чем проблема здесь точно?

Answer 1

Вы забыли сбросить ячейки перед возвратом. Вы оставляете неправильные номера повсюду, и в какой-то момент нет действительного числа для заполнения, и выполнение останавливается.

---

Добавить grid[x] = grid[x][0:k] + '0' + grid[x][k+1:] после

k -= 1 
if k < 0: 
    x -= 1 
    k = 8 

, чтобы исправить это.

---

Для остановки рекурсии, когда решение было найдено:

def recurse(x, k, grid): 
    if x>8: 
     return grid 

    if grid[x][k] == '0': 
     for number in '123456789': 
      if clear(number, x, k, grid): 
       grid[x] = grid[x][0:k] + number + grid[x][k+1:]   
       k += 1 
       if k > 8: 
        x += 1 
        k = 0 
       solution= recurse(x, k, grid) 
       if solution: 
        return solution 
       k -= 1 
       if k < 0: 
        x -= 1 
        k = 8 
       grid[x] = grid[x][0:k] + '0' + grid[x][k+1:]  
    else: 
     k += 1 
     if k > 8: 
      x += 1 
      k = 0 
     return recurse(x, k, grid)