SudokuK4

For fans of Killer Sudoku, Samurai Sudoku and other variants

SudokuK4

Postby Mathimagics » Thu Aug 15, 2019 8:06 am

These puzzles are like Killer Sudoku's, except that the sums where provided refer to the 4 adjacent cells. Apparently the UK Daily Telegraph publishes a form of these under the name "Sujiko". (See here for HATMAN's recent thread which describes Sujiko).

I had been looking at a similar idea, but using standard Sudoku grids and rules.

The rules for SudokuK4 are:

  • fill in the grid so that it forms a valid Sudoku, and satisfies all indicated cage sums
  • where a sum is given, this refers to the cage consisting of the 4 adjacent cells (ie 2x2)
  • a digit cannot be repeated within any cage

([EDIT] I have now removed the 3rd rule, which unnecessarily constrains the solution grids. See below for explanation.)

An easy example to begin with:
Puzzle #1: Show
SudokuK4-002.png
SudokuK4-002.png (10.44 KiB) Viewed 1034 times

Solution #1: Show
Code: Select all
 +-------+-------+-------+
 | 6 8 9 | 1 5 4 | 3 2 7 |
 | 1 5 7 | 8 3 2 | 9 6 4 |
 | 3 2 4 | 9 7 6 | 5 1 8 |
 +-------+-------+-------+
 | 4 1 6 | 5 2 9 | 8 7 3 |
 | 8 9 3 | 4 1 7 | 6 5 2 |
 | 5 7 2 | 6 8 3 | 1 4 9 |
 +-------+-------+-------+
 | 9 6 8 | 7 4 5 | 2 3 1 |
 | 7 3 5 | 2 9 1 | 4 8 6 |
 | 2 4 1 | 3 6 8 | 7 9 5 |
 +-------+-------+-------+


And a harder one:
Puzzle #2: Show
SudokuK4-001.png
SudokuK4-001.png (10.5 KiB) Viewed 1034 times

Solution #2: Show
Code: Select all
 +-------+-------+-------+
 | 2 8 9 | 4 7 3 | 1 5 6 |
 | 4 7 6 | 8 1 5 | 9 2 3 |
 | 1 5 3 | 9 6 2 | 7 4 8 |
 +-------+-------+-------+
 | 3 4 2 | 7 5 9 | 8 6 1 |
 | 8 9 1 | 3 4 6 | 2 7 5 |
 | 7 6 5 | 2 8 1 | 4 3 9 |
 +-------+-------+-------+
 | 9 2 8 | 6 3 7 | 5 1 4 |
 | 6 1 7 | 5 9 4 | 3 8 2 |
 | 5 3 4 | 1 2 8 | 6 9 7 |
 +-------+-------+-------+
Last edited by Mathimagics on Mon Aug 19, 2019 10:00 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuK4

Postby creint » Thu Aug 15, 2019 3:44 pm

Single solutions confirmed. Manual inputting the numbers in code. Solver does not have a scripting function. If you provided the numbers it would have been easier pasting them directly into my code.

Code: Select all
20, 29, 25, 17, 14, 18, 20, 19,
11, 18, 28, 27, 18, 22, 21, 19,
10, 13, 24, 23, 24, 28, 21, 19,
22, 19, 18, 12, 19, 30, 26, 17,
29, 21, 15, 19, 19, 17, 16, 20,
27, 23, 23, 25, 20, 11, 10, 17,
25, 22, 22, 22, 19, 12, 17, 18,
16, 13, 11, 20, 24, 20, 28, 28


Code: Select all
21, 30, 27, 20, 16, 18, 17, 16,
17, 21, 26, 24, 14, 23, 22, 17,
13, 14, 21, 27, 22, 26, 25, 19,
24, 16, 13, 19, 24, 25, 23, 19,
30, 21, 11, 17, 19, 13, 16, 24,
24, 21, 21, 19, 19, 17, 13, 17,
18, 18, 26, 23, 23, 19, 17, 15,
15, 15, 17, 17, 23, 21, 26, 26
creint
 
Posts: 393
Joined: 20 January 2018

