Mean Queens

Probability Level 4

How many ways are there to place 8 queens on a standard $8\times 8$ chessboard such that no two queens lie on a common row, column or diagonal ?

Bonus : can you generalize this for $n$ queens on a $n\times n$ chessboard?

The answer is 92.

1 solution

Amitha Elizabeth
Aug 24, 2015

i have found the answer using computer program. this is a famous problem called the 8 queens problem. If you are trying manually , it will take a lot of time for a single solution itself.

Can you post your code?

AntiMatter Technologies - 5 years, 9 months ago

http://www.c-program-example.com/2011/10/c-program-to-solve-n-queens-problem.html

you can find the solution from this link.

The basic idea is the row number or column number of 2 queens should not match or the difference between row and column number of one queen should not match with the difference of row and column number of another queen.

Amitha Elizabeth - 5 years, 9 months ago

Slow and simple Python 3 solution

perm_ct=0

def place queen(queenCount, nextSquare, board): global perm ct

if (queenCount == 8):
    perm_ct += 1
    print("#", perm_ct, " (", "".join(board), ")")
    return

while (nextSquare < 64):
    if (board[nextSquare] == " "):
        # We can place a queen here so copy the board
        newBoard = list(board)

        # Place queen and block off squares on same line
        row = nextSquare // 8
        col = nextSquare % 8
        y = 0
        while (y < 8):
            x = 0
            while (x < 8):
                ind = y * 8 + x
                dx = abs(col-x)
                dy = abs(row-y)
                if ((dx == 0) and (dy == 0)):
                    # print("Placed queen at (",x, ",", y, ")")
                    newBoard[ind] = "q"
                elif (dx == 0) or (dy == 0) or (dx == dy):
                    # print("Blocked square at (",x, ",", y, ")")
                    newBoard[ind] = "-"
                x += 1
            y += 1

        # Recurse to place new queen
        place_queen(queenCount+1, nextSquare + 1, newBoard)

    # Continue to next square
    nextSquare += 1

place queen(0, 0, list(" " * 64)) print("Permutations = ", perm ct)

John Sergeant - 2 years, 8 months ago

Mean Queens

The answer is 92.

1 solution

0 pending reports