Welcome, Guest. Please Login
SLINGING.ORG
 
Home Help Search Login


Pages: 1 2 
Send Topic Print
Not slinging related but I need help ! lol (Read 249 times)
Curious Aardvark
past-administrator
*****
Offline


Taller than the average
Dwarf

Posts: 13965
Midlands England
Gender: male
Not slinging related but I need help ! lol
Dec 5th, 2019 at 11:49am
 
So I think I've come up with a really good item to sell from my laser.

Clear acrylic jigsaws.
No picture to indicate which way up they go.
So each piece could go either way up.

How many combinations are there for a 64 piece jigsaw when you do not know the actual orientation of each piece ?

so an 8x8 grid.
each piece can be either way up.
How many possible combinations would there be ?

Or am i overtaking this lol
Back to top
 

Do All things with Honour and Generosity: Regret Nothing, Envy None, Apologise Seldom and Bow your head to No One  - works for me Smiley
 
IP Logged
 
joe_meadmaker
Slinging.org Administrator
*****
Offline


Slinging Ice is Cool!

Posts: 3303
PA, USA
Re: Not slinging related but I need help ! lol
Reply #1 - Dec 5th, 2019 at 3:49pm
 
I'm sure there's a way to calculate it, but wow, that's going to be a big number.  And it's not just which side of the piece is up, but also how each piece is rotated.  Even if an image on a piece doesn't tell you how it will be rotated, it will normally indicate how the rotation will be oriented with pieces next to it.  Not so if it's blank.

If you haven't seen this, it looks just like what you're describing.  Can't wait to see a prototype.

https://www.youtube.com/watch?v=ks3vbiCSmKI
Back to top
 
 
IP Logged
 
NooneOfConsequence
Slinging.org Moderator
*****
Offline



Posts: 2993
Texas
Re: Not slinging related but I need help ! lol
Reply #2 - Dec 5th, 2019 at 7:41pm
 
Back to top
 

“My final hour is at hand. We face an enemy more numerous and cunning than the world has yet seen. Remember your training, and do not fear the hordes of Judas. I, without sin, shall cast the first stone. That will be your sign to attack! But you shall not fight this unholy enemy with stones. No! RAZOR GLANDES!  Aim for the eyes! May the Lord have mercy, for we shall show none!“  -Jesus the Noodler
 
IP Logged
 
NooneOfConsequence
Slinging.org Moderator
*****
Offline



Posts: 2993
Texas
Re: Not slinging related but I need help ! lol
Reply #3 - Dec 5th, 2019 at 7:54pm
 
Well... the four corners each have two sides. The first one has 8 possible places. The next has 6, then 4, then the last corner has  two. That’s 20 possibilities.

Next, there are 24 edge pieces times two sides. That’s 48+ 46+ 44... down to 2

Finally you have a 6x6 grid in the middle, but these have 4 rotational orientations and two sides. That’s 2x4x(36+35+34...+1)

That’s all your possibilities.
Back to top
 

“My final hour is at hand. We face an enemy more numerous and cunning than the world has yet seen. Remember your training, and do not fear the hordes of Judas. I, without sin, shall cast the first stone. That will be your sign to attack! But you shall not fight this unholy enemy with stones. No! RAZOR GLANDES!  Aim for the eyes! May the Lord have mercy, for we shall show none!“  -Jesus the Noodler
 
IP Logged
 
joe_meadmaker
Slinging.org Administrator
*****
Offline


Slinging Ice is Cool!

Posts: 3303
PA, USA
Re: Not slinging related but I need help ! lol
Reply #4 - Dec 5th, 2019 at 10:57pm
 
Not quite.  If you open the video I linked, the puzzle has what appears to be a corner piece that actually goes in the middle.  Several (what appear to be) edge pieces that go in the middle area.  And two sides of the puzzle have multiple pieces that don't fit the standard edge piece shape.
Back to top
 
 
IP Logged
 
NooneOfConsequence
Slinging.org Moderator
*****
Offline



