The New Sudoku Players' Forum

[Mathimagics]

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.

A very little hard puzzle

KT0606_MinForm_Hard.jpg (61.18 KiB) Viewed 1637 times

So, what would you do next?

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


PS: I generated this example myself.

[Leren]

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

[Mathimagics]

Interesting stuff!

You can actually combine your interest in graph theory with puzzling, by considering the Futoshiki problems described here.