import random

'''
The n-queens puzzle: how to put n queens on an nXn chess board
in such away that no queen attacks another.
Two queens attack each other if they are on the smae row
the same col, or the same diagonal.

The board is represented by a list of n elemnts.
board[i] stores the col. of the queen in the ith row.
[1,2,0,3] represents the board:
#Q##
##Q#
Q###
###Q

The algorithm staets with a random board.
It, repeatedly, move one queen to a new col.
It chooses the move that minimizes the number o threats.
When no improvement is possible, it checks the number of threats:
if it is 0 - a solution was found, if no not the algorithm starts over
with a new random board.
'''

def rndboard(n):
    #Returns a board with n queens in random cols
    board = []
    '''
    Your code here.
    board should contain a list of n random number (0..n-1)
    '''
    return board

def threats(board):
    #Returns the number of pairs of queens that threat each other
    count = 0
    for i in range(len(board)-1):
        for j in range(i+1, len(board)):
            '''
            The if sentence checks queens i and j are not on the same col.
            Add a boolean expression that checks that they are not on
             the same diagonal.
            '''
            if board[i] == board[j]
                count += 1
    return count

def improve(board):
    #Improves board, if  improvment is possible,
    #by lowering the number of pairs of queens that threat each other.
    #Returns the num of threats in the board
    minimum = threats(board)
    #Improved holds the best move so far.
    #Improved[0] is the row number and improves[1] is the new col. number
    #of the queen that should move.
    improved = [0,board[0]]
    for r in range(len(board)):
        tmp = board[r]#Saves the original place of the queen i row r
        cols = list(range(len(board)))
        cols.remove(board[r])#All cols. but r
        for c in cols:
            board[r] = c#Tries a new col. for the queen in row r
            x = threats(board)
            if x < minimum:#Checks whether the new board has min. threats.  
                minimum = x
                improved = [r,c]
        board[r] = tmp#Restores the original place of the queen i row r
    '''
    Your code here.
    The code you write here should make the chosen move.
    '''
    return minimum

def solve(size):
    #Solves the (size) queens problem
    b = rndboard(size) #Creates a random board
    n = threats(b)
    while n>0:                #While there are pairs of queens that threat each other 
        x = improve(b)        #  Tries to reduce the number of threats
        if x == n:
            '''
            Your code here.
            complete the if statement and do not forget to erase pass.
            '''
            pass
    printboard(b)
            
    
solve(8)