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.
CodePudding user response：
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.
CodePudding user response：
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...
So whatever, here's my code, let me know if you have any questions.