A while back, during a company meeting, we had a brave soul who challenged us to go on an adventure with him. This F# enthusiast wanted us to learn functional programming together. Fast-forward a couple of months and things are starting to take shape.
Our latest mission was the famous 8 queens puzzle, which we had to solve using a functional language. What functional language you actually used was up to you. This resulted in two teams fighting for glory, F# vs Scala. So without further ado, here is the story from the F# side!
Coding challenge summarized:
• Place 8 chess queens on a standard chess board (8×8)
• Queens can’t attack each other, thus a solution requires that no two queens share the same row, column, or diagonal
• How many valid solutions are there?
As the awesome team of developers we are, familiar with all modern programming principles, we started developing pretty fast after we got our assignment. TDD style. Red, green, refactor. Just beautiful. Until.. Ugh.. We realized our mistake. Way over-complicating our solution, like true developers! The price of this mistake? Us commenting out at least 60% of our already written code and 100% of our tests. A minor setback, one would say. We went back to the drawing board and figured it out.
When we first analyzed the problem, we tried to determine if brute force was an option. Sadly, our conclusion at the time was wrong. If we don’t care about how long it would take, what is the simplest way to find all the solutions? Generate each possible arrangement, validate the correctness, and voila! But wait. How many arrangements are possible for this puzzle using no rules? Over 4.000.000.000! Way too many for brute force! And here lies our mistake, we didn’t consider trying to cheat the system.
Instead of generating each possible arrangement, we applied a simple rule that constrains each queen to a unique row. By doing that we now only get 16 777 216 (8^8) possible combinations. That’s a lot better already, but still too many. We were able to reduce this number even further by generating the permutations, which reduced the combinations down to just 40 320 (8!). Then the only thing left to do, was to filter those queens that are on the same diagonal and we got our final result!
Validating if a queen is in the diagonal of another queen, is essential for when we find all our permutations. We would loop over all those permutations and filter out all the permutations returning true for this function. Leaving only the valid solutions in the collection which we could then count.
A recursive function for comparing all the queens from a board against each other. all the queens from the tail will be compared to the head. If none of them are in the diagonal of the head, the head will be removed from the collection. The permutation is valid if the collection is empty in the end.
A function used to generate our permutations. For each row we create all possible column combinations. If the queens reached a count of 8 (0→7), where each queen can only be on a single row, all permutations would’ve been generated. Each time we use a column it gets removed from the collection of available columns.
All that was left to do was bringing it all together! In this case our yPositions are the columns of the chess board. We generate the permutations, we filter the permutations and then they get printed which gives us our final result.
First of all, a huge thanks to Axxes for supporting this event. Investing in people to learn a new language is just one of the many examples that show how great our company can be. It brought us joy and made us better programmers.
Secondly, a small spotlight for Florian Verdonck, responsible for making all of this a success. I think everyone would agree that it was a great afternoon, a fun and interactive way to learn a new language with useful insights and a lot of gotchas, while also seeing a different side from your colleagues at the same time.
I hope you learned something new like I did and if you want to learn more about F# and Functional Programming feel free to join us at FableConf Antwerp later this year and order your early bird ticket today!
Get to know Axxes and our corporate culture!