TWO SIMPLE ALGORITHMS TO SOLVE N QUEENS PROBLEM

Detail explanations of N queens problem may be found at Wikipedia.

Here I present two programs that solve N queens puzzle.


'NEIGHBOURHOOD' ALGORITHM


The first way uses classical stack technique and neighbourhoods to make search more selective. Neighbourhood here means that when we look for new queen's position we start search near current queen. The figure below shows queens neighbourhood. Queens position is marked with black cross. Neighbourhood positions are filled with green color. Positions with '1' tried first, then positions labelled with '2' and so on.

Queen Neighbourhood

 

Such heuristic enhancement increase algorithm performance.

  
//
//  Program.cs - N queen problem solution using 'neighbourhood' heuristic.
//               It means that new queen position is selected from 
//               current queen neighbourhood.
//
//  Project: 
//  Author: S.Zabinskis
//

using System;
using System.Drawing;
using System.Collections.Generic;


namespace Queens1
{
    class Program
    {
        // you may change N 
        public const int N = 8;
        public const int INVALID_MOVE = -1;
        public const int INVALID_POSITION = -1;
        // used to generate random position for first queen
        public static Random rnd = new Random(DateTime.Now.Millisecond + 1000*(DateTime.Now.Second+DateTime.Now.Minute*60));
        // list to hold queens
        public static List queens = new List();
        // list of displacements from current queen position (
        //public static List displacement = new List();
        public static List displacement = new List();

        // this function creates neighbourhood
        static void Initialize()
        {
            for(int dr=2; dr<=N/2+1; dr++)
            {
                for(int dc=1; dc < dr; dc++)
                {
                    displacement.Add(new Point(dc, dr));
                    displacement.Add(new Point(-dc, dr));
                    displacement.Add(new Point(dc, -dr));
                    displacement.Add(new Point(-dc, -dr));

                    displacement.Add(new Point(-dr, -dc));
                    displacement.Add(new Point(dr, -dc));
                    displacement.Add(new Point(-dr, dc));
                    displacement.Add(new Point(dr, dc));
                }
            }
        }

        // returns 'true' if position (row,col) is on the same row with any queen
        static bool OnSameRow(int row, int col)
        {
            foreach (int q in queens)
                if (q / N == row)
                    return true;
            return false;
        }

        // returns 'true' if position (row,col) is on the same column with any queen
        static bool OnSameColumn(int row, int col)
        {
            foreach (int q in queens)
                if ((q % N) == col)
                    return true;
            return false;
        }

        // returns 'true' if position (row,col) is on the same diagonal with any queen
        static bool OnSameDiagonal(int row, int col)
        {
            foreach (int q in queens)
                if (Math.Abs(q / N - row) == Math.Abs(q % N - col))
                    return true;
            return false;
        }

        // returns 'true' if position (row,col) is under attack 
        static bool IsAttacked(int row, int col)
        {
            return OnSameRow(row, col) || OnSameColumn(row, col) || OnSameDiagonal(row, col);
        }

   
        public static int UpdateCoord(int x)
        {
            if (x < 0)
                return N + x;
            if (x < N)
                return x;
            return x - N;
        }

   
        public static int NextMove(int pos, int start)
        {
            for (int index = start; index < displacement.Count; index++)
            {
                if (TryMove(pos, index) != INVALID_MOVE)
                    return index;
            }
            return INVALID_MOVE;
        }

        static void GetRowCol(out int row, out int col, int pos, int index)
        {
            row = pos / N + displacement[index].Y;
            col = pos - N * (row - displacement[index].Y) + displacement[index].X;
            row = UpdateCoord(row);
            col = UpdateCoord(col);
        }

        static int ApplyMove(int pos, int index)
        {
            int row, col;
            GetRowCol(out row, out col, pos, index);
            return row*N + col;
        }


        public static int TryMove(int pos, int index)
        {
            int row, col;
            GetRowCol(out row, out col, pos, index);
            return IsAttacked(row, col) ? INVALID_MOVE : row * N + col;
        }

        static void ShowSolution()
        {
            int[] showboard = new int[N * N];

            foreach (int q in queens)
            {
                showboard[q] = 1;
            }
            for (int row = 0; row < N; row++)
            {
                for (int col = 0; col < N; col++)
                {
                    Console.Write("{0} ", showboard[row * N + col] == 0 ? "0" : "X");
                }
                Console.WriteLine("");
            }
        }


