Getting better at problem solving?

[adam2016]

Hi guys,

One thing that catches me up is my relatively weak problem solving skills, take for example, I was doing a practice problem on Brilliant.org, The problem was as follows. There is a 3*3 grid, each box can accept one number from 1-9(each number can also only be used once), each row and column must add up to 15, also the diagonal columns must also add up to 15. Right off the bat I didn't have a notion of where to start, about 15 minutes later and no avail. I reluctantly clicked "show explanation". After reading the explanation I felt more comfortable. A day later I re-attempted the question on a piece of a paper and got the correct answer but if I hadn't clicked "show explanation" the previous night I without a shadow of a doubt wouldn't have got the correct answer.

15 15 15
[][][] 15
[][][] 15
[][][] 15

I'm not sure how many of you could solve this problem within say 15-30 minutes? I'm not going to give the answer because your reasoning could be helpful.

But having failed to conquer this rudimentary problem, my confidence took a hit. And I've come to a stark conclusion, my problem solving skills aren't the best, I never struggled at math in fact I was always pretty good at it in school but my pattern recognition is awful. And even solving puzzles, I guess I'm not great at that either.

Is there anyway to improve these cognitive skills? (pattern recognition and puzzle solving), does practice really help? And will stuff like crosswords,minesweeper and suduko help at all?

Lastly is there anything you found helpful that improved your logic and problem solving skills?

Thanks

[mbozzi]

Look at this table:
15 - (N=1) = 14 = (5 + 9), (6 + 8)
15 - (N=2) = 13 = (4 + 9), (5 + 8), (6 + 7)
15 - (N=3) = 12 = (4 + 8), (5 + 7)
15 - (N=4) = 11 = (2 + 9), (3 + 8), (5 + 6)
15 - (N=5) = 10 = (1 + 9), (2 + 8), (3 + 7), (4 + 6)
15 - (N=6) = 9 = (1 + 8), (2 + 7), (4 + 5)
15 - (N=7) = 8 = (2 + 6), (3 + 5)
15 - (N=7) = 7 = (1 + 6), (2 + 5), (3 + 4)
15 - (N=9) = 6 = (1 + 5), (2 + 4)

The diagonal box must add with four pairs of numbers (both diagonals, up/down and left/right) to equal 15; only 5 fits the bill from the table above. Therefore 5 is the middle box.
x x x
x 5 x
x x x

Now consider the corner squares. A corner square is added to 3 pairs of numbers to produce 15 (up/down, left/right, and a single diagonal). N = 9, 7, 3, 1 can be eliminated.

We can place 2 and 8 on a diagonal to satisfy 2 + 8 + 5 = 15, and 6 and 4 on the opposite. Observe that we can swap 2 with 8 and 6 with 4 if needed.
2 x 4
x 5 x
6 x 8
Looking at the table we can find only one number N=9 is a solution to 15 = 2 + 4 + N
So put 9 in the top middle
2 9 4
x 5 x
6 x 8
N=1 goes on the bottom middle
2 9 4
x 5 x
6 1 8
7 and 3 go in the remaining spots
2 9 4
7 5 3
6 1 8
Done

It took me about 10-15 minutes to consider making the table and another 10 minutes to realize how to use it in the solution.

Lastly is there anything you found helpful that improved your logic and problem solving skills?

I don't consider myself a good (mathematical) problem solver. I'm better in a practical setting.

Many of the posters here would wipe the floor with me in this sort of contest.

[adam2016]

Yup that's the correct answer,

@10-15 minutes is still really impressive, I spent at least double that until I caved in and looked at the explanation.

How do you solve these kind of puzzles, does it just come natural to some people or is it a matter of experience and years of solving problems?

Another question that came up was this

12 12
[][][] 12
[][X][]
[][][] 12

