# Minimal Sudoku Generator

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.

-
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
A Sudoku board contains 81 digits (3x3 boxes, 3x3 digits each), your examples have 27 only. – ugoren May 2 '12 at 4:41
@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