PadLocking

Padlocking Problem – Brute Force Method

The padlocking problem is a simple real-life example that can be used to explain the Brute Force method of problem solving.

The problem is:

A combination padlock has several number dials. The correct combination is unknown. Find the combination that opens the lock by systematically trying all possible combinations.

For classroom teaching, we can use a small hypothetical 3-digit padlock.

---

1. Understanding the Problem

Suppose we have a padlock with 3 dials, and each dial contains digits from 0 to 9.

For example:

   Dial 1    Dial 2    Dial 3
     ↓         ↓         ↓
     0         0         0

Each dial has 10 possible values.

Therefore, the total number of possible combinations is:

$$10 \times 10 \times 10 = 10^3 = 1000$$

So there are 1,000 possible combinations, ranging from:

000
001
002
003
...
997
998
999

---

2. Brute Force Approach

We don't have any information about the correct combination.

Therefore, we simply try the combinations systematically, one after another.

For example:

000 → Not correct ✗
001 → Not correct ✗
002 → Not correct ✗
003 → Not correct ✗
   .
   .
   .
745 → Not correct ✗
746 → Correct ✓

If the correct combination is 746, the process stops when 746 is reached.

---

3. Step-by-Step Process

Step 1: Start with the First Combination

000

Check whether it opens the lock.

If it doesn't:

000 → ✗

Step 2: Try the Next Combination

001 → ✗
002 → ✗
003 → ✗

Continue systematically.

Step 3: Continue Until the Correct Combination

Suppose:

746 → ✓

The lock opens.

Therefore:

Solution = 746

---

4. Algorithm

We can express the brute-force solution as an algorithm:

Algorithm: Find the Padlock Combination

1. Start with 000.
2. Try the current combination.
3. If the lock opens:
       Stop.
4. Otherwise:
       Move to the next combination.
5. Repeat Steps 2–4 until the lock opens.

---

5. Flow of the Solution

              Start
                ↓
          Try combination
                ↓
          Does it work?
           ↙          ↘
         Yes           No
          ↓             ↓
        Stop       Try next combination
                        ↓
                        └───────┐
                                ↓
                         Check again

This continues until the correct combination is found.

---

6. Why Is This Called Brute Force?

The method does not use:

• clues,
• shortcuts,
• patterns,
• previous knowledge,
• intelligent guesses.

It simply does:

“Try every possible combination until one works.”

Therefore, it is called Brute Force.

---

7. Best Case and Worst Case

The number of attempts depends on where the correct combination occurs.

Best Case

If the combination is:

000

then only 1 attempt is required.

Worst Case

If the combination is:

999

then 1,000 attempts may be required.

Average Case

If all combinations are equally likely, the average number of attempts is approximately:

$$\frac{1000+1}{2}=500.5$$

So roughly 500 attempts on average.

---

8. Why Does the Problem Become Difficult?

Consider increasing the number of dials.

Number of dials	Possible combinations
1	$10$
2	$10^2 = 100$
3	$10^3 = 1,000$
4	$10^4 = 10,000$
5	$10^5 = 100,000$
6	$10^6 = 1,000,000$

This demonstrates an important principle of algorithmic thinking:

As the problem size increases, the number of possibilities can increase very rapidly.

---

9. What Students Should Learn from This Example

The padlock example is not really about locks. It is about understanding the algorithmic concept of exhaustive search.

Students should recognize:

Problem
   ↓
Identify all possible solutions
   ↓
Try one solution
   ↓
Check it
   ↓
If incorrect → Try next
   ↓
Continue systematically
   ↓
Find solution

The key lesson

Brute Force solves a problem by examining possible solutions systematically rather than trying to find a shortcut.

Python Program for padlock guessing - bruteforce method

import itertools

# The actual combination we want to guess

correct_combination = (4, 7, 6)

# Define the range of digits for each dial (0-9)

digits = range(10)

# Function to perform brute force guessing of the padlock combination
def brute_force_padlock_guess(correct_combination):
    # Generate all possible combinations for a 3-dial padlock

    for combination in itertools.product(digits, repeat=len(correct_combination)):
        print(f"Trying combination: {combination}")
        if combination == correct_combination:
            print(f"Padlock opened with combination: {combination}")
            return combination

    print("Combination not found")
    return None

# Call the brute force function
guessed_combination = brute_force_padlock_guess(correct_combination)