The number of "cube paths" (both canonical and non-canonical) of length 15, and the total number of cube states at distance 15, are exactly known.
One gold star to the first person to put all three numbers in the same post.
Which 3x3x3 positions require at least 20 moves to solve?
- Thread starter learypost
- Start date
-
- Tags
- god's number minimum moves
The number of "cube paths" (both canonical and non-canonical) of length 15, and the total number of cube states at distance 15, are exactly known.
One gold star to the first person to put all three numbers in the same post.
Stefan
Legend
The "number" of paths leading to 15f* states (I think that's what he said (not sure it's what he meant)) is "known" as well.
If this is true, the margin must be too small to contain its number.
Renslay
Legend
Actually, the "five states in one byte" sounds very easy to implement. Maybe I try to do a 2x2 look-up table in that way. Then 3.674.160 states means 718 kilobytes to store. I wonder about the running time... The "cube to state" function is also easy: permutation ranking combined with the orientation number (a number in base 3), i.e., the orientation "CCW-N-CW-CCW-N-CW" means 201201[SUB]3[/SUB], which can be decoded as 532. So, the final number should be
state_to_number = PR * 3^6 + ON,
where PR is the permutation rank (from 0 to 7!-1), ON is the orientation number (from 0 to 3^6-1). It should work, right?
Last edited:
Dapianokid
Regular
- Joined
- Aug 24, 2013
- Messages
- 214
I know that the number of length 15 states are known, but I was referring to the (unknown) number of length 15 paths that lead to the same (length 15) state.
Stefan
Legend
Ooh, I just had another idea. For the 3x3x3, about 1.146 bits per state suffice! Guess how.
Renslay
Legend
Uhm... Huffman-encode the whole table?
Can you tell me the exact number (I guess 1.146 is just a rounding). Maybe I can figure out from that.
AvGalen
Premium Member
If you are going to theoretically optimise a practically too large storage by an insignificant amount I am guessing you are taking advantage of the "only 1 in 12 states can be solved". I am also going to see nonononononononononononoNEIN
Renslay
Legend
We are considering only the solvable states.
Stefan
Legend
Uhm... Huffman-encode the whole table?
Can you tell me the exact number (I guess 1.146 is just a rounding). Maybe I can figure out from that.
Yes that's rounded. No I can't tell you the exact number.
You're close. What number of bits do you get with Huffman?
(Even less might be possible, but I just have an idea and can't analyze it and it depends on something arbitrary anyway)
For the 3x3 that's true, but for other puzzles this might actually be a useful idea.
Last edited:
AvGalen
Premium Member
Yes, but you could save a bit (pun intended) by not saving the entire state but just enough so that you could calculate the entire state because you know it should be solvable
Stefan
Legend
I get the feeling you don't know what we're doing. We're already kinda using zero bytes to encode the entire state.
Explanation for those who don't know what we're talking about: Instead of storing states along with their solutions, we're storing *neither*.
We encode a state by turning it into a number from 0 to n-1, where n is the number of possible states (about 43 quintillion for 3x3 if we ignore symmetry). Now instead of *storing* that number, we just *use* it as a pointer into a large list, one list entry for each state. And such an entry is not a solution, not even just a move, but only the distance to the solved state modulo 3. So if a state can optimally be solved in 17 moves, we store "2" for it. Then to find a solution for a state, we compare its mod3dist to those of its neighbour states to determine a move that gets us closer to solved, and repeat until we're at solved.
Since each such mod3dist value is 0, 1 or 2, we can encode it in two bits. But since two bits also allow the value 3 and we're never using it, we can do better. For example we can combine five consecutive values into a number from 0 to 3[sup]5[/sup]-1=242, which is less than 2[sup]8[/sup]-1=255 so we can store the values for five states in eight bits (one byte), averaging 8/5=1.6 bits per state. Now here we're never using the numbers 243 to 255 that eight bits also allow, so we're still wasting storage opportunity. This then is where arithmetic coding comes in, which kinda really uses *fractions* of bits and we don't have any such waste anymore.
Last edited:
whauk
Veteran
why don't you write out the whole number in base 3 and store it? my intuition makes me feel that this requires less space. instead of loosing space every fifth state you would only loose it once. also if this number is "very big" (begins with a 2) you could try to attach a certain premove, conjugate every state, or exchange every state with its inverse and hope to make the number significantly smaller. ( -> it begins with lots of zeros)
Stefan
Legend
What number do you mean?
Renslay
Legend
I think he means the whole distance table mod 3. Since every record (row) is either 0, 1 or 2, the whole table is just one number in base 3, with 4.3*10^19 digits.
Stefan
Legend
I suspected that's what he meant, but nobody had been talking about that number, and I can't make sense of the rest of the message with it (the "very big (begins with a 2)" etc).
Is the next significant digit 2?
Stefan
Legend
Might be. I actually got 1.14613859026 but it's not an accurate calculation (partly because you don't provide complete accurate data anyway
).Edit: I get 1.1451205786459624 when using all your data (from cube20.org).
whauk
Veteran
ok here is in detail what i meant:
every cube state receives a distinct number n (e.g. when it is the nth position in the hamiltonian circle that was already found). in the following i will refer to a cube state with the number n as (n). then we create a number in base 3 by writing the optimal solution length for state (n) mod 3 at digit n. this number then contains exactly the same information as your look up table.
(not so important idea for making the number smaller and therefore easier to store):
so now we attempt to store that number and hope that it requires "a small amount of space". but if this number happens to be "big" (=> requires much storage volume) one can try to make it smaller by applying inner automorphisms to the cube group (=> every cube state) so that the number becomes smaller (=> requires less storage volume). the number becomes significantly smaller if you try to get as many zeros as possible to the first digits of the number.
the number is certainly smaller than 3^(4.4*10^19). (this is 3^(~number of cube states)). the number of digits in base 2 of this number (equals the amount of bits we need for storing it) is log2(3^(4.4*10^19)) and we therefore need (log2(3^(4.4*10^19)))/(4.3*10^19)=0.477121 bits per cube state. (result obtained using the correct number of cube states).
every cube state receives a distinct number n (e.g. when it is the nth position in the hamiltonian circle that was already found). in the following i will refer to a cube state with the number n as (n). then we create a number in base 3 by writing the optimal solution length for state (n) mod 3 at digit n. this number then contains exactly the same information as your look up table.
(not so important idea for making the number smaller and therefore easier to store):
so now we attempt to store that number and hope that it requires "a small amount of space". but if this number happens to be "big" (=> requires much storage volume) one can try to make it smaller by applying inner automorphisms to the cube group (=> every cube state) so that the number becomes smaller (=> requires less storage volume). the number becomes significantly smaller if you try to get as many zeros as possible to the first digits of the number.
the number is certainly smaller than 3^(4.4*10^19). (this is 3^(~number of cube states)). the number of digits in base 2 of this number (equals the amount of bits we need for storing it) is log2(3^(4.4*10^19)) and we therefore need (log2(3^(4.4*10^19)))/(4.3*10^19)=0.477121 bits per cube state. (result obtained using the correct number of cube states).
Last edited:
Remember in all of this: the most obvious "optimization" is to store the distances for equivalence classes mod M+inv, so the "base" number is log(3)/log(2)/96 or 0.01651 bits per "state"---to start with.
Any improvement to this must either work on these equivalence classes, or obtain substantially less than 0.01651 bits per state, just to be in the running.
I don't think the Hamiltonian path found "works" mod M+inv.
Any improvement to this must either work on these equivalence classes, or obtain substantially less than 0.01651 bits per state, just to be in the running.
I don't think the Hamiltonian path found "works" mod M+inv.
Similar threads
