Brute force method would probably be the favorite algorithmic paradigm of every developer. The beauty of a brute force method is that it is pretty straightforward and if a solution to a problem exists, you are guaranteed to find it. This option is also the most exhaustive option as we might go through all the possibilities before arriving at the result.
What is Brute Force Method?
You might have heard the phrase “Brute force method to solve the problem”. What exactly do you mean by that? It simply means that try out all the alternatives until you are exhausted of options. If the problem is solvable, you will eventually find an answer.
Let us understand it with a very easy example. Suppose you have a locked folder that can be opened by a 5-digit lock code. You have no hint about the lock code, but you just want to see what is behind that lock, what would you do? You would start from 00000 and go all the way to 99999. If the lock is working correctly, one of the combination would definitely open the lock. Although it would take some time, but eventually you would be able to solve the problem.
What you just did was a Brute force solution. On the other hand, if you have hints about who owns the folder, or what date was the folder created, you may be able to try out some known combinations first. That could be an optimized approach. Similarly, for problem solving skills in computer science, if a solution to a problem exists, it guaranteed, that you will find it by a brute force method, i.e. applying all the possible combinations.
What do we mean by “if a solution exists”?
In the above example you may have noticed words like, “if the lock is working correctly” and “if a solution exists“. This statement is very essential when approaching any problem. Let us try to understand what do we mean by this.
QUESTION: Given a 3 * 3 grid, you need to fill in numbers from
1-9such that sum of all diagonals, rows and columns is the same. Also note that none of the numbers should be repeated.
1-9We also call it the magic square problem. Now you have to approach this problem in a brute force manner. You can start of by trying numbers in any fashion, and keep on verifying the sum in all directions.
Eventually you will reach the correct answer. It is shown in the figure below. The sum of every row, column and diagonal is equal to 15 in this combination of numbers. Because a solution to this problem existed, we were able to find it in a brute force manner. But do keep in mind that the brute force method to solve this problem could be very time taking. There are a total of 362880 total possible ways to fill up the grid.
Important! Let us try to change the question a little bit. Instead of a 3 * 3 grid, what if you have a 2 * 2 grid? You need to fill the grid with numbers 1-4 such that no numbers are repeated. No matter what combination you try, you can never reach a condition where the sum of all rows, diagonals and columns is the same.
This means that the solution to this problem does not exist. Hence, even a brute force approach would be unsuccessful.
Summary:
This is what makes the brute force paradigm so popular and one of the favorites. It gives a sure shot way to determine if a problem is solvable. Usually developers try to approach the problem with a brute force approach first, if you are able to verify that a solution exists, only then you go ahead and try to optimize it.
You can have a look at some of the problems where we discuss a brute force method first, before we start to optimize the solution:
Video Explanation:
