Use breadth first search with memoization

[stefnotch]

Hello!

I just found this quite nice project and saw that you're throwing some serious mathematics at the Genshin Inazuma puzzles. However, I wanted to point out that there is a much simpler, algorithmic approach. And it even guarantees finding an the optimal, best solution.

Basically, when you have a puzzle, you have a finite state machine

• some rotated cubes (state)
• and if you hit a cube, some cubes will turn (state transition)

Then, an algorithm can try out all possibilities. Starting from the beginning, it would simulate what happens if you hit cube number 0, cube number 1, ... up until cube number 3. And then, it would simulate hitting cube number 0 again. And cube number 1 again. And so on. After a relatively short time, the algorithm will have tried out everything. And more importantly, every reachable state will have been reached.

We did this over here https://github.com/mgatelabs/GenshinSolvers/issues/1 It includes some example code if you are curious.

[Neboer]

Hi, I'm very glad to see someone is also interested in the project! I'm a programmer and I play Genshin for a long time, I love the game and I love most of the puzzles in the world. It's very exciting to write a program to help us solve the puzzles.

The program is use some serious mathmetics ways to solve the problem because I think it worth it. In fact, it is not complex at all -- What I do is only translate the puzzle into a so-called "diophantine equation system", which can easily find the set of solutions. The solving algorithm is mature enough to find all the solutions easily and effienctily. So actually all we need to do is to create a diophantine equation system by user input which represents the puzzle, and, solve it.

Image the puzzle like this: three light with a initial state of 2-1-3, when I hit the first, the first and the second self plus one. When I hit the second, all blocks plus one, and when I hit the last, the second and the last plus one. We want all cubes turns 2, so we can draft the following equation system:

2+x+y = 3a + 2 -> x + y - 3a = 0 1+x+y+z = 3b + 2 -> x + y + z - 3b - 1 = 0 3+y+z = 3c + 2 -> y + z - 3c + 1 = 0

The equation above has an infinite solution because it has 6 unknown variables but only has 3 equations. But there's another limitation -- all the unknowns are integer. This is a so-called "linear diophantine equation system". Now our task is to find its solution set, which can represent all the possible roots of the equation system.

There are many ways to solve a typical linear diophantine equation system, the library I use here takes a method named lllhermite to give the final result. The result is a solution set, which contains several vectors represent the unknown variables x y z a b c. We solve the above equations and get a result : [-1, 1, 1, 0, 0, 1] the solution set only contains one vector so it is the final result. We only need to plus 3 on the first to get 211, this is the final solution. We need to hit the first block twice, the second once and the third once.

It seems much more complex to use this method to solve the puzzle. But it is worth it. The solution here is the FINAL solution of the problem. We can easily get ANY way to solve the puzzle. And this is an optimized algorithm, I think it is faster than Breadth-First Search, but I don't test it. In fact, I think there's no need to compare the two methods: your solution is very straightforward and mine is quite confusing, I wrote the program only to prove it can, for I already know there are a lot of solvers like this exists.

Thank you for your interest. We can cooperate with each other more on solving more Genshin puzzles. Wish you a good day, thank you very much.

[stefnotch]

First of all, thank you so much for explaining your approach. I think I understand it. Seeing a mathematical solution to those puzzles is most certainly delightful. If I understood it correctly, it's equivalent to solving a linear system of equations mod 3. (Mod 3 because light puzzles have 3 valid states)

I'm still amazed that Diophantine equations can be used for this.

As for performance, I think both algorithms are more than fast enough to "instantly" solve all the puzzles in Genshin.

The breadth-first search has a time complexity of roughly O(number of cubes ^ solution steps) For example, to find the 211 solution, it would take O(3^(2+1+1)) = O(3^4) = 81 recursive calls until that solution has been found.

There is one other algorithm I've seen, which is "do random things until a good solution has been found". That one is definitely a bit slower for some puzzles.

Finally, regarding the cooperation, we'd love to have your feedback regarding the site. https://mgatelabs.github.io/GenshinSolvers/puzzle/x14197 The main parts that we still need to do are

1. finding every single puzzle on the map and figuring out its exact rules
2. polishing and making the site really nice to use

[Neboer]

I'm amazed for your fast reply. I must point out that the linear Diophantine equations is like but not equals to the linear system of equations. When it happens to mod 3, everything is fine, you can just ignore the mod3 and solve the linear system strightfully. But when it comes to mod 4, like the rotation of a cube, the complexity suddenly increase a lot. The mod 4 cannot be ignore so there's no simple way to solve the equation system. That's why I use Diophantine equations, they are born to work on this.

I like your project very much. I think Genshin puzzles are not only puzzles, they are also great challenges for algorithm creators to enjoy themselves. By the way, I am astonished with the stone puzzles on Tsurumi Island. The puzzle is like Sokoban game but is more complex and difficult because it is on a map rather than a mesh. I really want an algorithm to solve it.

[stefnotch]

Good to know that the "easy" modular arithmetic approach breaks down. Sounds like Diophantine equations are super useful, I'll definitely have to put them on my list of topics to learn.

And yes, some of the Genshin puzzles are really interesting and enjoyable. I have written a breadth first Sokoban solver in the past. It basically boils down to

1. Encode the state: A graph could represent the puzzle. And the stones would be pointers at nodes of the graph
2. Write a function to get from one state to the next: Check if the adjacent graph nodes are empty, if yes, we have a new state
3. Try out everything: Breadth first search

But now I'm wondering if there might be a mathematical approach as well ;)