Posts: 2993
Texas
Re: Not slinging related but I need help ! lol
Reply #5 - Dec 6th, 2019 at 12:16am
 
The math still works out.
If you obfuscate the edges and corners, then it’s actually simpler to calculate:
2x4x(64+63+...1)
Back to top
 

“My final hour is at hand. We face an enemy more numerous and cunning than the world has yet seen. Remember your training, and do not fear the hordes of Judas. I, without sin, shall cast the first stone. That will be your sign to attack! But you shall not fight this unholy enemy with stones. No! RAZOR GLANDES!  Aim for the eyes! May the Lord have mercy, for we shall show none!“  -Jesus the Noodler
 
IP Logged
 
Teg
Interfector Viris Spurii
*****
Offline



Posts: 1115
Central Europe
Gender: male
Re: Not slinging related but I need help ! lol
Reply #6 - Dec 6th, 2019 at 8:07am
 
Isn't it (2*4)^64*64!  ?

So (2*4*64)*(2*4*63)*(2*4*62)*….  assuming corners, edges and central pieces are indistinguishable. For the detail fanatics: I also assume, that field 1 is always in the same corner.

This is approximately 8*10^146 possibilities, i.e. an awful lot.

The exclamation mark (!) is the notation for factorial.

https://en.wikipedia.org/wiki/Factorial#Applications
Back to top
 
 
IP Logged
 
NooneOfConsequence
Slinging.org Moderator
*****
Offline



Posts: 2993
Texas
Re: Not slinging related but I need help ! lol
Reply #7 - Dec 6th, 2019 at 2:29pm
 
Why are you using a factorial?  The factorial equation falsely assumes that multiple pieces can be in the same location. There are 64 pieces with 8 orientations each for the first slot, then 63x8 for the next, and so on. Add it all up, and you only get 16640 possibilities.

Question: answered.


Back to top
 

“My final hour is at hand. We face an enemy more numerous and cunning than the world has yet seen. Remember your training, and do not fear the hordes of Judas. I, without sin, shall cast the first stone. That will be your sign to attack! But you shall not fight this unholy enemy with stones. No! RAZOR GLANDES!  Aim for the eyes! May the Lord have mercy, for we shall show none!“  -Jesus the Noodler
 
IP Logged
 
NooneOfConsequence
Slinging.org Moderator
*****
Offline



Posts: 2993
Texas
Re: Not slinging related but I need help ! lol
Reply #8 - Dec 6th, 2019 at 2:50pm
 
Now how many attempts you need to solve it is a different question:

First pick a piece at random. It is automatically “in the right place”.  That reduces the number of  possibilities by 512.  Depending on whether it’s a corner, edge, or middle piece, you have 2,3 or 4 other pieces that match up with it. If it’s a middle piece, you would have to make no more than 14160 attempts before getting a match, but if you were that unlucky, then you would know that the last four pieces were all matches and you would only have 24 tries to get the next one (worst case) then 16, then 8. 

After matching 4 pieces, you have 8 slots to test with 59 pieces.  That’s 51wrong pieces times 8 orientations worst case. After a very unlucky 10615 tries, you get another match and have 7 more pieces that definitely fit your remaining connections.

... and so on.  The worst case for number of attempts is  maybe in the hundreds of thousands, but way smaller than  8x(64x63x62x...1)

The factorial number is around 1x10^90, or 1 with 90 zeros behind it. That’s waaay too big of a number.
Back to top
« Last Edit: Dec 6th, 2019 at 5:44pm by NooneOfConsequence »  

“My final hour is at hand. We face an enemy more numerous and cunning than the world has yet seen. Remember your training, and do not fear the hordes of Judas. I, without sin, shall cast the first stone. That will be your sign to attack! But you shall not fight this unholy enemy with stones. No! RAZOR GLANDES!  Aim for the eyes! May the Lord have mercy, for we shall show none!“  -Jesus the Noodler
 
IP Logged
 
Teg
Interfector Viris Spurii
*****
Offline



