Jump to content

Sudoku: NP-Complete


DonRocks

Recommended Posts

I just tried Sudoku for the first time today - I went straight to "Evil," thinking that it was possible to look at the puzzle, and solve it based on what you see (using "candidate numbers" in the blank cubes).

I solved the first puzzle in about thirty minutes, and didn't see what the big deal was (although I couldn't have done it without using the candidate numbers as a sort of "scratch pad").

Then I tried another one, and worked my way into a dead end - every single possibility staring at me was ambiguous, and it was then-and-there that I realized that Sudoku puzzles are NP-complete, and that there's no way to guarantee their solution without "peeking into the future," choosing between one number and another, and going forward until you either solve the puzzle, or hit a dead end. 

For this, it would require a separate "scratch pad," so that if you hit the dead end, you could undo your work. When I realized this, I realized that Sudoku is a puzzle best left for Turing Machines, and not for the human mind.

In a worst-case scenario, a 9-row by 9-column Sudoku puzzle requires 9**9 (9 to the ninth power) combinations. They're *always* solvable (if designed correctly), but they aren't solvable unless you're willing to "peak into the future" and see if your choice was right or wrong.

Fo dat sheet.

Link to comment
Share on other sites

Ha. I'm addicted to Sudoku. I've been playing mega-Sudoku (16x16) for years now.  I think what you say might be true for the 5* puzzles, sometimes for the 4*, but in my experience, when I've reached a "this or that" decision, it's because I've made a mistake early on. Anyway, don't give up, they're fun! :)

Link to comment
Share on other sites

4 hours ago, porcupine said:

Ha. I'm addicted to Sudoku. I've been playing mega-Sudoku (16x16) for years now.  I think what you say might be true for the 5* puzzles, sometimes for the 4*, but in my experience, when I've reached a "this or that" decision, it's because I've made a mistake early on. Anyway, don't give up, they're fun! :)

After reading your post, I did a little research - sure enough, from the Wikipedia article:

The general problem of solving Sudoku puzzles on n2×n2 grids of n×n blocks is known to be NP-complete.[18]

Which means that, for my purposes, playing Sudoku is like playing Solitaire - even if you play perfectly, you can run into the situation I was in yesterday - with everything correct, but also with no further moves available (without peaking into the future). I looked at this damned puzzle for *3 hours*, and even did a methodical row-column-matrix sweep for numbers 1-9 (twice!), and I'm certain it was correct - but I had painted myself into a corner, and could go no further.

One thing Sudoku does is to provide *excellent* mental focus if you don't use the open squares as scratch pads - that is very, very difficult, but forces you to think and think hard ("mental P.E.," a college professor of mine would have called it).

I'm also intrigued that for an 81-square Sudoku, the minimum number of clues that needs to be provided is 17 - this was mathematically proven in 2012 (confirmed in 2013). The reason I'm intrigued is that 81-17=64. 

I haven't looked into this, but both 81 and 64 are special numbers (9-squared and 8-squared, respectively), and I'm wondering if there has ever been a "general proof" for Sudoku puzzles of any size - my hypothesis is that for an "n-squared" Sudoku, the maximum number of empty boxes (which is mutually exclusive to the minimum number of clues) required is "(n-1)-squared."

So I'm guessing that, for a mega-Sudoku, or 256-space Sudoku (which is 16-squared), the maximum number of empty boxes you can have is 15-squared, or 225, which means that the minimum number of clues required is 256-225=31.

BTW, what do you use to fill in the boxes in a mega-Sudoku - hexadecimal digits (these just replace "10 through 15" with "A through F")?

Link to comment
Share on other sites

1 hour ago, DanielK said:

Try Kakuro puzzles instead for math-related puzzles.

The problem is that anything that's NP-Complete involves either incredibly lengthy (exponential) steps to complete (not every time, but in a worst-case scenario), or you have to flip a coin and hope you guess correctly (sometimes multiple coin flips).

"The Computational Complexity of the Kakuro Puzzle, Revisited" by Oliver Ruepp and Markus Holzer on link.springer.com

Refer to the Busy Beaver problem, Al Dente. :lol:

(Incidentally, this is the kind of (dare I say) useless shit that a grad student in Computer Science must study. Oh my *God* and my adviser (whom I like and respect immensely, but whose enthusiasm was absolutely exhausting) was buddies with Ron Graham, of all people.)

 

Link to comment
Share on other sites

20 hours ago, DonRocks said:

BTW, what do you use to fill in the boxes in a mega-Sudoku - hexadecimal digits (these just replace "10 through 15" with "A through F")?

1-9 and A-G. There's also a thing called beach sudoku, which is one example of why Western civilization is doomed.

  • Like 1
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...