# heuristiques :
## 1 reine par ligne
## 1 reine par colonne
## les prises étant symétriques, vérifier vers le haut suffit

class Echiquier:
    def __init__(self, taille):
        self.taille = taille
        self.plateau = []
        for _ in range(taille):
            self.plateau.append([" "] * taille)
        self.colonnesUtilisees = set()

    def __str__(self):
        separation = "-" * (2 * self.taille + 1)
        retour = separation + "\n"
        for ligne in self.plateau:
            for case in ligne:
                retour += "|" + case
            retour += "|" + "\n"
            retour += separation + "\n"
        return retour

    def placerReine(self, num_reine = 0):
        if num_reine == self.taille:
            # on a fini !
            return self
        for colonne in range(self.taille):
            if colonne in self.colonnesUtilisees:
                continue
            nouvel_echiquier = self.copier()
            try:
                nouvel_echiquier.jouerReine(num_reine, colonne)
            except Exception:
                continue
            solution = nouvel_echiquier.placerReine(num_reine+1)
            if solution is not None:
                return solution
        return None

    def jouerReine(self, num_ligne, num_colonne):
        self.plateau[num_ligne][num_colonne] = "R"
        self.verifierNordOuest(num_ligne, num_colonne)
        self.verifierNordEst(num_ligne, num_colonne)
        self.colonnesUtilisees.add(num_colonne)

    def copier(self):
        copie = Echiquier(self.taille)
        copie.colonnesUtilisees = set(self.colonnesUtilisees)
        for num_ligne in range(self.taille):
            for num_colonne in range(self.taille):
                copie.plateau[num_ligne][num_colonne] = self.plateau[num_ligne][num_colonne]
        return copie

    def verifierNordOuest(self, num_ligne, num_colonne):
        while num_ligne > 0 and num_colonne > 0:
            num_ligne -= 1
            num_colonne -= 1
            if self.plateau[num_ligne][num_colonne] == "R":
                raise Exception()

    def verifierNordEst(self, num_ligne, num_colonne):
        while num_ligne > 0 and num_colonne < self.taille - 1:
            num_ligne -= 1
            num_colonne += 1
            if self.plateau[num_ligne][num_colonne] == "R":
                raise Exception()