# Largest cages Killer Sudoku

Task 1: Find the maximum value of $n$ for which it is possible to create a regular uniquely-solvable Killer Sudoku (9x9) such that every cage has atleast $n$ cells in it.

Rules for killer sudoku

Quoting Wikipedia

The objective is to fill the grid with numbers from 1 to 9 in a way that the following conditions are met:

1. Each row, column, and nonet contains each number exactly once.
2. The sum of all numbers in a cage must match the small number printed in its corner.
3. No number appears more than once in a cage.

Task 2: What if rule number 3 was ignored?

• Why does this imply n <= 9? Hexadecimal sudoku's are entitely possible, is there Some theory that excludes them from being valid solutions or are you limiting them yourself? Dec 26 '15 at 7:19
• I must admit that I misread the question before, I'm now assuming that you only want this answered for a regular sudoku, (I didn't notice that n was the cage size, not the sudoku size) Dec 26 '15 at 9:28
• @DrunkWolf I meant a 3x3 Sudoku Dec 26 '15 at 10:13
• I am fairly sure that for task 1. n < 9 since for (3) to hold every cage would be constrained to containing all 9 numbers once each and the only possible cage arrangements would be the 9 nonets, the 9 rows or the 9 columns. Apr 23 '16 at 13:05
• @JonathanAllan As far as I can tell, the cages are not necessarily rectangle shaped (they might not even have to be contiguous). However, for a solution of an $n=9$ Killer, you could apply a permutation of the numbers 1-9 and still get a solution. Apr 23 '16 at 17:45

$n=36$

The approach

The biggest $n$ we could hope to find is $81$ with a single cage which is obviously not going to work.
The next biggest would be $40$ with two cages of $41$ and $40$ cells.
We need to get as close to this as possible while enforcing uniqueness, which means we need to first force some cell to be some value and then have that force another and so on cascading through the entire sudoku.

How to achieve that?

Make it so one cage has rows and columns containing $(1),(1,2),\dots,(1,2,3,4,5,6,7,8,9)$ overlapping on the highest numbers and the other has the rest (overlapping on the smallest numbers). The two cages will now be the cages with the smallest and largest possible sums for their sizes too.
Two separate ones and two separate nines will fall out first, then two pairs of "a one and a two" and two pairs of "a nine and an eight", and so on until the whole sudoku is filled in the only way possible.

The cage sums will be

For the $[1,9]$ ($45$ cells) $\sum_{i=1}^9(\sum_{j=1}^ij)=165$
For the $[1,8]$ ($36$ cells) $405-165=240=\sum_{i=1}^8(\sum_{j=10-i}^9j)$

That is

$165=(1)+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+5)+(1+2+3+4+5+6)+(1+2+3+4+5+6+7)+(1+2+3+4+5+6+7+8)+(1+2+3+4+5+6+7+8+9)$

And

$240=(9)+(9+8)+(9+8+7)+(9+8+7+6)+(9+8+7+6+5)+(9+8+7+6+5+4)+(9+8+7+6+5+4+3)+(9+8+7+6+5+4+3+2)$

Can we do it?

Yes, here is one: which has the unique solution: The first cells to fall out are:
$A9$ (the only column in $165$ with one cell);
$I1$ (the only row in $165$ with one cell);
$A8$ (the only row in $240$ with one cell); and
$F1$ (the only column in $240$ with one cell)

Now the rows and columns with two cells for each are uniquely defined - they must have values $(1,2)$ and $(9,8)$ respectively and one of each pair cannot be the $1$ or $9$ due to those already placed in either the same row or column - these are (in the same order as before):
$(D8,D9)$;
$(F2, I2)$;
$(A7,D7)$; and
$(C1,C2)$

This same process then cascades through to completion.

• Brain hurts now; task 1 will be harder. Apr 24 '16 at 18:08
• Great answer. I'll probably award the bounty to you. I can award another 100 rep for solving the other task, if you (or anyone else) manages to do it Apr 25 '16 at 10:40

To get things going: a simple observation giving us an upper bound $n \leq 8$ for task 1.

Task 1 for $n=9$ (creating a uniquely solvable $9 \times 9$ killer Sudoku with cages of size $n=9$) can not be accomplished. This follows from the fact that if a solution would exist such that each row, each column, each nonet and each 9-cage contains the numbers $1, .. 9$, one could swap any two numbers across the grid (e.g. swap all $1$'s and $2$'s) and thereby obtain another solution.