Блог

Я начал решать проблему 8 queens с обратным отслеживанием в Python. Все хорошо и хорошо. Он даже распечатал первый ответ. Тем не менее, он застрял при первой попытке возврата.

Задача звучала таким образом:

Реализуйте функцию Python, которая решает головоломку 8 queens. Головоломка с 8 ферзями состоит из размещения 8 ферзей на шахматной доске так, чтобы ни одна из ферзей не могла захватить другую. Обратите внимание, что королевы могут перемещаться ортогонально или по диагонали в любом направлении.

Вы должны реализовать функцию solve(), которая при вызове печатает первое решение головоломки, а затем ожидает ввода. Как только пользователь нажимает ‘ввод’, печатается следующее решение и так далее.

— Ваша программа должна быть в состоянии найти все решения для головоломки и каждое решение только один раз. ‘

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

— В любой строке есть ровно одна королева. Следовательно, все, что вам нужно вычислить, это столбец, в который может быть помещен каждый из 8 ферзей.

— Вы должны реализовать рекурсивную функцию solve (n), которая находит место для n-го 1 ферзя, а затем вызывает себя рекурсивно для n 1 ферзя (если не были размещены все ферзи). Он должен систематически исследовать все возможности, используя отслеживание возврата.

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

 
    import numpy as np
    grid = np.zeros((8, 8), dtype = int)
    
    
    def possible(y, n):
        global solved
        global grid
        for i in range(0, 8):
            if grid[y][i] == n:
                return False
        try:
            for item in solved[str(y)]:
                if grid[y].all() == item.all():
                    return False
        except KeyError:
            return True
        return True
    
    max_y = 7
    max_x = 7
    
    def print_grid():
        global grid
        for line in grid:
            for square in line:
                if square == 0:
                    print(".", end = " ")
                else :
                    print("Q", end = " ")
            print()
    
    solved = {}
    
    def prefilled_solved():
        global solved
        for i in range(0, len(grid[0])):
            solved[f"{str(i)}"] = []
    
    def solve(y=0):
        global grid
        global solved
        while y < 8:
            for x in range(0, 8):
                if grid[y][x] == 0:
                    if possible(x, 1):
                        grid[y][x] = 1
                        solved[f"{str(y)}"].append(grid[y])
                        y  = 1
                        solve(y)
                        #y -= 1 or y = 0 or y -=2
                        # backtracking - bad choice
                        # grid[y][x] = 0
    
        print_grid()
        print(grid)
        return
        input("More?")
    
    if __name__ == '__main__':
        prefilled_solved()
        solve()

  

Я последовал совету @mkam, теперь у меня есть случайное созвездие Queen, но я полностью избавился от рекурсии.

 ```import numpy as np
grid = np.zeros((8, 8), dtype = int)
from random import randint, shuffle, choice
from itertools import permutations


constellations_drawn  = []


def print_grid():
    global grid
    for line in grid:
        for square in line:
            if square == 0:
                print(".", end = " ")
            else :
                print("Q", end = " ")
        print()

solved = []

def prefilled_solved():
    global solved
    new_board = ['1', '2', '3', '4', '5', '6', '7', '8']
    new_board_i = ''.join(new_board)
    solved = permutations(new_board_i, 8)



def solve(y=0):
    global grid
    global solved
    global constellations_drawn
    list_solved = list(solved)
    len_solved = len(list_solved)
    board_drawn = list_solved[randint(0, len_solved-1)]
    board_drawn_str = ''.join(board_drawn)
    while board_drawn_str in constellations_drawn:
        board_drawn = list_solved[randint(0, len_solved - 1)]
    new_board_list = [int(item) for item in board_drawn]
    for i, x in enumerate(new_board_list):
        if grid[i-1][x-1] == 0:
            grid[i-1][x-1] = 1
            #y  = 1
            #solve(y)
            #y -= 1 or y = 0 or y -=2
            # backtracking - bad choice
            # grid[y][x] = 0
    constellations_drawn.append(board_drawn_str)
    print_grid()
    print(grid)
    return
    input("More?")

if __name__ == '__main__':
    prefilled_solved()
    solve()
  

 
I've merged the code of @mkam and mine. And it works. I still use numpy ndarray.

  

 import numpy as np

    from numpy.core._multiarray_umath import ndarray
    
    
    def print_grid(solutions_found, board) -> None:
        line: ndarray
        len_board = len(board)
        grid: ndarray = np.zeros((len_board, len_board), dtype=int)
        for i, number in enumerate(board):
            grid[i - 1][number - 1] = 1
        for line in grid:
            for square in line:
                if square == 0:
                    print(".", end=" ")
                else:
                    print("Q", end=" ")
            print()
        print(f'Solution - {solutions_found}')
    
    
    def solve(boardsize, board=[], solutions_found=0):
        if len(board) == boardsize:
            solutions_found  = 1
            print_grid(solutions_found, board)
        else:
            for q in [col for col in range(1, boardsize   1) if col not in board]:
                if is_safe(q, board):
                    solutions_found = solve(boardsize, board   [q], solutions_found)
        return solutions_found
    
    
    def is_safe(q, board, x=1):
        if not board:
            return True
        if board[-1] in [q   x, q - x]:
            return False
        return is_safe(q, board[:-1], x   1)
    
    
    if __name__ == '__main__':
        solve(8)