How to solve this Number Grid?

Question

I have a maths puzzle from a book. It is labelled computation and logic but I cannot make any progress. The book lists the answer and it is valid but I cannot see how the answer can be found.

                                        43
2   3   .   .   5   .   2   9   1   .   47
3   .   8   7   .   .   2   .   3   8   41
.   6   5   4   .   7   4   .   .   9   51
2   .   5   7   8   .   6   4   .   1   45
.   2   9   .   .   6   .   8   9   1   51
7   4   3   .   2   .   .   5   5   .   35
.   9   8   1   1   .   2   8   .   .   55
6   2   .   7   .   5   2   .   2   8   43
9   .   .   .   8   4   1   3   1   3   47
2   .   3   9   8   7   .   .   4   4   52
44 40  54  51  52  46  36  56  34  54   32

In the completed grid, all numbers in a row total to the number at the end of the row. Same for columns. There are also two diagonal totals. Each missing number (represented by a dot) is between 1 and 9 inclusive. Numbers can appear any number of times.

The steps I've taken so far:

1) Substracted all the numbers from the totals (in effect turning all provided numbers in cells to zero

2) Written the range of possible values in each cell (eg; if a row has a total of 9 and 3 cells to fill the range for each cell is 1 to 7 (a cell cannot hold 8 or 9 as if the others held the minimum 1 this would overflow the total)

3) Checked the ranges again now that they are all entered to see if any can be reduced based on other lines the cell is part of

There doesn't appear to be enough information to only use logic. I don't particularly want to go through every possible digit in a cell to find a possible solution as this seems long-winded and not fun. I'm sure I'm missing something!

Any hints on which direction to go in to solve it? It's the only puzzle in the book I haven't done yet!

I have found a similar puzzle here but cannot find the name of this particular type of puzzle (hence the post!)

EDIT:

I assumed this puzzle could be solved with logic. My question should have been: Any hints on which direction to go in to solve it OR any proof that it cannot be solved purely by logic

Answer 1

There are millions of solutions, which I obtained via integer linear programming (ILP), with integer decision variable $x_{i,j} \in \{1,\dots,9\}$ for the number that appears in row $i$ and column $j$. The ILP model has 64 fixed variables and 22 linear constraints. Here are two of the solutions:

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

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

In fact, no missing number can be uniquely determined! For the 36 missing numbers, here are the smallest and largest values that appear in a solution: \begin{array}{cccc} \text{row} &\text{col} &\text{min} &\text{max} \\ \hline 1 &3 &1 &9 \\ 1 &4 &1 &9 \\ 1 &6 &1 &9 \\ 1 &10 &5 &9 \\ 2 &2 &1 &6 \\ 2 &5 &1 &7 \\ 2 &6 &1 &7 \\ 2 &8 &1 &7 \\ 3 &1 &1 &9 \\ 3 &5 &1 &9 \\ 3 &8 &1 &9 \\ 3 &9 &1 &7 \\ 4 &2 &1 &9 \\ 4 &6 &1 &9 \\ 4 &9 &1 &7 \\ 5 &1 &1 &9 \\ 5 &4 &1 &8 \\ 5 &5 &1 &8 \\ 5 &7 &3 &9 \\ 6 &4 &1 &5 \\ 6 &6 &1 &5 \\ 6 &7 &1 &5 \\ 6 &10 &2 &6 \\ 7 &1 &2 &9 \\ 7 &6 &1 &9 \\ 7 &9 &1 &7 \\ 7 &10 &5 &9 \\ 8 &3 &1 &7 \\ 8 &5 &1 &9 \\ 8 &8 &1 &7 \\ 9 &2 &2 &9 \\ 9 &3 &1 &9 \\ 9 &4 &1 &9 \\ 10 &2 &1 &8 \\ 10 &7 &3 &9 \\ 10 &8 &1 &9 \\ \end{array}

Answer 2

Here is only the beginnings of an answer, to the sub-question

Any hints on which direction to go in to solve it?

After summing the lines and noting how many missing values and their sum,
I would begin at column 9 because it has the fewest empty cells (3) and
the lowest missing sum (9), with 7 possible sets of (single digit) numbers:
117 126 135 144 225 234 333
Then I would work on row 4 because it now has only 2 empty cells and a
missing sum (originally 12) now in the range 5 to 11.
and so on...

OR...

Marking up lines with only 3 missing numbers, which will create the best options?
Column 3, because that will reduce two rows to only two missing numbers.
Of those rows 8 and 9, row 8's missing sum is initially only 11.
and so on...

So my strategy would be to follow/create a search space with the least options.

Answer 3

Any hints on which direction to go in to solve it?

Here is the general method.

Clue 1

These are simultaneous linear equations There are more variables than equations, but

Clue 2 (EDITED - see discussion in comments below)

There are constraints (as pointed out by @Deusovi in comments). See Clue 4.

Clue 3

Line 1 would be 2 + 3 + a + b + 5 + c + 2 + 9 + 1 + d = 47 Eliminate numerical constants --->
This gives a + b + c + d = 25 Do the same with each row, column and diagonal. (You will need uppercase variables as well!) Eliminate variables and take it from there.

Clue 4

Constraints Again looking just at the first line, a, b, c, and d, are integers that add up to 25. The way that this can happen is finite. If they were allowed to be real numbers there would be infinite solutions. With integers, the solution set is finite. Staying within the bounds of 1-9, the solution set is even smaller.

Simple (large) upper bound on the solution set

We can get an absolute upper bound without much work. There are (if I counted right) 36 empty slots. Each can contain an integer from 1-9. The possible permutations are therefore 9^36, which is in the order of 23 billion trillion trillion. This takes no notice of the other constraints. However it does show that simple guessing would probably take a very long time. Lower upper bounds (sic) can be found by elimination.

Answer 4

There are multiple ways to do this. A method for finding one solution is as follows: • Replace all empty squares with zeros • In each row change one of the zeros to a positive integer to satisfy all row sums. Obviously all the column sums will be wrong and some digits will be outside the range 1-9. • Now fudge the rows by repeatedly adding 1 to some entry and subtracting 1 from the same row. This means all rows remain correct. If done “strategically” you should be able to gradually improve the columns so their sums approach the correct total. • By this stage you should have correct row and column totals and you only need sort out the diagonals. You now have to fudge by adding or subtracting 1 to four corners of a rectangle. This way the row and column sums should stay constant. If done strategically the diagonals should approach the right total and make sure all digits are between 1 and 9.

This is a bit tedious but should work.