### ivan.popelyshev's blog

By ivan.popelyshev, 9 years ago, translation, Congratulations to Petr Mitrichev impressive victory!

We need to assign some number from 0 to 6 to each of the 14 squares. Note that if you take the solution and apply some permutation of digits to the field, you obtain another correct solution. So, the solution is characterized by division of 14 squares to pairs. If we have such a partition, then it is possible to generate a 7! corresponding solutions. Count of possible partitions is 13!! = 13·11·9·7·5·3 = 135135 . It is easily to verify the correctness for each of the 100k options.

With up to rotations, count of all field configurations that have solutions is about 6000. The largest number of solutions - 22·7!.

Подколки:
1) If you do not optimize the solution in 7! time, you can get a TL. As was shown in the comments it’s enough to optimize 7 times.
2) You would think that the squares are divided into two classes - 7 squares that have double dominoes, and 7, in which it is not present. If we talk in terms of graphs there are 7 vertices with degree 2, and 7 with degree of 4. Clearly, two vertices of degree 2 can not correspond to a single digit, otherwise we get two double dominoes. With this division is sufficient to iterate over 7! possible matches vertices of the second type to vertices of the first type.  Double domino 4-4 split between the two squares. There are 6 vertices of degree 2 and 8 vertices of degree. Challenge Succeeded.
Furthermore: Here for two double dominoes lie between squares!

And bonus, one of the most beautiful configurations with several holes: Disconnected configuration with solutions don’t exist :( Tutorial of Yandex.Algorithm 2011: Finals  Comments (0)