This is my first post. In this post I am going to explain how to solve the puzzle IBM Ponder This Dec 2012. I have solved quite a few 'Ponder This' puzzles earlier, and had wanted to blog about techniques I used to solve them. Unfortunately this is the first post about them.
Lets deep dive into the puzzle now. We have to find a 6X6 matrix, with total sum of numbers greater than 90 and that satisfies the constraint of each cell with a number N>1 should have neighbor numbers from 1,2.,,, N-1. Following diagram shows the neighbors of a cell 'c' colored in gray.
Clearly, we don't need to use any negative numbers in the matrix, since that would only reduce the total sum. We can easily see that a matrix full of '1's satisfies the constraint and gives total sum of 6*6=36. We can also observe that the largest number possible in the matrix is '5'. Since a cell can have utmost 4 neighbors, numbers above '5' can't satisfy the constraint.
Once we have identified each cell can hold values from 1, 2,.. 5, we can try guessing the complexity of brute force technique. It is O(5^36)
O(2^84) [using 5
2^2.322]. O(2^84) is not a complexity that can be solved in reasonable time using reasonable computing resources. I would say O(2^40) is achievable with moderate speed processors in a few hours. But O(2^84) is not.
Since brute force is not viable, we need to look for other techniques. What we can observe is that if two successive diagonals have fixed values, then the matrix is divided into two parts and each part has an optimal solution. Following diagram explains this. If diagonals d1, d2 have fixed values then part of the matrix with yellow colored cells will have an optional solution, and part of matrix with blue colored cells will have an optimal solution. What we have done with this observation is that split the problem into subproblems which can be solved independently.
Subproblems being independent is an important aspect. It helps to work on a subproblem without being worried about solution of another subproblem. It splits the complexity as well. For example, we can say the brute force complexity by applying this technique is O( 5^11 * (5^10 + 5^15) ). The term 5^11 represents complexity for having all combinations in diagonals d1 & d2. 5^10 represents the yellow colored part of the problem, and 5^15 represents the blue colored part of the problem.
We can also make use of dynamic programming technique to save the solutions for subproblems, which reduces the complexity further.
Source code:
My approach is as follows:

My approach is as follows:
- Choose all possible combination of values for diagonals d1, d2, d3. Make sure diagonal values d2 satisfy the constraint. [Lines 60-70]
- Solve the yellow colored part of the subproblem [Lines 70-75]
- Solve the grey colored part of the subproblem [Lines 75-78]
- Combine the optimal solutions of the subproblems to see if we have better solultion and note them [Lines 79-84]
get_solution() uses dynamic programming to find the optimal solution.
check_neighbor() is a helper to check if a cell satisfies the problem
constraint.
Runtime:
Solution:
Matrix diagonals are printed. Need to assemble these diagonals. best 91 [(1,), (3, 4), (1, 2, 3), (4, 5, 1, 2), [2, 3, 4, 4, 1], [1, 1, 2, 3, 5, 2], [1, 3, 1, 2, 3], (1,), (1, 2), (2, 5, 4), (4, 4, 3, 1)] Matrix diagonals are printed. Need to assemble these diagonals. best 92 [(3,), (2, 1), (1, 5, 4), (4, 4, 3, 2), [2, 3, 2, 1, 3], [1, 2, 1, 3, 5, 1], [1, 3, 4, 4, 2], (2,), (1, 4), (2, 1, 3), (4, 5, 2, 1)] Matrix diagonals are printed. Need to assemble these diagonals. best 93 [(2,), (3, 1), (1, 5, 2), (4, 2, 4, 4), [2, 3, 3, 1, 3], [1, 4, 1, 4, 2, 1], [1, 5, 2, 5, 3], (3,), (1, 2), (4, 1, 4), (2, 3, 3, 1)] real 480m45.986s user 480m25.329s sys 0m0.704s
Solution:
2
|
1
|
2
|
4
|
3
|
1
|
3
|
5
|
4
|
1
|
2
|
3
|
1
|
2
|
3
|
4
|
5
|
1
|
4
|
3
|
1
|
2
|
3
|
4
|
2
|
4
|
5
|
3
|
1
|
2
|
1
|
1
|
2
|
4
|
1
|
3
|
No comments:
Post a Comment