# Domino Solitaire Algorithm

Problem Statement - Given a 2xN grid of numbers, the task is to find the most profitable tiling combination (each tile covers 2x1 cells; vertically or horizontally) covering all tiles.

I thought of approaching it in the greedy way, enqueuing the max possible for any cell, but it has a fallback that a low-profit choice at i, could yield a greater profit at i+n tiles.

So what should be the approach?

EDIT - Test Data Range - N<=105

Source - INOI 2008 Q Paper

UPDATE - Working out the plausibility of a Dynamic programming Approach.

UPDATE 2 - Worked out an answer using DP.

• @Dennis Test Data Range is N<=10^5. Brute-force, would be the last-resort. Still, I'd be interested in knowing a better approach... – 7Aces Dec 24 '12 at 11:11
• Deleted my previous comment, are you interested in finding the best solution only, or in finding a good solution in a reasonable time (thus resort to heuristics)? – Dennis Jaheruddin Dec 24 '12 at 11:15
• @Dennis The Q demands the best solution in the least time. – 7Aces Dec 24 '12 at 11:20

Worked out a Dynamic Programming Approach to the problem -

``````int t[n]; //Stores grid values
int b[n]; //Stores best solution upto a particular column
b= t-t; //Compute score for first column (Absolute Value)
b= Max (b + Score for column 1 vertically, Score for first 2 horizontal columns);
for i=0...n
b[i]= Max ( b[i-1] + Score for column i vertically, b[i-2] + Score for horizontal columns i & i-1);
print b[n-1];
``````

Works efficiently on the given data set, with a linear time complexity!

• +1 Excellent solution and question. Any reasons why you feel Dynamic Programming Approach was appropriate? Is this possible with brute force and if so how would it compare performance wise? – maple_shaft Dec 24 '12 at 13:12
• Note that the performance may be improved if you also run it on the reversed/rotated version of your testset. @maple_shaft Given the size of the testset brute force would probably not be possible. – Dennis Jaheruddin Dec 27 '12 at 9:00

Here is one way to approach/describe the problem:

When looking at the 2xN grid, you can see that any tiling is uniquely defined in the following way:

For the most left block, see if it is horizontal or vertical. Then look at the next block.

Suppose 2 stands for horizontal and 1 stands for vertical your Tiling 1 can be written as: 121 whilst Tiling 2 can be written as 22

Given each vector, calculating the total cost should be straightforward.

Now you can use this algorithm:

1. Find a starting position (probably your own algorithm can do the trick here)
2. Given a window length (say 5) try all combinations of ones and zeros within the window and calculate what the maximum improvement is.
3. Optional: Execute this improvement
4. Shift the window, so instead of looking at the first 5 odd columns now look at odd column 2 to 6
5. If you are not yet at the end, go to step 2, else execute the improvement.
6. Optional: If you found any improvements, you can go to step 1

Here's C++ implementation in O(n) :

Using dynamic programming, we are building from the bottom-up, the best solution for each and every column.

Base cases are column 0 and 1 :

Best => The score for mini tiles of column 0

Best => The maximum out of 2 possible solutions set! (1. Row wise pairing and 2. column wise pairing)

Otherwise :

Best[n] => The maximum out of 2 possible solutions set again (1. The sum of new column and the older best solution B[n-1] 2. The sum of older best solution B[n-2] and the new 2x2 tile square formed)

``````#include<iostream>
using namespace std;
int abs(int n) { if(n < 0) return -1*n ; else return n; }

int main()
{
int n, A, B, i, j;
cin>>n;
for(i=0;i<2;i++)
{
for(j=0;j<n;j++)
cin>>A[j][i];
}

B = abs(A - A);
B = max( B + abs(A-A) , abs(A-A)+abs(A-A) );
for(i=2;i<n;i++)
B[i] = max( B[i-1] + abs(A[i]-A[i]) , B[i-2] + abs(A[i]-A[i-1]) + abs(A[i]-A[i-1]) );

cout<<B[n-1]<<endl;
return 0;
}
``````
• I have used Dynamic Programming (Tabulation). If you could post me the implementation using Memoization, I would be pleased. – Prazzzy Sep 5 '15 at 16:59
• Prazzy, Programmers.SE isn't about writing code for other people. You can propose algorithms or architectural advice. Moreover, the OP was looking for an algorithm/approach to solving the problem. I suggest reading the Help Center's guidelines. – Chris Cirefice Sep 5 '15 at 18:04