Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 4 down vote favorite
4

Ask questions if you need to, I'll elaborate on anything that needs clarified.

My challenge is to unsolve a sudoku to a minimal state. Basically take a supplied, solved, sudoku board and unsolve it as far as possible while keeping the solution unique.

I'll leave input up to you, I don't like forcing anything which would make some solutions longer.

Output can be anything reasonable, as long as it spans the nine lines it'll take to display the sudoku board, for example:

{[0,0,0], [0,0,0], [0,1,0]} ┐
{[4,0,0], [0,1,0], [0,0,0]} ├ Easily understood to me
{[1,2,0], [0,0,0], [0,0,0]} ┘

000000010 ┐
400010000 ├ A-OKAY
120000000 ┘

000, 000, 010 ┐
400, 010, 000 ├ Perfectly fine
120, 000, 000 ┘

000000010400010000120000000 <-- Not okay!

Example

input:
693 784 512
487 512 936
125 963 874

932 651 487
568 247 391
741 398 625

319 475 268
856 129 743
274 836 159

output:

000 000 010
400 000 000
020 000 000

000 050 407
008 000 300
001 090 000

300 400 200
050 100 000
000 806 000

Most minimal answer in shortest time is the winner.

share|improve this question
So we should take in a sudoku board with some entries filled in, and output another sudoku board with some more entries filled in, such that it has a unique solution? – Keith Randall May 1 '12 at 20:41
Changed challenge a bit, will add puzzles for input. – Rob May 1 '12 at 21:16
Is it required that the output board be solvable without brute force (i.e. using some polynomial-time strategy)? And what does "as far as possible" mean? Is a local minimum acceptable even if it isn't a global minimum? – Peter Taylor May 1 '12 at 23:02
4  
A Sudoku board contains 81 digits (3x3 boxes, 3x3 digits each), your examples have 27 only. – ugoren May 2 '12 at 4:41
1  
@Rob, Problem isn't finding a program which generates a valid (solvable) sudoku puzzle. The problem is proving it is as minimal as you can get. I think that in of itself makes this a polynomial-order problem, which makes the solution to this problem work in polynomial speed or otherwise it is merely an approximation. – Neil May 4 '12 at 8:24
show 7 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.