Re: SudokuK4

Postby Mathimagics » Thu Aug 15, 2019 3:59 pm

Some more examples!

Astute observers will have noticed that, if we specify ALL possible cage sums, then the Killer cage rule (no digit repeats in any cage) means that the solution grid must be a SudokuDP grid (Diagonal Pairs) property - that is, no 2 cells that are diagonally adjacent can have the same value.

This constraint only affects pairs of cells that are in different boxes, but it does reduce the potential puzzle grids (roughly one in 10,000 grids have this property) .

But if we only specify cages that are wholly contained within a box, then this restriction on solution grids disappears. These examples demonstrate this, and I think, the puzzle presentation is neater.

First, an easy one:

Puzzle #3: Show
SudokuK4-003.png
SudokuK4-003.png (9.01 KiB) Viewed 1022 times

Solution #3: Show
Code: Select all
 +-------+-------+-------+
 | 9 7 1 | 6 5 8 | 4 3 2 |
 | 8 4 3 | 1 2 9 | 5 7 6 |
 | 6 2 5 | 4 3 7 | 9 8 1 |
 +-------+-------+-------+
 | 3 9 2 | 7 6 4 | 1 5 8 |
 | 7 1 4 | 5 8 2 | 3 6 9 |
 | 5 6 8 | 3 9 1 | 2 4 7 |
 +-------+-------+-------+
 | 4 8 6 | 2 1 5 | 7 9 3 |
 | 1 5 9 | 8 7 3 | 6 2 4 |
 | 2 3 7 | 9 4 6 | 8 1 5 |
 +-------+-------+-------+


And a harder one:

Puzzle #4: Show
SudokuK4-004.png
SudokuK4-004.png (9.08 KiB) Viewed 1022 times

Solution #4: Show
Code: Select all
 +-------+-------+-------+
 | 4 3 1 | 7 5 8 | 6 9 2 |
 | 8 6 9 | 1 2 4 | 5 3 7 |
 | 7 2 5 | 6 9 3 | 4 8 1 |
 +-------+-------+-------+
 | 9 4 2 | 3 7 6 | 1 5 8 |
 | 3 1 6 | 5 8 2 | 9 7 4 |
 | 5 7 8 | 9 4 1 | 2 6 3 |
 +-------+-------+-------+
 | 6 8 7 | 2 1 5 | 3 4 9 |
 | 1 5 4 | 8 3 9 | 7 2 6 |
 | 2 9 3 | 4 6 7 | 8 1 5 |
 +-------+-------+-------+


For creint:
Puzzle Sums: Show
Code: Select all
Puzzle #3:
 28, 15,  0, 14, 24,  0, 19, 18,
 20, 14,  0, 10, 21,  0, 29, 22,
  0,  0,  0,  0,  0,  0,  0,  0,
 20, 16,  0, 26, 20,  0, 15, 28,
 19, 19,  0, 25, 20,  0, 15, 26,
  0,  0,  0,  0,  0,  0,  0,  0,
 18, 28,  0, 18, 16,  0, 24, 18,
 11, 24,  0, 28, 20,  0, 17, 12

Puzzle #4:
 21, 19,  0, 15, 19,  0, 23, 21,
 23, 22,  0, 18, 18,  0, 20, 19,
  0,  0,  0,  0,  0,  0,  0,  0,
 17, 13,  0, 23, 23,  0, 22, 24,
 16, 22,  0, 26, 15,  0, 24, 20,
  0,  0,  0,  0,  0,  0,  0,  0,
 20, 24,  0, 14, 18,  0, 16, 21,
 17, 21,  0, 21, 25,  0, 18, 14

(I had a bug in the solver, so could you verify these for me?)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuK4

Postby Wecoc » Thu Aug 15, 2019 6:14 pm

Best thing about this is JSudoku can solve it.

Code: Select all
Puzzle #3
180 nodes traversed
Unique solution found with 4 guesses

Puzzle #4
460 nodes traversed
Unique solution found with 22 guesses
Last edited by Wecoc on Thu Aug 15, 2019 9:50 pm, edited 1 time in total.
Wecoc
 
