using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _8_queen
{
    class Program
    {
        static void Find(byte[,] board, List<byte[,]> results, int index = 0, int count_q = 0)
        {
            byte[,] saved_board = (byte[,])board.Clone();
            for (int i = 0; i < 8; i++)
            {
                for (int j = index;  j < 8; j++)
                {
                    if (board[i, j] == 0)
                    {
                        Mark(board, i, j);
                        count_q++;
                        Find(board, results, 0, count_q);
                    }
                }
            }
            int saved_count = count_q;
            if (count_q != 8 && index != 8)
            {
                index++;
                count_q = saved_count;
                Find(saved_board, results, index, saved_count);
            }
            if (count_q == 8) results.Add(board);
        }
        static void Mark(byte[,] board, int index1, int index2)
        {
            board[index1, index2] = 2;
            int difference = index1 - index2;
            int sum = index1 + index2;
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    if ((i == index1 || j == index2 || i - j == difference || i+j == sum) && board[i,j] == 0) board[i, j] = 1;
                }
            }
        }
        static void Main(string[] args)
        {
            byte[,] board = new byte[8, 8];
            List<byte[,]> results = new List<byte[,]>();
            Find(board, results);

            List<byte[,]> actual_results = new List<byte[,]>();
            foreach (byte[,] b in results)
            {
                int count = 0;
                for (int i = 0; i < 8; i++)
                {
                    for (int j = 0; j < 8; j++)
                    {
                        if (b[i, j] == 2) count++;
                    }
                }
                if (count == 8) actual_results.Add(b);
            }
            board = actual_results[0];
        }
    }
}