New killer setter

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: New killer setter

Postby mith » Fri Jul 09, 2021 2:06 pm

I managed this morning, will post when I’m back home :)
mith
 
Posts: 577
Joined: 14 July 2020

Re: New killer setter

Postby mith » Fri Jul 09, 2021 6:08 pm

White Room (8 cages, 18 cells)

Code: Select all
.........
.A...BB..
.A....CC.
.A...DD..
.........
..EE....F
..GE....F
..G......
.....HH..


A = 7
B = 5
C = 6
D = 6
E = 23
F = 15
G = 17
H = 3

(There are a few variations with the same arrangement of cages.)
Last edited by mith on Fri Jul 09, 2021 8:28 pm, edited 1 time in total.
mith
 
Posts: 577
Joined: 14 July 2020

Re: New killer setter

Postby mith » Fri Jul 09, 2021 8:27 pm

Powerhouse (7 cages, 19 cells)

Code: Select all
.........
.A...BBB.
.A...CC..
.A...C...
.........
..DD....E
..FD...EE
..F......
.....GG..


A = 6
B = 8
C = 7
D = 23
E = 24
F = 16
G = 4
mith
 
Posts: 577
Joined: 14 July 2020

Re: New killer setter

Postby mith » Fri Jul 09, 2021 9:13 pm

And 7 cages with 18 cells is possible with some slight massaging of White Room:

Code: Select all
.........
.A....BB.
.A...CC..
.A...CC..
.........
..DD....E
..FD....E
..F......
.....GG..


A = 7
B = 6
C = 11
D = 23
E = 15
F = 17
G = 3
mith
 
Posts: 577
Joined: 14 July 2020

Re: New killer setter

Postby Mathimagics » Sat Jul 10, 2021 5:30 am

Curiously, Broughton's solver can't solve the 7-cage, 18 cell example above.

It's certainly valid, but to confirm this, I had to dust off the ancient SumoCue app ...

Anyway, well done! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1802
Joined: 27 May 2015
Location: Canberra

Re: New killer setter

Postby creint » Sat Jul 10, 2021 9:17 am

Broughton's bruteforce can solve it too.
My solver can solve it using nets. Impact of having multi cage tactics decreases it seems.
creint
 
Posts: 322
Joined: 20 January 2018

Re: New killer setter

Postby Mathimagics » Sat Jul 10, 2021 11:42 am

creint wrote:Broughton's bruteforce can solve it too.

I cannot find that option, where is it?

I did manage to get a solution by enabling all the technique options, many of which are off in the default setup.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1802
Joined: 27 May 2015
Location: Canberra

Re: New killer setter

Postby creint » Sat Jul 10, 2021 9:50 pm

Solve, Yes, >> no more eliminations, press > same message and asking for bruteforce, yes.
Bowman's bingo can also be used without bruteforce.

JSudoku and Color Sudoku can solve it too with bruteforce.
creint
 
Posts: 322
Joined: 20 January 2018

Re: New killer setter

Postby 999_Springs » Sun Jul 11, 2021 12:11 am

there is absolutely no need for brute force 8-) :mrgreen:

the (8-cage, 18-cell) White Room puzzle got featured on cracking the cryptic's youtube channel here. congratulations to mith, you're youtube famous :) (how do you know CTC?!) CTC finds a solution by hand in half an hour which is an impressive time, faster than what i did it in

the 7-cage 18-cell version is the same puzzle but rows 2&3 are swapped and the two 2-cell cages that add up to 5 and 6 are now replaced by an 11 cage. CTC actually doesn't use the fact that those two cages add to 5 and 6 until 18:35 into the video, and i can easily adapt his video solution to the 7-cage version of the puzzle. here is a summary below if you don't want to watch a half hour video. note that rows 2 and 3 are swapped in the 7-cage version below if you want to directly compare it to his video solution

basics: A={124}, B={15} or {24}, C={1235}, D={689}, E={69} or {78}, F={89}, G={12}
r6c3=6, naked pairs 89 in c4, r7, r6, hidden pair 12 in b7

