2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you have a copy of the given solution? It may not actually be unique at all. I see a place that could be potentially easily modified. $\endgroup$ – Deusovi Jun 29 at 17:35
  • $\begingroup$ Should the no-computers tag be added? $\endgroup$ – Weather Vane Jun 29 at 17:53
  • 2
    $\begingroup$ There are multiple solutions. $\endgroup$ – RobPratt Jun 29 at 18:46
  • 1
    $\begingroup$ There are millions of solutions. Did you maybe omit some clues or some constraints on the missing numbers? $\endgroup$ – RobPratt Jun 29 at 19:12
  • $\begingroup$ @RobPratt That seems answer-worthy to me. $\endgroup$ – Deusovi Jun 29 at 19:42
2
$\begingroup$

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}

| improve this answer | |
$\endgroup$
  • $\begingroup$ Where is the "logical deduction" that the question asks? You've bunged this into a solving machine. $\endgroup$ – Weather Vane Jun 29 at 19:49
  • 2
    $\begingroup$ The point is that you cannot determine a unique solution through logical deduction or any other means. $\endgroup$ – RobPratt Jun 29 at 19:50
  • 2
    $\begingroup$ The question does not ask for a unique solution. It asks how to solve it. Can you post a link to your number cruncher? I got a downvote for a suggested approach on how to solve it by hand. $\endgroup$ – Weather Vane Jun 29 at 20:08
  • 1
    $\begingroup$ I did assume there was a unique answer that could be determined through logic. My question asked for hints based on this assumption. This answer is the answer I am looking for and will allow me to move on to something else! $\endgroup$ – 48dd0092 Jun 30 at 11:23
  • $\begingroup$ @48dd0092 - Thanks for making this comment. I was thinking of formulating quite a long answer that would explain why this is such a badly posed question; how to determine bounds for the answer, and the maths necessary to discover the (finite) set of answers. As you are moving on, I don't have to bother! Note: Something to look up online is how to solve simultaneous Diophantine equations. Here is an excellent (very accessible) video using just 4 variables and 3 equations. youtube.com/watch?v=KyXO6_0S5Ek&feature=emb_logo $\endgroup$ – chasly - supports Monica Jun 30 at 11:46
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This seems like a random guess, not a definitive answer to the question. $\endgroup$ – Deusovi Jun 29 at 19:43
  • 1
    $\begingroup$ @Deusovi it's not a random guess. It should be obvious that I put some study into the problem and put forward a strategy. Are you in DV mood today? And as commented, there isn't a definitive answer. $\endgroup$ – Weather Vane Jun 29 at 19:45
  • $\begingroup$ Perhaps not "random", but it seems that you haven't actually given a suggestion that leads to any logical deductions. (There may not be any logical deductions possible, in which case the answer is "there are no logical deductions possible".) I don't believe this answers the question asked. $\endgroup$ – Deusovi Jun 29 at 19:52
  • $\begingroup$ @Deusovi as I wrote at the top: "an answer, to the sub-question Any hints on which direction to go in to solve it?" This is supposed to be such a hint to solve it with pencil and paper, short of chucking it into a solving machine. $\endgroup$ – Weather Vane Jun 29 at 19:55
  • $\begingroup$ But a "hint on which direction to go to solve it" is useless if it doesn't actually give you a direction to go to solve it. If there is no direction to go to solve it, then nothing can be a hint for finding a direction. $\endgroup$ – Deusovi Jun 29 at 19:56
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Not being independent imposes less constraints, not more. This method may work if the puzzle had a unique solution, but it doesn't seem to. $\endgroup$ – Deusovi Jun 29 at 19:43
  • $\begingroup$ @Deusovi - Have you tried? Remember that the solutions are integers - this is a massive constraint.Even if you were right, this method would pin down the range of solutions. $\endgroup$ – chasly - supports Monica Jun 29 at 20:11
  • $\begingroup$ Yes, I know the solutions are integers. That doesn't change the fact that nonindependence gives less constraints, not more. And because all the coefficients are 1, the integer constraint shouldn't change much - the only constraint that can 'pull its weight' to make the puzzle unique is the bounds of the variables. And judging by the OP's attempts, it doesn't appear likely that it does. $\endgroup$ – Deusovi Jun 29 at 20:27
  • $\begingroup$ @Deusovi. I've edited my second clue and added a fourth. Dammit, I may have to solve this thing. No time at the moment. Maybe tomorrow. $\endgroup$ – chasly - supports Monica Jun 29 at 21:21
  • $\begingroup$ @Deusovi -- As the OP has stated in a comment that they are happy with an existing answer and are moving on. I've decided not to take this any further. Thanks for your input! $\endgroup$ – chasly - supports Monica Jun 30 at 11:51
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.