A Dynamic Approach to the Famous Euler Puzzle. Is it Possible?

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?

5x5 Euler Solution | Image by Author

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.

Permuted Classes After Running Algorithm. Each Number Represents a Class of Pieces.
Permuted Ranks After Running Algorithm. Each Rank is Represented by a Colour.

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.

Resulting Solution of the 6x6 from Iteration

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.

Matrix Output. Notice How the Algorithm had Placed Two Purples in the Prime Number Rows.

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaival Patel

Jaival Patel

16y/o Computer Scientist x Mathematics Enthusiast. I love to share my research and interest in these two topics so you will see a lot of my blogs about my work!