211 - The Domino Effect

[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 ???

[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.

[AlexandreN]

Thank you very much.
Now I understand this problem.

[zizi]

I use DFS for this problem but it was very slow to get the result. What's the best solution for this problem

[junbin]

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]

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.

[Ndiyaa ndako]

Do not forget to add a newline after the last line of output.

[adelar]

thanks, I got AC.