Posts: 76
Joined: 08 April 2019
Location: Girona, Catalonia

Re: SudokuK4

Postby creint » Thu Aug 15, 2019 8:06 pm

Missed that it had row and column constraints (not needed in example 1 and 2).
Both have single solution too. So normal sudoku rules + sum cages only.
creint
 
Posts: 393
Joined: 20 January 2018

Re: SudokuK4

Postby Mathimagics » Fri Aug 16, 2019 5:38 am

Wecoc wrote:.. JSudoku can solve it

Really? How did you get it to do that?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuK4

Postby tarek » Fri Aug 16, 2019 11:03 am

It shouldn't be a problem to manually add sum cages to Jsudoku to solve puzzle. It is tedious to do though for a batch of puzzles.

A single line code provided with the puzzle (similar to a killer sudoku puzzle line code) can be copied and passed easily into Jsudoku and possibly into many others

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: SudokuK4

Postby Mathimagics » Fri Aug 16, 2019 12:46 pm

Yes, but I don't know of any puzzle string definition format that allows a cell to be in multiple cages.

So perhaps Wecoc did it manually. It's still surprising (and fortunate) that JSudoku even allows overlapping cages at all. Richard Broughton's SudokuSolver won't allow it.

Once the cages are setup, presumably one can save the puzzle template and just manually change the sums for different puzzles.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuK4

Postby Wecoc » Fri Aug 16, 2019 4:53 pm

Mathimagics wrote:So perhaps Wecoc did it manually.

Exactly, I did it manually. I checked on the User Guide and as expected all the text formats the program accepts are defined for non-overlapping cages only.
What you can do is save it as JSD and open it again without losing the overlaps.
Maybe you could generate a temporary JSD file from a string and load it into the program, I don't know how hard (and time-consuming) would that be :?
Custom solvers are probably a better option.
Wecoc
 
Posts: 76
Joined: 08 April 2019
Location: Girona, Catalonia

Re: SudokuK4

Postby Mathimagics » Fri Aug 16, 2019 5:18 pm

Wecoc, thanks for going to the trouble of testing that!

