12
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ 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? $\endgroup$
    – DrunkWolf
    Dec 26, 2015 at 7:19
  • $\begingroup$ 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) $\endgroup$
    – DrunkWolf
    Dec 26, 2015 at 9:28
  • $\begingroup$ @DrunkWolf I meant a 3x3 Sudoku $\endgroup$
    – ghosts_in_the_code
    Dec 26, 2015 at 10:13
  • $\begingroup$ 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. $\endgroup$
    – Jonathan Allan
    Apr 23, 2016 at 13:05
  • $\begingroup$ @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. $\endgroup$
    – BaSzAt
    Apr 23, 2016 at 17:45

4 Answers 4

Reset to default
18
+50
$\begingroup$

Solution to task 2:

$n=45$

The approach

Consider splitting the entire grid into cages, in this case the biggest $n$ we could hope to find is $81$ with a single cage which is obviously not going to work as it won't be solvable.
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?

Use two cages and 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:
2-cage-grid-as-described
which has the unique solution:
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.

Now, as codewarrior0 notes, the smaller cage is unnecessary, as it is implicit, so we only need the $165$ cage of $45$ cells.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Brain hurts now; task 1 will be harder. $\endgroup$
    – Jonathan Allan
    Apr 24, 2016 at 18:08
  • $\begingroup$ 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 $\endgroup$
    – ghosts_in_the_code
    Apr 25, 2016 at 10:40
  • 1
    $\begingroup$ Given that the problem does not specify "every cell must be in a killer cage", you may update your answer to the size of the larger cage. $\endgroup$
    – codewarrior0
    Jun 10 at 4:36
  • $\begingroup$ Good point @codewarrior0, updated! $\endgroup$
    – Jonathan Allan
    Jun 10 at 14:11
4
$\begingroup$

Final Update, Aug 18th 2023:

TopAutism from the CTC Discord server has found an $n=8$ killer sudoku where every cell is a part of a cage!!!!!!

This puzzle has nine 8-cell cages (with each of the nine possible 8-cell sums appearing once) and one 9-cell cage (with the unique 9-cell sum).

Read more on Philip Newman's Sudoku wiki page.

killer sudoku

An $n=8$ (!) killer sudoku was found by Reson from the CTC Discord server in April, 2022.

killer sudoku

My old solution

Solution to task 1:

$n=7$

The puzzle

Solve it on f-puzzles: https://f-puzzles.com/?id=27tmlh73

killer sudoku

which has the unique solution:

solution

Improve this answer
$\endgroup$
1
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

Not a complete answer, sorry, but -- For task one, the only way to lay the board out with n=8 would be to have 9 cages of 8 and one cage of 9 (no other combinations of 8 and 9 add up to 81); with each 8 cage having a different sum from the range (36, 37...44).

I tried a few different arrangements of those cages in a solver and the highest number of cells I was able to get it to fill was 19 (using a few different boards, among which is the one attached here as an image) but I've hardly tried everything.

screenshot of a killer sudoku cage layout

Improve this answer
$\endgroup$
1
  • $\begingroup$ If the cage areas were as you say, why would all the 8-cell cages need to have distinct sums? There are killer sudoku puzzles with cages of equal area and equal sum and a unique solution. $\endgroup$
    – Rosie F
    Jun 18 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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