Recursive solution
Recursive solution. Should be called using SolveNQueens(int N) method.
public class NQueensAlgorithm
{
List<List<string>> ans;
List<List<char>> board;
public List<List<string>> SolveNQueens(int N)
{
ans = new List<List<string>>();
board = new List<List<char>>();
for (int i = 0; i < N; i++)
{
board.Add(new List<char>());
for (int j = 0; j < N; j++)
{
board[i].Add('.');
}
}
Place(0, 0, 0, 0);
return ans.ToList<List<string>>();
}
private void Place(int i, int vert, int ldiag, int rdiag)
{
int N = board.Count;
if (i == N)
{
List<string> res = new List<string>();
for (int row = 0; row < N; row++)
{
string rowStr = new string(board[row].ToArray());
res.Add(rowStr);
}
ans.Add(res);
return;
}
for (int j = 0; j < N; j++)
{
int vmask = 1 << j;
int lmask = 1 << (i + j);
int rmask = 1 << (N - i - 1 + j);
if ((vert & vmask) + (ldiag & lmask) + (rdiag & rmask) > 0)
continue;
board[i][j] = 'Q';
Place(i + 1, vert | vmask, ldiag | lmask, rdiag | rmask);
board[i][j] = '.';
}
}
}
This solution can be called this way:
NQueensAlgorithm algorithm = new();
List<List<string>> result = algorithm.SolveNQueens(N);Non-recursive solution
This is a non-recursive solution to n-queens problem.
public class NQueensAlgorithm
{
private readonly int N;
private int[] queens;
private int totalSolutions;
public NQueensAlgorithm(int N)
{
this.N = N;
queens = new int[N];
totalSolutions = 0;
}
private bool IsQueenSafe(int row, int col)
{
for (int r = 0; r < row; r++)
{
int c = queens[r];
if (c == col || Math.Abs(row - r) == Math.Abs(col - c))
{
return false;
}
}
return true;
}
private void PrintTheBoard()
{
Console.WriteLine("solution:");
for (int row = 0; row < N; row++)
{
char[] line = new char[N];
for (int i = 0; i < N; i++)
{
line[i] = '.';
}
if (row < queens.Length)
{
line[queens[row]] = 'Q';
}
Console.WriteLine(new string(line));
}
}
public void Solution()
{
Array.Clear(queens, 0, queens.Length);
int col = 0, row = 0;
while (true)
{
while (col < N && !IsQueenSafe(row, col))
{
col++;
}
if (col < N)
{
queens[row] = col;
if (row + 1 >= N)
{
totalSolutions++;
PrintTheBoard();
queens[row] = 0;
col = N;
}
else
{
row++;
col = 0;
}
}
if (col >= N)
{
if (row == 0)
{
Console.WriteLine($"Total solutions: {totalSolutions}");
return;
}
col = queens[--row] + 1;
}
}
}
}
This algorithm implementation can be called with
NQueensAlgorithm algorithm = new(N);
algorithm.Solution();Multithread solution
Below is a multithreaded, parallelized solution.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ParallelComputingCS3
{
public class NQueensAlgorithm
{
private readonly int N;
private int[] queens;
private int totalSolutions;
public NQueensAlgorithm(int N)
{
this.N = N;
queens = new int[N];
totalSolutions = 0;
}
private bool IsQueenSafe(int row, int col)
{
bool result = true;
Parallel.For(0, row, new ParallelOptions() { MaxDegreeOfParallelism=2},r =>
{
int c = queens[r];
if (c == col || Math.Abs(row - r) == Math.Abs(col - c))
{
result = false;
}
});
return result;
}
private void PrintTheBoard()
{
for (int row = 0; row < N; row++)
{
char[] line = new char[N];
for (int i = 0; i < N; i++)
{
line[i] = '.';
}
if (row < queens.Length)
{
line[queens[row]] = 'Q';
}
Console.WriteLine(new string(line));
}
}
public void Solution()
{
Array.Clear(queens, 0, queens.Length);
int col = 0, row = 0;
while (true)
{
while (col < N && !IsQueenSafe(row, col))
{
col++;
}
if (col < N)
{
queens[row] = col;
if (row + 1 >= N)
{
totalSolutions++;
//PrintTheBoard();
queens[row] = 0;
col = N;
}
else
{
row++;
col = 0;
}
}
if (col >= N)
{
if (row == 0)
{
Console.WriteLine($"Total solutions: {totalSolutions}");
return;
}
col = queens[--row] + 1;
}
}
}
}
}