## 211 - The Domino Effect

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

### 211 - The Domino Effect

Maybe I don't understood what is a valid board of bones
for a given board of pips but I think that for any board
of pips, including the ones in the sample output, there are
a lot of boards of bones.

For example, for the for the first board in the sample input,

5 4 3 6 5 3 4 6
0 6 0 1 2 3 1 1
3 2 6 5 0 4 2 0
5 3 6 2 3 2 0 6
4 0 4 1 0 0 4 1
5 2 2 4 4 1 6 5
5 5 3 6 1 2 3 1

the sample output has only one solution but I think that there
are several trivial others like:

[5 4] [3 6] [5 3] [4 6]
[0 6] [0 1] [2 3] [1 1]
[3 2] [6 5] [0 4] [2 0]
[5 3] [6 2] [3 2] [0 6]
[4 0] [4 1] [0 0] [4 1]
[5 2] [2 4] [4 1] [6 5]
[5 5] [3 6] [1 2] [3 1]

replacing the pairs [a b] by pip[ a ][ b ] pip[ a ][ b ]:

24 24 22 22 21 21 25 25
7 7 2 2 15 15 8 8
15 15 27 27 5 5 3 3
21 21 18 18 15 15 7 7
5 5 11 11 1 1 11 11
17 17 16 16 11 11 27 27
26 26 22 22 9 9 10 10

or
_ _ _ _ _ _ _ _
5 4 3 6 5 3 4 6
0 6 0 1 2 3 1 1
- - - - - - - -
_ _ _ _ _ _ _ _
3 2 6 5 0 4 2 0
5 3 6 2 3 2 0 6
- - - - - - - -
4 0 4 1 0 0 4 1
5 2 2 4 4 1 6 5
- - - - - - - -
[5 5][3 6][1 2][3 1]

replacing the vertical pairs between _ e - e the horizontal pairs between []:

6 25 4 13 17 19 11 13
6 25 4 13 17 19 11 13
21 15 28 17 4 16 3 7
21 15 28 17 4 16 3 7
24 3 16 11 5 2 25 12
24 3 16 11 5 2 25 12
26 26 22 22 9 9 10 10

is this correct ???
broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada
I don't think that's correct. for instance, you have the [0 4] domino
repeated twice (the second time as [4 0]). But there is only one of each
domino, so that layout isn't valid.

When i solved this problem I assumed that each domino had to be used
exactly once.

Hope this helps.
AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:
Thank you very much.
Now I understand this problem.
zizi
New poster
Posts: 7
Joined: Fri Jan 30, 2004 4:51 am

### 211

I use DFS for this problem but it was very slow to get the result. What's the best solution for this problem
junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

### Re: 211

zizi wrote:I use DFS for this problem but it was very slow to get the result. What's the best solution for this problem
I believe DFS is the correct method to solve this.. but you have to add in a lot of pruning.
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

### 211: minor error in presented output

I believe there is an error in the output as presented in the description for 211. In the first problem instance, the first column is lined up under the 'o' in 'Layout': column 4. However, in the second, it falls under the 'u', which is column 5. I cannot conceive how this could have been output by any reasonable program. And since my program (which adds the initial space in all cases, following the most common usage) got AC on the first attempt, I believe the pip data for Layout #1 is improperly justified.
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"
Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

### About the output

Do not forget to add a newline after the last line of output.
adelar
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

### Test Cases

thanks, I got AC.