Anonymous user
N-queens problem: Difference between revisions
→{{header|Python}}
(coffeescript) |
|||
Line 3,357:
for answer in solve(BOARD_SIZE): print(list(enumerate(answer, start=1)))</lang>
===Solution with Backtracking===
def solveNQueens(n):
"""Solve N queens with board size n and print each step."""
# Our approach depends on the fact that each piece must be in a different
# column (if two pieces are in the same column, they can attack each other).
# We recursively place a piece in each column and backtrack, if necessary.
# Initialize N by N board (0 for empty, 1 for queen).
board = [[0 for i in xrange(n)] for i in xrange(n)]
# Call recursive helper to find solutions, starting from the first column.
solveNQueensHelper(board, 0)
def solveNQueensHelper(board, col):
"""Try to solve N queens from column col, rightwards."""
n = len(board)
for row in xrange(n):
# Place piece in the first row, or move piece down, in the column.
if row != 0:
board[row-1][col] = 0
board[row][col] = 1
if canQueensOnBoardAttack(board):
# Queens can already attack, so no more can be placed on board.
printBoard(board, "Queens can attack:\n", True)
continue
elif col == n-1:
# board must be a solution because no queens can attack each
# other and the current one is in the last column.
printBoard(board, "Solution:\n", True)
break
printBoard(board, "Queens can't attack:\n", True)
# Try placing another piece in the next column.
solveNQueensHelper(board, col+1)
board[row][col] = 0 # Remove piece so board is back to its original state.
# At this point, we've tried placing the piece in every possible row for this
# column. Now we go back up the call stack (backtrack).
def canQueensOnBoardAttack(board):
"""Test if any queens on the board can attack each other."""
n = len(board)
rows = board
cols = [[row[i] for row in board] for i in xrange(n)]
diags = diagonals(board)
def canAttack(grouped_pieces_list):
"""Test if there is more than one queen in each group of pieces"""
for pieces in grouped_pieces_list:
if pieces.count(1) > 1:
return True
return False
return canAttack(rows) or canAttack(cols) or canAttack(diags)
def diagonals(board):
"""Return all the diagonal elements on the board"""
n = len(board)
def diagonal(b, i):
"""Return diagonals in the / direction (leaning leftwards."""
return [b[row][col] for row in xrange(n) for col in xrange(n)
if row + col == i]
diags = [diagonal(board, i) for i in xrange(n*2-1)]
board.reverse() # Flip board, so diagonal() can be reused.
diags.extend([diagonal(board, i) for i in xrange(n*2-1)])
board.reverse() # Reset board to its original state.
return diags
def printBoard(board, message, pause):
"""Print board in a human-readable format."""
print message
for row in board:
print " ",
for piece in row:
if piece:
print "Q",
else:
print ".",
print
print
if pause:
raw_input()
if __name__ == "__main__":
solveNQueens(8)
=={{header|R}}==
| |||