SudoKakuro

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Tarek SudoKakuro 01

Postby tarek » Thu Sep 20, 2018 10:57 am

Here is my attempt. A Sudokakuro X AK. I intentionally made the clues 2 squares diagonally apart so that it can work as an AK zero killer X too
at the moment this is machine level difficulty

Image

tarek

[Edit: Forgot to mention explicitly that the puzzle is has also X diagonals & Anti-King)
Last edited by tarek on Thu Sep 20, 2018 5:20 pm, edited 2 times in total.
User avatar
tarek
 
Posts: 2756
Joined: 05 January 2006

Re: SudoKakuro

Postby hkociemba1 » Thu Sep 20, 2018 1:47 pm

tarek wrote:Here is my attempt.

BUt it seems that the solution is not unique. Here are two of them.
Code: Select all
 +----------+----------+----------+
 |  5  .  . |  . 15  . |  .  . 16 |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  . 16 |  .  .  . | 22  .  . |
 +----------+----------+----------+
 |  .  .  . |  .  .  . |  .  .  . |
 | 19  .  . |  . 15  . |  .  . 21 |
 |  .  .  . |  .  .  . |  .  .  . |
 +----------+----------+----------+
 |  .  . 20 |  .  .  . | 29  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 | 12  .  . |  . 13  . |  .  . 17 |
 +----------+----------+----------+

 +-------+-------+-------+
 | 4 3 8 | 6 9 5 | 2 7 1 |
 | 2 5 7 | 1 4 3 | 8 6 9 |
 | 1 6 9 | 2 8 7 | 5 4 3 |
 +-------+-------+-------+
 | 7 8 1 | 4 5 9 | 3 2 6 |
 | 6 9 2 | 3 7 1 | 4 8 5 |
 | 3 4 5 | 8 6 2 | 9 1 7 |
 +-------+-------+-------+
 | 9 2 3 | 7 1 8 | 6 5 4 |
 | 5 1 6 | 9 2 4 | 7 3 8 |
 | 8 7 4 | 5 3 6 | 1 9 2 |
 +-------+-------+-------+

+-------+-------+-------+
 | 4 3 8 | 6 9 5 | 1 7 2 |
 | 2 5 7 | 1 4 3 | 8 6 9 |
 | 1 6 9 | 2 8 7 | 5 4 3 |
 +-------+-------+-------+
 | 7 8 1 | 4 5 9 | 3 2 6 |
 | 6 9 2 | 3 7 1 | 4 8 5 |
 | 3 4 5 | 8 6 2 | 9 1 7 |
 +-------+-------+-------+
 | 9 2 3 | 7 1 8 | 6 5 4 |
 | 5 1 6 | 9 2 4 | 7 3 8 |
 | 8 7 4 | 5 3 6 | 2 9 1 |
 +-------+-------+-------+
User avatar
hkociemba1
 
Posts: 33
Joined: 08 August 2018

Re: SudoKakuro

Postby tarek » Thu Sep 20, 2018 5:13 pm

thanks hkociemba1 for taking the interest and time,

I should have explicitly said that it was also X diagonalss & Anti-King

here is my unique solution

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


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

Re: SudoKakuro

Postby hkociemba1 » Fri Sep 21, 2018 3:32 pm

I added support for SudokuX and SudokuP to my solver which was very easy since this means just the addition of some clauses to the cnf file. I observed that you can remove many clues from your puzzle and it still is valid. These 9 clues are sufficient for example
Code: Select all
 5  .  .  .  .  .  .  . 16
  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  . 22  .  .
  .  .  .  .  .  .  .  .  .
 19  .  .  .  .  .  .  . 21
  .  .  .  .  .  .  .  .  .
  .  . 20  .  .  . 29  .  .
  .  .  .  .  .  .  .  .  .
 12  .  .  .  .  .  .  . 17

though this looks of course nicer:
Code: Select all
  5  .  .  .  .  .  .  . 16
  .  .  .  .  .  .  .  .  .
  .  . 16  .  .  . 22  .  .
  .  .  .  .  .  .  .  .  .
 19  .  .  .  .  .  .  . 21
  .  .  .  .  .  .  .  .  .
  .  . 20  .  .  . 29  .  .
  .  .  .  .  .  .  .  .  .
 12  .  .  .  .  .  .  . 17
User avatar
hkociemba1
 
Posts: 33
Joined: 08 August 2018

Re: SudoKakuro

Postby hkociemba1 » Fri Sep 21, 2018 11:08 pm

Code: Select all
 +----------+----------+----------+
 |  .  .  . |  8  . 18 |  . 14  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 +----------+----------+----------+
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . | 23  . 15 |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 +----------+----------+----------+
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  6  . | 15  . 14 |  .  .  . |
 +----------+----------+----------+

This example shows that you only need at most 8 clues for a valid SudokuKakuro-X-P-DP.
Does there exist a valid "standard" Sudoku with the X, P and DP property and only 8 clues? It seems that the information about the sum of the adjacent values of a cell provides more information than the value of the cell itself.
Hidden Text: Show
+-------+-------+-------+
| 8 6 2 | 4 5 9 | 7 1 3 |
| 9 3 7 | 1 8 6 | 2 4 5 |
| 5 1 4 | 3 2 7 | 9 8 6 |
+-------+-------+-------+
| 3 8 6 | 9 4 5 | 1 2 7 |
| 7 9 1 | 8 6 2 | 3 5 4 |
| 2 4 5 | 7 3 1 | 8 6 9 |
+-------+-------+-------+
| 6 7 8 | 2 9 4 | 5 3 1 |
| 4 2 9 | 5 1 3 | 6 7 8 |
| 1 5 3 | 6 7 8 | 4 9 2 |
+-------+-------+-------+
User avatar
hkociemba1
 
