C# code to solve N Queen problem using backtracking

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace NQueen
{
    class Program
    {
        const int N = 8;
        static void Main(string[] args)
        {
            int count = 0;
            int[,] board = new int[N, N];

            //Initialize the board array to 0
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    board[i, j] = 0;
                }
            }

            //Initialize the pointer array
            int[] pointer = new int[N];
            for (int i = 0; i < N; i++)
            {
                pointer[i] = -1;
            }

            //Implementation of Back Tracking Algorithm
            for (int j = 0; ; )
            {
                pointer[j]++;
                //Reset and move one column back 
                if (pointer[j] == N)
                {
                    board[pointer[j] - 1, j] = 0;
                    pointer[j] = -1;
                    j--;
                    if (j == -1)
                    {
                        Console.WriteLine("All possible configurations have been examined...");
                        break;
                    }
                }
                else
                {
                    board[pointer[j], j] = 1;
                    if (pointer[j] != 0)
                    {
                        board[pointer[j] - 1, j] = 0;
                    }
                    if (SolutionCheck(board))
                    {
                        j++;//move to next column
                        if (j == N)
                        {
                            j--;
                            count++;
                            Console.WriteLine("Solution" + count.ToString() + ":");
                            for (int p = 0; p < N; p++)
                            {
                                for (int q = 0; q < N; q++)
                                {
                                    Console.Write(board[p, q] + " ");
                                }
                                Console.WriteLine();
                            }
                        }
                    }
                }
            }
        }
        public static bool SolutionCheck(int[,] board)
        {
            //Row check
            for (int i = 0; i < N; i++)
            {
                int sum = 0;
                for (int j = 0; j < N; j++)
                {
                    sum = sum + board[i, j];
                }
                if (sum > 1)
                {
                    return false;
                }
            }
            //Main diagonal check
            //above
            for (int i = 0, j = N - 2; j >= 0; j--)
            {
                int sum = 0;
                for (int p = i, q = j; q < N; p++, q++)
                {
                    sum = sum + board[p, q];
                }
                if (sum > 1)
                {
                    return false;
                }
            }
            //below
            for (int i = 1, j = 0; i < N - 1; i++)
            {
                int sum = 0;
                for (int p = i, q = j; p < N; p++, q++)
                {
                    sum = sum + board[p, q];
                }
                if (sum > 1)
                {
                    return false;
                }
            }
            //Minor diagonal check
            //above
            for (int i = 0, j = 1; j < N; j++)
            {
                int sum = 0;
                for (int p = i, q = j; q >= 0; p++, q--)
                {
                    sum = sum + board[p, q];
                }
                if (sum > 1)
                {
                    return false;
                }
            }
            //below
            for (int i = 1, j = N - 1; i < N - 1; i++)
            {
                int sum = 0;
                for (int p = i, q = j; p < N; p++, q--)
                {
                    sum = sum + board[p, q];
                }
                if (sum > 1)
                {
                    return false;
                }
            }
            return true;
        }
    }
}
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

11 Responses to C# code to solve N Queen problem using backtracking

  1. KedarPhatak says:

    Hay have you solved this problem using Hill climbing random restart ?

  2. Zander says:

    Hi there, this is e very nice solution, i would like to see other comments on the code above, can you put more comments in the code please

  3. Saikat says:

    Any specific section of code you need more clarity?

  4. Gandhi says:

    Thank you man, that really helped.

  5. Behar says:

    Hi, very nice solution, great job

  6. Hi,
    can u explain why did u used the Pointers array??

  7. Hi. Thanks for post.
    Could you explain why did you use major and minor diagonal check? I can not understand..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s