Posts: 1115
Central Europe
Gender: male
Re: Not slinging related but I need help ! lol
Reply #9 - Dec 6th, 2019 at 3:23pm
 
I'm not sure I can follow you.

Let's go slowly and let's make sure we try to answer the same question. Otherwise it's a bit difficult to come to an agreement.

I calculated the number of all possible permutations.
This is: How many possible ways are there, to put 64 pieces in a unique order onto a square field. It does not matter if they match. Just in how many ways can you put them on the board.

I think this is what CA asked. Do both of you, CA and Noone, agree?

In the next step, I propose to do the 2x2 puzzle, without orientation, first. Then work our way up from there.

Fine for you?


---
Modified: Sorry for not putting any actual question mark in the question, but I think its comprehensible  Cheesy If not, feel free to tell me.
Back to top
 
 
IP Logged
 
NooneOfConsequence
Slinging.org Moderator
*****
Offline



Posts: 2993
Texas
Re: Not slinging related but I need help ! lol
Reply #10 - Dec 6th, 2019 at 5:52pm
 
Nope. You calculated all possible permutations with a “superposition” property for the pieces. Superposition implies that two pieces can simultaneously occupy the same grid space.  Only one piece can occupy one of 64 slots at any time though, and once it does, there is one less slot left to occupy.  That restriction reduces the possibilities exponentially. The maximum number of states for an 8x8 puzzle is  16640.
This does, of course, assume that there is only one possible correct position and orientation for each piece. If there are multiple solutions to the puzzle, then that’s different.
Back to top
 

“My final hour is at hand. We face an enemy more numerous and cunning than the world has yet seen. Remember your training, and do not fear the hordes of Judas. I, without sin, shall cast the first stone. That will be your sign to attack! But you shall not fight this unholy enemy with stones. No! RAZOR GLANDES!  Aim for the eyes! May the Lord have mercy, for we shall show none!“  -Jesus the Noodler
 
IP Logged
 
Teg
Interfector Viris Spurii
*****
Offline



Posts: 1115
Central Europe
Gender: male
Re: Not slinging related but I need help ! lol
Reply #11 - Dec 7th, 2019 at 10:01am
 
At least we can agree, that we have to calculate the number of states, i.e. the number of permutations  Grin I'll focus on what I agree with you and leave the rest aside, if I may.

NooneOfConsequence wrote on Dec 6th, 2019 at 5:52pm:
Only one piece can occupy one of 64 slots at any time though, and once it does, there is one less slot left to occupy. 


I agree with that.  For the first piece you have 64 possible choices, for the second piece 63 choices and so on.

My statement is: to calculate the number of all possible permutations, or states, you have to multiply the number of choices you have while placing all pieces. This means: 64*63*62*.... *1 = 64!

As far as I understood your statement, Noone, it is: To calculate the number of all possible states, you have to add the number of possible choices you have while placing all pieces.  This is: 64 + 63 + 62 + ... + 1.
Did I understand you correctly?


We can test this. Let's take a 2x2 square, so 4 pieces. Orientation is neglected for the moment.
Then the two ways give:
4! = 4*3*2*1 = 24 (for multiplication)
or
4+3+2+1 = 10 (for addition)

Appended is a picture with all possible arrangements I found. I count 24 different arrangements.


---
If anyone else is still reading or interested:
http://onlinestatbook.com/2/probability/permutations.html
Here is an introduction into combinatorics. The sections of interest are: Possible orders as well as multiplication rule.





Back to top
 
 
IP Logged
 
joe_meadmaker
Slinging.org Administrator
*****
Offline


Slinging Ice is Cool!

Posts: 3303
PA, USA
Re: Not slinging related but I need help ! lol
Reply #12 - Dec 7th, 2019 at 10:09am
 
NOC's explanation sounds logical to me.  But there's something that still doesn't seem to be adding up.  If you look at the possible permutations for a Rubik's Cube, this number is stated to be more than 43 quintillion.  The specific number is on the Wikipedia page here: https://en.wikipedia.org/wiki/Rubik%27s_Cube.  It's also stated that this is what is achievable by turning the sides of the Cube.  Disassembly would result in a higher number of possibilities.

