C# - Backtracking Using Recursion
Backtracking using recursion in C# is a powerful technique used to solve problems where you need to explore all possible solutions in a systematic way, typically in scenarios like searching for solutions in a game, finding the shortest path in a maze, or solving combinatorial problems. This approach involves making a series of choices and exploring their consequences, and if a choice leads to a dead end, you backtrack and try another option until a solution is found or all possibilities are exhausted.
1. Finding Permutations Using Backtracking
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
List<int> elements = new List<int> { 1, 2, 3 };
List<List<int>> permutations = new List<List<int>>();
FindPermutations(elements, new List<int>(), permutations);
Console.WriteLine("All Permutations:");
foreach (var perm in permutations)
{
Console.WriteLine(string.Join(", ", perm));
}
}
static void FindPermutations(List<int> elements, List<int> current, List<List<int>> permutations)
{
if (elements.Count == 0)
{
permutations.Add(new List<int>(current));
return;
}
for (int i = 0; i < elements.Count; i++)
{
int element = elements[i];
elements.RemoveAt(i);
current.Add(element);
FindPermutations(elements, current, permutations);
elements.Insert(i, element);
current.RemoveAt(current.Count - 1);
}
}
}
Explanation
- In this code, we have a list of elements [1, 2, 3], and we want to find all possible permutations of these elements.
- We use a recursive function
FindPermutations to explore all possible choices and backtracks when needed.
- The base case checks if all elements have been used, and if so, adds the current permutation to the
permutations list.
- Inside the loop, we choose an element, remove it from the list, add it to the current permutation, and recursively call
FindPermutations.
- After the recursion, we backtrack by restoring the original state, allowing us to explore other possibilities.
Expected Output
When you run this program, you will see the following output:
All Permutations:
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 2, 1
3, 1, 2
The program finds all permutations of [1, 2, 3] using backtracking and recursion.
In summary, backtracking using recursion in C# is a powerful technique for solving complex problems by exploring all possible choices and systematically finding solutions. It involves making choices, exploring their consequences, and backtracking when necessary to explore other options.
2. N-Queens Problem:
The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten each other (no two queens are in the same row, column, or diagonal).
using System;
public class NQueens
{
private int[] queens;
private int n;
public NQueens(int n)
{
this.n = n;
this.queens = new int[n];
}
public void Solve()
{
PlaceQueens(0);
}
private void PlaceQueens(int row)
{
if (row == n)
{
PrintSolution();
return;
}
for (int col = 0; col < n; col++)
{
if (IsSafe(row, col))
{
queens[row] = col;
PlaceQueens(row + 1);
}
}
}
private bool IsSafe(int row, int col)
{
for (int i = 0; i < row; i++)
{
if (queens[i] == col || Math.Abs(queens[i] - col) == Math.Abs(i - row))
return false;
}
return true;
}
private void PrintSolution()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
Console.Write(queens[i] == j ? "Q " : ". ");
}
Console.WriteLine();
}
Console.WriteLine();
}
}
public class Program
{
public static void Main()
{
int n = 4; // Change 'n' to solve N-Queens for different board sizes
NQueens nQueens = new NQueens(n);
nQueens.Solve();
}
}
The provided C# program solves the N-Queens problem using a backtracking algorithm. This problem aims to place N chess queens on an N×N chessboard so that no two queens threaten each other. In other words, the goal is to find a placement where no two queens share the same row, column, or diagonal.
Output for n = 4:
Q . . .
. . Q .
. . . Q
. Q . .
. . Q .
Q . . .
. . . Q
. Q . .
Explanation of the Output:
- The program successfully finds and prints two solutions to the 4-Queens problem.
- Each solution is represented by a grid of size 4x4, where 'Q' represents a queen, and '.' represents an empty square.
- In both solutions, there are no two queens in the same row, column, or diagonal. This satisfies the rules of the N-Queens problem.
- The program uses backtracking to explore different queen placements. It starts by placing a queen in the first row and iterates through the columns to find a safe position. If a safe position is found, it proceeds to the next row. If not, it backtracks and explores other possibilities.
- The backtracking algorithm continues until all solutions are found or all possibilities are exhausted.
- In this case, the program found two valid solutions to the 4-Queens problem.
- You can change the value of 'n' in the Main method to solve the N-Queens problem for different board sizes.
This program demonstrates the power of backtracking to systematically find solutions to complex combinatorial problems like the N-Queens problem, where a brute-force approach would be impractical. It ensures that no two queens threaten each other, providing valid solutions to the problem.
3. Sudoku Solver:
The Sudoku puzzle involves filling a 9x9 grid with digits such that each column, each row, and each of the nine 3×3 subgrids (also called boxes) contains all of the digits from 1 to 9.
using System;
public class SudokuSolver
{
private int[,] board;
public SudokuSolver(int[,] board)
{
this.board = board;
}
public bool Solve()
{
int row, col;
if (!FindUnassignedCell(out row, out col))
return true; // All cells are filled, solution found!
for (int num = 1; num <= 9; num++)
{
if (IsSafe(row, col, num))
{
board[row, col] = num;
if (Solve())
return true;
board[row, col] = 0; // Undo the choice (backtrack)
}
}
return false; // No solution found for this configuration
}
private bool FindUnassignedCell(out int row, out int col)
{
for (row = 0; row < 9; row++)
{
for (col = 0; col < 9; col++)
{
if (board[row, col] == 0)
return true;
}
}
row = col = -1;
return false; // All cells are assigned
}
private bool IsSafe(int row, int col, int num)
{
return !UsedInRow(row, num) &&
!UsedInColumn(col, num) &&
!UsedInBox(row - row % 3, col - col % 3, num);
}
private bool UsedInRow(int row, int num)
{
for (int col = 0; col < 9; col++)
{
if (board[row, col] == num)
return true;
}
return false;
}
private bool UsedInColumn(int col, int num)
{
for (int row = 0; row < 9; row++)
{
if (board[row, col] == num)
return true;
}
return false;
}
private bool UsedInBox(int startRow, int startCol, int num)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (board[row + startRow, col + startCol] == num)
return true;
}
}
return false;
}
public void PrintBoard()
{
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
Console.Write(board[row, col] + " ");
}
Console.WriteLine();
}
}
}
public class Program
{
public static void Main()
{
int[,] sudokuBoard = {
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}
};
SudokuSolver solver = new SudokuSolver(sudokuBoard);
if (solver.Solve())
{
Console.WriteLine("Sudoku Solution:");
solver.PrintBoard();
}
else
{
Console.WriteLine("No solution exists for the given Sudoku.");
}
}
}
The output of the program is a completed Sudoku board:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
In all examples we used recursion and explored all possible choices. If a choice leads to a valid solution, the algorithm proceeds further. Otherwise, it backtracks and tries other possibilities until a valid solution is found or all possibilities have been explored.
Explanation of the Algorithm
This output is the result of a Sudoku solving algorithm, implemented in C# in the provided program and replicated in Python for demonstration. The algorithm employs a backtracking approach, a common technique in solving constraint satisfaction problems like Sudoku.
Here's a breakdown of how the algorithm works:
- Initialization: A partially filled Sudoku board is provided as input.
- Finding Unassigned Cells: The algorithm searches for cells that are not assigned (i.e., cells with a value of 0). If all cells are assigned, the Sudoku is solved.
- Trying Numbers: For each unassigned cell, the algorithm tries numbers from 1 to 9, checking if the number can be placed without violating Sudoku rules.
- Checking Safety: A number is considered safe if it does not appear in the same row, column, or 3x3 subgrid of the cell being filled.
- Backtracking: If a number is found to be safe, the algorithm assigns it to the cell and recursively attempts to solve the rest of the board. If it encounters a situation where no numbers can be placed in an unassigned cell, it backtracks, undoing the last number assignment and trying a different number.
- Completion or Failure: The algorithm repeats these steps until either the entire board is filled (a solution is found), or it is determined that no solution exists for the given initial configuration.
The backtracking approach is efficient for Sudoku as it systematically explores the possible configurations, quickly pruning the search space by undoing choices that lead to no solution (backtracking), thus finding a solution or proving none exists.