# 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... Commented Dec 24, 2012 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)? Commented Dec 24, 2012 at 11:15
• @Dennis The Q demands the best solution in the least time. Commented Dec 24, 2012 at 11:20

Worked out a Dynamic Programming Approach to the problem -

``````int t[n][2]; //Stores grid values
int b[n]; //Stores best solution upto a particular column
b[0]= t[0][1]-t[0][0]; //Compute score for first column (Absolute Value)
b[1]= Max (b[0] + 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? Commented Dec 24, 2012 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. Commented Dec 27, 2012 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[0] => The score for mini tiles of column 0

Best[1] => 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[100001][2], B[100001], i, j;
cin>>n;
for(i=0;i<2;i++)
{
for(j=0;j<n;j++)
cin>>A[j][i];
}

B[0] = abs(A[0][0] - A[0][1]);
B[1] = max( B[0] + abs(A[1][0]-A[1][1]) , abs(A[1][0]-A[0][0])+abs(A[1][1]-A[0][1]) );
for(i=2;i<n;i++)
B[i] = max( B[i-1] + abs(A[i][0]-A[i][1]) , B[i-2] + abs(A[i][0]-A[i-1][0]) + abs(A[i][1]-A[i-1][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. Commented Sep 5, 2015 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. Commented Sep 5, 2015 at 18:04