Swift, Recursion and the Recursive Sense

Understanding recursion and recursive thinking in Swift programming

Written by

Traveller

in

✍️ Note

Some codes are sourced from Loony Corn’s Udemy Course (https://www.udemy.com/user/janani-ravi-2/). This post is for personal notes where I summarize the original contents to grasp the key concepts

Warming up, Recursive sense

Iterative solutions involve loops

Recursive solutions involve function that call themselves

A recursively written function takes in input, splits that input into smaller parts. Then calls itself on the smaller parts and re-combines the outputs

If the inputs to the function are too simple to split further, the recursive function will return a simple output (and not call itself)

Base case of the recursion (It prevents the recursion from going on forever)

This special case for simple inputs is called

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463332#content

Reverse String

screenshot 2024 03 24 at 10.42.45e280afam
func reverseStringIteratively(input: String) -> String {
    if input.count == 1 || input.isEmpty {
        return input
    }
    var inputArray = Array(input)
    for i in 0..<input.count {
        let firstIndex = i
        let lastIndex = (input.count - 1) - i
        
        if firstIndex == lastIndex {
            break
        }
        inputArray.swapAt(firstIndex, lastIndex)
    }
    return String(inputArray)
}
reverseStringIteratively(input: "2AB") //BA2

Recursion approach

screenshot 2024 03 24 at 10.48.50e280afam
func reverseStringRecursively(input: String) -> String {
    //Base case
    if input.count == 1 || input.isEmpty {
        return input
    }
    var inputArray = Array(input)
    let first = inputArray.removeFirst()
    let reversedString = reverseStringRecursively(input: String(inputArray))
    return reversedString + String(first)
}
reverseStringRecursively(input: "2AB") //BA2

Exercise 1. Binary Search

Choose an element in at the mid point of a sorted list

Check whether it’s smaller than or greater than the element you are looking for

If the element at the mid point is larger than the element you are searching for

Reduce your search area to the portion where the element might be present

Base case

  • There is no part of the list to search and the element has not been found
  • The search element has been found at the mid point of the portion we’re searching

Recursive case

  • Binary search smaller portions of the list where the element might be found

Summary

  • By halving the search area at every step, binary search works much fatser than linear search
  • The complexity of binary search is O(logN)
  • The Iterative approach to binary search might perform better than the recursive approach in terms of space complexity. There is not recursive stack in the iterative approach, which means we save on some space.
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463334#content

Example 1. No boundary, Assumed that You will search entire input ranges

let input = Array(0...10000)
/// Return : Index
func binarySearch(input: [Int], search: Int) -> Int {
    if input.isEmpty {
        return -1
    }
    let midPoint = (input.count - 1) / 2
    if input[midPoint] == search {
        return input[midPoint]
    }
    if search > input[midPoint] {
        return binarySearch(input: Array(input[midPoint..<input.count]), search: search)
    }
    else {
        return binarySearch(input: Array(input[0..<midPoint]), search: search)
    }
}
let searchedItem = binarySearch(input: input, search: 2859)

Example 2. Boundary search

let input = Array(0...10000)
/// Return : Index
/// min, max: Search Area in Input
func binarySearch(input: [Int], search: Int, min: Int, max: Int) -> Int {
    //If the indices have crossed one another at the center, the term is not present in the array, return -1, base case of the recursion
    if min > max {
        return -1
    }
    let midPoint = min + (max - min) / 2
    if input[midPoint] == search {
        return input[midPoint]
    }
    //Call binary search on a smaller portion of the array depending on whether the element might be found in the first or second half of the list
    if search > input[midPoint] {
        return binarySearch(input: input, search: search, min: midPoint + 1, max: max)
    }
    else {
        return binarySearch(input: input, search: search, min: min, max: midPoint - 1)
    }
}
let searchedItem = binarySearch(input: input, search: 2859, min: 2800, max: 2900)
print(searchedItem)

Exercise 2. Find all subsets of a given set

Example, {1, 2, 3, 4}

  • There are 2^4 subsets of this set, If we have a set of N elements the number of subsets will be 2^N
  • At subsets, order is not important!

Recursive mind (Find a pattern!)

  • Break this down, 1 element {1} -> subsets are {}, {1}
  • 2 elements {1, 2} -> subsets are {}, {1}, {2}, {1, 2}
  • 3 elements {1, 2, 3} -> subsets are {}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463346#content
func findAllSubSets(input: [Int]) -> [[Int]] {
    //Base case, Break the Recursive
    if input.isEmpty {
        return [[]]
    }
    if input.count == 1 {
        return [[], [input.first!]]
    }
    
    var inputArray = input
    
    //Recursive case
    let currentItem = inputArray.removeFirst()
    //Reduce the inputArray at every step by removeFirst
    var subsets = findAllSubSets(input: inputArray)
    
    var currentSubSets = [[Int]]()
    
    for subset in subsets {
        var temp = subset
        //Subset's items order can be ignored
        temp.insert(currentItem, at: 0)
        currentSubSets.append(temp)
    }
    for currentSubSet in currentSubSets {
        subsets.append(currentSubSet)
    }
    return subsets
}
let subsets = findAllSubSets(input: [1, 2, 3, 4])
print(subsets)
//Prints
[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4]]
Program ended with exit code: 0
screenshot 2024 03 25 at 11.36.21e280afam