9 boxes but the middle one is blocked out(can't hold any number), each row and col must add up to 12, so 4 sums each adding to 12 and you can only use the numbers 1-8(any given number can only be placed inside one box)

I tried applying the same logic to this question as with the previous ones, but it's not effective.

[helios]

I started by searching for a combination that added up to 15. The easiest one was 1 5 9. I put it as row 1. I searched for another one in the remaining six numbers: 2 6 7. That was row 2. The last one, 3 4 8, also added up to 15 and was row 3.
1 5 9
2 6 7
3 4 8
Now I just needed to rotate rows 2 and 3 horizontally until the columns added up. This is mostly trial-and-error, since there's only a few possible configurations. I ended up with
1 5 9
6 7 2
8 3 4
To get the diagonal to add up to 15, the table as a whole needs to rotate horizontally.
9 1 5
2 6 7
4 8 3
Done.

Note that it's possible for plain rotations to not have been enough for each of these steps, but thankfully that never came up.

I'm not sure how indicative these kinds of brain teasers are of someone's problem solving skills.
Most people only get good at solving problems by solving lots of different problems and then applying techniques that they know work, to solve problems they've never seem before that resemble in some way problems that they have solved. So, as with most other things, it just comes down to practice.

[dutch]

Assuming the diagonals don't matter, this adds two 12 in all rows and columns:

1 5 6
8 X 4
3 7 2

[adam2016]

Thanks guys, that's of some assurance :)

[dutch]

@helios, both diagonals are supposed to add to 15.

[mbozzi]

For the second puzzle:

12 - (N=1) = 11 = (3 + 8), (4 + 7), (5 + 6)
12 - (N=2) = 10 = (2 + 8), (3 + 7), (4 + 6)
12 - (N=3) = 9 = (1 + 8), (2 + 7), (3 + 6), (4 + 5)
12 - (N=4) = 8 = (1 + 7), (2 + 6), (3 + 5)
12 - (N=5) = 7 = (1 + 6), (3 + 4)
12 - (N=6) = 6 = (1 + 5), (2 + 4)
12 - (N=7) = 5 = (1 + 4), (2 + 3)
12 - (N=8) = 4 = (1 + 3)

So N = 8 can only add with 1 and 3: it must not be a corner. Observe that we can swap 1 and 3 if needed.
1 8 3
- X -
- - -
Now look for any N that can't add with (1 + p) or (3 + q); this must be the opposite edge (beneath the X). N = 2 is the culprit. N=1 is already taken as a corner next to 8.
1 8 3
- X -
- 2 -
Now choose the bottom left corner by considering any N which adds with (1 + p) and (2 + q) to make 12. N = 7, 6, and 4 and 3 are options. But 3 Is already on the board. Therefore 4 and 6 go in the bottom corners:
1 8 3
- X -
4 2 6
This arrangement doesn't work, so swap corners:
1 8 3
- X -
6 2 4
Then solve
1 8 3
5 X 7
6 2 4

Assuming the diagonals don't matter

It's impossible if the diagonals matter, because the two pairs
(4 + 8), (5 + 7),
must go on the diagonals.
4 - 5
- X -
7 - 8

[dutch]

Then solve
1 8 3
5 X 7
6 2 4

3+7+4 = 14 and 8 + 2 = 10

I solved it by noticing that two of the sums are made up of only two numbers and must be 8 + 4 and 7 + 5. It doesn't matter how you place them since all placements are rotations or mirrorings of each other.

* 7 *
8 X 4
* 5 *

The remaining numbers are easy to get by trial and error.

1 5 6
8 X 4
3 7 2

That's the only solution, modulo mirroring and rotations.


For the original puzzle, there's only 8 ways to get 15 with triplets from {1,2,3,4,5,6,7,8,9}:

1 + 5 + 9
1 + 6 + 8
2 + 4 + 9
2 + 5 + 8
2 + 6 + 7
3 + 4 + 8
3 + 5 + 7
4 + 5 + 6

We need 8 sums, so these must be them.

The number of sums the values occur in are:

1. 2
2. 3
3. 2
4. 3
5. 4
6. 3
7. 2
8. 3
9. 2

The value in the middle of the square participates in four sums.
The corners participate in three sums.
The remaining values participate in two sums.

So 5 must go in the middle square.
2, 4, 6, 8 must go in the corners.
And 1, 3, 7, 9 must go in the remaining positions.

Sticking 2 in the upper left corner and 5 in the middle gives us the lower right corner.

2
  5
    8

The position to the right of 2 must be either 7 or 9.
Choosing either one forces the rest of the values:

2 7 6
9 5 1
4 3 8

2 9 4
7 5 3
6 1 8

Note that these are mirrored rotations of each other. If you think about it, all solutions must be rotations or mirrored versions of this solution. So there are eight possible solutions.

[mbozzi]

Ah thanks, I need to swap 2 and 4

[adam2016]

Oh Okay, clicks now, I've realized my mistake. That said mistake was I added each total from the rows and columns respectively but that isn't the summation of the grid. The summation of the grid is still (1+2+3+4+5+6+7+8+9) = 45, by adding 15 * 8(120) we get the total of each row + column. Since we summed some numbers more than once, we subtract these values from the total.

So the numbers we've added twice - 7 and 3, the numbers we added thrice - 2,6,8,4 and the number added four times 5.

twice: 7,3
thrice: 2,6,8,4
four times: 5

remember we added them all once, so we - 1 from the amount of times we multiply them.

so it becomes 120 - (5 * 3) - (2*2) - (6*2) - (8*2) - (4*2) - 7 - 3 - 9 - 1 = 45
1+2+3+4+5+6+7+8+9 = 45

As stated in the answers, we get the number of triplets from 1-9 that sum to 15, we find there are 8 ways to sum to 15 with the numbers 1-15 which coincides with the number of sums a 3*3 grid encompasses(if you count diagonals). From there simple deduction helps us place the numbers that appear most frequently in the sums, this allows us to slot them into positions on the grid.

[JRManx]

Wonder if you could write a program to solve this in C++ or maybe Python...Something to think about.

[adam2016]

actually did in C++(still need to tidy it up), was pretty straight forward, no more difficult than let's say console tic tac toe.

but I'll post my solution very soon whenever I get time to tidy it up haha, IN the meantime if you want to give it a shot, please do share your solution in here :)

[lastchance]

This really doesn't scale well.

If you turn N up to 4 (and comment out the display();, and turn optimisation up to -O3) you get 7040 solutions ... eventually.

#include <iostream>
#include <iomanip>
using namespace std;

const int N = 3, PLACES = N * N;
const int TARGET = N * ( PLACES + 1 ) / 2;
int A[PLACES] = { 0 };
bool used[1+PLACES] = { false };
bool findAllCases = true;
int ncases = 0;

//==========================================================

void display()
{
   for ( int p = 0; p < PLACES; p++ )
   {
      cout << setw( 2 ) << A[p] << ' ';
      if ( ( p + 1 ) % N == 0 ) cout << '\n';
   }
   cout << '\n';
}

//==========================================================

bool line( int start, int num, int inc )
{
   int total = 0, filled = 0;
   for ( int i = 0, p = start; i < num; i++, p+= inc )
   {
      total += A[p];
      if ( A[p] ) filled++;
   }
   if ( filled == N ) return total == TARGET;
   else               return total <= TARGET - ( N - filled );
}

//==========================================================

bool check( int r, int c )
{
   if ( !line( N * r, N, 1 ) ) return false;
   if ( !line( c    , N, N ) ) return false;
   if ( ( r     == c     ) && !line( 0    , N, N + 1 ) ) return false;
   if ( ( r + c == N - 1 ) && !line( N - 1, N, N - 1 ) ) return false;
   return true;
}

//==========================================================

bool solve( int p )                                        // main backtracking routine
{
   if ( p == PLACES )                                      // *** COMPLETION
   {
      ncases++;
      display();
      return !findAllCases;
   }
   
   int row = p / N, col = p % N;
   for ( int x = 1; x <= PLACES; x++ )
   {
      if ( !used[x] )
      {
         A[p] = x;
         used[x] = true;
         if ( check( row, col ) && solve( p + 1 ) ) return true;     // *** MAIN RECURSIVE CALL
         A[p] = 0;
         used[x] = false;
      }
   }
   return false;
}


//==========================================================


int main()
{
   solve( 0 );
   cout << ncases << " solutions\n";
}

 2  7  6 
 9  5  1 
 4  3  8 

 2  9  4 
 7  5  3 
 6  1  8 

 4  3  8 
 9  5  1 
 2  7  6 

 4  9  2 
 3  5  7 
 8  1  6 

 6  1  8 
 7  5  3 
 2  9  4 

 6  7  2 
 1  5  9 
 8  3  4 

 8  1  6 
 3  5  7 
 4  9  2 

 8  3  4 
 1  5  9 
 6  7  2 

8 solutions

[againtry]

wrong

[lastchance]

Write E for even, O for odd.
The only way of getting an odd sum from 3 is {two Es and an O} or {three Os}.
As there are 4 Es in total you must have two rows of { two Es and an O} and one of {three Os}
If OOO went along a side, then the only possibilities (up to rotation and mirror symmetry) are

OOO          OOO
OEE  and     EOE
OEE          EOE

Both of these screw up at least one diagonal sum.

So the only possible arrangement preserving all of row, column and diagonal sums is of form

EOE
OOO
EOE

As both diagonals share a common element, the even numbers in them must be in pairs, adding up to the same number. So 2 must be in opposite corner to 8 and 4 must be in opposite corner to 6. The central element must then be 5. This gives (up to mirroring and rotational symmetries):

2O4
O5O
6O8

The odd numbers can then be filled in:

294
753
618

The sum-preserving transformations are the two mirrorings (say, in a diagonal) and the 4 cyclic permutations of the corners (which fix the intermediate odd numbers).

So there are 2x4=8 solutions which preserve all rows, all columns and all diagonals adding up to 15.


But no, I haven't worked out the equivalent for side 4 (although my brute-force back-tracking solution seems to suggest 7040 solutions with all rows, columns and the two diagonals adding up to 34).

[JRManx]

Why not try a vector? Or would that have the same problem?