5
$\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?

$\endgroup$
  • 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 '15 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 '15 at 9:28
  • $\begingroup$ @DrunkWolf I meant a 3x3 Sudoku $\endgroup$ – ghosts_in_the_code Dec 26 '15 at 10:13
  • $\begingroup$ Is the q really that boring. I don't see any upvotes..... $\endgroup$ – ghosts_in_the_code Apr 23 '16 at 10:50
  • $\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 '16 at 13:05
9
+50
$\begingroup$

Solution to task 2:

$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:
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.

$\endgroup$
  • 1
    $\begingroup$ Brain hurts now; task 1 will be harder. $\endgroup$ – Jonathan Allan Apr 24 '16 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 '16 at 10:40
2
$\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.

$\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.