Let’s take a look How to make subsets

screenshot 2024 03 25 at 11.54.23e280afam

Create the subsets of very small sets first

The for every subset, add a new element in to create newer subsets

Repeat till all elements from the original set have been used

Base Case

  • When the original set is empty, only the empty set is it’s subset

Recursive Case

  • Add the elements to the existing subsets to create new subsets

Since there are 2^N Subsets the complexity of this Code is O(2^N) -> This cannot be reduced further

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463346#content

Exercise 3. Find whether 2 binary trees are exactly the same

A binary tree is one where every node can have a maximum of two children – A left child and right child

Two binary trees are the same if

  • Every corresponding node has the same value
  • The structure of the tree at every corresponding node is the same

Base case

  • A null current node on one tree should correspond to a null in the other tree
  • Node values should be the same at every node

Recursive case

  • Check that the sub-tree rooted at every node is the same

Time Complexity

  • We have to visit every node in both trees so 2N nodes, the complexity is O(N)
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463352#content
screenshot 2024 03 25 at 2.20.11e280afpm
class Tree {
    let value: String
    var left: Tree?
    var right: Tree?
    
    init(value: String, left: Tree? = nil, right: Tree? = nil) {
        self.value = value
        self.left = left
        self.right = right
    }
}
let treeA = Tree(value: "a")
treeA.left = Tree(value: "b")
treeA.right = Tree(value: "c")
treeA.left?.left = Tree(value: "d")
treeA.left?.right = Tree(value: "e")
treeA.right?.right = Tree(value: "f")
treeA.right?.right?.right = Tree(value: "g")
let treeB = Tree(value: "a")
treeB.left = Tree(value: "b")
treeB.right = Tree(value: "c")
treeB.left?.left = Tree(value: "d")
treeB.left?.right = Tree(value: "e")
treeB.right?.right = Tree(value: "f")
treeB.right?.right?.right = Tree(value: "g")
func isSameTree(_ a: Tree?, _ b: Tree?) -> Bool {
    //Base case
    if a?.left == nil, a?.right == nil, b?.left == nil, b?.right == nil, a?.value == b?.value {
        return true
    }
    if a?.value == b?.value {
        return isSameTree(a?.left, b?.left) && isSameTree(a?.right, b?.right)
    }
    return false
}
let isSame = isSameTree(treeA, treeB)
print(isSame) //True

Exercise 4. Build a car given all tasks and each task’s dependencies