now we use the digit relabelling trick, first discovered by eleven here and two more examples here (there are many others, i think space used this a lot before he got banned)

we label 8,9 with a,b without knowing the order

any cell marked with x can't be 6+
Code: Select all
. . . | . . . | . . .
. x . | . . . | x x .
. x . | . . x | x . .
------+-------+-------
. x . | . . x | x . .
. . . | . . . | . . .
. . 6 | a . . | . . b
------+-------+-------
x . a | b . . | . . 67
x . b | . . . | . . .
. . . | . . x | x . .

singles solve to here
Code: Select all
. a . | . . . | b . .
. x . | . a b | x x .
b x . | . . x | x a .
------+-------+-------
a x . | . b x | x . .
. b . | . . . | a . .
. . 6 | a . . | . . b
------+-------+-------
x . a | b . . | . . 67
x . b | . . a | . . .
. . . | . . x | x b a

6 in c7 locked in b9 => r7c9=7 => b=8 and a=9

singles solve to here
Code: Select all
6 9 . | . . . | 8 7 .
7 x . | . 9 8 | x x .
8 x . | . . x | x 9 .
------+-------+------
9 x 7 | . 8 x | x . .
. 8 . | . . 7 | 9 . .
. . 6 | 9 . . | 7 . 8
------+-------+------
x . 9 | 8 . 6 | . . 7
x 7 8 | . . 9 | 6 . .
. 6 . | . . x | x 8 9

cage C must contain 1 and 2, so combined with cage G, no 1 or 2 can appear anywhere else in columns 6 or 7 => r2c7=45, r2c8=12, 12 hidden pair in r6 => r6c58=12, 12 naked pair in r26c8, 12 hidden pair in b9 => r8c9=12

do the relabelling trick again, set y,z=1,2 in either order, do singles
Code: Select all
6 9 . | . . . | 8  7 .
7 . . | . 9 8 | 45 y .
8 . . | . . . | .  9 .
------+-------+-------
9 . 7 | . 8 . | .  . .
. 8 . | . . 7 | 9  . .
. . 6 | 9 y . | 7  z 8
------+-------+-------
y . 9 | 8 z 6 | .  . 7
z 7 8 | . . 9 | 6  . y
. 6 . | . . y | z  8 9

this point is where CTC gets to at 18:35 in the video before he starts using the fact that the cage sums are 5,6 in r3,r4. this is where i adapt his solution path to the 7-cage version. there are more singles that he missed
Code: Select all
6 9 . | y . . | 8  7 .
7 * . | . 9 8 | 45 y .
8 y . | . . . | .  9 .
------+-------+-------
9 z 7 | . 8 . | y  . .
. 8 y | z . 7 | 9  . .
. . 6 | 9 y . | 7  z 8
------+-------+-------
y . 9 | 8 z 6 | .  . 7
z 7 8 | . . 9 | 6  . y
. 6 . | . . y | z  8 9

y+z+r2c2=7 => r2c2=4 => r2c7=5 => r2c8=y=1 and z=2

cage C must be {1235} so r3c6=2, r4c6=5, r3c7=3

singles to here
Code: Select all
6 9 . | 1 5 . | 8 7 .
7 4 . | . 9 8 | 5 1 .
8 1 5 | . . 2 | 3 9 .
------+-------+------
9 2 7 | . 8 5 | 1 . 3
. 8 1 | 2 . 7 | 9 . 5
. . 6 | 9 1 . | 7 2 8
------+-------+------
1 . 9 | 8 2 6 | 4 . 7
2 7 8 | . . 9 | 6 . 1
. 6 4 | . . 1 | 2 8 9

xy-wing r4c4,r6c6,r2c4 => r1c6=/=3 singles to the end

no need for brute force solving or anything ridiculous like that :P it's one of the nicest applications of eleven's relabelling technique i've seen, and it's great that it can be used in a killer sudoku as well as normal sudokus

