شاید شما با صورت مسئله N وزیر آشنا باشید و یا ممکن است فقط اسم آن را شنیده باشید. صورت مسئله بدین صورت است که باید N وزیر را در یک صفحه‌ی شطرنج NxN قرار دهیم، به طوری که هیچ کدام از آن‌ها یکدیگر را تهدید نکنند. مقدار N می‌تواند برار با هر عدد طبیعی (به غیر از ۲ و ۳) باشد.
ما در اینجا برای حل این مسئله از روش عقبگرد استفاده می‌کنیم. راه‌های دیگری نیز برای حل مسئله‌ی N وزیر وجود دارد، اما به دلیل اینکه قصد نداریم به محاسبات ریاضی بپردازیم، از روش عقبگرد استفاده نمودیم.

الگوریتم عقبگرد چیست؟

الگوریتم عقبگرد، یکی از شیوه‌های کلی جست و جوی فضای حالت برای حل مسائل ترکیبی است. این روش تمام ترکیب‌های ممکن را بررسی می‌کند تا به یک جواب برسد و یا تعداد تمام جواب‌های ممکن را برگرداند. مزیت روش عقبگرد در این است که می‌توان با در نظر گرفتن ویژگی‌های مسئله، برخی از حالت ها را بدون آنکه بررسی شوند، کنار گذاشت. بنابراین بدون نیاز به بررسی تمام ترکیبات، می‌توان بخش بزرگی از فضای جست و جو را کنار گذاشت.

نحوه استفاده از این الگوریتم برای حل مسئله N وزیر بصورت زیر است:

۱) یک وزیر را در سطر اول و ستون اول قرار می‌دهیم.
۲) یک وزیر را در ستون دوم به گونه‌ای قرار می‌دهیم که وزیر اول را تهدید نکند.
۳) وزیرهای باقی مانده را در ستون‌های دیگر به گونه‌ای قرار می‌دهیم که سایر وزیرها را تهدید نکند.
۴) اگر با موفقیت تمام وزیرها را قرار دادیم، یک راه حل پیدا شده است. حال وزیر را از ستون Nام برمی‌داریم و وزیر ستون N-1ام را به یک سطر بعد منتقل می‌کنیم.
۵) اگر این وزیر سایر وزیرها را تهدید می‌کرد، آن وزیر را برداشته و سپس وزیر ستون قبلی آن را به یک سطر بعد منتقل می‌کنیم.
۶) این کار را به همین صورت ادامه داده تا به وزیر ستون اول برسیم و آن را نیز به سطر بعدی منتقل می‌کنیم.

شیوه‌ی کار الگوریتم عقبگرد به منظور بدست آوردن یک راه حل، برای مسئله‌ی ۸ وزیر در زیر نشان داده شده است.

نوشتن برنامه

• در این برنامه از پایتون ۳ استفاده شده است.

کد پایتون راه حل این مسئله به صورت زیر است.

import copy

def take_input():
    """Accepts the size of the chess board"""

    while True:
        try:
            size = int(input('What is the size of the chessboard? n = \n'))
            if size == 1:
                print("Trivial solution, choose a board size of atleast 4")
            if size <= 3:
                print("Enter a value such that size>=4")
                continue
            return size
        except ValueError:
            print("Invalid value entered. Enter again")

def get_board(size):
    """Returns an n by n board"""
    board = [0]*size
    for ix in range(size):
        board[ix] = [0]*size
    return board

def print_solutions(solutions, size):
    """Prints all the solutions in user friendly way"""
    for sol in solutions:
        for row in sol:
            print(row)
        print()
            
def is_safe(board, row, col, size):
    """Check if it's safe to place a queen at board[x][y]"""

    #check row on left side
    for iy in range(col):
        if board[row][iy] == 1:
            return False
    
    ix, iy = row, col
    while ix >= 0 and iy >= 0:
        if board[ix][iy] == 1:
            return False
        ix-=1
        iy-=1
    
    jx, jy = row,col
    while jx < size and jy >= 0:
        if board[jx][jy] == 1:
            return False
        jx+=1
        jy-=1
    
    return True

def solve(board, col, size):
    """Use backtracking to find all solutions"""
    #base case
    if col >= size:
        return
    
    for i in range(size):
        if is_safe(board, i, col, size):
            board[i][col] = 1
            if col == size-1:
                add_solution(board)
                board[i][col] = 0
                return
            solve(board, col+1, size)
            #backtrack
            board[i][col] = 0

def add_solution(board):
    """Saves the board state to the global variable 'solutions'"""
    global solutions
    saved_board = copy.deepcopy(board)
    solutions.append(saved_board)

size = take_input()

board = get_board(size)

solutions = []

solve(board, 0, size)

print_solutions(solutions, size)

print("Total solutions = {}".format(len(solutions)))

این برنامه ابتدا سایز صفحه شطرنج را به عنوان ورودی از کاربر دریافت می‌کند. ورودی می‌تواند یک عدد طبیعی (به غیر از ۲ و ۳) باشد. پس دریافت سایز صفحه شطرنج، برنامه به محاسبه و بدست آوردن حالات موجود می‌پردازد. سپس تعداد راه‌حل های موجود را به همراه شکل آن‌ها نمایش می‌دهد.

همانطور که مشاهده می‌کنید در این برنامه برای ایجاد یک لیست NxM از روش زیر استفاده شده است:

A = [0] * N
for i in range(N):
    A[i] = [0] * M

همچنین برای ذخیره‌ی یک آرایه چند بعدی از دستور copy.deecopy(to_save) استفاده شده است.

خروجی این برنامه زمانی که N برابر ۴ باشد بصورت زیر است:

What is the size of the chessboard? n = 
4
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]

[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]

Total solutions = 2

با تغییر مقدار N میتوان سایر حالات این مسئله را نیز مشاهده نمود.

شما همچنین می‌توانید کد این برنامه را از اینجا دریافت نمایید.