        static void Main(string[] args)
        {
            // initialize array of translations that make current queen neighbourhood
            Initialize();

            // integer variable pos holds current queen position : 0..N*N-1
            // randomly generate position of the first queen
            int pos = rnd.Next(0, N * N - 1);
            // index variable holds current number of position of the next queen in neighbourhood
            int index = 0;

            // number of iterations needed to get solution
            int iter = 0;

            // stack to hold numbers of positions in neighbourhood (see explanation of 'index' variable)
            Stack track = new Stack();

            // add the first queen to the list
            queens.Add(pos);

            while (queens.Count < N)
            {
                // make new move - get number of free position in current queen neighbourhood
                index = NextMove(pos, index);

                // now get real position of next queen
                int newpos = index == INVALID_MOVE ? INVALID_POSITION : ApplyMove(pos, index);
                //Console.WriteLine("Index: {0}  Pos:{1} --> Pos:{2}", index, pos, newpos);

                // in case if there is no free (or not visited) position in neighbourhood
                if (newpos == INVALID_POSITION)
                {
                    if (track.Count > 0)
                    {
                        // pop last visited number of position in neighbourhood.
                        // Adding '1' we proceed with next number of position
                        index = track.Pop() + 1;
                        // delete last queen
                        queens.RemoveAt(queens.Count-1);
                        // and position of queen that becomes current
                        pos = queens[queens.Count - 1];
                        //Console.WriteLine("Back: {0}:{1} Total:{2}", pos, index, queens.Count);
                    }
                    else
                    {
                        // unexpected program behaviour - we get empty stack.
                        Console.WriteLine("Empty stack");
                        queens.Clear();
                        break;
                    }
                }
                else
                {
                    // save the number of last visited position in neighbourhood
                    track.Push(index);
                    // and make this queen current
                    pos = newpos;
                    queens.Add(newpos);
                    // start from the first neighbourhood position
                    index = 0;

                    // uncomment these lines to see current queens positions
                    //ShowSolution();
                    //Console.ReadLine();

                }
                iter++;
            }
            Console.WriteLine("Solution found after {0} iterations", iter);
            Console.WriteLine();
            ShowSolution();
            Console.WriteLine();
            Console.WriteLine("Press any key ...");
            Console.ReadLine();
        }
    }
}

Download source code here.

'ROWS' ALGORITHM

Other way uses obvious fact that for each solution of the problem we have that each chessboard row (or column) contains one and only one queen. So, starting from the first row we have 8 possible positions for the first queen, for second row he have no more that 6 available positions and so on. In case if the next row doesn't have available positions (all cells are under attack) we go back to previous row and move queen to the next available position. The idea of algorithm is illustrated by figure:


'Row' algorithm illustration

Green cells are queens positions. Red cells are for cells under attack (cell label is ordinal number of queen that attacks this field). Blank fields are for available positions.

  
//
//  Program.cs - N queen problem solution using 'rows' approach.
//
//  Project:
//  Author: S.Zabinskis
//

using System;
using System.Collections.Generic;


namespace Queens4
{
    class Program
    {
        private enum States
        {
            SavePosition,
            NextLine,
            Back,
            NextColumn
        } ;


        // you may change N 
        public const int N = 10;
        public const int INVALID_MOVE = -1;
        public const int INVALID_POSITION = -1;
        public static Random rnd = new Random(DateTime.Now.Millisecond + 1000 * (DateTime.Now.Second + DateTime.Now.Minute * 60));
        public static List queens = new List();
        public static List dx = new List();

        static void Initialize()
        {
            for(int j=2; j<N; j++)
            {
                dx.Add(j);
                dx.Add(-j);
            }
        }

        static void ShowSolution()
        {
            int[] showboard = new int[N * N];

            foreach (int q in queens)
            {
                showboard[q] = 1;
            }
            for (int row = 0; row < N; row++)
            {
                for (int col = 0; col < N; col++)
                {
                    Console.Write("{0} ", showboard[row * N + col] == 0 ? "0" : "X");
                }

                Console.WriteLine("");
            }
        }

        static bool NextLine(int lineno, int[] line)
        {
            int numfree = N;
            foreach (int q in queens)
            {
                // occupy the whole column
                line[q % N] = 1;
                numfree--;
                // occupy diagonal
                if ((q % N) + lineno - (q / N) < N)
                {
                    line[(q % N) + lineno - (q / N)] = 1;
                    numfree--;
                }
                // occupy diagonal
                if ((q % N) - (lineno - (q / N)) >= 0)
                {
                    line[(q % N) - (lineno - (q / N))] = 1;
                    numfree--;
                }
            }
            return numfree > 0;
        }

        static void ClearLine(int[] line)
        {
            for (int j = 0; j < N; j++)
                line[j] = 0;
        }

        static int NextPosition(int[] line)
        {
            int pos = queens.Count > 0 ? queens[queens.Count - 1]%N : N/2;
            for (int j = 0; j < dx.Count; j++)
            {
                if((pos+dx[j] >= 0) && (pos+dx[j] board = new List();

            // here chess board is represented as collection (array) of rows
            for (int j = 0; j < N; j++)
            {
                board.Add(new int[N]);
            }

            // get random position in first row
            int pos = rnd.Next(0, N - 1);
            board[0][pos] = 1;
            int lineno = 0;
            int iter = 0;
            States state = States.SavePosition;

            while (queens.Count < N)
            {
                switch (state)
                {
                    case States.SavePosition:
                        queens.Add(lineno * N + pos);
                        state = States.NextLine;
                        break;

                    case States.NextLine:
                        lineno++;
                        NextLine(lineno, board[lineno]);
                        state = States.NextColumn;
                        break;

                    case States.NextColumn:
                        pos = NextPosition(board[lineno]);
                        state = pos == INVALID_POSITION ? States.Back : States.SavePosition;
                        break;

                    case States.Back:
                        ClearLine(board[lineno]);
                        lineno--;
                        queens.RemoveAt(queens.Count - 1);
                        state = States.NextColumn;
                        break;
                }
                iter++;
            }
            Console.WriteLine("Solution found after {0} iterations", iter);
            Console.WriteLine();
            ShowSolution();
            Console.WriteLine();
            Console.WriteLine("Press any key ...");
            Console.ReadLine();
        }
    }
}

Download source code here.