# Search for a solution to the N Queens problem using random probing

import random

# Keep doing random probes until you find a solution. (Note that a solution
# exists for all n>=4.) Return the solution plus the number of probes.

def NQueensRandomProbe(n):
    count=1;
    while True:
       board, found = NQRandomProbe(n)
       if found:
           return board, count
       count+=1

# Top level function for random probe: Initialize empty board,
# call "NextSquare" to fill in row i randomly until you get stuck. 

def NQRandomProbe(n):
    board = [-1]*n
    board[0] = random.randint(0,n-1)
    for i in range(1,n):
        q = NextSquare(board,i,n)
        if q==-1:
            return [], False
        board[i] = q
    return board, True

# Given the board filled up through row i-1. Accumulate all the unattacked
# squares in row i in possSquares and choose randomly among them. If there
# are none, return -1 as a failure flag.

def NextSquare(board,i,n):
    possSquares = []
    for j in range(0,n):
        attack = False
        for k in range(i):
#           print("Attack", board, k, i, j)
            attack = QAttack(k,board[k],i,j)
            if attack:
                break
        if not(attack):
           possSquares += [j]
    l = len(possSquares)
    if l == 0:
        return -1
    return random.choice(possSquares)

# Return true if <k,m> attacks <i,j>
def QAttack(k,m,i,j):
    return (m==j) or (k+m == i+j) or (k-m == i-j)