Tip (It’s the same, How OperationQueue works, see my post)

  • Set up the data structure that you plan to use to store a tasks and it’s dependencies
  • Dependencies of Task “A” are all tasks which should be complete before “A” can execute.
    • Paint a car, depends on build chassis of the car, The chassis needs to be ready before it can be painted
  • The method should take in a list of all tasks which are needed to build a car along with their dependencies and execute every task in order to build the car
    • The tasks are in any order, It’s up to you to determine some order in which it can be executed.

Tasks and dependencies

  • Tasks are A, B, C, D, E, F, G, H
    • B depends on A
    • D depends on E
    • C depends on A, B, D
    • F depends on C
  • An acceptable order of performing the tasks are
    • E-> D -> A -> B -> C -> F
    • or A -> E -> B -> D -> C -> F
    • and more

Remember

  • Remember that you can’t execute a task unless it’s dependencies have completed
  • Store the dependencies such that they are easily accessible from a task
  • Recursively execute the dependencies till you get to the task

Base case

  • The current task has been executed, it’s marked done

Recursive case

  • Execute dependencies before coming to the current task

Notes

  • The tasks and it’s dependencies form a directed acyclic graph
  • The graph may not be fully connected, I.E. certain tasks stand completely alone.
  • It’s a topological sort.
  • We have to visit every task to execute it, the complexity is O(N), where N is the number of tasks.
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463360#content

Example 1. Recursively run a tasks

class TaskQueue {
    let value: String
    var dependsOn = [TaskQueue]()
    var isFinished = false
    
    init(value: String) {
        self.value = value
    }
}
let taskA = TaskQueue(value: "A")
let taskB = TaskQueue(value: "B")
let taskC = TaskQueue(value: "C")
let taskD = TaskQueue(value: "D")
let taskE = TaskQueue(value: "E")
let taskF = TaskQueue(value: "F")
let taskG = TaskQueue(value: "G")
let taskH = TaskQueue(value: "H")
taskB.dependsOn = [taskA]
taskD.dependsOn = [taskE]
taskC.dependsOn = [taskA, taskB, taskD]
taskF.dependsOn = [taskC]
func buildCar(_ tasks: [TaskQueue]) {
    //Base case
    if tasks.isEmpty {
        return
    }
    var remainingTasks = tasks
    let dequeue = remainingTasks.removeFirst()
    if dequeue.isFinished {
        return buildCar(remainingTasks)
    }
    
    //[a, b, c]
    // a: finish return
    
    //Recursive case
    let dependsOnUnfinishedTasks = dequeue.dependsOn.filter { $0.isFinished == false }
    
    if !dependsOnUnfinishedTasks.isEmpty {
        buildCar(dependsOnUnfinishedTasks)
    }
    dequeue.isFinished = true
    print("\(dequeue.value)", terminator: "->")
    return buildCar(remainingTasks)
}
buildCar([taskA, taskB, taskC, taskD, taskE, taskF, taskG, taskH])
//Prints
A->B->E->D->C->F->G->H

Example 2. Simplify version

class TaskQueue {
    let value: String
    var dependsOn = [TaskQueue]()
    var isFinished = false
    
    init(value: String) {
        self.value = value
    }
    
    func run() {
        if isFinished {
            return
        }
        //Before run, recursively call run on all the dependencies of this task
        for task in dependsOn {
            task.run()
        }
        isFinished = true
        print("Completed task: \(value)")
    }
}
let taskA = TaskQueue(value: "A")
let taskB = TaskQueue(value: "B")
let taskC = TaskQueue(value: "C")
let taskD = TaskQueue(value: "D")
let taskE = TaskQueue(value: "E")
let taskF = TaskQueue(value: "F")
let taskG = TaskQueue(value: "G")
let taskH = TaskQueue(value: "H")
taskB.dependsOn = [taskA]
taskD.dependsOn = [taskE]
taskC.dependsOn = [taskA, taskB, taskD]
taskF.dependsOn = [taskC]
func runTask(_ tasks: [TaskQueue]) {
    for task in tasks {
        task.run()
    }
}
runTask([taskA, taskB, taskC, taskD, taskE, taskF, taskG, taskH])
//Prints
Completed task: A
Completed task: B
Completed task: E
Completed task: D
Completed task: C
Completed task: F
Completed task: G
Completed task: H

