|
View previous topic :: View next topic |
Author |
Message |
| jdh30
| Joined: 29 Nov 2005 | Posts: 4 | : | Location: Cambridge, UK | Items |
|
Posted: Tue Nov 29, 2005 3:37 am Post subject: 19-line Sudoku solver |
|
|
Here's a 19-line OCaml program for solving Sudoku puzzles:
http://www.ffconsultancy.com/free/sudoku/
Any idea what the shortest Sudoku solving program is?
Has anyone used Sudoku solvers to compare programming languages by performance or verbosity?
Cheers,
Jon. |
|
Back to top |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Tue Nov 29, 2005 7:14 am Post subject: |
|
|
Hi Jon !
FWIW, I recoded my OCaml solver in C and got only a 10% speedup. Clearly, my OCaml solver is already in C style, so this is not very surprising...
Alain |
|
Back to top |
|
|
| jdh30
| Joined: 29 Nov 2005 | Posts: 4 | : | Location: Cambridge, UK | Items |
|
Posted: Tue Nov 29, 2005 11:22 am Post subject: |
|
|
Hi Alain!
frisch wrote: |
FWIW, I recoded my OCaml solver in C and got only a 10% speedup. Clearly, my OCaml solver is already in C style, so this is not very surprising...
|
I recoded my mini implementation in C++ and it was much longer and less capable (e.g. couldn't fold over the solutions easily) but 4x faster than the OCaml. In particular, gcc does a much better job of optimising the "invalid" function.
I implemented a few low-level optimisations and the OCaml remained faster per line or byte of code than the C++. Interestingly, my OCaml implementation gets a lot faster if you hoist computation of the coordinates out of the "invalid" function into a list but if you do the same in the C++ then it becomes much slower.
I'll port my OCaml to SML when I get the time...
Cheers,
Jon. |
|
Back to top |
|
|
| Mark
| Joined: 19 Oct 2005 | Posts: 30 | : | Location: Arizona | Items |
|
Posted: Thu Dec 01, 2005 1:26 am Post subject: Re: 19-line Sudoku solver |
|
|
I'm not sure about THE shortest, but here's an amusing 4-liner in Perl:
Code: |
$a=8;$G{int(++$a/9).$a%9+1}=$_ for split//,<>;@A=1..9;sub c{int(($_[0]-1
)/3)*3}sub G{for$y(@A){for$x(@A){$p=$t=$G{my$c=$y.$x}&&next;$t.=$G{$_.$x
}.$G{$y.$_}for@A;for$f(1..3){$t.=$G{c($y)+$f.c($x)+$_}for 1..3}G($G{$c}=
$_)&&return for grep$t!~m/$_/,@A;return$G{$c}=0}}die map{$G{$_}}9..99}G
|
Annotations of the above code can be found at:
http://www.ecclestoad.co.uk/blog/2005/05/27/obfuscation_as_a_learning_tool.html
Mark |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Thu Dec 01, 2005 4:43 am Post subject: |
|
|
jdh30 wrote: | Hi Alain!
frisch wrote: |
FWIW, I recoded my OCaml solver in C and got only a 10% speedup. Clearly, my OCaml solver is already in C style, so this is not very surprising...
|
I recoded my mini implementation in C++ and it was much longer and less capable (e.g. couldn't fold over the solutions easily) but 4x faster than the OCaml. Jon. |
I'd like to see these C-versions nevertheless.
Are they available or do you insist people must learn
OCaml first ? ;-) |
|
Back to top |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Thu Dec 01, 2005 7:33 am Post subject: |
|
|
I'm kind of ashamed of my C-style The C program is partly generated by an OCaml program, and not up-to-date (it was when I compared it with the OCaml solver). I might publish the code later this week.
-- Alain |
|
Back to top |
|
|
| jdh30
| Joined: 29 Nov 2005 | Posts: 4 | : | Location: Cambridge, UK | Items |
|
Posted: Thu Dec 01, 2005 5:34 pm Post subject: |
|
|
Here's the C++ translation of my OCaml code:
Code: |
#include <iostream>
#include <vector>
using namespace std;
vector<string> m(9);
void print() {
for (vector<string>::iterator it = m.begin(); it != m.end(); it++)
cout << *it << endl;
}
bool invalid(int i, int x, int y, int n) {
return i<9 && (m.at(y).at(i) == n || m.at(i).at(x) == n ||
m.at(y/3*3 + i/3).at(x/3*3 + i%3) == n ||
invalid(i+1, x, y, n));
}
template<typename F, typename T>
T search(int x, int y, F f, T accu) {
if (x == 9) return search(0, y+1, f, accu);
if (y == 9) return f(accu);
if (m.at(y).at(x) != '0') return search(x+1, y, f, accu);
for (char n='1'; n<='9'; n++)
if (!invalid(0, x, y, n)) {
m.at(y).at(x) = n;
accu = search(x+1, y, f, accu);
m.at(y).at(x) = '0';
}
return accu;
}
int main_aux(int i) { print(); return i+1; }
int main() {
for (vector<string>::iterator it=m.begin(); it != m.end(); it++) cin >> *it;
cout << search(0, 0, main_aux, 0) << " solutions\n";
return 0;
}
|
C++ has no support for closures, of course, so the utility of a folding "search" function is limited. Pattern matching also makes the OCaml slightly easier to understand.
However, g++ does a much better job of optimising the expressions x/3*3, i/3 and i mod 3 than the OCaml compilers, so the C++ is up to 5x faster overall.
The task of solving Sudoku puzzles is so simple that programmers can manually apply a variety of low-level optimisations to C/C++ code which are not as effective with OCaml. Consequently, OCaml's performance is not likely to be as good as C++ for this task. However, a simple solver is significantly more concise and comprehensible in OCaml and performance is not really an issue.
Cheers,
Jon. |
|
Back to top |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Thu Dec 01, 2005 5:42 pm Post subject: |
|
|
Code: |
The task of solving Sudoku puzzles is so simple that programmers can manually apply a variety of low-level optimisations to C/C++ code which are not as effective with OCaml. Consequently, OCaml's performance is not likely to be as good as C++ for this task. However, a simple solver is significantly more concise and comprehensible in OCaml and performance is not really an issue.
|
I think that many people here are now interested in more difficult puzzles (eg. 25x25), precisely because it makes it possible to somewhat abstract from very low-level optimizations and to focus on algorithms. I doubt than a transcription of my OCaml solver to C would give a significant improvement (my last attempt gave a 10% speedup). |
|
Back to top |
|
|
| jdh30
| Joined: 29 Nov 2005 | Posts: 4 | : | Location: Cambridge, UK | Items |
|
Posted: Thu Dec 01, 2005 6:03 pm Post subject: |
|
|
frisch wrote: | Jon Harrop wrote: |
The task of solving Sudoku puzzles is so simple that programmers can manually apply a variety of low-level optimisations to C/C++ code which are not as effective with OCaml. Consequently, OCaml's performance is not likely to be as good as C++ for this task. However, a simple solver is significantly more concise and comprehensible in OCaml and performance is not really an issue.
|
I think that many people here are now interested in more difficult puzzles (eg. 25x25), precisely because it makes it possible to somewhat abstract from very low-level optimizations and to focus on algorithms. I doubt than a transcription of my OCaml solver to C would give a significant improvement (my last attempt gave a 10% speedup).
|
I haven't tried developing any more sophisticated algorithms but my impression is that the most efficient approaches (e.g. dancing links) would be easier to write and faster to run in C++ than in OCaml. |
|
Back to top |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Thu Dec 01, 2005 6:17 pm Post subject: |
|
|
I think my solver can be translated to C in a quite straightforward way, but I doubt it will run really faster
(at least I was not able to do it). Now you can say that it does not use dancing links, but it seems to be competitive with solvers that do. |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Fri Dec 02, 2005 1:37 pm Post subject: |
|
|
below is my C-version. Not very much optimized
but you see the algo.
Anyone interested to do it in assembly ?
http://groups.yahoo.com/group/hugi-compo/
#include <stdio.h>
int a,b,i,j,k,x,y;
int A[88],B[88],X[88],Y[88],S[88];
int Ux[9],Uy[9],Ub[9];
int main(){
for(i=0;i<9;i++){Ux[i]=0;Uy[i]=0;Ub[i]=0;}
i=-1;k=3;for(x=0;x<9;x++)for(y=0;y<9;y++){
i++;S[i]=fgetc(stdin)-48;X[i]=x;Y[i]=y;b=k*(x/k)+y/k;B[i]=b;
if(S[i]>0){a=1<<S[i];Ux[x]|=a;Uy[y]|=a;Ub[b]|=a;} }
i=-1;
m1:i++;if(i>80){for(j=0;j<81;j++)printf("%i",A[j]);printf("\n");exit(0);}
if(S[i]>0){A[i]=S[i];goto m1;};b=B[i];x=X[i];y=Y[i];A[i]=0;
m2:A[i]++;a=1<<A[i];if(A[i]>9)goto m3;
if(a&(Ux[x]|Uy[y]|Ub[b]))goto m2;
Ux[x]+=a;Uy[y]+=a;Ub[b]+=a;goto m1;
m3:i--;x=X[i];y=Y[i];b=B[i];a=1<<A[i];if(S[i]>0)goto m3;
Ub[b]-=a;Uy[y]-=a;Ux[x]-=a;goto m2;
} |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|