# ======================= #
# Le problème des n dames #
# ======================= #
# www.panamaths.net       #
# Juin 2015               #
# ======================= #

from numpy import array, zeros

# fonction Prise
# Permet la mise à jour de l'échiquier (cases en prise) dès qu'une nouvelle dame
# est placée.
# Arguments :
# M : l'échiquier (tableau numpy) dans son état courant (i.e. venant de recevoir
# une nouvelle dame.).
# a et b : les coordonnées de la nouvelle dame dans le tableau M.
def Prise(M,a,b):
    global n
    # Mise à 1 des éléments de la ligne d'indice a
    for j in range(n):
        if j != b and M[a,j] == 0:
            M[a,j] = 1
    # Mise à 1 des éléments de la colonne d'indice b
    for i in range(n):
        if i != a and M[i,b] == 0:
            M[i,b] = 1
    # Mise à 1 des éléments de la diagonale principale passant par M(a,b)
    i = 1
    while a+i < n and b+i < n:
        if M[a+i,b+i] == 0:
            M[a+i,b+i] = 1
        i += 1
    i = 1
    while a-i >= 0 and b-i >= 0:
        if M[a-i,b-i] == 0:
            M[a-i,b-i] = 1
        i += 1
    # Mise à 1 des éléments de la diagonale secondaire passant par M(a,b)
    i = 1
    while a+i < n and b-i >= 0:
        if M[a+i,b-i] == 0:
            M[a+i,b-i] = 1
        i += 1
    i = 1
    while a-i >= 0 and b+i < n:
        if M[a-i,b+i] == 0:
            M[a-i,b+i] = 1
        i += 1
    # Renvoi de l'échiquier à jour
    return(M)

# fonction Place
# Fonction récursive permettant le placement des dames
def Place(T,N):
    global n, S
    for i in range(n):
        if T[i,n-N] == 0:
            T2 = array(T)
            T2[i,n-N] = 2
            T2 = Prise(T2,i,n-N)
            # Il n'y a qu'une dame à placer (N=1) et on a pu le faire : on a une
            # nouvelle solution !
            # On incrémente le nombre de solutions (S) et on affiche la solution
            # courante (T2)
            if N == 1:
                S += 1
                print('Solution N°',S,':')
                print(T2,'\n')
            # On a pu placer une dame mais il en reste N-1 à placer : appel
            # récursif à la fonction Place
            else:
                Place(T2,N-1)
    return()

# =============== #
# DEBUT DU SCRIPT #
# =============== #
# variables globales
global n, S
# Saisie de la taille de l'échiquier
n = -1
while n <= 0:
    n = int(input('Nombre de dames à placer ? '))
# Initialisation de l'échiquier et du nombre de solutions
E = zeros((n,n))
S = 0
# Appel initial de la fonction place
Place(E,n)
if S == 0:
    print('Le problème n\'admet pas de solution !')
# ============= #
# FIN DU SCRIPT #
# ============= #