Anonymous user
N-queens problem: Difference between revisions
→Solution with Backtracking
Line 3,359:
===Solution with Backtracking===
<lang python>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
Line 3,399 ⟶ 3,398:
# 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):
Line 3,421 ⟶ 3,419:
"""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
Line 3,437 ⟶ 3,435:
"""Print board in a human-readable format."""
print message
for row in board:
print " ",
Line 3,452 ⟶ 3,450:
if __name__ == "__main__":
solveNQueens(8)</lang>
=={{header|R}}==
| |||