"""
 queens_backtrack.py

 Searching for N-queens solutions using an adaptation
 of Skienna's backtrack() template. (This has the
 same backtrack() routine and function names as
 permutation_backtrack.py.)

 Jim Mahoney | April 2013 | MIT License
"""

# --- general purpose backtrack search algorithm ---

def backtrack(answer, data):
    """ A generic backtrack algorithm
        answer = [a1, a2, ..., ak] solution so far
        data   = anything else we need for the particular problem
    """
    # Skienna's variables :
    # a      (i.e. answer) is the vector that we're building
    # k      is len(answer), the index we're working on
    # S      is possible extensions to the answer
    # data   is anything else that we need to pass along.
    #
    ## print "backtrack answer='%s', data='%s'" % (str(answer), str(data))
    if is_a_solution(answer, data):
        process_solution(answer, data)
    else:
        for candidate in construct_candidates(answer, data):
            ## print " candidate = '%s'" % str(candidate)
            make_move(candidate, answer, data)   # e.g. answer.append(c)
            backtrack(answer, data)
            unmake_move(candidate, answer, data) # e.g. answer.pop()

# --- data and functions for backtrack permutations ---

data = {'N'         : 4,          # size of board
        }
answer = []

def is_a_solution(answer, data):
    return len(answer) == data['N']

def process_solution(answer, data):
    # print a Q in each column given by digit in answer, e.g.
    # if answer = [0, 1, 2, 3] then print
    #    Q . . .         queen in column 0
    #    . Q . .         queen in column 1
    #    . . Q .         etc
    #    . . . Q
    for column in answer:
        output = ['.'] * data['N']
        output[column] = 'Q'
        print '   ' + ' '.join(output)
    print

def construct_candidates(answer, data):
    # This is the tricky part: find the list of integers (queen columns)
    # that are constent with the placment of the previous ones
    #
    # Here's a picture:
    #
    #   answer = [1, 3]                . Q . .    column 1   row 0
    #                                  . . . Q    column 3   row 1
    #                                  ? . . .    candidates row 2
    #
    # Here I'm trying a candidate at the '?', i.e. column=0
    # Then what I need to check is that
    #   a) there is no queen above in column 0
    #   b) no queen on right diagonal above the '?'
    #   c) no queen on left diagonal above the '?'
    # All of these can be done by looking at the column difference
    # and row differene between ? and a possible queen,
    # which will be 0, or +- the same as the row difference
    # if the two can attack each other.
    candidates = []
    this_row = len(answer)
    for column in range(data['N']):
        ok = True
        for row in range(this_row):
            column_offset = column - answer[row]
            row_difference = this_row - row
            if column_offset in [0, row_difference, - row_difference]:
                ok = False
        if ok:
            candidates.append(column)
    return candidates

def make_move(candidate, answer, data):
    answer.append(candidate)

def unmake_move(candidate, answer, data):
    answer.pop()

# --- and we're off! ---

backtrack(answer, data)