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   

Is it worth making an open source Sudoku library?

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

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Sat Jan 16, 2010 2:19 pm    Post subject: Is it worth making an open source Sudoku library? Reply with quote

I keep thinking about starting a production quality open source library of Sudoku routines. There are many places one can find various bits and pieces of open source Sudoku code, but finding that code takes a fair bit of work, no one source really has all the bits and pieces that you really want, and the details of the licenses vary from place to place. Wouldn't it be nice if there was one place you could look for high quality code that is fast, readable, and fairly complete?

Personally, I want to see something that is in C, C++, or a mixture of the two, has readable well documented code, has a license that allows commercial use, is written so you can use individual parts without bringing in the entire library, and covers a reasonable range of things.

What I don't know is if others would be interested in working on that, or if one of my preferences needs to be changed to gain sufficient support for the project. Some people might be more comfortable with a more restrictive license, others might prefer a different programming language, and so on. The Sudoku field isn't that large, compared to say operating systems or web servers, so a comparatively large percentage of us would need to be on board to have any chance of success.

Is there any interest in such a project, or am I just day dreaming?
Back to top
View user's profile Send private message
humble_programmer

Joined: 27 Jun 2006
Posts: 69
:
Location: Colorado Springs, USA

Items
PostPosted: Sat Jan 16, 2010 5:23 pm    Post subject: Reply with quote

I'm on board...I think it's a great idea. Plain ANSI C would probably give the best combination of performance and portability, and I would also suggest that it be hosted on SourceForge, CodePlex, or a similar site. I am willing to contribute code and/or documentation.
_________________
Cheers!
Humble Programmer
,,,^..^,,,
www.humble-programmer.com
Back to top
View user's profile Send private message Visit poster's website
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Sat Jan 16, 2010 7:34 pm    Post subject: Really good idea JasonLion Reply with quote

Really good idea JasonLion
Back to top
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Sat Jan 16, 2010 11:15 pm    Post subject: Reply with quote

id be on board with this idea as well i have all my search routines open sourced already in turbo pascal.. Smile
Back to top
View user's profile Send private message
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Sun Jan 17, 2010 4:45 am    Post subject: Reply with quote

I am an olde and hoary coder.

I think that a library of pseudo code is better.

The comments of well documented code are enough to let
a clever person know what and how to do stuff.

A library of mixed code isn't bad, people that cannot code cannot profit.

Shortest, I prefer pseudo code as it can be read by most.
Good commenting is pseudo code.

I have no code to offer, I wrote at hardware level, around 40 years ago.

Just for a laugh, any of you remember "peeks and pokes"?
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sun Jan 17, 2010 4:24 pm    Post subject: Reply with quote

a problem with pseudo code is you need a working implementation that faithfully transalates the pseudo code
to prove that it works and is efficient

case in point: what would the pseudo code for bbsudoku look like?
I bet it would be non-trivial to go from that pseudo code back to a comparably fast re-implementation of the original

a problem for real code is agreeing on an api and grid representation
e.g., for algorithmic readability vs. efficiency I strive for readability
but efficiency almost always win out
especially in hot inner loops

I can cite many (non-sudoku) papers that present beautiful and simple algorithms that would never be used in practice

so I think that the purpose of the project must be clear from the start
a tutorial code exposition would be much different from an exposition
that you would want to use in your competitive solver implementation
Back to top
View user's profile Send private message Visit poster's website
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Sun Jan 17, 2010 5:35 pm    Post subject: Reply with quote

My personal interest is in production quality, readable, well documented, source code. Inner loops in routines that cause user visible delays need to be optimized, occasionally heavily optimized. However, most of the code, which gets run infrequently or at user invisible times, should aim for readability and maintainability, without worrying too much about speed (at least until performance problems become apparent). In practice, that seems to mean very heavy optimization of the brute force solver, and only occasional tweaks to just about everything else.
Back to top
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Sun Jan 17, 2010 6:59 pm    Post subject: Reply with quote

For my first code submission, I offer JSolve, documented in JSolve - yet another really fast brute force Sudoku solver.

This provides a real world example of what I am thinking when I say readable and well documented code.

JSolve was designed to fit the Sudoku routine library category of fastest possible brute force solver.
Back to top
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Wed Jan 20, 2010 7:50 pm    Post subject: Reply with quote

