Page 1 of 1

211 - The Domino Effect

Posted: Tue Aug 06, 2002 7:25 pm
by AlexandreN
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 ???

Posted: Tue Aug 06, 2002 10:02 pm
by broderic
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.

Posted: Wed Aug 07, 2002 2:07 pm
by AlexandreN
Thank you very much.
Now I understand this problem.

211

Posted: Fri Jan 30, 2004 4:53 am
by zizi
I use DFS for this problem but it was very slow to get the result. What's the best solution for this problem

Re: 211

Posted: Fri Jan 30, 2004 8:30 am
by junbin
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.

211: minor error in presented output

Posted: Thu Aug 26, 2004 1:37 am
by GreenPenInc
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.

About the output

Posted: Sat Nov 04, 2006 8:18 am
by Ndiyaa ndako
Do not forget to add a newline after the last line of output.

Test Cases

Posted: Fri Jun 29, 2007 5:31 pm
by adelar
thanks, I got AC.