Hello guys. I have been for a while playing arround with a challenge that I have called the "Man's number" challenge (by Man, here I mean the "human beeing" meaning of the word, women are also very welcome to the challenge!! 
). The porpous of the challenge is following: try to determine the value of God's number without the assistence of computers.
Here are the rules: the usage of computer programs to do something a real human would not realistically be able to do (like finding solutions for millions of states of the rubik's cube in 20 moves or less) is completely banned. Using a computer to generate solutions for individual cube states or specific states on a substep is allowed, but it can't be considered "provenly optimal" for the porpouses of the challenge, in order to avoid computer based lower bound proving. Programs that do not give any kind of unfair advantage are allowed, like for example but not likited to notepad, paint and calculator (as calculations could technically instead be done on paper, doing them on a computer simply makes them more efficient as reduces errors).
Since proving that the God's number is 20 without using a computer is on practice, impossible, instead I'll be focusing on increasing the lower bound and decreasing the upper bound. For the lower bound I'll be looking at both the constructive lower bound (where you find a specific state of the cube and prove it requires at least n moves to solve) and the non-cobstructive lower bound (where you prove a state that requires at least n moves to solve must exist).
- The non-constructive lower bound
Using a clever counting trick, a lower bound for the God's number can be set as 17. The idea is simple, there are ~4.325*10^19 possible states that a rubik's cube may be at. However, only 1 state can be reached after 0 turns, so clearly a state requiring at least 1 move must exist.
Similarly, only 18 valid moves exist, which means at most 18 states may be reached in exactly 1 move, or 1+18=19 total states if you also count the 0 move state, but since 19 is still strictly less than 4.325^10^19, there must be a position that requires at least 2 moves to solve. I promise I won't list you all the values up to 17, but it is really important I still talk about the 2 move states. For 2 move states, you may think we have 18² of them, since you could do any one of 18 moves for the first one, and any one of them for the secound one, however, we can do better than that. Since 3 of the options for the secound move would just turn the same side again, we don't actually have to consider them, reducing the ammount of options for the secound move (and for all subsequent others for that matter) to 15. Thus, we have exactly 18*15=270 possible 2-move-long move combinations. That results in a running total of 289 move combinations up to 2 moves long, which is clearly less than 4.325*10^19, so a state requiring at least 3 moves must exist. If you keep applying this logic, you'll reach the conclusion that, in htm, a state of the rubik's cube requiring at least 17 moves to solve must exist. The reason why this is a lower-bound and not a definitive proof for the God's number is because multiple move sequences may generate the same state. A comic example of such is the sequence of 9 moves "R2 F2 B2 L2 D2 R2 F2 B2 L2", which does the exact same thing as the sequence of 1 move "U2".
- Constructive lower bound
Now, with the added restriction of actually finding a specific case and proving it actually must require at least n moves to solve, it becomes much harder, since the super efficient counting trick doesn't work anymore. When JPerm tried this on his video about the God's number, he constructively proved that a cube hand-scrambled by him required at least 2 moves to solve by going thru every single one of the possible 1 move combinations and showing that none of them solved the cube, and thus the cube required at least 2 moves to solve and thus the God's number is at least 2. As good as this was as an example to help his viewers understand what a constructive lower bound is, it is a really bad bound, as I was capable of creating an algorithm (computer science definition of algorithm, not cubing definition of algorithm) for determining the lower bound for any given state of the cube, and the maximum lower bound it can generate happends to be 9 on some very specific scrambles, and so that is my constructive lower bound. The way how this algorithm works is the following: firstly, count how many edges are bad edges (unoriented). If this ammount is 4, then at least one F or B move is required to orient them, and they must be oriented for the cube to be solved. If there are 2, 6, or 8 bad edges, then at least 2 F or B moves are required to orient them. If 10 or 12 edges are bad edges, then at least 3 F or B moves. Now repeat this proccess for the LR and UD axies and add the ammount of required F/B moves to the ammount of L/R moves and to the ammount of U/D moves. On the worst case this would be 3 F/B moves + 3 L/R moves + 3 U/D moves = 9 moves. So this proves that ANY state that has at least 10 bad edges in each axis must require at least 9 moves to solve. A famous example of this is the superflip (the state where all corners are solved and all edges are flipped in their place), which was also the state used to prove the lower bound of 20 in the version of this challenge that allows for computers.
- Upper bound
This one is, by a long shot, the hardest of the 3 bound to set, since it requires proving that ALL rubik's cube states can be solved in at most m moves, rather than proving that a state requires at least n moves. The most streight forward way to do this is by creating a solving method and strictly proving, without the usage of computers, that each substep must require at most n moves, and then summing the maximum ammount of moves for each state.
First, I'll walk thru a trivial solution for this using the old pochmann method, and then I'll walk thru a proper method I developed for this challenge specifically.
Since the old pochmann example will just be a trivial demonstration, I won't bother about efficiency too much. I'll also be using the standard T perm, R perm, modified-Y perm variation. For corners, the maximum ammount of targets you can have is 14, which would happend if all corners are twisted. The longest setup move for corners is 2 moves, and the swapping algorithm itself is 15 moves. This totals a maximum of (2+15+2)*14=266 moves for corners. Similarly, the worst case for edges would have 22 targets, when all edges are flipped. The longest setup move for edges is 4 moves long, and the swapping algorithm itself is 14 moves long, resulting in a maximum of (4+14+4)*22=396 moves for edges. The parity algorithm is 16 moves, so the upper bound for this version of old pochmann is 266+396+16=678 moves. This upper bound os absolutely horrendous and tremendously unoptimised, but it wasn't meant to be otherwise anyway.
Now for the actual method I developed, which is a variation of Petrus. Since I wanted to actually rigurously prove each step's upper bound (it is a requirement of the challenge; the challenge (the upper bound part of it) is to prove that the cube MUST be solveable in at most n moves, not that it probabilly will always be), I chose to opt for a mostly piece-by-piece aproach, specially on the first few steps, where solving 2 pieces at a time will easilly reach the hundreds of algorithms/cases. The following is a list of the steps of the method, along with the alg count/case count for each step, the maximum ammount of moves it can require to be solved and the running total.
It will be formatted as such:
[Step name] - [move count] - [running total] - [case count; including skip case, such that multiplying all theese numbers should result in the ammount of states of the cube] // [Aditional comments]
DB - 3 - 3 - 24
DBL - 3 - 6 - 24
DL - 5 - 11 - 22
BL - 5 - 16 - 20
DF - 4 - 20 - 18
DFL - 6 - 26 - 21
FL - 6 - 32 - 16
EO - 8 - 40 - 64 // by abusing simetries, it is possible to do an alg list with less than 63 algs. I was capable of doing it in 30-few
DR (down-right edge piece, NOT domino reduction) - 2 - 42 - 7
DBR - 7 - 49 - 18
BR - 5 - 54 - 6 // Note: on the future I plan on making DBR and BR a single step called 3rd F2L pair.
F2L - 10 - 64 - 75 // Thanks to António Gomes for providing me some efficient algorithms for this step, without him I would still be stuck on 12 moves.
OCLL - 10 - 74 - 27 // When done in isolation, this step may require up to 11 moves. However, since only the worst case matters, we must assume we did not skip the last F2L slot. All last F2L slot cases end with a R* move, and all 11-move OCLL cases may be done starting on a R*, which means that this step will always cancel at least 1 move with the previous one.
PLL - 15 - 89 - 288 // AUF included in this step. That's why the worst case is 15 rather than 14. I did this to simplify "alg count" calculations.
In case you didn't understand fully the notation, or completely skipped the method definition (which I would not recommend at all), all that is there to say that the upper bound is 89 moves. Altho this upper bound is much better than the previous 678 one, it still is not enough to always fit in the FMC limit of 80 moves, which is annoying.
And I finish it here, wishing to read what you all think about this challenge and to see what brilliant original solutions you come up with. Also remember, please do not cheat. The actual answer has been known for douzens years to be 20, so cheating is really just a way to steal everyone's fun. I also think that there is little to no progress to be made in the lower bound section of this (maybe on the constructive lower bound side??), so I would recommend you to try to improve the upper bound instead.
). The porpous of the challenge is following: try to determine the value of God's number without the assistence of computers.Here are the rules: the usage of computer programs to do something a real human would not realistically be able to do (like finding solutions for millions of states of the rubik's cube in 20 moves or less) is completely banned. Using a computer to generate solutions for individual cube states or specific states on a substep is allowed, but it can't be considered "provenly optimal" for the porpouses of the challenge, in order to avoid computer based lower bound proving. Programs that do not give any kind of unfair advantage are allowed, like for example but not likited to notepad, paint and calculator (as calculations could technically instead be done on paper, doing them on a computer simply makes them more efficient as reduces errors).
Since proving that the God's number is 20 without using a computer is on practice, impossible, instead I'll be focusing on increasing the lower bound and decreasing the upper bound. For the lower bound I'll be looking at both the constructive lower bound (where you find a specific state of the cube and prove it requires at least n moves to solve) and the non-cobstructive lower bound (where you prove a state that requires at least n moves to solve must exist).
- The non-constructive lower bound
Using a clever counting trick, a lower bound for the God's number can be set as 17. The idea is simple, there are ~4.325*10^19 possible states that a rubik's cube may be at. However, only 1 state can be reached after 0 turns, so clearly a state requiring at least 1 move must exist.
Similarly, only 18 valid moves exist, which means at most 18 states may be reached in exactly 1 move, or 1+18=19 total states if you also count the 0 move state, but since 19 is still strictly less than 4.325^10^19, there must be a position that requires at least 2 moves to solve. I promise I won't list you all the values up to 17, but it is really important I still talk about the 2 move states. For 2 move states, you may think we have 18² of them, since you could do any one of 18 moves for the first one, and any one of them for the secound one, however, we can do better than that. Since 3 of the options for the secound move would just turn the same side again, we don't actually have to consider them, reducing the ammount of options for the secound move (and for all subsequent others for that matter) to 15. Thus, we have exactly 18*15=270 possible 2-move-long move combinations. That results in a running total of 289 move combinations up to 2 moves long, which is clearly less than 4.325*10^19, so a state requiring at least 3 moves must exist. If you keep applying this logic, you'll reach the conclusion that, in htm, a state of the rubik's cube requiring at least 17 moves to solve must exist. The reason why this is a lower-bound and not a definitive proof for the God's number is because multiple move sequences may generate the same state. A comic example of such is the sequence of 9 moves "R2 F2 B2 L2 D2 R2 F2 B2 L2", which does the exact same thing as the sequence of 1 move "U2".
- Constructive lower bound
Now, with the added restriction of actually finding a specific case and proving it actually must require at least n moves to solve, it becomes much harder, since the super efficient counting trick doesn't work anymore. When JPerm tried this on his video about the God's number, he constructively proved that a cube hand-scrambled by him required at least 2 moves to solve by going thru every single one of the possible 1 move combinations and showing that none of them solved the cube, and thus the cube required at least 2 moves to solve and thus the God's number is at least 2. As good as this was as an example to help his viewers understand what a constructive lower bound is, it is a really bad bound, as I was capable of creating an algorithm (computer science definition of algorithm, not cubing definition of algorithm) for determining the lower bound for any given state of the cube, and the maximum lower bound it can generate happends to be 9 on some very specific scrambles, and so that is my constructive lower bound. The way how this algorithm works is the following: firstly, count how many edges are bad edges (unoriented). If this ammount is 4, then at least one F or B move is required to orient them, and they must be oriented for the cube to be solved. If there are 2, 6, or 8 bad edges, then at least 2 F or B moves are required to orient them. If 10 or 12 edges are bad edges, then at least 3 F or B moves. Now repeat this proccess for the LR and UD axies and add the ammount of required F/B moves to the ammount of L/R moves and to the ammount of U/D moves. On the worst case this would be 3 F/B moves + 3 L/R moves + 3 U/D moves = 9 moves. So this proves that ANY state that has at least 10 bad edges in each axis must require at least 9 moves to solve. A famous example of this is the superflip (the state where all corners are solved and all edges are flipped in their place), which was also the state used to prove the lower bound of 20 in the version of this challenge that allows for computers.
- Upper bound
This one is, by a long shot, the hardest of the 3 bound to set, since it requires proving that ALL rubik's cube states can be solved in at most m moves, rather than proving that a state requires at least n moves. The most streight forward way to do this is by creating a solving method and strictly proving, without the usage of computers, that each substep must require at most n moves, and then summing the maximum ammount of moves for each state.
First, I'll walk thru a trivial solution for this using the old pochmann method, and then I'll walk thru a proper method I developed for this challenge specifically.
Since the old pochmann example will just be a trivial demonstration, I won't bother about efficiency too much. I'll also be using the standard T perm, R perm, modified-Y perm variation. For corners, the maximum ammount of targets you can have is 14, which would happend if all corners are twisted. The longest setup move for corners is 2 moves, and the swapping algorithm itself is 15 moves. This totals a maximum of (2+15+2)*14=266 moves for corners. Similarly, the worst case for edges would have 22 targets, when all edges are flipped. The longest setup move for edges is 4 moves long, and the swapping algorithm itself is 14 moves long, resulting in a maximum of (4+14+4)*22=396 moves for edges. The parity algorithm is 16 moves, so the upper bound for this version of old pochmann is 266+396+16=678 moves. This upper bound os absolutely horrendous and tremendously unoptimised, but it wasn't meant to be otherwise anyway.
Now for the actual method I developed, which is a variation of Petrus. Since I wanted to actually rigurously prove each step's upper bound (it is a requirement of the challenge; the challenge (the upper bound part of it) is to prove that the cube MUST be solveable in at most n moves, not that it probabilly will always be), I chose to opt for a mostly piece-by-piece aproach, specially on the first few steps, where solving 2 pieces at a time will easilly reach the hundreds of algorithms/cases. The following is a list of the steps of the method, along with the alg count/case count for each step, the maximum ammount of moves it can require to be solved and the running total.
It will be formatted as such:
[Step name] - [move count] - [running total] - [case count; including skip case, such that multiplying all theese numbers should result in the ammount of states of the cube] // [Aditional comments]
DB - 3 - 3 - 24
DBL - 3 - 6 - 24
DL - 5 - 11 - 22
BL - 5 - 16 - 20
DF - 4 - 20 - 18
DFL - 6 - 26 - 21
FL - 6 - 32 - 16
EO - 8 - 40 - 64 // by abusing simetries, it is possible to do an alg list with less than 63 algs. I was capable of doing it in 30-few
DR (down-right edge piece, NOT domino reduction) - 2 - 42 - 7
DBR - 7 - 49 - 18
BR - 5 - 54 - 6 // Note: on the future I plan on making DBR and BR a single step called 3rd F2L pair.
F2L - 10 - 64 - 75 // Thanks to António Gomes for providing me some efficient algorithms for this step, without him I would still be stuck on 12 moves.
OCLL - 10 - 74 - 27 // When done in isolation, this step may require up to 11 moves. However, since only the worst case matters, we must assume we did not skip the last F2L slot. All last F2L slot cases end with a R* move, and all 11-move OCLL cases may be done starting on a R*, which means that this step will always cancel at least 1 move with the previous one.
PLL - 15 - 89 - 288 // AUF included in this step. That's why the worst case is 15 rather than 14. I did this to simplify "alg count" calculations.
In case you didn't understand fully the notation, or completely skipped the method definition (which I would not recommend at all), all that is there to say that the upper bound is 89 moves. Altho this upper bound is much better than the previous 678 one, it still is not enough to always fit in the FMC limit of 80 moves, which is annoying.
And I finish it here, wishing to read what you all think about this challenge and to see what brilliant original solutions you come up with. Also remember, please do not cheat. The actual answer has been known for douzens years to be 20, so cheating is really just a way to steal everyone's fun. I also think that there is little to no progress to be made in the lower bound section of this (maybe on the constructive lower bound side??), so I would recommend you to try to improve the upper bound instead.
