Sunday, November 27, 2005

Ocaml Sudoku solver

I stumbled upon this Sudoku solver by an accident. It's written in Ocaml, solves Sudoku puzzles and is 769 bytes (19 lines) long! (Also see the links to other solvers at the bottom of the linked page.)

I am not sure if "code density" is the right term but it's astonishing how much can be done in Ocaml in so few program instructions. When I analyze the program above, I understand how it works but I seriously doubt I will be able to write anything like it soon. Almost everything I ever knew about programming must be thrown out of the window and I must approach the problems from the new angle and actually THINK while coding. It's very nice feeling, the feeling I didn't have since VIC-20 Basic in the early 1980s. :)

Of course, it's not easy to approach programming from fresh angles when you have to make living for yourself and programming is currently not part of making that living... :)

7 comments:

r0b0t said...

Good luck with functional programming. I think that the future of programming lies within this paradigm.

Mormegil said...

Sudoku is an obvious example of a task suited much better for non-procedural languages. See also a very simple version in Prolog (well, not exactly Prolog, it uses the finite-domain solver in Prolog, actually) -- maybe it is a bit longer than the Ocaml version, but is IMHO much more understandable.

Anonymous said...

to r0b0t,
logical and func programming has been around for years and wasn't as successful as expected. For these kindda problems it works well (contraint programming even better) but in general...

r0b0t said...

To anonymous:

Facts:
- functional programming is there for a long time
- functional aproach works very well for these kind of problems

I don't know what were the expectations but for sure the functional aproach wasn't adopted not because it isn't suited for "general" problems. It wasn't adopted _despite_ the fact that it's great for solving all kind of problems with easiness that imperative languages can never achieve.

So why we still use C++ or java?
- programs written in any functional language used to have big overhead (they were interpreted, garbage collecting didn't work very well etc etc)
- programmers were used to imperative languages and the change of paradigm isn't that easy when you are coding in C for ten years every day

An why I say that the future lies in functional programming?
If we want applications to evolve and to offer more functionality, their code will become inevitably complex. And I don't see any better way for reducing it than functional approach.

Anonymous said...

r0b0t and anonymous(1): i studied functional programming (prolog and lisp) like 10 years ago and for me it's all only just backtracking, i don't believe that in future we'll learn the way to formulate all our computing tasks to solve just like that. it's tempting idea to write statements instead of writting code, but it doesn't sound realistic to me. i understands fuxoft's enthusiasm (remember my own finding out how to write quicksort on three lines), but it's virgin fascination of unkown pleasures...

r0b0t said...

Functional and logic programming is _NOT_ just backtracking!

Read for example this for nice examples:
Why Functional Programming Matters


And mister Fuka can also find some interesting learning material
there
.

Anonymous said...

Several people have said or implied that problems like solving Sudoku puzzles are inherently well suited to functional programming.

That is simply not true.

My OCaml Sudoku solver is not significantly different in terms of size or speed compared to implementations written in a variety of non-functional languages (e.g. C, C++, Java, C#).

Indeed, I have since replaced my implementation with a less functional one and I would say that Sudoku solving is not well suited to functional programming.

Cheers,
Jon Harrop.