Python Рекурсивный Sudoku Solver

Question

Это код recursive Sudoku solve, это не школьное задание. Я не могу понять, как заставить его «поддержать» мои предыдущие шаги. Он застревает в конце first row, поскольку для этого места нет действительного номера, и он просто пытается найти тот, который там подходит. У меня проблемы с check.

После прочтения ваших ответов я сблизился с этим, но это не совсем так. Он поддерживает весь путь вверх и выходит из рекурсии

import sys 

class Board: 

    def __init__(self, grid): 
     self.grid = grid 
     self.ogrid = grid 

    def get_col(self, col): 
     column = [] 
     for i in self.grid: 
      column.append(str(i[col])) 
     return column 

    def get_row(self, row): 
     return self.grid[row] 

    def check_row(self, r, val): 
     row = self.grid[r] 
     for i in range(0,9): 
      if str(val) in row: 
       return False 

     return True 

    def check_col(self, column, val): 
     col = self.get_col(column) 
     for i in range(0,9): 
      if str(val) in col: 
       return False 

     return True 

    def check_square(self, x, y, val): 
     col = (y//3)*3 
     row = (x//3)*3 
     s = '' 
     for i in range(row, row+3): 
      for j in range(col, col+3): 
       s += str(self.grid[i][j]) 
     if str(val) in s: 
       return False 

     return True  

    def check_cell(self, x, y, val): 
    if self.check_col(y, val) == False: 

     return False 
    elif self.check_row(x, val) == False: 

     return False 
    elif self.check_square(x, y, val) == False: 

     return False 
    return True 


def check(self, x, y): 

     if y == 9: 
      y = 0 
      x += 1 

     if x == 9: 
      self.print_board() 
      sys.exit() 

     if self.ogrid[x][y] == '.': 
      for val in range(1,10): 
       if self.check_cell(x, y, val): 
        self.grid[x][y] = str(val) 
        self.check(x, y+1) 
       ##I don't think the reset is working and I'm not sure why 
       if self.ogrid[x][y] == '.': #reset index 
        self.grid[x][y] = '.' 
        self.print_board() #Notice it never prints a '.' in spots that have changed 
     else: 
      self.check(x,y+1) 
     return 

    def print_board(self): 
     for i in range(0,9): 
      for j in range(0,9): 
       sys.stdout.write(self.grid[i][j]) 
       if j == 2 or j == 5: 
        sys.stdout.write(' ') 
      if i == 2 or i == 5: 
       sys.stdout.write('\n') 
      print('') 

def main(): 

    f = open("./easySudoku.txt",'r') 
    s = '' 

    grid = [] 
    row = [] 
    for line in f: 
     s += line 
     print line 
    s = s.replace(' ','') 
    s = s.replace('\n','') 

    for i in range(0,9): 
     row = [] 
     for j in range(0,9): 
      row.append(s[(i*9) + j]) 
     grid.append(row) 

    sudoku = Board(grid) 
    sudoku.check(0,0, 1) 

if __name__ == "__main__": 
    main() 

Вот как предполагается, функция проверки работы

check принимает й и у координаты для доски и начинается 0,0 она проходит через цикл for от 1-9 и устанавливает первое значение, которое работает с этим индексом, а затем переходит к следующему индексу. Когда он достигает конца строки, он перемещается вниз по одной строке и возвращается к первому столбцу. Если никакие значения не работают с индексом, обновите текущий индекс до '.' и переместите индекс назад и продолжайте считать в направлении 9. то есть, если значение тока в индексе 0,0 равно 2, то продолжайте движение до 3. Если 3 работает, то переместите один индекс так далее и так далее до тех пор, пока плата не будет заполнена. Для упрощенного ответа он пытается каждое значение, 1-9, на каждом пустом индексе

Если это непонятно, то дайте мне знать

Также здесь есть совет, который я использую

..6 ..7 3.. 
.18 ..9 .5. 
5.. ... .64 

92. .8. ... 
... 763 ... 
... .9. .75 

63. ... ..8 
.9. 3.. 52. 
..2 4.. 6.. 

Answer 1

Что я сделал, чтобы проверить свой код: добавьте эту строку в первой строке вашего метода check:

raw_input('x: %d, y: %d, val: %d' % (x,y,val)) 

и печати платы после вставки номера.

Похоже, ваш решатель совершает первую ошибку на (x,y) = (0,3). Он проверяет все числа до 9 и затем помещает 9. По вашему алгоритму он должен положить 1. Вешать трубку - это ваш метод check_square. Вы должны иметь

col = (y//3)*3 
row = (x//3)*3 

После фиксации, что следующая ошибка выплывает в (x,y) = (1,8), начиная с self.check(1, 8, 1).Нет никаких правовых значений (используя ваш алгоритм до этой точки) для этого квадрата (вплоть до self.check(1, 8, 9)). Итак, следующий называется self.check(1, 8, 10). Начиная с val==10, он возвращается, а затем в рамках вызова self.check(1, 8, 9) выдается окончательная строка self.check(x, y-1, val+1), то есть self.check(1, 7, 10). Это, конечно, сразу же возвращается, потому что val == 10. И мы вернулись к self.check(1, 8, 8) и назвали окончательную строку определения метода. Рядом с исполнением находится self.check(1, 7, 9), в котором появляется следующий self.check(1, 8, 1). Выглядит знакомо? Мы уже были здесь, и между тем мы не изменили состояние. Даже не осознавая этого, это становится бесконечным циклом.

Было ли это смущает? Конечно. Есть причина, по которой программисты стараются избегать рекурсии, за исключением того, что учат о концепции рекурсии. Отслеживание этих типов ошибок рекурсии сложно, но с несколькими линиями печати это можно сделать.

P.S. Ваш алгоритм интересен. Интересно, где вы его нашли ... Это определенно не то, как люди играют (со всеми угадываниями и редактированием). FWIW, я бы сначала вставлял значение в доску, если это значение было единственным законным движением для квадрата и угадывало, только когда все пустые квадраты на доске были неоднозначными.

EDIT ПОСЛЕ ВАШИХ редактирует

Добавить import copy, часть стандартной библиотеки, в верхней части и изменения в __init__ к self.ogrid = copy.deepcopy(grid). Должно решить вашу проблему. См. https://stackoverflow.com/a/2612815/2100286. Ваш метод создания дублирующей версии сетки обеспечивает одно и то же.

Answer 2

Проблема заключается в том, что вы, кажется, повторяете один шаг за каждый номер, который вы пытаетесь, который будет потреблять каждый нормальный стек. Я бы предположил, что вы также используете итерацию и используете return, чтобы сделать резервную копию (таким образом, вы должны использовать только 81 стек кадров или около того - здесь он терпит неудачу, когда вы получаете тысячу уровней кадров стека).

Я сделал решатель раньше, и он будет найти решение довольно быстро ...

Answer 3

я не получаю этот фрагмент:

 if y == -1: 
      y = 8 
      x -= 1 

Если y равен последнюю позицию в строке вы устанавливаете его на 8, который является индексом последней позиции в строке? Может ли это быть причиной того, почему это не происходит должным образом?

Answer 4

Хорошо, я исправил свою проблему!

Вот что я сделал. Я принял совет @Skyking дал мне, рекурсивный только по индексу, а не по значениям для индекса, который у меня был изначально. Второе, что я изменил, заключалось в том, чтобы принять @James Pringles совет о том, как исправить мою функцию check_square и скопировать сетку, так что ogrid не изменится при изменении grid. Поскольку я не могу дать два зеленых чеков, которые я дал его @James Прингл, так как он/она помогла мне больше всего, но я не мог бы получить его без @ совет Skyking в

Вот готовый код

import sys 
import copy 

class Board: 

    def __init__(self, grid): 
     self.grid = grid 
     self.ogrid = copy.deepcopy(grid) 

    def get_col(self, col): 
     column = [] 
     for i in self.grid: 
      column.append(str(i[col])) 
     return column 

    def get_row(self, row): 
     return self.grid[row] 

    def check_row(self, r, val): 
     row = self.grid[r] 

     if str(val) in row: 
      return False 
     return True 

    def check_col(self, column, val): 
     col = self.get_col(column) 

     if str(val) in col: 
      return False 
     return True 

    def check_square(self, x, y, val): 
     col = (y//3)*3 
     row = (x//3)*3 
     s = '' 
     for i in range(row, row+3): 
      for j in range(col, col+3): 
       s += str(self.grid[i][j]) 

     if str(val) in s: 
      return False 
     return True  

    def check_cell(self, x, y, val): 
     if self.check_col(y, val) == False: 
      return False 
     elif self.check_row(x, val) == False: 
      return False 
     elif self.check_square(x, y, val) == False: 
      return False 
     return True 


    def check(self, x, y): 

      if y == 9: 
       y = 0 
       x += 1 

      if x == 9: 
       self.print_board() 
       sys.exit() 

      if self.ogrid[x][y] == '.': 
       for val in range(1,10): 
        if self.check_cell(x, y, val): 
         self.grid[x][y] = str(val) 
         self.check(x, y+1) 

        if self.ogrid[x][y] == '.': 
         self.grid[x][y] = self.ogrid[x][y]      
      else: 
       self.check(x,y+1) 
      return True 

    def print_board(self): 
     for i in range(0,9): 
      for j in range(0,9): 
       sys.stdout.write(self.grid[i][j]) 
       if j == 2 or j == 5: 
        sys.stdout.write(' ') 
      if i == 2 or i == 5: 
       sys.stdout.write('\n') 
      print('') 

def main(): 

    f = open("./easySudoku.txt",'r') 
    s = '' 

    grid = [] 
    row = [] 

    for line in f: 
     s += line 

    s = s.replace(' ','') 
    s = s.replace('\n','') 

    for i in range(0,9): 
     row = [] 
     for j in range(0,9): 
      row.append(s[(i*9) + j]) 
     grid.append(row) 

    sudoku = Board(grid) 
    sudoku.check(0,0) 
    print('shouldn\'t be here') 

if __name__ == "__main__": 
    main()