9
\$\begingroup\$

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.

\$\endgroup\$

closed as off-topic by Rainbolt, ProgramFOX, Geobits, user80551, Hosch250 Apr 11 '14 at 15:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Rainbolt, ProgramFOX, Geobits, user80551, Hosch250
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ 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? \$\endgroup\$ – Keith Randall May 1 '12 at 20:41
  • \$\begingroup\$ Changed challenge a bit, will add puzzles for input. \$\endgroup\$ – Rob May 1 '12 at 21:16
  • \$\begingroup\$ 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? \$\endgroup\$ – Peter Taylor May 1 '12 at 23:02
  • 6
    \$\begingroup\$ A Sudoku board contains 81 digits (3x3 boxes, 3x3 digits each), your examples have 27 only. \$\endgroup\$ – ugoren May 2 '12 at 4:41
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Neil May 4 '12 at 8:24