thanks to sclt for sending me the youtube link to the puzzle which i otherwise wouldn't have seen

-----------------------

for the original white room with 8 cages, i solved it by hand (without watching the video) with a different method than what CTC did, but my solution is not easily adaptable to the 7-cage version as his is. here is my solution

eliminate the possibility of {14} in the 5-cage. if the 5-cage is {14} then all the lower numbered cages instantly solve like this
Code: Select all
.  . . | .  . . | . . .
.  2 . | .  . 1 | 4 . .
.  4 . | .  . . | 5 1 .
-------+--------+-------
.  1 . | .  . 4 | 2 . .
.  . . | .  . . | . . .
.  . 6 | 89 . . | . . 89
-------+--------+-------
12 . 89| 89 . . | . . 67
12 . 89| .  . . | . . .
.  . . | .  . 2 | 1 . .

and you get a contradiction in r6 because the only place for both 1 and 2 is r6c5. so the 5-cage must be {23} and you get to here (r2c7 can't be 2 because of cage C and column 7)
Code: Select all
.  .   . | .  . . | .  .  .
.  14  . | .  . 2 | 3  .  .
.  124 . | .  . . | 45 12 .
---------+--------+---------
.  24  . | .  . 5 | 1  .  .
.  .   . | .  . . | .  .  .
.  .   6 | 89 . . | .  .  89
---------+--------+---------
12 .   89| 89 . . | .  .  67
12 .   89| .  . . | .  .  .
.  .   . | .  . 1 | 2  .  .

hidden singles in r6: r6c5=1 and r6c8=2 which resolves cage C

then do the same relabelling trick on 8,9 to get r7c9=7, r6c9=8 and solve the puzzle like a normal sudoku because all information from cages is represented - only thing needed from here is the same xy-wing

White Room was the name of my local hairdresser's in 2019... thanks to this puzzle for reminding me of that place, maybe i might give them another visit soon
999_Springs
 
Posts: 570
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: New killer setter

Postby mith » Tue Jul 13, 2021 8:30 pm

999_Springs wrote:the (8-cage, 18-cell) White Room puzzle got featured on cracking the cryptic's youtube channel here. congratulations to mith, you're youtube famous :) (how do you know CTC?!) CTC finds a solution by hand in half an hour which is an impressive time, faster than what i did it in


I spend a lot of time on the CTC discord server... I'm up to about a dozen CTC features now (starting with Tatooine Sunset, which I first published here). The #theory-and-programming channel over there was getting frequent updates of my progress last week. :)

We're getting close to a proof that 17 cells can't be done with an existing 17 given classic. Best I've been able to manage for 17 cell coverage is 2 givens in caged cells (one of which is in the three cell cage; obviously the one in a domino immediately gives another digit). And our lowest solution count for 17 caged cells with no givens is 56.
mith
 
Posts: 577
Joined: 14 July 2020

Re: New killer setter

Postby mith » Wed Jul 14, 2021 1:27 pm

So we've basically completed a proof that 17 cell coverage with no givens is impossible, unless there is still a 17c classic to be found.

Trivially, if a 17 cell killer exists, then it must correspond to a 17c classic. So whereas I got down to 18 by hand (with a solver running for solution count), for 17 we started from the list of 49158 17c grids and did some brute force.

In order for a 17c grid to be viable for turning into a killer, we obviously need adjacency (after morphing, every given must be adjacent to another given) so that we can replace givens with cages. There is a stronger condition though, which is: every given must be adjacent to another given such that swapping the two givens results in a broken puzzle. If this condition does not hold for a pair of givens, then we can't replace those givens with a cage - even after filling in the other 15 givens, the puzzle must have multiple solutions if both orders for that cage give solutions.

Independently, someone else had been working on this and arrived at the same conditions, posting his results yesterday:

1. There are 167 puzzles such that every given shares a row or column with another given such that swapping those two givens results in 0 solutions. (I have already verified this separately and arrived at the same number.)
2. Of those 167 puzzles, only one can be morphed such that every given has this property with an adjacent given. (In the process of verifying this.)