Personally, I wouldn't like my source code being part of other commercial software, or worse, the assignment of some student who doesn't take the effort of doing his assignments by himself

However, I think that there could be some common C++ interface for all sudoku solvers and generators libraries

It is possible to design an interface that provides all (or most) sudoku related functionality, so that each different contributer can inherit and implement this abstract class with its own implementation

Moreover, once there is a common interface, it is possible to create a timing measurement program that use this interface, so all implementations timings can be compared with the same operations, thus creating a benchmark

In addition, there could be some kind of algorithmic archive for sudoku solvers and generators where only the algorithms behind the implementations are described
Back to top
View user's profile Send private message Send e-mail
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Fri Jan 22, 2010 12:19 am    Post subject: Reply with quote

gsf wrote:
a problem with pseudo code is you need a working implementation that faithfully transalates the pseudo code
to prove that it works and is efficient


I hear you.

I don't want a library for "idiots" to build a sudoku program that they can or sell or buy a grade.

As a side issue, offered flavors of C ( and others ) as well as OS make the code an adventure, not to mention computer issues for speed checks.

I don't want a library made up of one platform, one cpu, one OS.

Ideal to me is the best algorithm for each useful chunk of code,
independent of cpu and OS.

( Yes, I know that is only sort of attainable. Low level stuff is hardware and software dependent.)

I like this library idea. I like it in the "best algorithm" sense, broken down to routines, subroutines and functions.

Yep, I know. Confused
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Fri Jan 22, 2010 2:48 am    Post subject: Reply with quote

wapati wrote:
I don't want a library made up of one platform, one cpu, one OS.

Ideal to me is the best algorithm for each useful chunk of code,
independent of cpu and OS.

( Yes, I know that is only sort of attainable. Low level stuff is hardware and software dependent.)

portable algorithms in C are easily attainable
its the gui's that foul up the works
that's one of the reasons why my solver is strictly command line
that solver btw contains algorithms from 4 other contributors
the hardest part in gluing them together was reconciling the grid data structure
Back to top
View user's profile Send private message Visit poster's website
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Fri Jan 22, 2010 3:12 am    Post subject: Reply with quote

Right now I am thinking about including things like: a fast brute force solver, a small very easy to port solver that is reasonably fast, puzzle compression, random puzzle generation (with an approximately uniform distribution and various symmetry options).

I wonder about having "human methods" solvers (beyond the simplest methods) and difficulty rating, because I suspect that this is where most of us who have commercial products feel that we have the most value added. If people want to contribute this, then great. But, this isn't something I expect to be included early on.

I do not want to include anything that deals with the OS or GUI. The only exceptions would be a command line utility to allow us to run/test the code and makefiles/project files for the major build systems.

One of the things that most excites me is talking about the various possibilities for the grid data structure with other people who have actual experience with choices other than the ones I made. I have never seen anyone talk about this for more than two or three sentences.


Last edited by JasonLion on Sun Jan 24, 2010 2:59 pm; edited 1 time in total
Back to top
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Fri Jan 22, 2010 7:06 am    Post subject: Reply with quote

wapati wrote:
Ideal to me is the best algorithm for each useful chunk of code,
independent of cpu and OS.


That sounds like java

If using C code, it is possible to ensure all code is supported by strict ansi-C compiler mode, and to make a porting layer per OS for specific code that runs differently on each different OS, such as time measurment, random numbers generation, threads operations etc

The porting layer should contain defines for each functionality, with the same interface, so that per OS, there will be different implementation for the defines, but the library code will remain the same
Back to top
View user's profile Send private message Send e-mail
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Fri Jan 22, 2010 7:47 am    Post subject: Reply with quote

Quote:
One of the things that most excites me is talking about the various possibilities for the grid data structure with other people who have actual experience with choices other than the ones I made. I have never seen anyone talk about this for more than two or three sentences.


grid structure is the main factor here: most people use only 4 definitive area
types when calling functions when doing logic type moves.

and its another question is how is it stored?

for example my program can be viewed here

uses integer arrays

{ i am nearly completed rebuilding the program from ground up and will post it in the next week or so.}

uses logic only and i did manage to code a generator that verifies the uniqueness based on the logic i have implemented.

the big difference in mine is bit sets i don't use them and every call function i have programed uses pieces or sections of call arrays that i utilize. (11)

i built mine to look for mathematic identities that are associated with move types.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming 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