Exercise 5. Generate anagrams of a Word

Anagrams

  • A word have all the same letters of the word itself in a different order
  • Consider that the letters in the word passed in are unique and that there are no spaces. I.E. It’s a word not a sentence
  • The anagram need not be a valid word, we just want all the permutations of the letters.
  • If all letters are unique then there are N! anagrams.

Example

  • “ROAD” -> 4! Anagrams
    • “ROAD”, “ORAD”, “OARD”, “RDOA”, “RAOD”, …more!

Hint

  • Basic idea is the same as finding a all subsets from given a string

Break this down! (Finding a patterns!)

  • Consider a word of 1 letter “A” -> Anagrams are “A”
  • Consider a word of 2 letters “AB” -> Anagrams are “AB“, “BA”
  • Consider a word of 3 letters “ABC” -> Anagrams are “CAB”, “ACB”, “ABC“, “CBA”, “BCA”, “BAC“

Break the word into smaller and smaller words, till we find the anagram of the smallest word.

To the smaller anagrams add in letter by letter at every possible positions

Recursively do this till we get all the letters in at every position

Base case

  • The anagram of an empty string is an empty string
  • The smallest word of one letter is the anagram itself

Recursive case

  • Find anagrams of smaller words by removing letters from the original word
  • Add the letters back one by one to every position

Complexity

  • The number of anagrams for a word with unique letter is N! which means the complexity of this algorithm is also O(N!)
  • This cannot be further optimized
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463362#content
screenshot 2024 03 25 at 4.29.31e280afpm
func generateAnagrams(input: String) -> [String] {
    //Base case
    if input.count <= 1 {
        return [input]
    }
    var inputString = input
    let currentLetter = inputString.removeFirst()
    var anagram = generateAnagrams(input: inputString)
    
    var newAnagrams = [String]()
    for (index, word) in anagram.enumerated() {
        let wordCount = word.count
        for i in 0...wordCount {
            var tempWord = anagram[index]
            tempWord.insert(currentLetter, at: tempWord.index(tempWord.startIndex, offsetBy: i))
            newAnagrams.append(tempWord)
        }
    }
    return newAnagrams
}
let anagrams = generateAnagrams(input: "ABC")
print(anagrams)
//Prints
["ABC", "BAC", "BCA", "ACB", "CAB", "CBA"]
screenshot 2024 03 25 at 4.55.15e280afpm

Exercise 6. Implement the paint fill feature from MS Paint

Paint starts from one pixel where you click and moves outwards

All adjoining pixels with the same original color get the color fill with the new color

The color fill moves outwards till it reaches a boundary which has a different color

https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463358#content
screenshot 2024 03 24 at 11.16.57e280afam

Start with one pixel which has some original color

Move outwards, If the neighboring pixels have the same original color, color them as well

Repeat till the borders are reached

What is the base case?

  • The current pixel does not have the same original color, so represents a border
  • The current pixel is beyond the screen boundaries

