Глобальная переменная сбрасывается в Python - PullRequest
Новая
       45

Глобальная переменная сбрасывается в Python

0 голосов
/ 25 февраля 2020

Я создал решатель судоку с алгоритмом возврата (Python 3.8). Это рекурсивный алгоритм. Доска судоку (головоломка) - это глобальная переменная (несколько функций должны совместно использовать ее). Функция solve() выполняет свою задачу, но значение доски не меняется даже после использования ключевого слова global. Ваша помощь нужна.

Код: 

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

def isPossible(y, x, val): # checks if it is legal to put a value at a certain position
    for row in board: # row condition
        if val == row[x]:
            return False

    for col in board[y]: # column condition
        if val == col:
            return False

    # subcell condition

    subCellRow = (y // 3) * 3
    subCellCol = (x // 3) * 3

    for row in board[subCellRow:subCellRow + 3]:
        for col in row[subCellCol:subCellCol + 3]:
            if val == col:
                return False

    return True

def solve():
    global board
    for y in range(9):
        for x in range(9):
            if board[y][x] == 0:
                for n in range(1, 10):
                    if isPossible(y, x, n): # python stairs
                        board[y][x] = n
                        solve() # recursion starts
                        board[y][x] = 0 # 1-line backtracking algorithm

                return

    printPuzzle() # prints the solved puzzle
    return True

def printPuzzle(): # to display the puzzle
    print()
    for row in board:
        for val in row:
            print(val, end = ' ')

        print()

printPuzzle()
solve()
printPuzzle() # prints the unsolved board

1 Ответ

1 голос
/ 25 февраля 2020

Это не было ошибкой глобальной переменной, это происходит потому, что в вашей реализации алгоритма есть небольшая ошибка, которая переназначает значение на ноль в board[y][x] = 0.

Вот реализация, которую я считаю правильной. 

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


def isPossible(y, x, val): # checks if it is legal to put a value at a certain position
    for row in board: # row condition
        if val == row[x]:
            return False

    for col in board[y]: # column condition
        if val == col:
            return False

    # subcell condition

    subCellRow = (y // 3) * 3
    subCellCol = (x // 3) * 3

    for row in board[subCellRow:subCellRow + 3]:
        for col in row[subCellCol:subCellCol + 3]:
            if val == col:
                return False

    return True


def solve():
    global board
    for y in range(9):
        for x in range(9):
            if board[y][x] == 0:
                for n in range(1, 10):
                    if isPossible(y, x, n): # python stairs
                        board[y][x] = n
                        if solve():
                            return True # recursion starts
                        board[y][x] = 0
                return False

    printPuzzle() # prints the solved puzzle

    return True


def printPuzzle(): # to display the puzzle
    print()
    for row in board:
        for val in row:
            print(val, end = ' ')

        print()

printPuzzle()
solve()
printPuzzle() # prints the unsolved board

Вывод, который я получаю:

Program Output

...