Almost impossible Sudoku like puzzle

I was set a puzzle in my math class. I tried to do it using an equation but it didn't work it looked like a trial and error puzzle so I took it into school and the math teachers couldn't solve it.

Is there a way to do this using an equation. This is not homework it's not set anymore. I was just curious.

• I'd refer to the shape of the grid as St Brigid's cross, or any other name for that woven shape. So maybe 'St Brigid's sudoku'.
– smci
Jul 8, 2020 at 9:31

Following on from Stiv's answer here are a few mathematical observations

Let the magic number (common sum) be denoted $$X$$. First notice that in boxes labelled $$A,B,C,D$$ we must have $$A+B = C+D$$. We can see this by either adding the rows or the columns and subtracting the total in the middle $$2 \times 2$$ square.
Also notice that when we add the rows and the columns we get $$4X$$, a number divisible by $$4$$.
Since the sum of the numbers from $$1$$ to $$8$$ is divisible by $$4$$, this means that the sum of the numbers $$A+B+C+D$$ is also divisible by $$4$$ as is the sum of the numbers in the middle $$2 \times 2$$. This is because when we denote the sum of the middle squares as $$M$$, then $$4X=A+B+C+D+2M$$. The sum of all the numbers is $$Y=A+B+C+D+M$$. Since both terms are divisible by 4, any linear combination with integer coefficients is also divisible by 4 (the difference between $$4X$$ and $$Y$$ is just $$M$$). In particular, $$2Y−X=A+B+C+D$$ is divisible by $$4$$. Going back to the first observation, the first thing I would have tried for $$(A,B,C,D)$$ would be $$(1,4,2,3)$$ but this sum ($$10$$) is not divisible by $$4$$. The second thing I would try is $$(1,5,2,4)$$ whose sum ($$12$$) is divisible by $$4$$. This would make $$4X = (1+2+4+5)+2(3+6+7+8) = 60$$ and that means $$X = 15$$. Placing $$A,B,C,D$$ in the rest of the grid can be easily completed in a unique way.

It seems to be the case that if

(i) $$A+B = C+D$$
(ii) $$A+B+C+D = 2(A+B)$$ is divisible by $$4$$
(iii) $$(A,B,C,D)$$ are not all of the same parity.

Then an answer exists and is determined by $$(A,B,C,D)$$.

Showing that (iii) is a necessary condition

If all of $$A,B,C,D$$ are even, then $$X$$ is $$13$$ but each row/column contains odd/odd/even whose sum must be even and can never add up to $$13$$. Similarly, if all of $$A,B,C,D$$ are odd, then $$X$$ is $$14$$ but each row/column contains odd/even/even whose sum must be odd and cannot add up to $$14$$.

• Interesting to see you went about this almost the opposite way to me - I began my trial-and-error approach by trying to maximise the 4 numbers in the edge boxes, while you appear to have tried to minimise it! (+1) I'm not convinced there truly is a purely algebraic way to do this without at some point having to pick a number for a particular space and follow the logic along its natural path - there just seem to be too many unknowns. Plus, given that you have demonstrated a different solution to me there are clearly multiple solutions anyway!
– Stiv
Jul 6, 2020 at 12:39
• @Stiv Yes, what you say is right although once you make a choice for $(A,B,C,D)$ following the conditions above it seems the answer is determined. The only time I've found that you don't get an answer is if all of $(A,B,C,D)$ are even or all are odd. Not 100% certain that this is the case but it seems to be. Jul 6, 2020 at 12:41
• Yes, I believe your final 3 bullet points are as far as we can go algebraically without ending up in a maze of unsolvable simultaneous equations! I don't think we can improve upon this...
– Stiv
Jul 6, 2020 at 12:57
• The all-even or all-odd case is in fact impossible: Either $|A-B|=6$ or $|C-D|=6$, but the largest possible difference for the four inner numbers is $4$. Jul 7, 2020 at 11:40
• "this means that the sum of the numbers $A+B+C+D$ is also divisible by $4$" Sorry, but I don't get why the two premises imply this. Can someone elaborate? Jul 8, 2020 at 10:00

Without using any formal algebra an answer can be reached fairly quickly through trial-and-error. Here is one example:

Here, all runs of three boxes sum to:

13

A brief note on my trial-and-error process:

