As a Rubic cube's enthusiast sooner or later I would come up with some app about it.
My goal is to learn and play with code combine with my passion.

It's a desktop app that allows user to play with cubes.

Program is write in JAVA version 12, with help of libraries: AWT, swing, GUAVA, Lombok, JavaTuples.
Build using Maven. Test are written in JUnit5.

• scramble cube with randomly generated algorithm
• move cube with your own algorithm
• solve cube using basic solving method
• finding the shortest algorithm which solves the cube (FWM - fewest moves)
• shorten algorithm, with option of deleting rotation moves
• history of actions taken by user
• setting delay between single moves

• 2x2x2 full functionality

Regular NxNxN cube is implemented using 2x2 matrix of integers.
Example for 2x2x2 cube:
      4 4
      4 4
3 3 0 0 2 2 5 5
3 3 0 0 2 2 5 5
      1 1
      1 1
Empty spaces have value 9 but are irrelevant.
Every number corresponds to different colors:

• white = 0
• yellow = 5
• red = 1
• orange = 4
• blue = 2
• green = 3
  

All opposite colors sum up to 5, what ended up as a useful property further. Depends on type of cube, classes can implement different interfaces. Cube.class implement two interfaces, one which allows cube to be rotated and second concerning moves of outer walls.
Every NxNxN cube allows these two types of moves.
Moving cube is quite simple process:

• move(String alg) check if alg is proper, convert it to list and pass each move to moveOneWall(char wall, int rotate) method
• moveOneWall(char wall, int rotate) determine which method of MoveOneWallInterface or RotateInterface use
• eg. moveCounterR() changes matrix

Each move has three different methods: normal, counter and double. Since there are no loops they are very fast, compare to one method which would include loop and in case od counter move could result in unnecessary repetition.

Algorithm.class contains static methods for manipulating algorithms. Here I explain some of them.

returns random algorithm, taking under consideration that in 2x2x2 cube moves like D and U are on the sam axis and can be combined in one move, counter moves appear in probability of 2/7 and double moves 1/7

returns boolean, whether algorithm is good or not, it checks if character is from poll "xyzUDRLFB", ' and 2 are not in poll, because method skips them if previous char is in poll, so only when they are repeated there is violation

uses HashBasedTable, which consist all possible permutation of rotation and move. first loop go through alg and adds to xyz list when rotations appear and deleted from alg, if it's not rotation second loop is trigger, current move is changed as many times as rotations occurred in alg before, going through xyz and changing current move based on HashBasedTable, ' adn 2 can be omitted and just added again after changes

FWM methods are the most interesting part of application.
God's number for 2x2x2 it is 11, but generally it will be about 7-9.
The most straight forward solution of finding god's number is checking all possible situation and choosing quickest, but it would take days using normal computer since there are 3,674,160 possible positions!!!

What about multithreading? It will be definitely useful, but still, you don't want to wait hours for solution. After many hours of testing and thinking I end up with my own method.

In general algorithm works by finding the best possible move for current state, which changes cube to be closer to be solved.
To find the best move, entropy has to be calculated every move which is currently possible. But some moves can be omitted
e.g. when last move is R' next move cannot be of R wall.

R'R2 can be shorten to R and R'R dosen't cahnge anything <br />
Even though L wall moves don't exist in algorithm, they alos would be inneficient.
Consecutive moves cannot be parallel!

Algorithm will choose the best move from list of all possible moves of U, R and F walls.
In that case left-back-down element is the one that will be not moved cause is already solved.

ALL_POSSIBLE_MOVES = {U, U', U2, R, R', R2, F, F', F2} 
instead {U, U', U2, R, R', R2, F, F', F2, D, D', D2, L, L', L2, F, F', F2}
Using that approach makes the method twice faster wihout losese in solution!

Calculating entropy is the most expensive part of algorithm. To do it cube has to be moved and then move has to be reversed to proceed with another calculations.

Every entropy is compared to entropy of current state of cube. If no entropy is better than current, no move is returned, otherwise the best move is returned and then cube is moved. Entropy is calculated by checking every wall and adding potions if there is pattern.
Current points ranking, for white and yellow in that example:

• fullWallUni = 6
  
• fullWall = 5
  
• threeWallUni = 3
  
• threeWall = 2
  
• twoWallUni = 4
  
• twoWall = 1
  

Even though god's number is constant, in code it indicates current best solution so starts with 11 and can change.

For current points ranking FINAL_ENTROPIES = {4, 12, 14, 18, 20, 22, 26, 30, 32, 36, 42, 44}

To keep track of moves that have been done, HashMap of HashSets of that moves is stored, so algorithm won't use them again.
Algorithm automatically clears necessary moves and whole map between iterations.

movesDone = { 
              1 -> (R, U),
              2 -> (U2, F, F'),
              3 -> (R, R', R2. U),
              4 -> (R, R', R2. U, U', U2, F, F', F2) 
              }
Curretn solution is UF'UF' (with some premove)
If algorithm needs another move it sees that 4th move is full so previous move has to be changed.
4th is cleared and another 3rd move is meant to be find, then addes.
movesDone = { 
              1 -> (R, U),
              2 -> (U2, F, F'),
              3 -> (R, R', R2. U, U2),
              4 -> () 
              }
Curretn solution is UF'U2

Even though number of permutation and time is significantly lower single threaded solution still would be too long.
Program creates 4 threads, which on my computer that was the limit where more threads would end up in same or longer computation time.

Other computers could be faster using more thread, or even going through more cases

There are two types of threads, first with ascending and second with descending approach. Both are initialized with pre-move from all available moves so 9 threads will be created. Pre-moves allows algorithm to reduce number of moves to 10, therefore number of permutations.

All threads observe shared god's number (apart from their own) which indicates current shortest solution. If a better solution is found value will change. Threads are checking if their solution is worse, so they can abort and program can proceed with another thread without unnecessary computations. Descending thread will set their god's number with that value when they are created and ascending would work until their god's number is lower.

Every thread is meant to be fast, but in case of duration > 2 seconds solutions is aborted. For now there is no premises that could indicate any problems with that.

In general, they use all mentioned features. Finding best solution

Ascending starts from the shortest algorithms and goes up, so works similar to brute force solution. In some cases in super efficient because can find short solutions in the blink of an eye. Downgrade si that mvoesDone is cleared after each iteration, so moves when godsNumber is 2, it won't be used with 3.

On the other hand descending approach finds optimal solution up to length of 11 (actually 10, pre-move!), and if there is no solution checks other solves by changing current solution.