Sudoku v Kakuro

Advanced methods and approaches for solving Sudoku puzzles

Sudoku v Kakuro

Postby Mathimagics » Tue Aug 16, 2016 6:34 am

I just thought I'd post you Sudoku technico's a little note to remind you how lucky you are, to have such a rich and varied menu of solver techniques - you have a variety of seafood, not to mention Xwings and Exocets (or some sort of missile) and the frabjous 3D Medusa ...

Apparently Sudoku, like Kakuro, has been shown to be NP-complete.

Bah humbug, I say ... :?

You guys have fixed domains. Luxury!!

Here's a little teaser, on a paltry 5x5 grid ... the effective cell domains are shown.

KT0606_MinForm_Hard.jpg
A very little hard puzzle
KT0606_MinForm_Hard.jpg (61.18 KiB) Viewed 211 times


So, what would you do next?

Me, I'm going tohave a beer .... :?


PS: I generated this example myself.
User avatar
Mathimagics
2017 Supporter
 
Posts: 334
Joined: 27 May 2015

Re: Sudoku v Kakuro

Postby Leren » Tue Aug 16, 2016 9:32 am

Actually Sodoku is not the only NP-complete problem that has been investigated on this site. Back in 2013 jpf posed the problem of finding the longest list of 5 digit primes that differ by only one digit between each successive prime in the list.

I took up the challenge with him and we swapped successive "record" length lists. As you probably know this is a Hamiltonian Path Problem which is NP-complete.

There are 8363 such primes, five of which are only "connected" to one other such prime by a single digit difference.

So the longest possible Hamiltonian cycle could only be of length 8358 and the longest Hamiltonian path could be of length 8360, but do examples of these in fact exist ?

After several weeks of trying, and using a modified version of an algorithm I found on the web and with a bit of luck, I finally succeeded on both counts and produced maximal examples of each.

The link to my triumphant post announcing these results is here.

Suffice it to say that this is the most satisfying thing I have ever done on this site - it beat Sudoku solving hands down, to put it mildly.

Leren
Leren
 
Posts: 2573
Joined: 03 June 2012

Re: Sudoku v Kakuro

Postby Mathimagics » Tue Aug 16, 2016 11:29 am

Interesting stuff!

You can actually combine your interest in graph theory with puzzling, by considering the Futoshiki problems described here.
User avatar
Mathimagics
2017 Supporter
 
Posts: 334
Joined: 27 May 2015


Return to Advanced solving techniques