Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

19-line Sudoku solver

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
jdh30

Joined: 29 Nov 2005
Posts: 4
:
Location: Cambridge, UK

Items
PostPosted: Tue Nov 29, 2005 3:37 am    Post subject: 19-line Sudoku solver Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Tue Nov 29, 2005 7:14 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
jdh30

Joined: 29 Nov 2005
Posts: 4
:
Location: Cambridge, UK

Items
PostPosted: Tue Nov 29, 2005 11:22 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Mark

Joined: 19 Oct 2005
Posts: 30
:
Location: Arizona

Items
PostPosted: Thu Dec 01, 2005 1:26 am    Post subject: Re: 19-line Sudoku solver Reply with quote

jdh30 wrote:
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?


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
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Dec 01, 2005 4:43 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Thu Dec 01, 2005 7:33 am    Post subject: Reply with quote

I'm kind of ashamed of my C-style Wink 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
View user's profile Send private message Send e-mail Visit poster's website
jdh30

Joined: 29 Nov 2005
Posts: 4
:
Location: Cambridge, UK

Items
PostPosted: Thu Dec 01, 2005 5:34 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Thu Dec 01, 2005 5:42 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
jdh30

Joined: 29 Nov 2005
Posts: 4
:
Location: Cambridge, UK

Items
PostPosted: Thu Dec 01, 2005 6:03 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Thu Dec 01, 2005 6:17 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Dec 02, 2005 1:37 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron