import copy


def adatok_megadasa():
    # Érvényes táblaméret kierőszakolása

    while True:
        try:
            meret = int(input('Mi legyen a tábla mérete? n = '))
            if meret == 1:
                print('Hülyeség, legalább 4 legyen a méret! ')
            if meret <= 3:
                print('Mondom >= 4 legyen!')
                continue
            return meret
        except ValueError:
            print('Baromság! Szedd össze magad!')


def tabla_megadasa(meret):
    # Előállítja az nxn-es táblát
    tabla = [0] * meret
    for i_sor in range(meret):
        tabla[i_sor] = [0] * meret
    return tabla


def print_megoldasok(megoldasok, meret):
    # Megoldások kiírása
    for megold in megoldasok:
        for sor in megold:
            print(sor)
        print()


def jo_eset(tabla, sor, oszl, meret):
    # sor,oszl pozíció vizsgálata

    # balra eső mezők az adott sorban
    for i_oszl in range(oszl):
        if tabla[sor][i_oszl] == 1:
            return False

    # átlósan balra fel
    i_sor, i_oszl = sor, oszl
    while i_sor >= 0 and i_oszl >= 0:
        if tabla[i_sor][i_oszl] == 1:
            return False
        i_sor -= 1
        i_oszl -= 1

    # átlósan balra le
    j_sor, j_oszl = sor, oszl
    while j_sor < meret and j_oszl >= 0:
        if tabla[j_sor][j_oszl] == 1:
            return False
        j_sor += 1
        j_oszl -= 1

    return True


def megoldas(tabla, oszl, meret):
    if oszl >= meret:
        return

    for sor in range(meret):
        if jo_eset(tabla, sor, oszl, meret):
            tabla[sor][oszl] = 1
            if oszl == meret - 1:
                hozzaad_megoldasokhoz(tabla)
                tabla[sor][oszl] = 0
                return
            megoldas(tabla, oszl + 1, meret)
            # backtrack
            tabla[sor][oszl] = 0


def hozzaad_megoldasokhoz(tabla):
    global megoldasok
    mentett_tabla = copy.deepcopy(tabla)
    megoldasok.append(mentett_tabla)


meret = adatok_megadasa()
tabla = tabla_megadasa(meret)
megoldasok = []
megoldas(tabla, 0, meret)
print_megoldasok(megoldasok, meret)

print('Összes megoldás száma = {}'.format(len(megoldasok)))