Description
Backtracking is a general algorithm to finding all solutions for a computational problem. It’s used in solving constraint satisfactions problems.
The N-queens problems is about placing N queens on an NxN chess board so that no queen would be a threat to another.
Functions Used
There are 2 main methods I used to determine this. One determines if a queen is safe to be placed on a certain row and the other handles backtracking
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Testing if it's safe to place the queen private bool IsSafe(char[,] Board, int row, int column) { //is column not safe - if for any other row on the same //column we have a queen that it's not safe for (int i = 0; i < row; i++) { if (Board[i, column] == 'Q') return false; } //testing for the same \ diagonal for (int i = row, j = column; i >= 0 && j >= 0; i--, j--) { if (Board[i, j] == 'Q') return false; } //testing for the same / diagonal for (int i = row, j = column; i >= 0 && j < Size; i--, j++) { if (Board[i, j] == 'Q') return false; } return true; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
private void Solve(char[,] Board, int row, int column) { if (column == 0 && row == Size) { this.Solutions.Add(CloneBoard(Board)); return; } for (int i = 0; i < Size; i++) { if (IsSafe(Board, row, i)) { Board[row, i] = 'Q'; Solve(CloneBoard(Board), row + 1, 0); Board[row, i] = '-'; } } } |
Complete Solution
The solution defines a class that stores all the solutions in a List of matrix char. Queens will have the char ‘Q’ and empty items will have the char ‘-‘
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
public class NQueens { //the size of the board public int Size { get; } //A list to place all solutions public List<char[,]> Solutions { get; } //counting no of solutions public int SolutionsCount => Solutions.Count(); public NQueens(int size) { this.Size = size; this.Solutions = new List<char[,]>(); } public void SolveNQueens() { char[,] board = new char[8, 8]; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { board[i, j] = '-'; } } Solve(board, 0, 0); } public void PrintSolution(int index) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < Size; i++) { for (int j = 0; j < Size; j++) { sb.Append(Solutions[index][i, j]); sb.Append(' '); } sb.AppendLine(); } Console.Write(sb.ToString()); } //Testing if it's safe to place the queen private bool IsSafe(char[,] Board, int row, int column) { //is column not safe - if for any other row on the same //column we have a queen that it's not safe for (int i = 0; i < row; i++) { if (Board[i, column] == 'Q') return false; } //testing for the same \ diagonal for (int i = row, j = column; i >= 0 && j >= 0; i--, j--) { if (Board[i, j] == 'Q') return false; } //testing for the same / diagonal for (int i = row, j = column; i >= 0 && j < Size; i--, j++) { if (Board[i, j] == 'Q') return false; } return true; } private char[,] CloneBoard(char[,] board) { char[,] newBoard = new char[Size, Size]; for (int i = 0; i < Size; i++) { for (int j = 0; j < Size; j++) { newBoard[i, j] = board[i, j]; } } return newBoard; } private void Solve(char[,] Board, int row, int column) { if (column == 0 && row == Size) { this.Solutions.Add(CloneBoard(Board)); return; } for (int i = 0; i < Size; i++) { if (IsSafe(Board, row, i)) { Board[row, i] = 'Q'; Solve(CloneBoard(Board), row + 1, 0); Board[row, i] = '-'; } } } } |
Console Application and WPF Preview
|
1 2 3 4 5 |
NQueens nQueens = new NQueens(8); nQueens.SolveNQueens(); nQueens.PrintSolution(0); Console.WriteLine(); nQueens.PrintSolution(10); |