Realising that the sum of the top-most and bottom-most boxes must be the same as the sum of the left-most and right-most boxes, I first decided to pair the highest number with the lowest and use 1/8 as one pair and 2/7 as the other (each summing to 9). When this didn't work, I tried 2/8 and 3/7 (each summing to 10) and the solution unfolded.

I appreciate you are also interested in a mathematical answer using algebra and that this does not yet address that part of your question. I'm not convinced there truly is a purely algebraic way to do this without at some point having to pick a number for a particular space and follow the logic along its natural path - there just seem to be too many unknowns for the number of distinct simultaneous equations that can actually be derived. In fact, as @hexomino has found another valid solution there isn't (and cannot exist) a unique algebra-aided solution.

I believe the mathematics detailed in @hexomino's answer is as detailed as you can get without tying yourself in knots with unsolvable simultaneous equations - you may just have to accept that some degree of trial-and-error is involved!

• You can examine the cases one by one. After 15 minutes you realize patterns of impossibility and it goes quite quickly. Well, quickly, it still took me about an hour to find all cases by a systematic consideration of cases for sums 12, 13, 14, 15 (it's easy to rule out other sums). Alexander below has all 12 cases (or 6 cases, depending on how you define uniqueness). Jul 8, 2020 at 11:29
• @PatrickT Indeed you can :) My answer here exists purely to demonstrate that it is possible to find an answer by trial and error, refuting any alleged need for the use of more complicated mathematics. Alexander's answer is impressively thorough I admit!
– Stiv
Jul 8, 2020 at 12:11

Since you have 8 elements, and 8 holes you need to fill without repetition and omission, you're dealing with permutations. The number of permutations is given by the formula:

$$^n\mkern-3muP\mkern-1mu_k=\frac{n!}{(n-k)!}$$

Solving given $$n = 8$$ and $$k = 8$$ we get:

\begin{aligned} ^8\mkern-3muP\mkern-1mu_8 &= \frac{8!}{(8-8)!} \\ &= \frac{40,320}{0!} \\ &= \frac{40,320}{1} \\ &= 40,320 \\ \end{aligned}

Generating 40,320 grids is a piece of cake, a computer can do that! So a brute-force solution is tractable.

Filtering these 40,320 permutations, we'll keep only those for which the 4 sums are equal (i.e. they constitute valid solutions). After doing so we can see that there are this many solutions:

48

However, they aren't unique solutions, because each true solution appears 4 times (in its four rotated forms).

To duplicate this, I define a normalized() function. It takes a PuzzleGrid, computes its 4 rotations, and returns the minimal one by comparison. In my solution, I define the minimal a PuzzleGrid as that with the lowest first number. If the firsts numbers are equal, I break ties by the second number, and so on.

After de-duplication, there are this many unique solutions:

12

And here they are:


┌─┐       ┌─┐       ┌─┐       ┌─┐
│1│       │1│       │1│       │1│
┌─┬─┼─┤   ┌─┬─┼─┤   ┌─┬─┼─┤   ┌─┬─┼─┤
│2│4│8│   │2│7│6│   │4│3│8│   │6│3│5│
└─┼─┼─┼─┐ └─┼─┼─┼─┐ └─┼─┼─┼─┐ └─┼─┼─┼─┐
│3│5│6│   │3│8│4│   │7│6│2│   │4│8│2│
├─┼─┴─┘   ├─┼─┴─┘   ├─┼─┴─┘   ├─┼─┴─┘
│7│       │5│       │5│       │7│
└─┘       └─┘       └─┘       └─┘
┌─┐       ┌─┐       ┌─┐       ┌─┐
│2│       │2│       │2│       │2│
┌─┬─┼─┤   ┌─┬─┼─┤   ┌─┬─┼─┤   ┌─┬─┼─┤
│3│4│6│   │3│7│4│   │5│1│8│   │7│1│5│
└─┼─┼─┼─┐ └─┼─┼─┼─┐ └─┼─┼─┼─┐ └─┼─┼─┼─┐
│1│5│7│   │1│8│5│   │7│4│3│   │4│6│3│
├─┼─┴─┘   ├─┼─┴─┘   ├─┼─┴─┘   ├─┼─┴─┘
│8│       │6│       │6│       │8│
└─┘       └─┘       └─┘       └─┘
┌─┐       ┌─┐       ┌─┐       ┌─┐
│3│       │3│       │4│       │4│
┌─┬─┼─┤   ┌─┬─┼─┤   ┌─┬─┼─┤   ┌─┬─┼─┤
│4│1│8│   │6│5│2│   │5│1│6│   │7│3│2│
└─┼─┼─┼─┐ └─┼─┼─┼─┐ └─┼─┼─┼─┐ └─┼─┼─┼─┐
│5│2│6│   │1│8│4│   │3│2│7│   │1│6│5│
├─┼─┴─┘   ├─┼─┴─┘   ├─┼─┴─┘   ├─┼─┴─┘
│7│       │7│       │8│       │8│
└─┘       └─┘       └─┘       └─┘


