5
$\begingroup$

I apologize if this question is out of the guidelines of this forum. If it is please let me know and I will abstain from requesting definitions and terminology.

Hello! I am currently writing a program to find the shortest path solution in a randomised Rubik's Cube. There is a certain language/search based methodology that has caught my attention, and which I would like to apply to the solution, but I am unaware of what kind of terminology I should be looking up.

THE METHODOLOGY:

The methodology is one where different languages are developed to satisfy different aspects of the cubes solution. For instance, we might find a language/grammar which appropriately describes/generates all transformations which move one block of the cube to some position we want it to be. We may then find another language which satisfies the movement of another block to some position we want it to be. The language which satisfies both of these languages is the one which generates transformations which will move BOTH blocks to where they are supposed to be.

WHAT I WOULD LIKE TO LEARN MORE ABOUT:

It is in this sense that I am interested in learning more about how languages can be tested against each other in order to CONSTRAIN the otherwise unweildly "search tree" that would be required to be derived and searched in order to find the solution.

At the same time I would like to build a symbolic vocabulary which would allow me to compare the different pertinent variables (runtime, memory size, etc.) of different tree search constraint methodologies, particularly language based methods (as I have poorly defined them).

I am also particularly interested in the methodologies that can be used to detect patterns in the strings which are satisfying two seperate languages so that a third language which satisfies both can be developed.

Also, I would like to learn more about how we can show that one language is mutually exclusive to another language.

I am particularly interested in terminology so that I might do research on the Internet, however I would also greatly appreciate any book recommendations. Thank You!

Improve this question
$\endgroup$
1
  • $\begingroup$ What is this question about? Can you given examples of these strings? $\endgroup$
    – Raphael
    Commented Jan 16, 2016 at 15:31

3 Answers 3

Reset to default
3
$\begingroup$

Kociemba wrote very nice algorithm, which is the fastest working algorithm returning optimal or almost optimal solution very efficiently.

If you want to derive your own system, try in steps:
0) invent notation for the cube, do not try to optimize it.
1) try BFS or something like A* (this one will be harder, with heuristics).
2) try some kind of memoization, and state precomputation.
3) if something is not efficient step back to 0 and change type of notation.

Why should you not optimize your notation?
Because a few bytes overhead is nothing in compare to smooth transitions between states.

Honestly, pure BFS will do the job, but without any help or reductions it will be very slow. You can make encoding relative to color and put your reference point (one corner or the cross), it will decrease hashing time.
To check your approach just take several thousands of permuted cubes, count turns per cube and time it took per cube to solve.
If you are interested in AI, solving cube is doable, but guaranteed least moves will take some time.

There is Rubik Group but language induced solvers in contrary to graph or group solvers are not common, so there might be some hidden treasure there. Look at Kociemba algorithm, he does not use Rubik Cube group per se, but changes it so he has smaller number of instances.

Improve this answer
$\endgroup$
2
$\begingroup$

It sounds like you want to compute the intersection of two languages. Depending upon what kind of languages you are looking at and how they're represented, you might look into the "product construction" and closure properties for your class of languages.

For instance, for regular languages, there is a standard method for computing the intersection of two regular languages (expressed as automata) using what's known as "the product construction". On the other hand, computing the intersection of two context-free languages is undecidable in the general case.

You mention search trees and efficiently incorporating multiple constraints into the search process. It seems possible that the formalizations of "languages" from automata theory might not be useful to you, and that thinking of this as languages might not be a useful perspective in the end. For instance, you might be more interested in work from the artificial intelligence field (e.g., A* and other search algorithms).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I understand what you are saying. It sounds like i am using languages out of place, but in this particular instance, each generated string is also a string in the "cube search tree." What is interesting to me is that by using this methodology, i constrain the states that i test for success to only those generated by the first language, although this does come at a cost of increased testing time as the string gets longer and i have to put it into more "push down automata" to test it at a higher level. this is why i was particularly interested in finding patterns between context free grammars $\endgroup$
    – TestingTuring
    Commented Dec 16, 2015 at 2:00
  • $\begingroup$ I googled closure properties for context-free languages who are not regular. When you say that it is undecideable in the general case, does that mean that there are cases in which they are decideable? $\endgroup$
    – TestingTuring
    Commented Dec 16, 2015 at 2:37
  • $\begingroup$ @TestingTuring, I don't know if there are cases in which they are decidable (rather: I'm sure there must be, but I don't know if they're useful and couldn't suggest any in particular). $\endgroup$
    – D.W. ♦
    Commented Dec 16, 2015 at 17:10
  • $\begingroup$ Alright, i will look into that. I've decided to go with a combination of methods for the program based off of various considerations, and this project will now be less about a language based approach and more about comparing different approaches. What i am missing now, however is a toolbox for comparing the variables of each approach (i.e. process time, thread requirements, memory requirement, RAM requirements, etc.). Also, my long term goals are ultimately in A.I., where would you suggest i go to learn more about search algorithms? $\endgroup$
    – TestingTuring
    Commented Dec 16, 2015 at 18:30
2
$\begingroup$

have not heard of use of abstract languages to model the rubiks cube. however, there is a huge amount of group theory intrinsically associated with it, and there are natural ways to represent group theory using languages (and automata). as for using the theory to solve the cube, there are many standard algorithms and it would be difficult for newcomers to invent them.

here is a very thorough introductory reference on group theory in the rubiks cube aimed at gifted high school students. the 2nd paper has much of the theory with an eye toward an algorithmic solution where group operations are modelled as "macros". the 3rd ref compares basic cube algorithms performance.

Improve this answer
$\endgroup$
1
  • $\begingroup$ addendum/ further thought: FSMs/RLs can be used for set logic in general, so anywhere set logic is used the FSM can be used as an implementation. ie if the algorithm can be reduced to set operations manipulating sets (eg valid moves) then RLs can be used to implement those operations. $\endgroup$
    – vzn
    Commented Jan 18, 2016 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.