C SUDOKU solver in 558 chars ============================ sudoku.c is a tiny, brute force sudoku solver. SOURCE: ======= #include <stdio.h> int s[81], m[82], k, i; main() { for (i=0;i<81;++i) { scanf("%d",&s[i]); m[i]=s[i]; } for(;;) { while (m[k]) k++; if (k>=81) { for (i=0;i<81;++i) { printf("%d ",s[i]); if (i%9>7) printf("\n"); } return; } if (++s[k]>9) { s[k--]=0; for(;m[k];) if (k--==0) return; } else { for (i=0;i<81;++i) { if (i==k || s[i]==0) continue; if (i%9==k%9 || i/9==k/9 || (i/3)%3==(k/3)%3 && i/3/9==k/3/9) if (s[i]==s[k]) break; } if (i>=81) k++; } } } COMPACT VERSION (295 chars) =========================== This (sudoku2.c) is a compacted version of the previous code. Can you make it smaller? Let me know! #define F for(;i<81 s[81],m[82],k,i,e;main(){F;++i)scanf("%d",s+i),m[i]=s[i];for(;!e; ){for(i=0;m[k];)k++;if(e=k>80)F;printf("%d%c",s[i++],i%9>7?10:32));else if(++s[k]>9)for(s[k--]=0;m[k];e=!k--);else{F&&(i==k||s[i]==0||s[i]-s[k] ||i%9-k%9&&i/9-k/9&&(i/3%3-k/3%3||i/3/9-k/3/9));++i);k+=i/81;}}} COMPILATION: ============ $ gcc -o sudoku sudoku.c The files grid<n> are some sample input grids. The file grid9 is a particularly difficul input. On my PC it take more 16 minutes to solve this. USAGE: ====== $ cat grid1 0 5 0 0 6 0 0 0 1 0 0 4 8 0 0 0 7 0 8 0 0 0 0 0 0 5 2 2 0 0 0 5 7 0 3 0 0 0 0 0 0 0 0 0 0 0 3 0 6 9 0 0 0 5 7 9 0 0 0 0 0 0 8 0 1 0 0 0 6 5 0 0 5 0 0 0 3 0 0 6 0 $ ./sudoku < grid1 9 5 3 7 6 2 8 4 1 6 2 4 8 1 5 9 7 3 8 7 1 3 4 9 6 5 2 2 8 9 4 5 7 1 3 6 1 6 5 2 8 3 4 9 7 4 3 7 6 9 1 2 8 5 7 9 6 5 2 4 3 1 8 3 1 8 9 7 6 5 2 4 5 4 2 1 3 8 7 6 9 HISTORY ======= 31.03.2009: I was amazed by the OCaml Sudoku solver by Marco Maggesi: http://web.math.unifi.it/users/maggesi/repos/ocaml-sudoku-solver/ So I decided I should learn OCaml! But... I failed. So, I wrote the Sudoku solver in my preferred computer language.