The 8Queens Problem In this problem you will write a Python

The 8-Queens Problem

In this problem, you will write a Python program to solve the 8-Queens problem. In chess, a queen can move any number of squares horizontally, vertically, or diagonally. The 8- queens problem is the problem of trying to place eight queens on an empty chessboard in such a way that no queen can attack any other queen. This problem is intriguing because there is no efficient algorithm known for solving the general problem. Rather, the straightforward algorithm of trying all possible placements is most often used in practice, with the only optimization being that each queen must be placed in a separate row and column:

a. Starting with the first row, try to place a queen in the current column.

b. If you can safely place a queen in that column, move on to the next column

c. If you are unable to safely place a queen in that column, go back to the previous column, and move that queen down to the next row where it can safely be placed. Move on to the next column. Write a program in python to solve the 8-queens problem. Your program should produce as output an 8X8 diagram of the chessboard, with a 1 indicating the presence of a queen in a square and a 0 indicating the absence of a queen.

Hints: You can represent the board as either an 8X8 list or as a one-dimensional list with the ith item representing the row number of the queen in column i. You can solve this problem recursively or iteratively, but the recursive solution is usually much easier.

Solution

//Python program for 8 queen problem

def queenproblem(row, column, queens):

    if not fit(queens): return False

    for queen in queens:

        if not fit(queen):

            continue

        row1,column1 = queen

        if row1 == row: return True

        if column1 == column: return True

        if (column-column1) == (row-row1): return True

        if (column-column1) == -(row-row1): return True

    return False

def solvefor(n):

    solve1 = None

    for row in range(1, n+1):

        Solve1 = check(solve1, row, n)

    return solve1

def check(solve1, row, n):

    getsolutions = []

    for column in range(1, n+1):

        if not solve1 or not fit(solve1):

            getsolutions.append([] + [(row, column)])

        else:

            for solution in solve1:

                if not queenproblem (row, column, solution):

                    getsolutions.append(solution + [(row, column)])

    return getsolutions