Build a minimum-clue Sudoku unsolver
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;
}