4 ms·

So there is 43,252,003,274,489,856,000 positions of a Rubik's Cube? Pretty mind blowing.

sjcsjc 7y ago
And there are 80658175170943878571660636856403766975289505440883277824000000000000 possible shuffles of a pack of cards which is also mind blowing but really just an excuse for me to wheel out this excellent link again https://czep.net/weblog/52cards.html https://czep.net/weblog/52cards.html
- Dylan16807 7y ago
  Or in the typical way of measuring entropy, about 2^225. So you can make a connection through these impossibly big numbers into levels of security for cryptography, and see how this particular amount of impossible is right in the middle of typical use. It's also interesting to think about how a deck of cards is both elegant and unwieldy as a way to store a key.
  - alex_stoddard 7y ago
    https://en.wikipedia.org/wiki/Solitaire_(cipher) https://en.wikipedia.org/wiki/Solitaire_(cipher) "The Solitaire cryptographic algorithm was designed by Bruce Schneier at the request of Neal Stephenson for use by field agents in his novel Cryptonomicon, enabling them to communicate securely without having to rely on electronics or having to carry incriminating tools, It was designed to be a manual cryptosystem calculated with an ordinary deck of playing cards. In Cryptonomicon, this algorithm was originally called Pontifex to hide the fact that it involved playing cards."
- BurningFrog 7y ago
  And yet sorting a deck of cards is vastly easier than solving a Rubik's Cube. Which shows that these numbers don't at all measure puzzle difficulty.
  - Dylan16807 7y ago
    Easier by what metric, though? Someone with moderate practice at both can do the cube faster. Someone with zero practice won't know what you mean by "sorting" a deck of cards. The cards only win at going backwards from goal to algorithm. And do we have any idea what God's Number is for sorting a deck of cards?
    - rocqua 7y ago
      Depending on what you will define as an 'operation' there are some probably some easy numbers. I think the simplest answer is 52. You need to place each card correctly once. Things get complicated if you account for searching in the deck, but we don't account for looking at the rubiks cube either. A more interesting question is 'what if we count how far we need to move the card' (i.e. moving it from position 1 to 52 is 52 steps, and from 1 to 3 is only 2 steps). This is a question of simple group theory though. Shuffling cards is the group S_52. The 'moving a card one position' is working with 51 simple operations of swap (idx, idx + 1). This is essentially bubble sort.
    - BurningFrog 7y ago
      I can also do the cube faster. That's completely separate from how easy the problem is to solve for a novice. Yes, obviously the solver has to understand what the desired solved state is in each case. If you can't see that sorting a deck of cards is easier, I doubt I can explain it to you, but the metric I'd use is give each problem to 100 people, and see how well each group does.
    - jerf 7y ago
      "And do we have any idea what God's Number is for sorting a deck of cards?" It depends on your definition of sorting. Since we have a known, finite, compact set of incoming inputs, essentially the numbers 1-52, as rocqua says we can use a bin sort with 52 bins and sort the cards in essentially 52 operations. This is physically practical as well. Generally the "constant overhead" on it is such that people will sort with something more like a merge sort, but it's certainly completely practical to find a space large enough to hold the entire deck laid out physically. If you limit sorting to the computer science sense of the term, in which the sort must be accomplished by swaps, I expect it could be worked out pretty easily by people skilled in the art of sorting, again because the small constant size and input makes it relatively easy. I know it can be proved that this style of sort can't take less than O(n log n) comparisons, but I'm not 100% sure I can guarantee it's literally ciel(52 * log2 52). Somebody else may be able to.
twright 7y ago
Subtract one and it's a prime number, so you can say there are prime number of unsolved states. This is only true for some cubes of different sizes [1]. [1]: https://www.speedsolving.com/forum/threads/a-collection-of-cubing-curiosities.31714/#post-630928 https://www.speedsolving.com/forum/threads/a-collection-of-c...

And there are 80658175170943878571660636856403766975289505440883277824000000000000 possible shuffles of a pack of cards which is also mind blowing but really just an excuse for me to wheel out this excellent link again https://czep.net/weblog/52cards.html https://czep.net/weblog/52cards.html

Dylan16807 7y ago
Or in the typical way of measuring entropy, about 2^225. So you can make a connection through these impossibly big numbers into levels of security for cryptography, and see how this particular amount of impossible is right in the middle of typical use. It's also interesting to think about how a deck of cards is both elegant and unwieldy as a way to store a key.
- alex_stoddard 7y ago
  https://en.wikipedia.org/wiki/Solitaire_(cipher) https://en.wikipedia.org/wiki/Solitaire_(cipher) "The Solitaire cryptographic algorithm was designed by Bruce Schneier at the request of Neal Stephenson for use by field agents in his novel Cryptonomicon, enabling them to communicate securely without having to rely on electronics or having to carry incriminating tools, It was designed to be a manual cryptosystem calculated with an ordinary deck of playing cards. In Cryptonomicon, this algorithm was originally called Pontifex to hide the fact that it involved playing cards."
BurningFrog 7y ago
And yet sorting a deck of cards is vastly easier than solving a Rubik's Cube. Which shows that these numbers don't at all measure puzzle difficulty.
- Dylan16807 7y ago
  Easier by what metric, though? Someone with moderate practice at both can do the cube faster. Someone with zero practice won't know what you mean by "sorting" a deck of cards. The cards only win at going backwards from goal to algorithm. And do we have any idea what God's Number is for sorting a deck of cards?
  - rocqua 7y ago
    Depending on what you will define as an 'operation' there are some probably some easy numbers. I think the simplest answer is 52. You need to place each card correctly once. Things get complicated if you account for searching in the deck, but we don't account for looking at the rubiks cube either. A more interesting question is 'what if we count how far we need to move the card' (i.e. moving it from position 1 to 52 is 52 steps, and from 1 to 3 is only 2 steps). This is a question of simple group theory though. Shuffling cards is the group S_52. The 'moving a card one position' is working with 51 simple operations of swap (idx, idx + 1). This is essentially bubble sort.
  - BurningFrog 7y ago
    I can also do the cube faster. That's completely separate from how easy the problem is to solve for a novice. Yes, obviously the solver has to understand what the desired solved state is in each case. If you can't see that sorting a deck of cards is easier, I doubt I can explain it to you, but the metric I'd use is give each problem to 100 people, and see how well each group does.
  - jerf 7y ago
    "And do we have any idea what God's Number is for sorting a deck of cards?" It depends on your definition of sorting. Since we have a known, finite, compact set of incoming inputs, essentially the numbers 1-52, as rocqua says we can use a bin sort with 52 bins and sort the cards in essentially 52 operations. This is physically practical as well. Generally the "constant overhead" on it is such that people will sort with something more like a merge sort, but it's certainly completely practical to find a space large enough to hold the entire deck laid out physically. If you limit sorting to the computer science sense of the term, in which the sort must be accomplished by swaps, I expect it could be worked out pretty easily by people skilled in the art of sorting, again because the small constant size and input makes it relatively easy. I know it can be proved that this style of sort can't take less than O(n log n) comparisons, but I'm not 100% sure I can guarantee it's literally ciel(52 * log2 52). Somebody else may be able to.

twright 7y ago

Subtract one and it's a prime number, so you can say there are prime number of unsolved states. This is only true for some cubes of different sizes [1]. [1]: https://www.speedsolving.com/forum/threads/a-collection-of-cubing-curiosities.31714/#post-630928 https://www.speedsolving.com/forum/threads/a-collection-of-c...