N queens placed in k*k chessboard?

Question

My problem should be a variant of N queens problem:

Is there an algorithm to print all ways to place N queens in a k*k chessboard?

I have tried to modify the DFS method used in the N-queens problem like the following but soon realized that I could only search the first "queen_number" of rows in the chessboard.

    def dfs(self, n, queen, queen_number, ret):
        if len(queen) == queen_number:
            ret.append(queen[:])
            return 
        
        for i in range(n):
            if i in queen:
                continue
            flag = False
            for j, idx in enumerate(queen):
                if abs(len(queen) - j) == abs(idx - i):
                    flag = True
                    break
            if flag:
                continue
            queen.append(i)
            self.dfs(n, queen, ret)
            queen.pop()
            

If there is a better way to accomplish this task, I am also interested to learn it.

Answer 1

I had some fun coming up with a brute force solution with this question:

from typing import Dict, List, Callable, Optional


def create_k_by_k_board(k: int) -> Dict[int, bool]:
    # True means the spot is available, False means it has a queen and None means it is checked by a Queen
    if k <= 0:
        raise ValueError("k must be higher than 0")
    return {i: True for i in range(1, k**2+1)}


def check_position(conditions: List[Callable], position: int) -> bool:
    # Checks if any function returns True
    for func in conditions:
        if func(position):
            return True
    return False


def get_all_checked_positions(queen_location: int, board_size: int) -> List[int]:
    from math import sqrt
    row_len = int(sqrt(board_size))
    conditions = [
        # Horizontal check
        lambda x: ((x - 1) // row_len) == ((queen_location - 1) // row_len),
        # Vertical check
        lambda x: (x % row_len) == (queen_location % row_len),
        # Right diagonal check
        lambda x: (x % (row_len + 1)) == (queen_location % (row_len + 1)),
        # Left diagonal check
        lambda x: (x % (row_len - 1)) == (queen_location % (row_len - 1)),
    ]
    return [
        position for position in range(1, board_size + 1)
        if position != queen_location
        and check_position(conditions, position)
            ]


def place_queen_on_board(board: Dict[int, Optional[bool]], position: int) -> Dict[int, Optional[bool]]:
    # We don't want to edit the board in place because we may need to go back to it
    new_board = board.copy()
    if new_board[position] is True:
        # Place a new queen
        new_board[position] = False
        for checked_position in get_all_checked_positions(position, len(board)):
            # Set the location as checked (no risk of erasing queens)
            new_board[checked_position] = None
        return new_board
    else:
        raise ValueError(f"Tried to add queen to position {position} in board {board}")


def get_all_queen_configurations(numb_queens: int, row_length: int) -> List[Dict[int, Optional[bool]]]:
    board = create_k_by_k_board(row_length)

    def recursive_queen_search(curr_round: int, curr_board: Dict[int, Optional[bool]]) -> List[Dict[int, Optional[bool]]]:
        successful_boards = []
        available_spots = [position for position, is_free in curr_board.items() if is_free is True]
        for spot in available_spots:
            new_board = place_queen_on_board(curr_board, spot)
            if curr_round < numb_queens:
                successful_boards.extend(
                    recursive_queen_search(curr_round+1, new_board)
                )
            else:
                successful_boards.append(new_board)
        return successful_boards

    success_boards_with_duplicates = recursive_queen_search(1, board)
    success_boards = []
    for success_board in success_boards_with_duplicates:
        if success_board not in success_boards:
            success_boards.append(success_board)
    return success_boards


def visualize_board(board: Dict[int, Optional[bool]]) -> None:
    from math import sqrt
    row_len = int(sqrt(len(board)))
    parse_dict = {
        False: "Q",
    }
    for row in range(len(board), 0, -row_len):
        print(
            "[" + "][".join([parse_dict.get(board[x], " ") for x in range(row - row_len + 1, row + 1)]) + "]"
        )

As I mentioned this is a brute force solution, you can further improve it by doing 2 things.

• Using this method on only one eighth of the board.

For example if we use the algorithm for 3 queens on a 4*4 board:

>>> a = get_all_queen_configurations(3,4)
>>> visualize_board(a[0])
[ ][ ][Q][ ]
[ ][ ][ ][ ]
[ ][ ][ ][Q]
[Q][ ][ ][ ]
>>> visualize_board(a[1])
[ ][Q][ ][ ]
[ ][ ][ ][Q]
[ ][ ][ ][ ]
[Q][ ][ ][ ]
>>> visualize_board(a[2])
[ ][ ][ ][Q]
[Q][ ][ ][ ]
[ ][ ][ ][ ]
[ ][Q][ ][ ]
>>> visualize_board(a[3])
[ ][ ][ ][Q]
[ ][ ][ ][ ]
[Q][ ][ ][ ]
[ ][ ][Q][ ]

You can see that all the solutions are the same solution mirrored through one of the axes of symmetry.

Using this simplification would make the code at least 8 times faster, probably more.

• Use a smarter algorithm. But this probably involves searching online and going through academic papers, which you've opted not to do.

The limitations of the brute force algo are quite serious:

• 5 queens in 6*6 board: ~0.2 sec
• 6 queens in 7*7 board: ~4 sec
• 7 queens in 8*8 board: ~128 sec
• 8 queens in 9*9 board: ~Legend has it it's still running to this day...

Answer 2

Here's a solution based on the Python port of Niklaus Wirth's n-queen solver from https://en.wikipedia.org/wiki/Eight_queens_puzzle

def queens(n, k, i=0, a=[], b=[], c=[]):
    if k == 0:
        yield a + [None] * (n - len(a))
        return
    for j in range(n):
        if j not in a and i+j not in b and i-j not in c:
            yield from queens(n, k-1, i+1, a+[j], b+[i+j], c+[i-j])
    if k < n - i:
        yield from queens(n, k, i+1, a+[None], b, c)

for i, solution in enumerate(queens(10, 9)):
    print(i, solution)

It finds all 56832 ways to place 9 queens on a 10x10 board in less than a second (1.5 sec if they are printed out to the console).

The program works like Wirth's: a contains the positions of the queens on the rows processed so far, and b and c contain the diagonal numbers of the queens placed so far. The only difference is that there's an extra k parameter, which says how many queens to place, and some extra code to consider solutions with no queen on a row. Other than this simple optimization of how the board is represented, it's just a depth-first search.

The format of the output is the solution number (0-based), and then a list of position of the queen on each row, or None if there's no queen on that row.