What is the recursive case?

  • Move outward from the start pixel coloring individual pixels
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463358#content
var screen: [[Int]] = [
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 2, 0, 0, 0, 0, 0],
[0, 0, 1, 2, 2, 2, 0, 0, 0, 0],
[0, 0, 1, 2, 2, 2, 2, 0, 3, 3],
[0, 0, 1, 1, 1, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 3, 0],
[0, 0, 0, 5, 0, 0, 0, 0, 3, 0],
[0, 0, 5, 5, 0, 0, 0, 0, 3, 0],
[0, 5, 5, 5, 0, 0, 0, 0, 3, 0]
]
func paintFill(screen: inout [[Int]], x: Int, y: Int, originalColor: Int, newColor: Int) {
    //Base Case
    let width = screen.first?.count ?? 0
    let height = screen.count
    //Boundary check
    if x < 0 || x > (width - 1) {
        return
    }
    if y < 0 || y > (height - 1) {
        return
    }
    //Important! y is row, x is column
    let currentColor = screen[y][x]
    if currentColor != originalColor {
        return
    }
    
    //Paint it
    screen[y][x] = newColor
    
    //Fill neighbors pixels too
    //Up, Y is Row
    paintFill(screen: &screen, x: x, y: y-1, originalColor: originalColor, newColor: newColor)
    //Down, Y is Row
    paintFill(screen: &screen, x: x, y: y+1, originalColor: originalColor, newColor: newColor)
    //Left, X is Column
    paintFill(screen: &screen, x: x - 1, y: y, originalColor: originalColor, newColor: newColor)
    //Right, X is Column
    paintFill(screen: &screen, x: x + 1, y: y, originalColor: originalColor, newColor: newColor)
}
paintFill(screen: &screen, x: 4, y: 3, originalColor: 2, newColor: 9)
print("2 -> 9\n")
printBoard(screen)
//Results
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 9, 0, 0, 0, 0, 0],
[0, 0, 1, 9, 9, 9, 0, 0, 0, 0],
[0, 0, 1, 9, 9, 9, 9, 0, 3, 3],
[0, 0, 1, 1, 1, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 3, 0],
[0, 0, 0, 5, 0, 0, 0, 0, 3, 0],
[0, 0, 5, 5, 0, 0, 0, 0, 3, 0],
[0, 5, 5, 5, 0, 0, 0, 0, 3, 0]
screenshot 2024 03 24 at 12.11.23e280afpm

Exercise 7. Find a path a rat can travel through a maze

💡 Hint: Backtracking

Game Rule

  • Assume the maze is made up of cells with 4 walls. Each wall can have a door
  • All walls do not have a door, only some do
  • The rat has been placed in one of the cells, It has to make It’s way to a cell which is the “End” cell
  • The rat should not go through the same cell twice while finding a path

Base case

  • The rat has reached the end cell

Recursive case

  • Keep visiting cells by passing through doors when they exist
  • Do not visit cells if they are present in the current path, we don’t want the rat to move in circles
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463368#content
screenshot 2024 03 24 at 3.05.55e280afpm

Solution 1. Using 2D Array

