1281 - Regine1

Cerința

Se consideră o tablă de șah de dimensiune n. Să se plaseze pe tablă n regine astfel încât să nu existe două regine care să se atace.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran o singură configurație validă a tablei de șah. Ea va fi alcătuită din n linii cu câte n caractere - sau *, separate prin câte un spațiu. Caracterul - reprezintă o poziție liberă de pe tablă, iar caracterul * reprezintă o poziție de pe tablă ocupată de o regină.

Restricții și precizări

• 4 ≤ n ≤ 10;
• două regine se atacă dacă se află pe aceeași linie, aceeași coloană sau aceeași diagonală;
• orice configurație validă a tablei este acceptată.

Exemplul 1

Intrare

4

Ieșire

- - * - 
* - - - 
- - - * 
- * - - 

Exemplul 2

Intrare

1

Consola

Dimensiunea tablei trebuie să fie între 4 ștre 4 și 10).

Rezolvare

def verifica_restrictie_n(n):
    # Verifică restricția asupra valorii lui n
    return 4 <= n <= 10

def verifica_restrictii(tabla, linie, coloana, n):
    # Verifică dacă este sigur să plasezi o regină la poziția (linie, coloana)

    # Verifică pe aceeași linie
    if '*' in tabla[linie]:
        return False

    # Verifică pe aceeași coloană
    if '*' in [tabla[i][coloana] for i in range(n)]:
        return False

    # Verifică pe diagonala principală
    if '*' in [tabla[i][i] for i in range(min(linie, coloana) + 1)]:
        return False

    # Verifică pe diagonala secundară
    if '*' in [tabla[i][coloana - (linie - i)] for i in range(min(linie, coloana, n - coloana - 1) + 1)]:
        return False

    return True

def afiseaza_tabla(tabla, n):
    # Afișează configurația tablei de șah
    for i in range(n):
        print(' '.join(tabla[i]))

def rezolva(tabla, linie, n):
    # Verifică dacă am plasat toate reginele
    if linie == n:
        afiseaza_tabla(tabla, n)
        exit()

    # Plasează regina pe fiecare coloană a liniei curente
    for coloana in range(n):
        if verifica_restrictii(tabla, linie, coloana, n):
            tabla[linie][coloana] = '*'
            rezolva(tabla, linie + 1, n)
            tabla[linie][coloana] = '-'

# Cerem utilizatorului să introducă dimensiunea tablei de șah
input_n = input("Introduceți dimensiunea tablei de șah (n între 4 și 10): ")

# Verificăm restricția asupra valorii lui n
try:
    n = int(input_n)
    if verifica_restrictie_n(n):
        # Inițializăm tabla de șah cu caractere '-'
        tabla = [['-' for _ in range(n)] for _ in range(n)]

        # Apelăm funcția pentru a rezolva problema
        rezolva(tabla, 0, n)
    else:
        print("Dimensiunea tablei trebuie să fie între 4 și 10.")
except ValueError:
    print("Introduceți o valoare validă pentru n.")