Posts: 33
Joined: 08 August 2018

Re: SudoKakuro

Postby Mathimagics » Sat Sep 22, 2018 6:46 am

.
I seem to have unleashed a monster! :shock:

We have as yet done little work on any of the DP variants, I had only just begun to look at these for the standard Sudoku case (see here) when I got the idea for SudoKakuro.

All we have so far is that MNC (minimum number of clues) for SudokuDP is probably less than 12.

For SudokuP we now know MNC is exactly 11, and we also have work in progress on SudokuPX, which has found some 9-clue puzzles, and owing to their scarcity we think that MNC is probably 9.

So it seems likely that adding the DP constraints to SudokuPX might well give us 8-clue SudokuPX-DP puzzles.

hkociemba1 wrote:It seems that the information about the sum of the adjacent values of a cell provides more information than the value of the cell itself.


Perhaps that should be "potentially provides"?

A complicating factor is that Kakuro clues (KC), unlike standard clues (SC), are sensitive to ANY variation of the grid, that is, both to grid relabelling, and to VPT's (validity-preserving grid transformations).

In any case, the proposition can be demonstrated by finding a grid G for which, in some Sudoku variant, there is a KC puzzle for which NKC(G) < NSC(G), where NSC(G) is minimal for G.

Or, equivalently, by finding any G for which NKC(G) = 7 for any variant.
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: SudoKakuro

Postby hkociemba1 » Sat Sep 22, 2018 8:13 am

Mathimagics wrote:Or, equivalently, by finding any G for which NKC(G) = 7 for any variant.

I found this valid XP-DP puzzle by just playing around and changing values manually.
Code: Select all
 +----------+----------+----------+
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  . 22 |  . 30  . |  .  .  . |
 +----------+----------+----------+
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  . 28 |  . 30  . | 29  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 +----------+----------+----------+
 |  .  . 22 |  . 22  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 +----------+----------+----------+
 +-------+-------+-------+
 | 7 8 4 | 3 1 6 | 2 5 9 |
 | 3 2 6 | 5 9 4 | 1 7 8 |
 | 5 1 9 | 7 2 8 | 6 3 4 |
 +-------+-------+-------+
 | 9 3 8 | 4 6 1 | 5 2 7 |
 | 2 6 1 | 9 5 7 | 4 8 3 |
 | 4 7 5 | 2 8 3 | 9 6 1 |
 +-------+-------+-------+
 | 1 9 3 | 6 7 5 | 8 4 2 |
 | 6 4 2 | 8 3 9 | 7 1 5 |
 | 8 5 7 | 1 4 2 | 3 9 6 |
 +-------+-------+-------+
User avatar
hkociemba1
 
Posts: 33
Joined: 08 August 2018

Re: SudoKakuro

Postby hkociemba1 » Sat Sep 22, 2018 8:29 am

Now manually found this one with only 6 clues
Code: Select all
 +----------+----------+----------+
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  . 22 |  . 30  . |  .  .  . |
 +----------+----------+----------+
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  . 28 |  .  .  . | 30  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 +----------+----------+----------+
 |  .  . 22 |  . 12  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 +----------+----------+----------+

 +-------+-------+-------+
 | 8 6 4 | 3 2 7 | 5 1 9 |
 | 3 2 7 | 5 9 1 | 8 4 6 |
 | 5 1 9 | 8 4 6 | 3 2 7 |
 +-------+-------+-------+
 | 2 4 6 | 1 7 5 | 9 8 3 |
 | 1 5 3 | 9 6 8 | 2 7 4 |
 | 9 7 8 | 2 3 4 | 6 5 1 |
 +-------+-------+-------+
 | 4 3 1 | 6 5 2 | 7 9 8 |
 | 6 8 5 | 7 1 9 | 4 3 2 |
 | 7 9 2 | 4 8 3 | 1 6 5 |
 +-------+-------+-------+

Where is the lower limit?
User avatar
hkociemba1
 
Posts: 33
Joined: 08 August 2018

Re: SudoKakuro

Postby Mathimagics » Sat Sep 22, 2018 9:29 am

.
Nice job, well done! 8-)

You found these in the time it took me to make my solver work with the various variant modes. For completness I have added W mode (Windoku), which is just P mode with a different grid partition.

So your proposition is certainly verified, NKC can clearly be less than NSC.

What is the minimum? Well, it can't be much lower than 6, can it? Do I hear 5?

BTW, your 6-clue puzzle appears to be minimal, I can't remove any clue
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: SudoKakuro

Postby Mathimagics » Sun Sep 23, 2018 9:37 am

.
There are definitely 8-clue SudokuPXD (SudokuPX + DP) puzzles!

See SudokuPXD for details.

hkociemba1's NKC = 6 example above has min NSC = 9, but from that grid I was able to find an 8-clue (SC) puzzle.
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Previous

Return to Sudoku variants

cron