• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Union Creator: A program for reaching multiple end states

Athefre

Member
Joined
Jul 25, 2006
Messages
1,291

In 2020, I developed CLL+1 and solved the problem of how to solve any of the four last layer edges. What I discovered was that an algorithm can be used with multiple cases to reach one of the desired end states. In the case of CLL+1, the end states are all of the possible last three edges cases. Algorithms will share with other algorithms several cases that they are able to solve to one of the end states. This creates several unions like a Venn or Euler diagram. It also reduces the number of required algorithms versus always solving to one end state, such as the solved case or, in the case of CLL+1, always solving the UF edge. The history of this goes back even further, to 2004 when Lars Petrus started developing his "270" system for solving ZBLL using two short and fast algorithms. Thom Barlow later extended this to 1LLL in what's called Duplex. Those two systems are based on pulling from a very small pool of algorithms and always combining two algorithms. My contribution is generalizing the concept to have any number of algorithms involved in the unions and the pool, and various techniques for solving to any desired and specified set of end states.

Union Creator is designed to be used in conjunction with Batch Solver. In the Cases text box, input the full list of algorithms that solve all cases for the involved pieces. In the Desired States text box, input the list of algorithms that solve all of the desired end states, including all possible AUFs at the beginning of each.

It takes the inverse of each end state in the Desired States text box then applies the inverse of each algorithm in the Cases text box. This creates a large table of crossed cases. All AUFs are included throughout the process. So for COLL+1 where you want to always end in a U Perm, it looks like (U*) M2 U' M' U2 M U' M2 (U*) R U2 R' U' R U' R' (U*). This gives a final state showing that if you were to apply R U R' U R U2 R' to that state, you will get a U Perm - the one solved by M2 U M' U2 M U M2. Each algorithm in the Cases text box is internally numbered top to bottom, starting at 1. Each case and desired state combo state is then compared with all cases to find which case it is. This produces rows of case state numbers for each algorithm in the Cases text box and those numbers are all of the cases that the algorithm covers to solve to one of the desired end states. Then the set coverage is calculated to find the minimum number of algorithms required to cover all cases and solve to one of the end states. There are other ways of finding the unions, such as the original CLL+1 way which did the inverse of this by applying the case forward then the end state forward. Or, a brute force solver that can solve to a list of desired end states.

I don't know if union involved multi state solving has a major use in speedsolving. For something like COLL+1 or CLL+1, there are better two look last layer methods and at the advanced level someone can learn ZBLL or 1LLL to solve in a single step. That issue doesn't exist with something like applying unions to L5C to solve in a single step to a set of good end states. But the biggest problem is that we don't know how difficult it is to associate one algorithm with multiple cases when learning.

This was a difficult program to develop because it involves an unsolved problem in mathematics called the "set cover problem". In 2020, I found my own set cover algorithm as can be seen in the Excel files linked in the CLL+1 thread. In 2022 when I first developed Union Creator, I found a programmatic set cover algorithm. This was before I knew that set cover is a concept in mathematics and is an unsolved problem. But my algorithm wasn't detailed enough to be able to handle numerous cases in a union. I hope that I can be forgiven for using AI to help with this unsolved mathematics problem and to rewrite my union finding function. I started trying to make this program in 2020, first hoping to make an Excel version, then switching to Python. But my programming skills weren't enough, so I reached out to others for assistance. Nothing was developed. So in 2022 I tried again on my own using JavaScript and developed a version of Union Creator that could handle unions of two algorithms. I upgraded it this year to be able to handle any number of algorithms and to include additional features.
 
It would've been pretty cool if you solved the set cover problem by accident.

Any mathematical proofs aside, this is really useful and I hope people take advantage of it!
Thank you. Maybe if I had pursued a career in mathematics I would be solving those kinds of problems instead of Rubik's Cube problems.
 
Back
Top