Build a minimum-clue Sudoku unsolver My attempt at stating this question, but with a more objective solving criterion.

Your task is to build a program or function that takes a solved Sudoku grid S in the format of your choice and attempts to generate a problem grid with as few clues as possible that has S as its unique solution. (It doesn't matter what method S is the unique solution by, including brute force, as long as the solution is provably unique.)



Your program will be scored by running it through a set of 100,000 solution grids found in this file (7.82 MB download), and adding up the number of clues in all 100,000 problem grids that your solution produces.

The Sudoku solutions in the above test file are expressed as an 81-character string, from left-to-right, then top-to-bottom. The code required to turn the input in the test file into a usable solution will not count towards your solution's byte count.

As in my Flood Paint challenge, your program must actually produce a valid output for all 100,000 puzzles to be considered a valid solution. The program that outputs the fewest total clues for all 100,000 test cases is the winner, with shorter code breaking a tie.



Current scoreboard:


2,361,024 - nutki, C
2,580,210 - es1024, PHP
6,000,000 - CarpetPython, Python 2
7,200,000 - Joe Z., Python
C - 2,361,024 2,509,949 clues

Remove clues starting from the last cell if a brute force solver finds only one unique solution.

Second try: use heuristic to decide in which order to remove clues instead of starting from the last. This makes the code run much slower (20 minutes instead of 2 to calculate the result). I could make the solver faster, to experiment with different heuristics, but for now it will do.

#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
char ll[100];
short b[81];
char m[81];
char idx[81][24];
int s;
char lg[513];
void pri2() {
    int i;
    for(i=0;i&lt;81;i++) putchar(lg[b[i]]);
    putchar('\n');
}
void solve(pos){
int i,p;
if (s &gt; 1) return;
if (pos == 81) { s++; return; }
if (b[pos]) return solve(pos+1);
for (p=i=0;i&lt;24;i++) p |= b[idx[pos][i]];
for (i = 0; i &lt; 9; i++) if (!(p&amp;(1&lt;&lt;i))) {
    b[pos] = 1 &lt;&lt; i;
    solve(pos + 1);
}
b[pos] = 0;
}
int main() {
    int i,j,t;
    for(i=0;i&lt;9;i++) lg[1&lt;&lt;i]='1'+i;
    lg[0] = '.';
    for(i=0;i&lt;81;i++) {
    t = 0;
    for(j=0;j&lt;9;j++) if(i/9*9 + j != i) idx[i][t++] = i/9*9 + j;
    for(j=0;j&lt;9;j++) if(i%9 + j*9 != i) idx[i][t++] = i%9 + j*9;
    for(j=0;j&lt;81;j++) if(j/27 == i/27 &amp;&amp; i%9/3 == j%9/3 &amp;&amp; i!=j) idx[i][t++] = j;
    }
    while(scanf("%s ",ll)&gt;0) {
    memset(m, 0, sizeof(m));
    for(i=0;i&lt;81;i++) b[i] = 1 &lt;&lt; (ll[i]-'1');
    for(i=0;i&lt;81;i++) {
    int j,k,l = 99;
    for(k=0;k&lt;81;k++) if (m[k] &lt;= l) l = m[k], j = k;
    m[j] = 24;
    t = b[j]; b[j] = 0;
    s = 0; solve(0);
    if (s &gt; 1) b[j] = t;
    else for(k=0;k&lt;24;k++) m[idx[j][k]]++;
    }
    pri2();
    }
    return 0;
}