CO2412: Computational Thinking
Lecture 8
Backtracking
1. Introduction to Backtracking
o Backtracking is a problem-solving approach that builds solutions
one piece at a time and discards those that do not meet the
problem's constraints.
o In the worst case, the time complexity may be O(n²), but the best
and average cases are often significantly better.
o Backtracking is often implemented recursively, referred to as
recursive backtracking.
Simple Backtracking - A Walkthrough
1. Problem Space Representation
o The problem space consists of states (nodes) and actions (paths
leading to new states). When in a node, you can only see paths to
connected nodes.
o If a node leads to failure, the algorithm backtracks to its "parent"
node and tries other alternatives. If all alternatives lead to failure,
further backtracking is necessary.
Example: Sudoku Problem
1. Sudoku Problem Definition
o Sudoku is a 9x9 grid with some numbers pre-filled. The goal is to
fill the grid so that each row, column, and 3x3 mini-grid contains all
digits from 1 to 9 without repetition.
2. Brute Force Approach to Sudoku
o The brute force approach tries all possible combinations until it
finds one that works. This method is not sophisticated but can be
effective due to the computational speed of modern computers.
Steps in the Brute Force Approach:
o If no open cells are left, the puzzle is solved.
o Scan the grid from left to right, top to bottom, for the first open cell.
o Cycle through digits 1 to 9 and place them in the cell if the setup
remains legal.
Lecture 8
Backtracking
1. Introduction to Backtracking
o Backtracking is a problem-solving approach that builds solutions
one piece at a time and discards those that do not meet the
problem's constraints.
o In the worst case, the time complexity may be O(n²), but the best
and average cases are often significantly better.
o Backtracking is often implemented recursively, referred to as
recursive backtracking.
Simple Backtracking - A Walkthrough
1. Problem Space Representation
o The problem space consists of states (nodes) and actions (paths
leading to new states). When in a node, you can only see paths to
connected nodes.
o If a node leads to failure, the algorithm backtracks to its "parent"
node and tries other alternatives. If all alternatives lead to failure,
further backtracking is necessary.
Example: Sudoku Problem
1. Sudoku Problem Definition
o Sudoku is a 9x9 grid with some numbers pre-filled. The goal is to
fill the grid so that each row, column, and 3x3 mini-grid contains all
digits from 1 to 9 without repetition.
2. Brute Force Approach to Sudoku
o The brute force approach tries all possible combinations until it
finds one that works. This method is not sophisticated but can be
effective due to the computational speed of modern computers.
Steps in the Brute Force Approach:
o If no open cells are left, the puzzle is solved.
o Scan the grid from left to right, top to bottom, for the first open cell.
o Cycle through digits 1 to 9 and place them in the cell if the setup
remains legal.