Here's my Swift implementation of a brute force solution:

struct PuzzleGrid {
/*   line 1 (down)
0,
line 2 -> 1, 2, 3
line 3 ->    4, 5, 6
7
line 2 ^
*/

let numbers: [Int]

var line1Sum: Int { numbers[0] + numbers[3] + numbers[5] }
var line2Sum: Int { numbers[1] + numbers[2] + numbers[3] }
var line3Sum: Int { numbers[4] + numbers[5] + numbers[6] }
var line4Sum: Int { numbers[2] + numbers[4] + numbers[7] }

var isValid: Bool {
let expectedSum = line1Sum
return expectedSum == line2Sum
&& expectedSum == line3Sum
&& expectedSum == line4Sum
}

/// Return a new PuzzleGrid that's self rotated clockwise by 90 degrees
func rotate() -> PuzzleGrid {
let indices = [
1,
7, 4, 2,
5, 3, 0,
6
]

return PuzzleGrid(numbers: indices.map { self.numbers[$0] }) } /// Return the "minimal" of the 4 rotations of self func normalized() -> PuzzleGrid { let r0 = self let r1 = r0.rotate() let r2 = r1.rotate() let r3 = r2.rotate() assert(r3.rotate() == r0) return [r0, r1, r2, r3].min()! } } extension PuzzleGrid: Comparable { static func < (lhs: PuzzleGrid, rhs: PuzzleGrid) -> Bool { for (leftNumber, rightNumber) in zip(lhs.numbers, rhs.numbers) { if leftNumber < rightNumber { return true } else if leftNumber > rightNumber { return false } else { continue } } assert(lhs.numbers == rhs.numbers) return true } } extension PuzzleGrid: Hashable {} extension PuzzleGrid: CustomStringConvertible { var description: String { let (a, b, c, d, e, f, g, h) = ( numbers[0], numbers[1], numbers[2], numbers[3], numbers[4], numbers[5], numbers[6], numbers[7] ) return """ ┌─┐ │\(a)│ ┌─┬─┼─┤ │\(b)│\(c)│\(d)│ └─┼─┼─┼─┐ │\(e)│\(f)│\(g)│ ├─┼─┴─┘ │\(h)│ └─┘ """ } } /// Given remainingElements, and the prefix, generate all permutations of remainingElements, /// prepending the prefix to each permutation. func createPermutations( from remainingElements: Set<Int>, prefix: [Int] = [] ) -> [[Int]] { if remainingElements.count == 1 { return [prefix + [remainingElements.first!]] } return remainingElements.flatMap { element -> [[Int]] in var newRemainingElements = remainingElements newRemainingElements.remove(element) return createPermutations( from: newRemainingElements, prefix: prefix + [element] ) } } let allPermutations = createPermutations(from: [1, 2, 3, 4, 5, 6, 7, 8]) print("Total number of permutations: \(allPermutations.count)") let allPuzzleGrids = allPermutations.map(PuzzleGrid.init(numbers:)) let solutions = allPuzzleGrids.filter(\.isValid) print("Total number of solutions: \(solutions.count)") let uniqueSolutions = Set(solutions.map {$0.normalized() }).sorted()

print("Total number of unique solutions: \(uniqueSolutions.count)")

uniqueSolutions.forEach { print(\$0) }

• A full permutation is just n!. Writing it as n!/0! is a bit redundant. Jul 8, 2020 at 2:41
• Very nice. You will note that your solutions come in pairs. So in a sense, there are only 6 fundamental solutions. Indexing by the middle numbers and let S denote the sum. For S = 12: (1, 2, 3, 6). For S = 13: (1, 4, 5, 6) and (1, 2, 5, 8). For S = 14: (3,4,5,8) and (1,4,7,8). For S = 15: (3,6,7,8). Jul 8, 2020 at 11:17
• How did you go from 40,320 to 48? Jul 8, 2020 at 11:18
• Edited your code: the problem was with white spaces on the right-hand side. Removing them fixed the issue. Jul 8, 2020 at 11:26
• Actually, I think I won't filter those out. I think they're "different enough" that they should constitute "unique solutions", even if there is a pattern to them. I think they're more useful to keep than rotations Jul 8, 2020 at 12:37

It is possible to find all the solutions without a computer.

Let the sum of the four middle squares be $$m$$ and the sum of the four "edge" squares be $$e$$.

We know $$e + m = 1+2+3+4+5+6+7+8 = 36$$. Also, the maximum and minimum values for $$e$$ and $$m$$ are $$10 = 1+2+3+4$$ and $$26 = 5+6+7+8$$.

The sum of the four equal rows and columns is $$e + 2m = 36 + m$$ which must be a multiple of $$4$$. So $$m$$ must be $$12$$, $$16$$, $$20$$, or $$24$$.

We therefore have the possibilities $$\begin{gather*} e= 12,\quad m = 24,\quad \text{row sum} = 15 \\ e= 16,\quad m = 20,\quad \text{row sum} = 14 \\ e= 20,\quad m = 16,\quad \text{row sum} = 13 \\ e= 24,\quad m = 12,\quad \text{row sum} = 12 \end{gather*}$$

Consider the first case. The four middle squares must be either $$8 + 7 + 6 + 3 = 24$$ or $$8 + 7 + 5 + 4 = 24$$. $$8$$ and $$7$$ can not be in the same row or column because $$8+7 = 15$$ leaves nothing for the edge square. So the middle four squares must be $$\begin{matrix} 8 & 6 \\ 3 & 7\end{matrix} \qquad \text{or} \qquad \begin{matrix} 8 & 5 \\ 4 & 7\end{matrix}$$ or a rotation or reflection of these patterns.

The first pattern gives a solution. The second one does not, because the bottom row would have to be $$4 + 7 + 4 = 15$$ repeating the $$4$$.

Another way to eliminate the second pattern is to notice that the two columns $$8 + 4$$ and $$5 + 7$$ both sum to $$12$$, so two of the edge squares would have to be equal.

Similar arguments can be used for the other three cases to find all the possible solutions.

Not strictly an equation, but there's a formula/algorithm for calculating odd-width magic squares (and another one for multiple of four width)... and from

438          276           1
951    --->  438  --->   276
276          951          384
5


(as in: you rotate rows (which breaks diagonal equality, but means the 9 can get dropped), and then rotate parts to get to the desired shape while preserving the equalities you care about)

So, if they wanted to expand this to a larger but similar shape, that would be how I'd consider solving it.

Just adding another possible solution to show that there are indeed way too many options for this to be solvable via equations, this time with 12 as the sum:

And another for 14:

I believe these (with the answers from Stiv and hexomino) show all four "classes" of solutions, regarding the sums for every row and column, as

the total sum of all four rows and columns must be divisible by 4, and in addition, it consists of the sum of the four outlying numbers and twice the four inner numbers each. Or in other words, the sum of all numbers from 1-8 (=36), and then any four of them again (between 10 for 1-4, and 26 for 5-8).

But this sum (between 46 and 62) must be divisible by 4, so it could only be one of 48, 52, 56 or 60, giving the sum for individual rows respectively as 12, 13, 14 or 15.

Here is a fairly mathematical approach. I number the squares as

We are looking for \begin{align} x_1+x_2+x_3&=x_4+x_5+x_6\\ x_1+x_2+x_3&=x_2+x_4+x_7\\ x_1+x_2+x_3&=x_3+x_5+x_8 \end{align} After row reduction, this system is equivalent to \begin{align} x_1+x_6&=x_7+x_8\\ x_2+x_7&=x_5+x_6\\ x_3+x_8&=x_4+x_6 \end{align} At this stage one needs to gess a bit. But, since $$x_2,x_3$$ and $$x_4,x_5$$ appear in two sums, they cannot be too small. So I prescribed $$x_1=1$$, $$x_7-2$$, $$x_8=3$$, $$x_6=4$$. This immediately satisfies the first equation. And we need $$x_2-x_5=2,\ \ \ x_3-x_4=1.$$ This is easily achieved with $$x_2=7$$, $$x_5=5$$, $$x_3=9$$, $$x_4=8$$.