var maze: [[String]] = [
[" ", "G", "H", "I"],
["D", "E", "F", " "],
["A", "B", "C", " "]
]
//l: left, u: up, r: right, d: down
let door: [String: [String]] = [
    "D":["l", "u", "r"],
    "A": ["l", "d"],
    "B": ["d"],
    "C": ["d", "l", "u"],
    "E": ["l"],
    "F": ["d", "r"],
    "G": ["l", "u"],
    "H": ["u"],
    "I": ["u", "r", "d"]
]
//Path: Keep track of the current path, The rat has traversed
func findPath(maze: [[String]], currentX: Int, currentY: Int, endX: Int, endY: Int, path: inout [String]) -> Bool {
    //Base case
    if maze.isEmpty {
        return false
    }
    let width = maze.first?.count ?? 0
    let height = maze.count
    
    if currentX < 0, currentX >= width {
        return false
    }
    if currentY < 0, currentY >= height {
        return false
    }
    if endX < 0, endX >= width {
        return false
    }
    if endY < 0, endY >= height {
        return false
    }
    //X is column, Y is row, start X, Y means rabit's current position
    let cellValue = maze[currentY][currentX]
    if cellValue == " " {
        return false
    }
    //Set visited
    path.append(cellValue)
    
    //Reached the destination
    if currentX == endX, currentY == endY {
        return true
    }
    
    let doors = door[cellValue]!
    let allDoors = Set(["l", "r", "u", "d"])
    let availableOpenedDoors = allDoors.subtracting(Set(doors))
    
//Check All available neighbors
    for direction in availableOpenedDoors {
        switch direction {
        case "l":
            let leftCellValue = maze[currentY][currentX - 1]
//Check If already visited or not
            if path.contains(leftCellValue) == false {
//Store current path
                var newPath = path
//Recursive call!
                if findPath(maze: maze, currentX: currentX - 1, currentY: currentY, endX: endX, endY: endY, path: &newPath) {
//It is very important
                    path.removeAll()
                    path.append(contentsOf: newPath)
                    return true
                }
            }
        case "r":
            let rightCellValue = maze[currentY][currentX + 1]
            if path.contains(rightCellValue) == false {
                var newPath = path
                if findPath(maze: maze, currentX: currentX + 1, currentY: currentY, endX: endX, endY: endY, path: &newPath) {
                    path.removeAll()
                    path.append(contentsOf: newPath)
                    return true
                }
            }
        case "u":
            let upCellValue = maze[currentY - 1][currentX]
            if path.contains(upCellValue) == false {
                var newPath = path
                if findPath(maze: maze, currentX: currentX, currentY: currentY - 1, endX: endX, endY: endY, path: &newPath) {
                    path.removeAll()
                    path.append(contentsOf: newPath)
                    return true
                }
            }
        case "d":
            let downCellValue = maze[currentY + 1][currentX]
            if path.contains(downCellValue) == false {
                var newPath = path
                if findPath(maze: maze, currentX: currentX, currentY: currentY + 1, endX: endX, endY: endY, path: &newPath) {
                    path.removeAll()
                    path.append(contentsOf: newPath)
                    return true
                }
            }
        default:
            break
        }
    }
    print("This cell is false: \(maze[currentY][currentX])")
    return false
}
var path = [String]()
let isFoundPath = findPath(maze: maze, currentX: 0, currentY: 1, endX: 3, endY: 0, path: &path)
print("\(isFoundPath) -> \(path)")
print("Finish")
//Prints Case 1
This is false: C
This is false: F
true -> ["D", "A", "B", "E", "G", "H", "I"]
Finish
//Prints Case 2
This cell is false: G
true -> ["D", "A", "B", "E", "F", "H", "I"]
Finish
Program ended with exit code: 0

Solution 2. Using Cell Class

class Cell {
    let id: String
    let isEnd: Bool
    var neighbors = [Cell]()
    
    init(id: String, isEnd: Bool) {
        self.id = id
        self.isEnd = isEnd
    }
}
let cellD = Cell(id: "D", isEnd: false)
let cellA = Cell(id: "A", isEnd: false)
let cellB = Cell(id: "B", isEnd: false)
let cellC = Cell(id: "C", isEnd: false)
let cellE = Cell(id: "E", isEnd: false)
let cellF = Cell(id: "F", isEnd: false)
let cellG = Cell(id: "G", isEnd: false)
let cellH = Cell(id: "H", isEnd: false)
let cellI = Cell(id: "I", isEnd: true)
cellD.neighbors = [cellA]
cellA.neighbors = [cellD, cellB]
cellB.neighbors = [cellA, cellC, cellE]
cellC.neighbors = [cellB]
cellE.neighbors = [cellG, cellF, cellB]
cellF.neighbors = [cellE, cellH]
cellH.neighbors = [cellG, cellF, cellI]
cellI.neighbors = [cellH]
func findPath(currentCell: Cell, path: inout [Cell]) -> Bool {
    path.append(currentCell)
    
    //Base case
    if currentCell.isEnd {
        return true
    }
    for neighborCell in currentCell.neighbors {
        if path.contains(where: { $0.id == neighborCell.id }) == false {
            var currentPath = path
            if findPath(currentCell: neighborCell, path: &currentPath) {
                path.removeAll()
                path.append(contentsOf: currentPath)
                return true
            }
        }
    }
    return false
}
var path = [Cell]()
let isFoundPath = findPath(currentCell: cellD, path: &path)
print("\(isFoundPath) -> \(path.compactMap { $0.id })")

Exercise 8. Place 8 Queens on a Chessboard so they don’t kill each other

Rules

  • Queens can move along their rows, columns and along both diagonals
  • Place one queen at a time, one on each row or one on each column
  • Remember to check at every step to see if the queen placed is safe, and if the remaining queens can be placed with that configuration

