N-queens problem: Difference between revisions
Content added Content deleted
| Line 3,359: | Line 3,359: | ||
===Solution with Backtracking=== |
===Solution with Backtracking=== |
||
<lang python> |
<lang python>def solveNQueens(n): |
||
def solveNQueens(n): |
|||
"""Solve N queens with board size n and print each step.""" |
"""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 |
# Our approach depends on the fact that each piece must be in a different |
||
| Line 3,399: | Line 3,398: | ||
# At this point, we've tried placing the piece in every possible row for this |
# 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). |
# column. Now we go back up the call stack (backtrack). |
||
def canQueensOnBoardAttack(board): |
def canQueensOnBoardAttack(board): |
||
| Line 3,421: | Line 3,419: | ||
"""Return all the diagonal elements on the board""" |
"""Return all the diagonal elements on the board""" |
||
n = len(board) |
n = len(board) |
||
def diagonal(b, i): |
def diagonal(b, i): |
||
"""Return diagonals in the / direction (leaning leftwards.""" |
"""Return diagonals in the / direction (leaning leftwards.""" |
||
return [b[row][col] for row in xrange(n) for col in xrange(n) |
return [b[row][col] for row in xrange(n) for col in xrange(n) |
||
if row + col == i] |
if row + col == i] |
||
diags = [diagonal(board, i) for i in xrange(n*2-1)] |
diags = [diagonal(board, i) for i in xrange(n*2-1)] |
||
board.reverse() # Flip board, so diagonal() can be reused. |
board.reverse() # Flip board, so diagonal() can be reused. |
||
diags.extend([diagonal(board, i) for i in xrange(n*2-1)]) |
diags.extend([diagonal(board, i) for i in xrange(n*2-1)]) |
||
board.reverse() # Reset board to its original state. |
board.reverse() # Reset board to its original state. |
||
return diags |
return diags |
||
| Line 3,437: | Line 3,435: | ||
"""Print board in a human-readable format.""" |
"""Print board in a human-readable format.""" |
||
print message |
print message |
||
for row in board: |
for row in board: |
||
print " ", |
print " ", |
||
| Line 3,452: | Line 3,450: | ||
if __name__ == "__main__": |
if __name__ == "__main__": |
||
solveNQueens(8) |
solveNQueens(8)</lang> |
||
</lang> |
|||
=={{header|R}}== |
=={{header|R}}== |
||