Swift Program to Solve the N-Queens Problem using Recursion

Swift – Solve the N-Queens Problem using Recursion

In this tutorial, we will learn how to solve the N-Queens problem using recursion in Swift. We will understand the problem, write an algorithm to solve it, and implement it step by step with a complete Swift program and output.

---

What is the N-Queens Problem?

The N-Queens problem is a classic backtracking problem in which the goal is to place N queens on an N × N chessboard such that no two queens threaten each other. This means:

• No two queens can be in the same row.
• No two queens can be in the same column.
• No two queens can be on the same diagonal.

The problem can be solved using recursion and backtracking, exploring all possible configurations until valid solutions are found.

---

Algorithm to Solve N-Queens Problem

1. Create a board of size N × N initialized with 0.
2. Define a recursive function solve to place queens row by row:
3. Base Case: If all queens are placed, save the configuration as a solution.
4. Recursive Case:
   1. Try placing a queen in each column of the current row.
   2. Check if placing the queen is safe (no threats from other queens).
   3. If safe, place the queen and recursively solve for the next row.
   4. If placing the queen leads to a conflict, backtrack and try the next column.

This approach ensures that all possible configurations are explored systematically.

---

Step-by-Step Implementation in Swift

1. Create the Board

Define a 2D array to represent the chessboard, initialized with zeros:

var board = [[Int]]()

func initializeBoard(_ n: Int) {
    board = Array(repeating: Array(repeating: 0, count: n), count: n)
}

2. Check if Placing a Queen is Safe

Define a function to check if placing a queen at a given row and column is safe:

func isSafe(_ row: Int, _ col: Int, _ n: Int) -> Bool {
    // Check column
    for i in 0..<row {
        if board[i][col] == 1 {
            return false
        }
    }
    // Check upper left diagonal
    var i = row, j = col
    while i >= 0 && j >= 0 {
        if board[i][j] == 1 {
            return false
        }
        i -= 1
        j -= 1
    }
    // Check upper right diagonal
    i = row
    j = col
    while i >= 0 && j < n {
        if board[i][j] == 1 {
            return false
        }
        i -= 1
        j += 1
    }
    return true
}

3. Solve the Problem Recursively

Implement the recursive function to place queens row by row:

func solve(_ row: Int, _ n: Int, _ solutions: inout [[[Int]]]) {
    if row == n {
        solutions.append(board) // Base case: Save the solution
        return
    }
    for col in 0..<n {
        if isSafe(row, col, n) {
            board[row][col] = 1 // Place the queen
            solve(row + 1, n, &solutions) // Recur for the next row
            board[row][col] = 0 // Backtrack
        }
    }
}

4. Collect and Display All Solutions

Wrap the solution in a function that initializes the board, solves the problem, and prints all solutions:

func nQueens(_ n: Int) -> [[[Int]]] {
    var solutions = [[[Int]]]()
    initializeBoard(n)
    solve(0, n, &solutions)
    return solutions
}

Complete Swift Program

Here’s the complete Swift program:

import Foundation

var board = [[Int]]()

// Initialize the board
func initializeBoard(_ n: Int) {
    board = Array(repeating: Array(repeating: 0, count: n), count: n)
}

// Check if placing a queen is safe
func isSafe(_ row: Int, _ col: Int, _ n: Int) -> Bool {
    // Check column
    for i in 0..<row {
        if board[i][col] == 1 {
            return false
        }
    }
    // Check upper left diagonal
    var i = row, j = col
    while i >= 0 && j >= 0 {
        if board[i][j] == 1 {
            return false
        }
        i -= 1
        j -= 1
    }
    // Check upper right diagonal
    i = row
    j = col
    while i >= 0 && j < n {
        if board[i][j] == 1 {
            return false
        }
        i -= 1
        j += 1
    }
    return true
}

// Recursive function to solve the N-Queens problem
func solve(_ row: Int, _ n: Int, _ solutions: inout [[[Int]]]) {
    if row == n {
        solutions.append(board) // Base case: Save the solution
        return
    }
    for col in 0..<n {
        if isSafe(row, col, n) {
            board[row][col] = 1 // Place the queen
            solve(row + 1, n, &solutions) // Recur for the next row
            board[row][col] = 0 // Backtrack
        }
    }
}

// Function to solve N-Queens and return all solutions
func nQueens(_ n: Int) -> [[[Int]]] {
    var solutions = [[[Int]]]()
    initializeBoard(n)
    solve(0, n, &solutions)
    return solutions
}

// Test for N = 4
let solutions = nQueens(4)
for solution in solutions {
    print("Solution:")
    for row in solution {
        print(row)
    }
    print()
}

Output:

Solution:
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]

Solution:
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]

Program ended with exit code: 0

Xcode Screenshot: