#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

bool igeretesZ(int *pInt, int k, int n, char **pString);

void kiirZ(int *pInt, int n, int k, char **pString);

void kiirMatrix(int *pInt, int k);

int countFives(int number, int count = 0) {
    if (number == 0)
        return count;
    if (number % 10 == 5)
        countFives(number / 10, count + 1);
    else countFives(number / 10, count);

}


long hatvanyozas(int alap, int kitevo) {
    if (kitevo == 0)
        return 1;
    if (kitevo % 2 == 0)
        return hatvanyozas(alap * alap, kitevo / 2);
    return alap * hatvanyozas(alap, kitevo - 1);
}

int kiirTomb(int n, int t[]) {
    if (n == 0) {
        return 0;
    }
    if (n > 0) {
//        kiirTomb(n - 1,t);
//        printf("%d ", t[n - 1]);
        return t[n - 1] + kiirTomb(n - 1, t);
    }

}


using namespace std;
void kiirZ(int *x, int k, char **szinek) {
    for (int i = 0; i <= k; ++i) {
        cout<<szinek[x[i]]<<' ';
    }
    cout<<'\n';
}

bool igeretesZ(int *x, int k, char **szinek) {
    if (k >= 1)
        if (strstr("feher sarga narancs", szinek[x[1]])==NULL)
            return false;
    if(k>0 and strcmp(szinek[x[0]],szinek[x[1]])==0)
        return false;
    if(k>1 and strcmp(szinek[x[2]],szinek[x[1]])==0)
        return false;

    return true;
}
void BTz(int *x, int n, int k, int p, char **szinek) {
    int i;
    for (i = 0; i < n; ++i) {
        x[k]=i;
        if (igeretesZ(x, k, szinek)) {
            if (k < p-1) {
                BTz(x, n, k + 1, p, szinek);
            } else kiirZ(x, k, szinek);
        }
    }
}

bool igeretes2( int x[], int k){
    for (int i=0; i<k; i++){
        if(x[k]== x[i]){
            return false;
        }
    }
    return true;
}
///@param x a verem
///Ez a fuggveny leszopja a faszod
///k a rekurzio szintje, de egyben a sor index is a matrixban (check the paper)
///x[k] a verem gyakorlatilag, es az oszlop index
void backTracking(int k, int n, int x[], int &megoldasCounter){
    for(int i=0; i<n; i++){
        x[k]=i;

        if(igeretes2( x, k)) {
            if (k < n - 1) {
                backTracking(k + 1, n, x, megoldasCounter);
            } else if(megoldasCounter <8){
                megoldasCounter++;
                kiirMatrix(x, k);
            }
        }
    }
}

void kiirMatrix(int x[], int n) {
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if(x[i]==j){
                cout<<"1 ";
            } else {
                cout<<"0 ";
            }
        }
        cout<<"\n";
    }
    cout<<"\n";
    cout<<"\n";

}

int main() {
    int megoldasCounter=0;
    int matrix[4][4]={0};
    int x[4];
    backTracking( 0 ,4, x, megoldasCounter);
    cout<<"\n"<<megoldasCounter;
    ///k- hanyadik szintrol indulunk
    ///n- hany elemem van(jelenleg a matrix merete)
    ///x- tomb(ferrari)
}