wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Domino Pieces 
        
(Message started by: Dudidu on Jan 7th, 2004, 2:05am)
Title: Domino Pieces
Post by Dudidu on Jan 7th, 2004, 2:05am
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.
Title: Re: Domino Pieces
Post by Barukh on Jan 7th, 2004, 8:15am
The first idea that came to my mind was: [hide]isn't this related to Euler's path in a graph?[/hide] ::)
Title: Re: Domino Pieces
Post by Dudidu on Jan 7th, 2004, 8:29am

on 01/07/04 at 08:15:29, Barukh wrote:
The first idea that came to my mind was: <Hide>.
It is related (I warned everybody that it will be easy) :P...
Well done Barukh !
Title: Re: Domino Pieces
Post by Barukh on Jan 7th, 2004, 10:50am

on 01/07/04 at 08:29:16, Dudidu wrote:
It is related (I warned everybody that it will be easy) :P...
Well done Barukh !


Thanks. Let me ask a related question: Is there an efficient algorithm to calculate the number of possible placements?
Title: Re: Domino Pieces
Post by Dudidu on Jan 8th, 2004, 4:11am

on 01/07/04 at 10:50:32, 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. [hide] the domino case - where there are at most 6 vertices in the corresponding graph[/hide]) 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 ([hide]can't be used in the case of the dominos[/hide]), 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...
Title: Re: Domino Pieces
Post by Barukh on Jan 8th, 2004, 6:10am

on 01/08/04 at 04:11:45, 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.
Title: Re: Domino Pieces
Post by THUDandBLUNDER on Jan 8th, 2004, 7:21am
Here's an interesting article concerning dominoes and graphs.

http://www.maa.org/editorial/mathgames/mathgames_12_15_03.html
Title: Re: Domino Pieces
Post by Dudidu on Jan 11th, 2004, 8:11am

on 01/08/04 at 06:10:55, 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 (http://mathworld.wolfram.com/MatrixTreeTheorem.html) (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)?
Title: Re: Domino Pieces
Post by Barukh on Jan 11th, 2004, 11:44am

on 01/11/04 at 08:11:35, 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? ::)
Title: Re: Domino Pieces
Post by Dudidu on Jan 14th, 2004, 1:11am

on 01/11/04 at 11:44:21, 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 [hide]11160261000000[/hide]. Barukh, I hope that you have reached the same result...

P.S. regarding the general question, I'm still thinking...
Title: Re: Domino Pieces
Post by Barukh on Jan 14th, 2004, 11:28am

on 01/14/04 at 01:11:57, 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 [hide]7,959,229,931,520[/hide] of these. If we count closed placements, this number should be divided by 28.
Title: Re: Domino Pieces
Post by Dudidu on Jan 14th, 2004, 11:58pm

on 01/14/04 at 11:28:11, 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:[hide]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.[/hide]

Waiting for your response...
Title: Re: Domino Pieces
Post by Barukh on Jan 15th, 2004, 11:57pm
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  :-/?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board