using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication67
{
    class Program
    {
        static void Main(string[] args)
        {
            //число вершин
            int size = 8;
            //необходимое число единиц в врехнем треугольнике матрицы смежности
            int count = size * 3 / 2;
            //создаем матрицу смежности
            SymmetricalMatrix matrix = new SymmetricalMatrix(size);
            //находим всевозможные кубические графы
            int matrixCount = 0;
            foreach (SymmetricalMatrix m in Build(count, -1, matrix))
            {
                matrixCount++;
                Console.WriteLine("Matrix #"+matrixCount + ": ");
                Console.WriteLine(m);
            }
            //
            Console.WriteLine("Found "+ matrixCount+" graphs");
            Console.ReadLine();
        }

        static IEnumerable<SymmetricalMatrix> Build(int count, int prev, SymmetricalMatrix m)
        {
            if (count <= 0)
            {
                //матрица корректна ?
                if (m.IsCubicGraphMatrix())
                    yield return m;
            }
            else
            {
                for (int i = prev + 1; i <= m.data.Length - count; i++)
                {
                    //ставим единицу в позицию i
                    m.data[i] = 1;
                    //идем к следующему столбцу
                    foreach (var next in Build(count - 1, i, m))
                        yield return next;
                    //удаляем единицу из позиции i
                    m.data[i] = 0;
                }
            }
        }
    }

    //симметричная бинарная матрица, с нулями по диагонали
    public class SymmetricalMatrix
    {
        public readonly int size;
        //верхний треугольник
        public readonly byte[] data;        

        public SymmetricalMatrix(int size)
        {
            this.size = size;
            data = new byte[(size*size - size)/2];
        }

        public int indicesToDataIndex(int i, int j)
        {
            int k = i + 1;
            int l = (k * k + k) / 2;
            return i*size + j - l;
        }

        byte this[int i, int j]
        {
            get{
                if (i == j)
                    return 0;
                
                if(i<j)
                    return data[indicesToDataIndex(i, j)];
                else
                    return data[indicesToDataIndex(j, i)];
            }
        }

        //это действительно корректная матрица смежности для кубического графа ?
        public bool IsCubicGraphMatrix()
        {
            //считаем суммы по столбцам, они должны быть все равны 3
            for(int i=0;i<size;i++)
            {
                int sum = 0;
                for(int j=0;j<size;j++)
                {
                    if(this[i, j]!=0)
                        sum++;
                }
                if(sum!=3) return false;
            }

            return true;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < size; j++)
            {
                for (int i = 0; i < size; i++)
                    sb.Append(this[i, j]);
                sb.AppendLine();
            }
            return sb.ToString();
        }
    }
}