Откат в sudoku solver failing

Question

Я пишу sudoku solver на Python, который занимает частично заполненную доску и использует обратную проверку и проверку вперед, чтобы заполнить все остальное и решить головоломку. Проверка пересылки - это когда каждый раз, когда вы назначаете значение пустой ячейке, вы проверяете, не осталось ли у ее строки, столбца и поля неназначенные «соседи» все еще непустые домены после назначения.

Чтобы представить мою доску (размеры: доска N x N с полями P x Q), я использую 2D-список, в котором каждая запись имеет вид [значение, [домен]], где значение назначено номер ячейки (0, если не назначен), а домен - возможные значения для ячейки, которые будут поддерживать головоломку судоку.

Я считаю, что я делаю что-то не так с моей рекурсией, но не могу понять, что. Функция всегда терпит неудачу и возвращает False. Ниже приведена часть моей рекурсивной решающей функции с выведенным кодом предварительной обработки. При необходимости я могу опубликовать всю функцию и ее вспомогательные функции.

def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout): 
    ###some preprocessing here to check if puzzle is solved and find next empty cell if not 

    vals = board[row][col][1] #domain/possible values for the empty cell 
    for num in vals: 
     #if num doesn't violate the row, col, and box sudoku constraints 
     if constraintCheck(row, col, num, P, N, Q, board): 
      #make copy of cell's domain for backtracking 
      tempDomain = copy.deepcopy(board[row][col][1]) 

      board[row][col][0] = num  #assign num to the cell 

      #remove num from domains of neighbors, 
      #if an empty domain results after removing num, 
      #return False and the original board, 
      #else return True and the updated board 
      noEmptyDomains, board = propagate_fc(board, N, P, Q, row, col, num) 
      if noEmptyDomains: 
       board[row][col][1] = [num] #update domain to be num and then recurse 
       if fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout): 
        return True 
       #backtrack -- reset value and domain of assigned cell 
       board[row][col][1] = tempDomain 
       board[row][col][0] = 0 
      else: 
       board[row][col][0] = 0 
    return False 

EDIT: больше кода и опробовать решение Blckknght в

def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout): 
    if time.clock() >= timeout: 
     return "timeout" 

    while row < N and board[row][col][0] != 0: #find next blank 
     if col == N-1: 
      row = row + 1 
      col = 0 
     else: 
      col = col + 1 

    if row == N: #solved 
     return True 

    for num in vals: 
     if constraintCheck(row, col, num, P, N, Q, board): 
      board[row][col][0] = num 
      noEmptyDomains, new_board = propagate_fc(board, N, P, Q, row, col, num) # new var 
      if noEmptyDomains: 
       new_board[row][col][1] = [num] # this doesn't modify board, only new_board 
       if fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout): 
        return True 
      board[row][col][0] = 0 # the only thing that's required to backtrack 
    return False 

def propagate_fc(board, N, P, Q, row, col, num): 
    origBoard = copy.deepcopy(board) 
    #row propagate 
    for x in range(N): 
     if board[x][col][0] == 0: 
      if num in board[x][col][1]: 
       board[x][col][1].remove(num) 
     if len(board[x][col][1]) == 0: 
      return False, origBoard #domain is empty; return original board 

    #col propagate 
    for y in range(N): 
     if board[row][y][0] == 0: 
      if num in board[row][y][1]: 
       board[row][y][1].remove(num) 
     if len(board[row][y][1]) == 0: 
      return False, origBoard #domain is empty 

    #box propagate 
    rDiv = row/P 
    cDiv = col/P 
    for i in range((rDiv * P), ((rDiv + 1) * P)): 
     for j in range((cDiv * Q), ((cDiv + 1) * Q)): 
      if board[i][j][0] == 0: 
       if num in board[i][j][1]: 
        board[i][j][1].remove(num) 
      if len(board[i][j][1]) == 0: 
       return False, origBoard #domain is empty 

    return True, board #success; return board with updated domains 

Answer 1

Если вы делаете возвратов вы должны быть в состоянии вернуть состояние вашего совета, как это было раньше. Ваш текущий код не делает этого. Функция propagate_fc изменяет board таким образом, что это не легко отменить.

Поскольку я не вижу простого способа изменить логику propagate_fc, я предлагаю изменить дизайн решателя так, чтобы он делал копии платы и только модифицировал копии, прежде чем передавать их на дальнейшие рекурсивные шаги. Если копия не приводит к решению, ее можно выбросить, вместо того, чтобы пытаться написать код возврата, чтобы восстановить его.

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

Во всяком случае , вот что я предлагаю для модифицированной версии решателя:

def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout): 
    if time.clock() >= timeout: 
     return "timeout" 

    while row < N and board[row][col][0] != 0: #find next blank 
     if col == N-1: 
      row = row + 1 
      col = 0 
     else: 
      col = col + 1 

    if row == N: #solved 
     return board 

    for num in vals: 
     if constraintCheck(row, col, num, P, N, Q, board): 
      new_board = copy.deepcopy(board) 
      new_board[row][col][0] = num 
      if propagate_fc(new_board, N, P, Q, row, col, num): 
       new_board[row][col][1] = [num] 
       result = fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout) 
       if result is not None and result != "timeout": 
        return result 
     return None 

Я изменил его вернуть решенную доску, если это успешно. В противном случае вы получите ответ True, но не сможете увидеть результат (так как код верхнего уровня board не будет изменен).

Вот измененная версия propagate_fc пойти с ним:

def propagate_fc(board, N, P, Q, row, col, num): 
    # no copying any more here 

    #row propagate 
    for x in range(N): 
     if board[x][col][0] == 0: 
      if num in board[x][col][1]: 
       board[x][col][1].remove(num) 
     if len(board[x][col][1]) == 0: 
      return False 

    #col propagate 
    for y in range(N): 
     if board[row][y][0] == 0: 
      if num in board[row][y][1]: 
       board[row][y][1].remove(num) 
     if len(board[row][y][1]) == 0: 
      return False 

    #box propagate 
    rDiv = row/P 
    cDiv = col/P 
    for i in range((rDiv * P), ((rDiv + 1) * P)): 
     for j in range((cDiv * Q), ((cDiv + 1) * Q)): 
      if board[i][j][0] == 0: 
       if num in board[i][j][1]: 
        board[i][j][1].remove(num) 
      if len(board[i][j][1]) == 0: 
       return False 

    return board #success; return new board 

Единственное реальное изменение заключается в том, что я не беспокоить возвращения board, так как мы всегда модифицируя его на месте. Требуется только результат bool (если допустима плата или нет).

(Первоначально я думал, что есть еще одна проблема с проверками if len(...) == 0 в каждом блоке, но в конце концов это оказалось не проблемой. Возможно, вы получите немного лучшую производительность, выполнив эти проверки только тогда, когда вы просто remove Значение da из текущего списка board[x][y][1] (путем отступов этих блоков на два уровня), но это вряд ли будет большим выигрышем в производительности.)

Answer 2

Основываясь на беглый взгляд, я думаю, что вы перепутали свой ряд/COL распространяющихся:

#row propagate 
for x in range(row):    <== should this be range(col) ? 
    if board[row][x][0] == 0:  <== row is fixed, but cols (x) changes 
     if num in board[row][x][1]: 
      board[row][x][1].remove(num) 
    if len(board[row][x][1]) == 0: 
     return False, origBoard #domain is empty; return original board