Solution

  • Place a queen in each row or column in a safe position
  • See if the remaining queens can be placed safely with the current position of the queen
  • Recursively do this till the right positions for all queens have been found
  • Place all 8 queens safety

Base case

  • The queens have been all placed and we’re beyond the boundary of the chessboard

Recursive case

  • Keep placing queens in different positions of the same row or column
  • Check whether the remaining queens can be successfully placed
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463370#content
screenshot 2024 03 24 at 5.08.13e280afpm
import Foundation
//https://github.com/ShawnBaek/Table
import Table
//0: Empty, 1: Queen
var chessBoard = Array(
    repeating: Array(repeating: 0, count: 8),
    count: 8
)
func isSafeOnLeftDiagonal(chess: [[Int]], row: Int, col: Int) -> Bool {
    var r = 0
    var c = 0
    
    //Find the initial position tracing the left diagonal from the first cell in the line of the placed queen
    if row > col {
        r = row - col
    }
    else {
        c = col - row
    }
    let columns = chess.first?.count ?? 0
    let rows = chess.count
    var numberOfQueen = 0
    while r < rows && c < columns {
        if chess[r][c] == 1 {
            numberOfQueen += 1
        }
        r += 1
        c += 1
    }
    return numberOfQueen <= 1
}
func isSafeOnRightDiagonal(chess: [[Int]], row: Int, col: Int) -> Bool {
    let columns = chess.first?.count ?? 0
    let rows = chess.count
    
    //Start position will be top right based on current position
    var r = 0
    var c = columns - 1
    var numberOfQueens = 0
    //Option 1. I suggest calculating it and checking the start position
    if (row + col < columns) {
        c = min(row + col, columns - 1)
    }
    else {
        r = (row + col) % (columns - 1)
    }
    
    while r < rows && c > 0 {
        if chess[r][c] == 1 {
            numberOfQueens += 1
        }
        r += 1
        c -= 1
    }
    return numberOfQueens <= 1
}
func isSafePosition(chess: [[Int]], row: Int, col: Int) -> Bool {
    let columns = chess.first?.count ?? 0
    let rows = chess.count
    //Edge case
    if col < 0 || col >= columns {
        return false
    }
    if row < 0 || row >= rows {
        return false
    }
    //Check horizontal
    for c in 0..<columns {
        //Found a Queen and It's not a current position of Queen
        if chess[row][c] == 1, c != col {
            return false
        }
    }
    //Check vertical
    for r in 0..<rows {
        if chess[r][col] == 1, r != row {
            return false
        }
    }
    
    //Check TopLeft -> DownRight Diagonal
    if !isSafeOnLeftDiagonal(chess: chess, row: row, col: col) {
        return false
    }
    
    if !isSafeOnRightDiagonal(chess: chess, row: row, col: col) {
        return false
    }
    return true
}
func placeQueen(
    chess: inout [[Int]],
    col: Int
) -> Bool {
    //Base case, Placed all Queens
    if col >= 8 {
        return true
    }
    for row in 0..<8 {
        //Place a Queen
        chess[row][col] = 1
        if isSafePosition(chess: chess, row: row, col: col) {
            if placeQueen(chess: &chess, col: col + 1) {
                return true
            }
        }
        //Remove Queen at this position
        chess[row][col] = 0
    }
    return false
}
let isPlacedAllQueens = placeQueen(chess: &chessBoard, col: 0)
print(table: chessBoard)
screenshot 2024 03 24 at 9.01.08e280afpm
screenshot 2024 03 24 at 9.02.39e280afpm
screenshot 2024 03 24 at 9.18.56e280afpm

Results

screenshot 2024 03 24 at 9.21.17e280afpm

Time Complexity is O(N!), We’re trying every possible position for the queens

Comments

Leave a Reply

More posts

Discover more from Shawn

Subscribe now to keep reading and get access to the full archive.

Continue reading