It certainly looks like only the custom solvers (such as mine, and creint's) can deal with these.

BTW, from what I can tell, JSudoku only allows overlapping cages because it has a "Twin Killer" mode, which as far as I can ascertain is an invention of djape's. (http://www.djape.net/twin-sudoku-killer/)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuK4

Postby Mathimagics » Mon Aug 19, 2019 9:55 am

On reflection, I have simplified the rules so that they do NOT require "no repeating digits within a cage".

The revised rules:

  • fill in the grid so that it forms a valid Sudoku, and satisfies all indicated 4-cell cage sums
  • wherever a cage sum is given, this refers to the cage consisting of the 4 adjacent cells (ie 2x2)

The revised rules allow puzzles to be created on any Sudoku grid. But normal Sudoku rules apply, so repeating digits within a cage can only occur in those cages that overlap Sudoku box boundaries. There are 64 x K4 cages in a Sudoku grid, and 36 of these are internal to a box. 24 overlap 2 boxes, and 4 (at the 4 corners of box 5) overlap 4 boxes.

Interestingly, nearly every Sudoku grid is uniquely defined by just the 36 cage sums that are internal to a box. I have run several random grid tests, and less than 1 in 15,000 fail to give a unique 36-sum puzzle. And on the rare occasion that it fails, a simple relabelling of the grid (swapping some pair of digits) is sufficient to fix it.

So puzzle generation is quite easy, and from the subset of 36 sums, some can be omitted to make a puzzle harder, and givens (or additional sums) can be added to make a puzzle easier.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuK4

Postby Wecoc » Mon Aug 19, 2019 5:05 pm

I made this one, just for fun:

Wecoc Puzzle #1: Show
Image


Puzzle Sums: Show
Code: Select all
6.............................1.............................2..
 16, 16,  0, 20, 20,  0, 18, 18,
 16, 16,  0, 20, 20,  0, 18, 18,
  0,  0,  0,  0,  0,  0,  0,  0,
 20, 20,  0, 20, 20,  0, 20, 20,
 20, 20,  0, 20, 20,  0, 20, 20,
  0,  0,  0,  0,  0,  0,  0,  0,
 22, 22,  0, 20, 20,  0, 24, 24,
 22, 22,  0, 20, 20,  0, 24, 24


Code: Select all
Wecoc Puzzle #1
12660 nodes traversed
Unique solution found with 21 guesses
Wecoc
 
Posts: 76
Joined: 08 April 2019
Location: Girona, Catalonia

Re: SudokuK4

Postby Mathimagics » Mon Aug 19, 2019 5:57 pm

Confirmed.

Solution: Show
Code: Select all
 +-------+-------+-------+
 | 6 2 9 | 7 3 4 | 5 1 8 |
 | 7 1 4 | 2 8 5 | 9 3 6 |
 | 5 3 8 | 9 1 6 | 4 2 7 |
 +-------+-------+-------+
 | 9 4 3 | 1 6 7 | 8 5 2 |
 | 1 6 7 | 8 5 2 | 3 4 9 |
 | 8 5 2 | 3 4 9 | 7 6 1 |
 +-------+-------+-------+
 | 3 8 6 | 4 9 1 | 2 7 5 |
 | 4 7 1 | 5 2 8 | 6 9 3 |
 | 2 9 5 | 6 7 3 | 1 8 4 |
 +-------+-------+-------+
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuK4

Postby Mathimagics » Mon Aug 19, 2019 6:58 pm

Wecoc: JSudoku is proving troublesome for me ... I'm trying to set these sums:

Code: Select all
20,29, 0,17,14, 0,20,19,
11,18, 0,27,18, 0,21,19,
 0, 0, 0, 0, 0, 0, 0, 0,
22,19, 0,12,19, 0,26,17,
29,21, 0,19,19, 0,16,20,
 0, 0, 0, 0, 0, 0, 0, 0,
25,22, 0,22,19, 0,17,18,
16,13, 0,20,24, 0,28,28


First cage (20) is fine, but when I try to add the second cage (29) it insists that "R1C2 has no possibility", no matter which "layer" I try. The sums are valid, they come from here:
Solution: Show
Code: Select all
 +-------+-------+-------+
 | 6 8 9 | 1 5 4 | 3 2 7 |
 | 1 5 7 | 8 3 2 | 9 6 4 |
 | 3 2 4 | 9 7 6 | 5 1 8 |
 +-------+-------+-------+
 | 4 1 6 | 5 2 9 | 8 7 3 |
 | 8 9 3 | 4 1 7 | 6 5 2 |
 | 5 7 2 | 6 8 3 | 1 4 9 |
 +-------+-------+-------+
 | 9 6 8 | 7 4 5 | 2 3 1 |
 | 7 3 5 | 2 9 1 | 4 8 6 |
 | 2 4 1 | 3 6 8 | 7 9 5 |
 +-------+-------+-------+


What am I doing wrong?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuK4

Postby Mathimagics » Mon Aug 19, 2019 7:21 pm

I was hoping to confirm unique solutions for the following (symmetric) reductions:

24 sums:
Code: Select all
 0,29, 0, 0, 0, 0,20, 0,
11,18, 0,27,18, 0,21,19,
 0, 0, 0, 0, 0, 0, 0, 0,
 0,19, 0,12,19, 0,26, 0,
 0,21, 0,19,19, 0,16, 0,
 0, 0, 0, 0, 0, 0, 0, 0,
25,22, 0,22,19, 0,17,18,
 0,13, 0, 0, 0, 0,28, 0


20 sums:
Code: Select all
 0,29, 0, 0, 0, 0,20, 0,
11, 0, 0,27,18, 0, 0,19,
 0, 0, 0, 0, 0, 0, 0, 0,
 0,19, 0,12,19, 0,26, 0,
 0,21, 0,19,19, 0,16, 0,
 0, 0, 0, 0, 0, 0, 0, 0,
25, 0, 0,22,19, 0, 0,18,
 0,13, 0, 0, 0, 0,28, 0
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Next

Return to Sudoku variants