CO2412 Computational Thinking Contents
Lecture 5 - Greedy Branch Bound
Lecture 6 - Recursive Backtacking.pdf
Backtracking involves building a solution incrementally (one piece at a time) which discards solutions that fail to satify the problems constraints.
In the worst case still O(n2) but best and average cases may be significantly better.
If a node only leads to failure go back to its "parent" node and try other alternatives. In the event all of these result in failure then even further backtracking may be necessary to find the most optimal with best success result.
Sudoku is a logic-based number placement puzzle with the following rules:
- Played on a 9x9 matrix, divided into mini matrices (3x3 sub-grids).
- Each row, column, and sub-grid must contain the numbers 1β9 exactly once.
- Duplicate numbers and values outside the range 1β9 are not allowed.
The Goal of Sudoku is that each row, each column, and each mini matrix must contain the numbers between 1 and 9 once each.
Duplicates are not allowed and only the values between 1 and 9 can be placed within each mini matrix.
A brute algorithm is simple but a general approach.
Try all combinations until finding one that works. While not a clever approach computer's are fast.
When the search results in a dead end, it backs up to the previous cell it was trying to fill and goes onto the next digit.
Backing up to the cell with a 9 and that turns out to be a dead end, as well so backup again.
Now the cell with the 8, trying again and 9 and move forward again.
Note: The algorithm needs to be aware of what digit to attempt next.
Problems such as Sudoku can be solved by using recursive backtracking.
The reason behind recursion being utilised here is due to the fact, that later versions of the problem are the same as the original problem and the reason for backtracking entirely is to test and approach different alternative solutions.
Place n
queens on a chessboard so that No Queen can attack another.
1) Start in the leftmost column
2) If all queens are placed then return true
The third step involves trying all the rows in the current column for the following:
a) If the queen can be placed safely in this row then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution.
b) If placing the queen in [row, column] leads to a solution then return true.
c) If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other rows.
Can be represented as a 2D array.
Lecture 7 - Binary Search Trees & Heaps