Day3NQueens

using System;

namespace NQP
{
    class Program
    {
        static int N;
        static int k = 1;

        static void PrintSolution(int[,] board)
        {
            Console.WriteLine("{0} - ", k++);
            for (int i = 0; i < board.GetLength(0); i++)
            {
                for (int j = 0; j < board.GetLength(1); j++)
                {
                    Console.Write("{0} ", board[i, j]);
                }
                Console.WriteLine();
            }
        }


        static bool IsSave(int[,] board, int row, int col)
        {
            for (int i = 0; i < col; i++)
            {
                if (board[row, i] == 1)
                {
                    return false;
                }
            }

            for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
            {
                if (board[i, j] == 1)
                {
                    return false;
                }
            }

            for (int i = row, j = col; i < N && j >= 0; i++, j--)
            {
                if (board[i, j] == 1)
                {
                    return false;
                }
            }
            return true;
        }




       static bool SolveNQ(int[,] board, int col)
        {
            if (N == col)
            {
                PrintSolution(board);
                return true;
            }

            bool res = false;

            for (int i = 0; i < N; i++)
            {
                if (IsSave(board, i, col))
                {
                    board[i, col] = 1;
                    res = SolveNQ(board, col + 1) || res;
                    board[i, col] = 0;
                }
            }
            return res;
        }


        static void Main(string[] args)
        {
            Console.Write("Enter number of queens: ");
            N = int.Parse(Console.ReadLine());
            int[,] matrix = new int[N, N];
            if(!SolveNQ(matrix, 0))
            {
                Console.WriteLine("Solution does not exist!");
            }

        }
    }
}