# Understanding Backtracking Through a Tetris Optimizer in Go

When I first heard the term backtracking, it sounded like a complicated algorithm reserved for computer scientists. After spending the last couple of weeks learning it and implementing it in a Tetris Optimizer project, I realized something surprising:

Backtracking is simply the art of making a decision, checking whether it works, and if it doesn't, undoing it and trying something else.

This article explains backtracking using a practical project instead of abstract examples.

---

The Problem

Imagine you have several Tetris pieces (tetrominoes), and your goal is to fit all of them into the smallest possible square.

It might look something like this:

A A
A A

B B B
  B

C C C C

D
D
D D

The challenge is to arrange every piece so that:

• No pieces overlap.
• No piece extends outside the board.
• Every piece is used exactly once.
• The board is as small as possible.

This is much harder than it looks.

---

My First Thought

Initially, I thought I could simply place one piece after another.

Place A
Place B
Place C
Place D
Done!

Unfortunately, programming isn't always that kind.

Sometimes the first position you choose for piece A makes it impossible to place D later.

The mistake wasn't with D.

The mistake happened much earlier.

---

Enter Backtracking

Backtracking works like this:

1. Place a piece.
2. Try placing the next one.
3. If you get stuck...
4. Remove the last piece.
5. Try a different position.
6. Repeat until every piece fits.

It's essentially saying:

"If this path doesn't work, let's go back and explore another one."

---

Visualizing the Search

Suppose we have four tetrominoes.

Start

 ├── Put A at (0,0)
 │      ├── Put B
 │      │      ├── Put C
 │      │      │      ├── D fits ✅
 │      │      │      └── D fails ❌
 │      │      └── Try another position
 │      └── Move A elsewhere
 └── Try another position for A

Every branch represents another possibility.

Backtracking explores these branches until it finds one that works.

---

How It Looks in Go

The heart of the algorithm is surprisingly small.

func solve(index int) bool {

    if index == len(pieces) {
        return true
    }

    for every position {

        if piece fits {

            place(piece)

            if solve(index + 1) {
                return true
            }

            remove(piece)
        }
    }

    return false
}

Everything revolves around four actions:

• Check if the piece fits.
• Place it.
• Continue recursively.
• Remove it if necessary.

That final step—removing the piece—is what gives backtracking its name.

---

Why Remove the Piece?

Imagine solving a maze.

You choose the left path.

After walking for a while, you reach a dead end.

Do you stay there forever?

No.

You walk back to the last intersection and try another direction.

Your algorithm does exactly the same thing.

Place piece

↓

Dead end

↓

Remove piece

↓

Try another location

---

The Biggest Lesson I Learned

The code wasn't the difficult part.

The difficult part was learning how recursive calls think.

Once I stopped imagining recursion as "functions calling functions" and started imagining it as exploring a decision tree, everything became much clearer.

Drawing recursion trees on paper helped me understand why the algorithm behaved the way it did.

---

Why This Isn't Brute Force

Many people assume backtracking is just brute force.

Not quite.

Brute force explores every possibility.

Backtracking stops exploring a path the moment it knows that path cannot succeed.

For example:

Can piece C fit?

No.

Don't continue.

Go back immediately.

That early rejection saves an enormous amount of work.

---

Making the Solver Faster

My Tetris Optimizer taught me that backtracking alone isn't enough.

Several improvements can dramatically reduce runtime:

• Start with the smallest possible board.
• Place the most restrictive pieces first.
• Skip positions where a piece obviously cannot fit.
• Stop searching as soon as a valid arrangement is found.
• Avoid repeating board states you've already explored.

Small optimizations can turn a solver that runs for minutes into one that finishes in seconds.

---

What I Took Away

Learning backtracking changed how I think about programming.

It taught me that solving complex problems doesn't always require knowing the answer immediately.

Instead, it requires having the confidence to:

• Make a decision.
• Test it.
• Admit when it doesn't work.
• Undo it.
• Try again.

That lesson applies far beyond algorithms.

Sometimes the fastest path to a solution begins with the willingness to step back.

---

Final Thoughts

If you're currently learning recursion or backtracking, don't get discouraged if it feels confusing at first.

Almost everyone struggles with it initially because the challenge isn't writing the code—it's changing the way you think about problem-solving.

Once that mental shift happens, backtracking becomes one of the most elegant techniques you'll ever use.

Happy coding!