Author |
Topic: Domino Pieces (Read 1508 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Domino Pieces
« on: Jan 7th, 2004, 2:05am » |
 Quote  Modify
|
This is a quite easy question (for my opinion), anyway...
You are given a set of domino pieces, devise an efficient algorithm that checks whether these pieces can be legally placed in a continuous line/sequence.
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
|
Re: Domino Pieces
« Reply #1 on: Jan 7th, 2004, 8:15am » |
Quote Modify
|
The first idea that came to my mind was: isn't this related to Euler's path in a graph? 
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Domino Pieces
« Reply #2 on: Jan 7th, 2004, 8:29am » |
Quote Modify
|
on Jan 7th, 2004, 8:15am, Barukh wrote:| The first idea that came to my mind was: <Hide>. |
|
It is related (I warned everybody that it will be easy)  ...
Well done Barukh !
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Domino Pieces
« Reply #3 on: Jan 7th, 2004, 10:50am » |
Quote Modify
|
on Jan 7th, 2004, 8:29am, Dudidu wrote:
It is related (I warned everybody that it will be easy) ...
Well done Barukh !
|
|
Thanks. Let me ask a related question: Is there an efficient algorithm to calculate the number of possible placements?
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Domino Pieces
« Reply #4 on: Jan 8th, 2004, 4:11am » |
Quote Modify
|
on Jan 7th, 2004, 10:50am, Barukh wrote:| Let me ask a related question: Is there an efficient algorithm to calculate the number of possible placements? |
|
Barukh, do you ask about this case (i.e. the domino case - where there are at most 6 vertices in the corresponding graph) or do you ask about the general case ?
If you're refering to the general case then, as far as I know, there is a polynomial time algorithm to calculate the number of Euler tours in a directed graph (can't be used in the case of the dominos), but it is still not known whether there is a a polynomial time algorithm to calculate the number of Euler tours in an undirected graph...
Waiting for your reply...
|
| « Last Edit: Jan 8th, 2004, 4:13am by Dudidu » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Domino Pieces
« Reply #5 on: Jan 8th, 2004, 6:10am » |
Quote Modify
|
on Jan 8th, 2004, 4:11am, Dudidu wrote:
Barukh, do you ask about this case ... or do you ask about the general case ? |
|
I was asking about the domino case.
Quote:| If you're refering to the general case... |
|
Interesting... I would like to see the results.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Domino Pieces
« Reply #6 on: Jan 8th, 2004, 7:21am » |
Quote Modify
|
Here's an interesting article concerning dominoes and graphs.
http://www.maa.org/editorial/mathgames/mathgames_12_15_03.html
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Domino Pieces
« Reply #7 on: Jan 11th, 2004, 8:11am » |
Quote Modify
|
on Jan 8th, 2004, 6:10am, Barukh wrote:| Interesting... I would like to see the results. |
|
The result (polynomial time algorithm) on the directed case can be found in W. T. Tutte. Graph Theory, volume 21 of Encyclopedia of Mathematics: Combinatorics. Addison-Wesley, 1984 and is releated to Kirchhoff's Matrix (don't ask me how since I don't know).
Some ideas on the undirected case can be found in P. Tetali and S. Vempala. Random sampling of Euler tours. Algorithmica, 30(3):376-385, 2001.
In either case, probably a trip to the library will be needed...
Quote:| I was asking about the domino case. |
|
Do you have an answer for this question or is it a challenge (or both)?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Domino Pieces
« Reply #8 on: Jan 11th, 2004, 11:44am » |
Quote Modify
|
on Jan 11th, 2004, 8:11am, Dudidu wrote:| In either case, probably a trip to the library will be needed... |
|
That's OK. And thanks for the references!
Quote:| Do you have an answer for this question or is it a challenge (or both)? |
|
a) I know a partial answer.
b) It's a challenge!
For instance, how many placements exist for the full set of dominos?
P.S. I haven't looked at the THUD&BLUNDER's referenced article - maybe it provides more answers?
|
| « Last Edit: Jan 11th, 2004, 11:45am by Barukh » |
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Domino Pieces
« Reply #9 on: Jan 14th, 2004, 1:11am » |
Quote Modify
|
on Jan 11th, 2004, 11:44am, Barukh wrote:| For instance, how many placements exist for the full set of dominos? |
|
In this case we actually looking for the number of Euler tours in a "modified" K7 graph (the modification is that we have self-edges for each vertex). Counting all of them (combinatorically), I get 11160261000000. Barukh, I hope that you have reached the same result...
P.S. regarding the general question, I'm still thinking...
|
| « Last Edit: Jan 14th, 2004, 1:15am by Dudidu » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Domino Pieces
« Reply #10 on: Jan 14th, 2004, 11:28am » |
Quote Modify
|
on Jan 14th, 2004, 1:11am, Dudidu wrote:| Barukh, I hope that you have reached the same result... |
|
My sources tell me something different: assuming that we count the open-ended placements, there are 7,959,229,931,520 of these. If we count closed placements, this number should be divided by 28.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Domino Pieces
« Reply #11 on: Jan 14th, 2004, 11:58pm » |
Quote Modify
|
on Jan 14th, 2004, 11:28am, Barukh wrote:
My sources tell me something different: assuming that we count the open-ended placements, there are...
|
|
Barukh hi,
I was refering open-ended placements (i.e. euler tours). Can you explain how you got your result ?
Here's the logic behind my solution:Lets calculate the number of Euler tours in K7 (corresponds to the domino pieces that are not same-sided (e.g. not from the form of [x|x])): first, we choose a starting vertex (7 options). Initially, you can leave it through 6 outgoing edges, but notice that the next time you return to this vertex, you'll have only 6-2 = 4 unused edges (that you can leave on), and the third time, only 2 edges. For the other vertices the logic is different but similar, because they are initially reached by an edge you can initially leave it through 5 outgoing edges, in the next time, you can leave it through 3... Thus, the number of Euler tours on K7 is 7 * 6 * 4 * 2 * (5 * 3 * 1)6.
Now, we will add the same-sided domino pieces – it is easy to see that each every vertex occurs 3 times in the K7 Euler tour, except the starting vertex that occurs 4 times. Each such occurrence can be used to insert the corresponding same-sided domino. Thus, the previous result should be multiplied by 36 * 4 reaching to a total of 11,160,261,000,000.
Waiting for your response...
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Domino Pieces
« Reply #12 on: Jan 15th, 2004, 11:57pm » |
Quote Modify
|
Dudidu, the source I was talking about is a book by Ball & Coxeter “Mathematical Recreations and Essays” (IMHO, an excellent book). As in your approach, it’s based on counting the number of Euler tours on a full graph of seven vertices K7 – denote it N. Note, however, that because every vertex in this graph has an even degree, every Euler tour will be necessarily closed (aka Euler cycle), so that N is actually the number of closed domino placements without double pieces. Taking into accout the double pieces and observing that an open-ended placement may be obtained by breaking the cycle at any piece, we obtain the number 3728N.
The big problem is to compute the N. This is done recursively by removing one vertex at a time and counting the number of Euler tours in the reduced graphs – until we reach the graph with only 2 vertices, whose Euler tours are calculated straightforwardly. To be more specific: take any vertex in K7, say 0. The six edges of this vertex may be connected into pairs in 3*5 = 15 different ways. Every such pairing determines all the closed domino placements with the particular pairing of 0-pieces, for instance: …[1|0][0|2] … [3|0][0|4]…[5|0][0|6]… . Replacing every pair with a single edge, we get a graph without vertex 0. So, in fact, K7 is reduced to 15 graphs, but because of its symmetry, all the reduced graphs are topologically equivalent. If we count N’ - the number of Euler cycles in any of the reduced graphs K’ – then obviously N = 15N’.
We proceed by reducing the graph K’. However, because it’s not symmetric anymore, different pairings won’t result in topologically equivalent graphs (that’s where the combinatorial approach is broken and indicates the flaw in your approach). So, actually, that’s a Dynamic Programming approach suitable for any graph whatsoever.
P.S. I didn't find any information on this on the web  , did you  ?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print