Skip to content
CCC Python Course

Backtracking search with pruning

Stage
4
Module
M4.10
Lessons
1

In this module

  • Explore all possibilities using recursion and backtrack when a path fails.
  • Prune search branches early to avoid exploring impossible solutions.
  • Recognize problems that fit the backtracking pattern.
  • Handle recursion depth limits with iterative approaches.

Before this module

M1.14Recursion fundamentalsM2.5Brute force and complete search

Lessons

  1. 1Backtracking search with pruning

Practice

Try this on the judge. The link opens the problem on DMOJ.

  1. 2019 J5
    Rule of Three (opens on DMOJ in a new tab) DMOJ

    Search for a valid configuration with constraints, backtracking out of dead ends.