{% extends "base.src" %}
{% block title %}sudoku{% endblock %}

{% block body %}
<ul>
<li><a href="Makefile">Makefile</a> (4.0K)</li>
<li><a href="README">README</a> (4.0K)</li>
<li><a href="grid1">grid1</a> (4.0K)</li>
<li><a href="grid2">grid2</a> (4.0K)</li>
<li><a href="grid3">grid3</a> (4.0K)</li>
<li><a href="grid4">grid4</a> (4.0K)</li>
<li><a href="grid5">grid5</a> (4.0K)</li>
<li><a href="grid6">grid6</a> (4.0K)</li>
<li><a href="grid9">grid9</a> (4.0K)</li>
<li><a href="maggesi.hs">maggesi.hs</a> (4.0K)</li>
<li><a href="solution1">solution1</a> (4.0K)</li>
<li><a href="solution2">solution2</a> (4.0K)</li>
<li><a href="solution3">solution3</a> (4.0K)</li>
<li><a href="solution4">solution4</a> (4.0K)</li>
<li><a href="solution5">solution5</a> (4.0K)</li>
<li><a href="solution6">solution6</a> (0)</li>
<li><a href="solution9">solution9</a> (4.0K)</li>
<li><a href="sudoku">sudoku</a> (12K)</li>
<li><a href="sudoku.c">sudoku.c</a> (4.0K)</li>
<li><a href="sudoku2">sudoku2</a> (8.0K)</li>
<li><a href="sudoku2.c">sudoku2.c</a> (4.0K)</li>
<li><a href="sudoku20090506.tgz">sudoku20090506.tgz</a> (4.0K)</li>
<li><a href="test.sh">test.sh</a> (4.0K)</li>
<hr><strong>README</strong>
<literal><pre>
C SUDOKU solver in 558 chars
============================

<a href=sudoku>sudoku</a>.c is a tiny, brute force sudoku solver.

SOURCE:
=======

#include &lt;stdio.h&gt;

int s[81], m[82], k, i;

main() {
for (i=0;i&lt;81;++i) {
scanf("%d",&s[i]);
m[i]=s[i];
}
for(;;) {
while (m[k]) k++;
if (k&gt;=81) {
  for (i=0;i&lt;81;++i) {
printf("%d ",s[i]);
if (i%9&gt;7) printf("\n");
  }
  return;
}
if (++s[k]&gt;9) {
  s[k--]=0;
  for(;m[k];)
if (k--==0) return;
} else {
  for (i=0;i&lt;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&gt;=81)
k++;
}
}
}


COMPACT VERSION (295 chars)
===========================

This (<a href=sudoku>sudoku</a>2.c) is a compacted version of the previous code.
Can you make it smaller? Let me know!

#define F for(;i&lt;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&gt;80)F;printf("%d%c",s[i++],i%9>7?10:32));else
if(++s[k]&gt;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 <a href=sudoku>sudoku</a> <a href=sudoku.c>sudoku.c</a>

The files grid&lt;n&gt; are some sample input grids.
The file <a href=grid9>grid9</a> is a particularly difficul input.
On my PC it take more 16 minutes to solve this.

USAGE:
======

$ cat <a href=grid1>grid1</a>
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

$ ./<a href=sudoku>sudoku</a> &lt; <a href=grid1>grid1</a>
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:

<a href="http://web.math.unifi.it/users/maggesi/repos/ocaml-<a href=sudoku>sudoku</a>-solver/">http://web.math.unifi.it/users/maggesi/repos/ocaml-sudoku-solver/</a>

So I decided I should learn OCaml! But... I failed. So, I wrote the
Sudoku solver in my preferred computer language.
</pre></literal>
{% endblock body %}
