A Dynamic Approach to the Famous Euler Puzzle. Is it Possible?
Two Approached Basic Computer Science Methods to Solve the Famous Puzzling Problem Without the Use of Quantum Algorithms.
A few weeks ago, I was reading articles about recent physics and math publications on Apple News, until I came across the publication Wired. Typically, I don’t read articles on Wired, but there was this one article that stuck out to me. This article was called “Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution”, written by Daniel Garisto, which talked about how several physicists found a solution to the famous problem with quantum algorithms. As a physics enthusiast, I had understood the impact of quantum computing and mechanics, and that quantum algorithms can easily solve such problems. When I first read about the solution, I was amazed about the power that quantum algorithms had, and their methods of increasing efficiency. As I continued to read the article, I had started to wonder if it was possible to have the same solution done with dynamic programming along with some computer science permutation algorithms. After all, when we look at a 5x5 Euler Grid, it seems possible doesn’t it?
By looking at this very solution, I embarked on a 3-week journey to see if it was really possible to make a 6x6 Euler grid without quantum algorithms. However, before I get into the journey of my solutions and what I learned, let’s start by defining what the Euler Puzzle is. In 1779, the Swiss mathematician Leonhard Euler created a famous puzzle that states that each six army regiments can have six officers of six different ranks. Can the thirty-six officers be arranged in a six-by-six square so that no row or column repeats a rank or regiment?
Surprisingly, there are computer science solutions up to a 7x7 grid, but there seems to be a void for the 6x6 grid. Just like me, you are probably asking why despite all the algorithms we have, and don’t worry, I was thinking the same thing! The quantum solution consisted of looking at each piece as a form of superpositions of different pieces. For instance, a green bishop and a red knight. Moreover, with the use of perpendicular vectors and quantum states, the quantum algorithm used a relationship called entanglement, which involves relationships between two entities, of which, in our case, are the pieces on the grid. If for example, the green bishop is entangled with the red knight, even if the knight and the bishop are superpositions of multiple pieces, noticing that the knight is red would immediately depict that the bishop is green. According to Daniel Garisto, this is due to the perpendicular peculiar nature of entanglement of the pieces. In summary for those who aren’t quantum enthusiasts or specialists, it’s like solving the Rubik’s Cube. Keep permuting the layer until all the colours are the same, or in our case, until all the ranks and pieces are unique in their row and column. More about the quantum solution can be read in the article, “ Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution”.
My approach was similar in the way that it consisted primarily of permutation. Instead of using quantum algorithms and vectors, I saw this puzzle as nothing more than just a simple pattern. The solution originally came to me when I was looking at the 5x5 board for hours and realized something in common. A common pattern was that each class (this will be defined later) had the same colour diagonally when the board was solved (you can see it yourself at the top of the article). I then took that into consideration and tried to extend it to a 6x6 grid (see, not too difficult as it looks). There were two methods based on the same approach, but one failed due to the computer tangling itself up! I will get more into this later in the article because that’s where we face immense difficulty. To begin, I saw the grid and the pieces differently. I viewed the board by not looking just at separate pieces, but as classes along with their respective ranks. Each number in my solution denotes a class, which can consist of a pawn, queen, king, bishop, rook, and a knight. The corresponding colours represent their ranks.
My successful solution is made of mostly array iteration. Based on my past programming experience, I had known that the pieces in a matrix do not repeat in their columns if you move the first element in the row to the back of the array. This iteration was done relative to either 5 or 6 times depending on the length of the board. I initially started this iteration with colours, then with pieces to illustrate that the pattern was universal to this problem (the output can be seen above this paragraph).
After combining the colours and classes, we can notice that there is no repeating colour or class in any column or row.
What had been seen in the 5x5 pattern is the same pattern that has been outputted by our algorithm for the 6x6 grid: the same classes were aligned with the same colour/rank diagonally. Thus, with a simple array iteration, I have managed to solve the puzzle without any quantum algorithms. Originally, it took me 10 days to realize that we didn’t have to consider permutations in each row if we can consider a class as a set of pieces. Essentially, we can assume as our initial setup that each piece is different in a class with a different rank — no repetition occurring in the row and making our sorting simpler as we just have to focus on columns. Thus, this approach resulted in a linear time complexity, which is pretty great for a complex problem like this one.
You can check out my solution on Github: Link
As easy as it may sound, this solution didn’t take until 15 days to complete because this was not my first solution. My initial approach to this puzzle consisted of creating a matrix. This method was more brute-force than any algorithm I have ever made! Instead of looking at a class as a whole, like our array-iteration solution, I looked at individual pieces, which in the end, was a far more complex process than I thought it would be.
Here’s how our matrix solution works: for each new piece, we would run two search algorithms, one for all the columns, and one for the rows to fetch all information about the current state of the grid. The computer then runs a few conditionals relative to the new piece that needs to be added, which consisted of:
- If the whole array was empty
- If this new piece was not in the current column
- If this new piece was not in the current row
It should be noted that these conditionals are success cases that a new piece must meet (second and third one primarily) to be added. Astonishingly, although having a time complexity of n! where n is the length of the matrix, the method worked, but only for half the board…What I ended up noticing with multiple trials, iterations, and even random sampling was that the computer didn’t know it was tangling itself up at times. It was only considering the conditionals above for the present case, but not the future outcomes of the row at all.
Let’s say we have pieces 3, 4, and 5, which represent a bishop, queen, and king that need to be placed in the row. To make it easier, all three of them are new pieces in the row. Though, there is a bishop in the third column and a king in the fifth column. By my conditionals and my linear search algorithms for simplicity cases, the computer would put the next piece that has not been put in the row, so in this case, the queen in the bishop’s spot and the bishop in the queen’s spot. It should be understood that by adding the new pieces to the row, both of them are new in their new respective columns as well. This solution would work to permute the bishop and the queen, but not for the king as the only spot left in the row was the column where a king was already placed in a previous row. The result of this was the computer tangling itself up and ending up in an infinite loop.
To fix this error, I have tried possible permutation algorithms including trying to permute the three top rows only, and running the array iteration for the bottom three using the top-three rows as reference. It did work, but just like how I stated above about each class having different pieces (which was the original definition), the matrix only outputted two pieces of each set and not all. If the matrix did work with all six rows, the computer would get mixed up when approaching the last few rows, as it starts to add multiple of the same ranks or pieces. After a few trials, I realized it was because the computer’s random sampling module was being exercised a lot, meaning, it was the quality of my conditionals that was the problem. Moreover, I also tried iterating through a secondary array for new possible cases, but the computer had always tangled itself up as well.
Looking back at it, it is possible to make my solution work. Maybe a cleaner, dynamic approach, such as running the search algorithms at two elements at the same time (the first and the last) would be more efficient as it would be theoretically splitting the time complexity in half. It would have also made the algorithm more aware of the possible outcomes of putting a certain element in a row at the time. Let’s also not forget that the comparison cases have to be improved as well to avoid edge cases as previously mentioned!
Attempted solution can be found on my Github: Link
Personally, at the end of this research journey, I am very happy that I found a possible solution. However, array-iteration can only go so far as it may break when working with larger matrices. Dynamic programming approaches such as my matrix theoretical solution are for sure artistic ways of solving such complex problems. What I learned over these past few weeks is that problems like these are prime examples of how powerful quantum mechanics and computing is compared to a typical computer. A quantum algorithm can help you look ahead with all possibilities and states, whereas with a normal algorithm, you are only so limited based on your current state. Despite the difference though, I was surprised (and I hope you are too!) that I could manage to get an algorithm to look at outcomes a few states ahead with basic dynamic programming approaches!
Sources
Garisto, D. (2022, January 23). Euler’s 243-Year-Old ‘Impossible’ Puzzle Gets a Quantum Solution. Apple News. Retrieved from https://apple.news/ATbKDUewTR-mQ4DA3Th9vpg
