Book of programming problems

Complexity (1-100): 23

There is a full set of 28 dominoes: (0,0), (0,1),...,(6,6). For the given natural numbers Sum and N print the correct layout of exactly N tiles so that the number of spots on the tiles is equal to Sum.The correct layout is a row of tiles such that each succeeding tile matches the preceeding: (a,b) (b,c) (c,d) ... If there is no correct layout, print the error messasge.

Examples:

• Sum=20, N=4, the layout is (0,1)(1,1)(1,6)(6,5)
• Sum=5, N=4, no layout possible (Sum is too small)
• Sum=92, N=10, the layout is (2,6)(6,6)(6,5)(5,5)(5,4)(4,4)(4,6)(6,3)(3,5)(5,2)

First, let us roughly estimate the maximum and minimum total number of spots k tiles can have. These are the spot count for all of the 28 tiles:


Therefore, the minimum(maximum) number of spots of a one tile is 0(12). For two tiles, this range is [1; 12+11], for three tiles - [1+2, 12+11+10] and so on... Let minCount(k) and maxCount(k) be the range within k tiles fit.

We use a simple backtracking algorithm. We can represent a correct domino layout by a vector M=(m₁,...,m_n):


At each step, we enlarge the vector by adding m_n+1 at the end, which is the same as adding the tile (m_n, m_n+1) and the end of the row. For each m_n+1 we should check that the following comditions are met:

• the new tile (m_n, m_n+1) did not appear earlier in the chain;
• the difference between the required sum and the cost of the current solution (m₁, m₂) ... (m_n, m_n+1) can be filled with N-n tiles, that is, this value is between minCount(N-n) and maxCount(N-n).

When we achive the required chain length and the required number of spots, that chain is the solution.