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. 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(); } } } ``` ```// // 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= 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[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(); } } } ```