#!/usr/bin/env python
# 8queens.py - A solver for the 8 queens problem.

# Copyright (c) 2012, Alan Saqui <alan.saqui@gmail.com>
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without 
# modification, are permitted provided that the following conditions are met:
#
# 1. Redistributions of source code must retain the above copyright notice, 
#    this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright notice, 
#    this list of conditions and the following disclaimer in the 
#    documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
#  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE 
# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 
# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

# Arbitrarily large constant to use for the value of the queen
QUEEN = 100000

class Board:
    def __init__(self):
        self.board = [ [ 0 for x in range(8) ] for y in range(8) ] 
        self.queens = []

    # Pretty-print the board
    def pprint(self):
        for x in range(8):
            for y in range(8):
                if self.board[x][y] == QUEEN:
                    print "Q",
                else:
                    print "_",
                    #print self.board[x][y],
            print

    def push_queen(self, coord):
        #XXX: Should check if coord is a valid move
        row, col = coord
        self.board[row][col] += QUEEN
        self.mark_queen(coord, 1)
        self.queens.append(coord)

    # Remove the last queen that was placed on the board.
    def pop_queen(self):
        row, col = self.queens.pop()
        # 'Unmark' all the squares the queen was covering.
        self.mark_queen((row, col), -1)
	# 'Unmark' the square the queen itself was on.
	self.board[row][col] -= QUEEN

    # Generate a list of all the valid squares a queen can be placed on.
    def list_valid_moves(self):
        valid_moves = []
        for x in range(8):
            for y in range(8):
                if self.board[x][y] == 0:
                    valid_moves.append((x, y))
        return valid_moves

    # 'Mark off' the squares the given queen at coord covers on the board.
    def mark_queen(self, coord, mark):
        row, col = coord
        # 'Radiate' out in all 8 directions from the queen.
        for x in range(1, 8):
            if row - x >= 0:
                self.board[row - x][col] += mark           # -x,  0 (W)
                if col - x >= 0:
                    self.board[row - x][col -x] += mark    # -x, -x (SW)
                if col + x <= 7:
                    self.board[row - x][col + x] += mark   # -x, +x (NW)
            if row + x <= 7:
                self.board[row + x][col] += mark           # +x,  0 (E)
                if col - x >= 0:
                    self.board[row + x][col - x] += mark   # +x, -x (SE)
                if col + x <= 7:
                    self.board[row + x][col + x] += mark   # +x, +x (NE)
            if col - x >= 0:
                self.board[row][col - x] += mark           #  0, -x (S)
            if col + x <= 7:
                self.board[row][col + x] += mark           #  0, +x (N)

    # Backtracking depth-first solver.
    def solver(self):
        # Get a list of valid moves
        valid_moves = self.list_valid_moves()
        for valid_move in valid_moves:
            self.push_queen(valid_move)
            self.solver()
            if len(self.queens) == 8:
                return 
	    # this queen placement did not lead to a solution with 8 queens. 
	    # Therefore, this placement can't be part of any valid solution, so
	    # roll it back and try the next one.
            self.pop_queen()
        # Nothing in the list of valid moves led to a solution, or there were 
	# no valid moves left to try.
        return

board = Board()
board.solver()
board.pprint()