Code: Select all
..............1..2..3.4..5..............3..4.16...2..7....5..3...4.8.....1......6
==>
..53..........61....8.....4..45....3..........1...2....2...761............34.....


(This is the only essentially different way to morph the puzzle and meet these conditions - r12, r89, and/or c12 can be switched, plus rotation/reflection, but there isn't any other way to pair the digits and meet these conditions.)

From here:

3. In order for a killer version to have any chance of solving uniquely, the digits need to be partitioned high/low such that the cage sums are as high/low as possible to limit options. The above grid partitions nicely into 1267 and 3458, so we can map these to 1234 and 6789 in some order.
4. Checking the digit permutations, the lowest solution count for a pure killer based on this grid is 1109* with something like the following (there are a few ways to do it):

Code: Select all
..79..........31....6.....8..87....9..........1...2....2...431............98.....


*You can get down to 828 by swapping rows 1 and 2, and putting 6r3c3 in the cage with 79r2c34 instead of 87r4c34; however, the 67 pair in c3 fails the swap criteria, so this version has already been ruled out at this stage.

You can make the resulting killer unique by adding two givens (8r4c3 must be one of them to disambiguate the high digits, and then you need one digit to disambiguate the 31 pairs in r27. It wouldn't totally surprise me if there's a 17 cell killer with just one given in cages (or even a 16 caged cell with 1 given outside the cages), but at this point I'm satisfied and probably won't spend much more time on it.
mith
 
Posts: 577
Joined: 14 July 2020

Re: New killer setter

Postby Mathimagics » Wed Jul 14, 2021 4:03 pm

mith wrote:So we've basically completed a proof that 17 cell coverage with no givens is impossible, unless there is still a 17c classic to be found.

Nice job, well done!! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1802
Joined: 27 May 2015
Location: Canberra

Re: New killer setter

Postby semax » Mon Aug 02, 2021 11:26 am

mith wrote:3. In order for a killer version to have any chance of solving uniquely, the digits need to be partitioned high/low such that the cage sums are as high/low as possible to limit options.


Well, to always have the maximum/minimum sums will limit options, but it's not necessary for a uniquely solvable killer. So, at this point, it's not really a proof.

Trivial counter examples are 4=1+3, or 11=1+2+3+5, etc.
Next would be sums with more options in the vicinity of other sums, which could mutually exclude combinations. E.g. 14=9+5 and 15=8+7, when in the same area.
And then you could have sums with lots of options that are only resolved later in the solving process.
semax
 
Posts: 1
Joined: 02 August 2021

Re: New killer setter

Postby mith » Tue Sep 07, 2021 8:00 pm

semax wrote:
mith wrote:3. In order for a killer version to have any chance of solving uniquely, the digits need to be partitioned high/low such that the cage sums are as high/low as possible to limit options.


Well, to always have the maximum/minimum sums will limit options, but it's not necessary for a uniquely solvable killer. So, at this point, it's not really a proof.

Trivial counter examples are 4=1+3, or 11=1+2+3+5, etc.
Next would be sums with more options in the vicinity of other sums, which could mutually exclude combinations. E.g. 14=9+5 and 15=8+7, when in the same area.
And then you could have sums with lots of options that are only resolved later in the solving process.


The point is not to have individual cage totals to be maximized or minimized - White Room has a 15 sum after all - but in order to have any hope of disambiguating all the digits the cages must be partitioned into high and low sets. For example, White Room has "small" cage totals of 3, 5, 6, 6, 7 containing digits 1-5, and "large" cage totals of 15, 17, 23 containing digits 6-9. It should be clear that splitting them differently (say swapping 5 and 6) will never improve the situation.

Regardless, there is only one 17-given grid which even passes the first two requirements, and it's not hard to verify that this one can't get down to a unique solution, whatever the digit permutation.
mith
 
Posts: 577
Joined: 14 July 2020

Previous

Return to Sudoku variants