So in the calculation for a Rubik's Cube, they're taking into account that the corners will need to remain in the corners, etc.  But if we just look at the numbers, the Cube has 9 squares on 6 sides for a total of 54.  Meaning 54 squares and 54 positions for them.  Regarding CA's puzzle, there are 64 pieces and 64 positions.  We're also figuring that each piece can be flipped or rotated.  That makes me think that the puzzle should have a significantly higher number than the Rubik's Cube.
Back to top
 
 
IP Logged
 
Teg
Interfector Viris Spurii
*****
Offline



Posts: 1115
Central Europe
Gender: male
Re: Not slinging related but I need help ! lol
Reply #13 - Dec 9th, 2019 at 3:15pm
 
joe_meadmaker wrote on Dec 7th, 2019 at 10:09am:
That makes me think that the puzzle should have a significantly higher number than the Rubik's Cube.

Exactly.

So here it is:
Case 1 (as in my first post): Corners, edges and middle parts can not be distinguished.
So for the first piece you have 2 sides, 4 rotations and 64 positions to choose from.
As you have to multiply the number of choices.

2*4*64 = 512 possible choices for the first piece.
For the second its: 2*4*63 choices.
Therefore for all pieces: (2*4*64)*(2*4*63)*(2*4*62)* .... (2*4*1) choices.
This can be simplified to: (2*4)^64*64! which you can type into e.g. wolframalpha.com to retrieve: ~ 8*10^146 which is an 8 with 146 zeros after it.

Case 2: you can distinguish the corners, edges and middle pieces.
For the 4 corners you have: (2*4)*(2*3)*... = 2^4 * 4! = 384 choices.
For the 24 edges you have: (2*24)*(2*23)*... = 2^24 * 24! = ~1*10^31 choices
For the 36 middle pieces you have:  (2*4*36)*(2*4*35)*... = 8^36 * 36! = ~1*10^74 choices.

For the total number of choices you have to multiply everything again. So:

2^4 * 4! * 2^24 * 24! * 8^36 * 36! = ~5*10^107

The extra mile:
For the above it was assumed, that overall rotation and flips are different, i.e. rotating the final puzzle gives a different solution, although all pieces are connected in the same way.
If we want to account for this, we have to divide each "total number of choices"  (~ 8*10^146 and ~5*10^107) by (2*4) = 8.

For the maximal number of attempts needed to solve it, you need to define an algorithm, i.e. instructions on how to solve it. Then the question can be answered.
The stupid method: put all pieces on 8 by 8 square and see if they fit together (Hey, it's a legit way to solve it  Cheesy).
You need maximally ~ 8*10^146 attempts, so the number from case 1 above. Because then you have literally tried all possible ways to lay them out.
Back to top
 
 
IP Logged
 
NooneOfConsequence
Slinging.org Moderator
*****
Offline



Posts: 2993
Texas
Re: Not slinging related but I need help ! lol
Reply #14 - Dec 10th, 2019 at 8:48am
 
Come on... Just think about it. Nobody lays down all of the pieces at once. You go one piece at a time. Once you have a match, you don’t need to keep moving a piece and trying it in new places. Also, there are actually 8 correct answers, because you can assemble the puzzle upside down or right side up, and the pieces still fit if you rotate the entire puzzle 90, 180, or 270 degrees.

The grid isn’t fixed in space either. It’s relative to the first piece, so the first piece is automatically in the right place no matter what orientation it’s in.

Back to top
 

“My final hour is at hand. We face an enemy more numerous and cunning than the world has yet seen. Remember your training, and do not fear the hordes of Judas. I, without sin, shall cast the first stone. That will be your sign to attack! But you shall not fight this unholy enemy with stones. No! RAZOR GLANDES!  Aim for the eyes! May the Lord have mercy, for we shall show none!“  -Jesus the Noodler
 
IP Logged
 
Pages: 1 2 
Send Topic Print
(Moderators: joe_meadmaker, woodssj, Rat Man)