What is backtracking?

Backtracking is a brute-force approach that finds all possible solution. What is brute-force? Brute-force exhaustively analyze the input and constraints to find a specific solution. Basically, backtracking is find the way of your way through a cornfield maze.

How does it relate to a maze in 4 steps?

1. Enter the cornfield
2. Take a path. Ex. Left, right
3. if Dead end, trace back aka "backtrack" to the intersection and explore another path.
4. Repeat steps 2 and 3 until you find exit.

Explanation

The maze in essence is related to backtracking because we traced back one step and made a different turn to find another possible solution.

More notes about backtracking

1. Represented in a State-Space Tree
2. Bounding function is used to add constraints to find the desired solutions. Note: We can have more than one solution in backtracking.
3. DFS!!!! [DFS = forms a root to child "path" by "path"]

More notes about brute-force

1. DP is a brute-force approach that finds the maximum or minimum optimal solution.
2. Branch and Bound is also a brute-force approach that is BFS[form the tree level by level].

Challenge: Solve the n-queen problem

Background

Queen is most valuable piece on the board...actually, the king is most valuable because if you don't have a king, you lose. The queen is the 2nd most valuable piece on the chess board. This piece is able to move diagonally, horizontally, and vertically. Your job is to place 7 queens on a chess board where each queen does not pose any threat to each other.
I have solved this challenge in 10 minutes. Can you beat it?

Steps

1. Navigate to the link below and have fun: Click on me [https://www.chess.com/analysis]
2. Click on 'Setup' and 'Trashcan' icon
3. Have fun!

My Solution

Reference:
Introduction to Backtracking [https://www.youtube.com/watch?v=DKCbsiDBN6c]