9
5
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.
Rob
Posted 2012-05-01T17:46:42.393
Reputation: 299
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 – 2012-05-01T20:41:57.187
Changed challenge a bit, will add puzzles for input. – Rob – 2012-05-01T21:16:13.663
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 – 2012-05-01T23:02:16.917
As far as your program can take it, and as long as it has a solution that requires no guessing/backtracking. – Rob – 2012-05-01T23:19:55.977
6A Sudoku board contains 81 digits (3x3 boxes, 3x3 digits each), your examples have 27 only. – ugoren – 2012-05-02T04:41:56.933
That seems to allow too much flexibility to constitute a real spec. I can make my program only know really simple rules, and then it won't get very far; whereas a program with Nishio in its ruleset could get further, but would be longer. – Peter Taylor – 2012-05-02T13:01:25.227
@ugoren those examples are demonstrative of how output should be while being succinct. Example input and output show 81. – Rob – 2012-05-02T13:18:47.030
@PeterTaylor changed it to a code challenge, most minimal answer is the goal, shortest time is second goal. – Rob – 2012-05-02T13:21:12.487
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 – 2012-05-04T08:24:59.710
@Neil: From wikipedia: "The problem of determining if a partially filled square can be completed to form a Latin square is NP-complete.[6]". – Joel Cornett – 2012-05-06T17:51:03.530
A single sudoku instance might have multiple minimal "unsolved" states. Do we have to return them all, or just give one? – ESultanik – 2012-10-23T14:45:20.940
Less technical question -- "Most minimal answer in shortest time is the winner." -- Doesn't that just mean the first person to answer will win, whatever the length of the solution? – guypursey – 2013-03-07T18:45:38.430
This would be a good [tag:code-golf]. – None – 2014-04-11T15:19:48.153