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   

Solving or creating, that's the question.

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

Joined: 15 Aug 2005
Posts: 2
:

Items
PostPosted: Mon Aug 15, 2005 11:59 pm    Post subject: Solving or creating, that's the question. Reply with quote

Hi all. Being a newbie I have a few thoughts: I find a lot of software _solving_ sukodus, but very few examples of software that actually creates them. Ok, it might be more exiting to solve a sukodu than to write one, but is it not so that creating them is more difficult?

I have a feeling that most of the sukodu generators around the web are pulling puzzles from a database, not creating them. Am I right? Are they actually done by hand?

Or is there a list somewhere of sukodu creating software (and source code)?

Ola Smile
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Tue Aug 16, 2005 12:23 am    Post subject: Re: Solving or creating, that's the question. Reply with quote

Ola wrote:
I have a feeling that most of the sukodu generators around the web are pulling puzzles from a database, not creating them. Am I right? Are they actually done by hand?

I don't know the answer to that but I suspect a significant number do pull puzzles from a database. However, if that's the case they have to get them from somewhere which potentially raises copyright issues if they do use someone else's puzzles.

Ola wrote:
Or is there a list somewhere of sukodu creating software (and source code)?


The only list I'm aware of is here - http://en.wikipedia.org/wiki/Sudoku/Resources
It's a real hodge-podge of everyone and anyone's sudoku software (and an embarrassment to wikipedia IMHO).

I'm not aware of any puzzle making source code but here's a list of what I'd consider very good puzzle makers (based on feedback in several forums). There may well be other very good puzzle makers 'out there' but I'm not aware of them so far.

http://www.angusj.com/sudoku/ (OK, I'm biased because it's mine Smile)
http://www.simes.clara.co.uk/programs/sudoku.htm
http://www.sudoku.com/
Back to top
View user's profile Send private message Visit poster's website
dukuso

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

Items
PostPosted: Tue Aug 16, 2005 3:32 am    Post subject: Re: Solving or creating, that's the question. Reply with quote

angusj wrote:
pull puzzles from a database. However, if that's the case they have to get them from somewhere which potentially raises copyright issues if they do use someone else's puzzles.


can you tell me, why you think this ?
is it possible to claim copyright on sudokus which
you created ? Which sort of sudokus can be
claimed copyright upon ?
I assume, noone can claim copyright on "canonical" sudokus,
at least.

What, if sudokus are encoded as numbers ?
That would mean, certain numbers are copyrighted !?!?
Is there a list of all copyrighted sudokus, and who claims
the copyright ?


Guenter.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Ola

Joined: 15 Aug 2005
Posts: 2
:

Items
PostPosted: Tue Aug 16, 2005 7:14 pm    Post subject: Re: Solving or creating, that's the question. Reply with quote

Well, I had this idea of trying to write some code myself generating puzzles. I think a real shortcut would have been to build a database with pre made puzzles and then serve these without saying a word. Especially in the case of a online service this could easily have been done.

But I don't want to cheat! On the other hand, I think this project is a lot more difficult than I first thought of Smile It would be of great help if there was some source code available. By the way: what is a valid Sukodu? 1) Must have a solution? 2) Must have only one solution?

And what about these patterns of fixed numbers, is that a must to make it valid? This makes the whole thing a LOT more difficult.

Ola
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Tue Aug 16, 2005 11:04 pm    Post subject: Re: Solving or creating, that's the question. Reply with quote

dukuso wrote:
can you tell me, why you think this ?
is it possible to claim copyright on sudokus which
you created ?

Firstly, IANAL (I am not a lawyer).

I doubt that anyone could successfully assert copyright over one specific sudoku. However, it is possible that a collection of puzzles are sufficiently distinctive to be beyond reasonable doubt as to how they were generated (eg some puzzle generators are not as random as may initially appear).

If someone is using a puzzle generator contrary to the terms and conditions of use specified by the copyright owner, then that would be a breach of copyright.

As another example, if someone publishes online a collection of puzzles, it's reasonable to claim copyright over the whole collection. The likelihood of anyone generating an identical collection via other means is way too small to happen by chance. Hence, if a number of puzzles from this collection appeared elsewhere, then there would be no doubt where they came from.

In short, if you want to publish someone else puzzles you do need to check that you have permission.
Back to top
View user's profile Send private message Visit poster's website
dukuso

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

Items
PostPosted: Wed Aug 17, 2005 11:16 am    Post subject: copyright Reply with quote

>
>dukuso wrote:
>can you tell me, why you think this ?
>is it possible to claim copyright on sudokus which
>you created ?

Angusj replied:

>Firstly, IANAL (I am not a lawyer).
>
>I doubt that anyone could successfully assert copyright over
>one specific sudoku. However, it is possible that a collection
>of puzzles are sufficiently distinctive to be beyond
>reasonable doubt as to how they were generated (eg some puzzle
>generators are not as random as may initially appear).

but they can be divided. If the copyright would apply to
the whole then to my understanding it would also apply to
its parts. At least, that's how it is usually with
books,music,art etc.

If the problem is just the possibly small number of items
out of which the copyrighted one is chosen, then just increase
the sudoku-size. By your logic a single 9*9 sudoku can't
be copyrighted, while a single 16*16 can !?!

>If someone is using a puzzle generator contrary to the terms
>and conditions of use specified by the copyright owner, then
>that would be a breach of copyright.

no "copyright owner" can tell me, how I have to use
my puzzle-generator.

>As another example, if someone publishes online a collection
>of puzzles, it's reasonable to claim copyright over the whole
>collection. The likelihood of anyone generating an identical
>collection via other means is way too small to happen by
>chance.

maybe he just happens to use the same algorithm to create them ?

>Hence, if a number of puzzles from this collection
>appeared elsewhere, then there would be no doubt where they
>came from.

I think you would still have to prove it.
And even then, how do we know that these sudokus don't have some
property which makes them rather special ?

>In short, if you want to publish someone else puzzles you do
>need to check that you have permission.

I very much doubt this. Not because I think I'm better informed
about the legal issues, but just because I can't make a consistent
theory about the consequences and how they are related to copyright
in other areas of science.
Are you referring to British law BTW. or US-law or "international" law ?


Does someone know, what the procedure is to claim copyright ?
Where do you have to claim it,what does it cost,
where are the copyrighted sudokus stored, is that list public ?



Guenter.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
rfb

Joined: 09 Apr 2005
Posts: 26
:

Items
PostPosted: Wed Aug 17, 2005 12:31 pm    Post subject: Re: Solving or creating, that's the question. Reply with quote

Ola wrote:


Or is there a list somewhere of sukodu creating software (and source code)?

Ola Smile

The source for Rubylips solver and generator is available http://act365.com/sudoku/

I haven't looked at the puzzles it generates
_________________
Bob
Back to top
View user's profile Send private message
rfb

Joined: 09 Apr 2005
Posts: 26
:

Items
PostPosted: Wed Aug 17, 2005 12:42 pm    Post subject: Re: copyright Reply with quote

dukuso wrote:
>

Does someone know, what the procedure is to claim copyright ?
Where do you have to claim it,what does it cost,
where are the copyrighted sudokus stored, is that list public ?



Guenter.

You automatically own copyright on anything you write or say without cost or registration.

To actually enforce copyright you need to be able prove that you generated the material prior to the other person and you are likely to be into lawyers and court cases and big costs Sad

See http://www.intellectual-property.gov.uk/std/faq/copyright/what.htm
_________________
Bob
Back to top
View user's profile Send private message
dukuso

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

Items
PostPosted: Wed Aug 17, 2005 2:18 pm    Post subject: Re: copyright Reply with quote

rfb wrote:
dukuso wrote:
>

Does someone know, what the procedure is to claim copyright ?
Where do you have to claim it,what does it cost,
where are the copyrighted sudokus stored, is that list public ?



Guenter.

You automatically own copyright on anything you write or say without cost or registration.

To actually enforce copyright you need to be able prove that you generated the material prior to the other person and you are likely to be into lawyers and court cases and big costs :(

See http://www.intellectual-property.gov.uk/std/faq/copyright/what.htm



something must be wrong here.

So anyone can claim copyright on anything without paying a fee
and without being officially registered and you can't find
out whether the copyright is justified without going to court ?
That's not much better than no copyright laws at all.

Say 10 people claim copyright for a certain sudoku
but don't reveal to public how and when that copyright
was "created". Now someone else wants to use that sudoku -
and with lots of effort finally figures out who 4 of these
10 are, from whom should he try to get permission ?
What with the other 6 ?
What about all the lurkers, who post their lists of sudokus
which they claim copyright for, encrypted and electronically
certified to some public archive etc.
Can I generate a list of all 5e9 sudoku-grids and claim copyright
for each ? Can I claim copyright for anything which is already
copyrighted by others ? (even if that copyright couldn't be enforced,
it could still be used to get money from someone else who doesn't
know that)
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Goran

Joined: 13 Aug 2005
Posts: 10
:

Items
PostPosted: Fri Aug 26, 2005 5:41 pm    Post subject: Copyright is beautiful Reply with quote

The beauty of copyright is exactly that it does not require any applications, like all other (IMHO) invisible assets do. Like patents, designs, brands, company names. It just comes into being. But I know one guy who writes music lyrics who makes sure that other people have read them b4 he sends them to record companies, in case someone would steal them.

Best,

Goran
Back to top
View user's profile Send private message
qbasicmac

Joined: 26 Jul 2005
Posts: 27
:
Location: Washington DC

Items
PostPosted: Fri Sep 02, 2005 6:15 pm    Post subject: Reply with quote

Hi, Ola.

I have created a simple puzzle generator. It can be found in the "SuDoku Companion", a QBasic program found at www.SuDoku.funURL.com. A reference to the source code is there, too.

But if you want to write your own, the simple technique used by me is as follows:

Install in the program the equivalent of a small library: 3 or 4 solved puzzles of various difficulties.

Then at random, pull a puzzle solution based on the users desire for easy, medium, etc.

I'm not sure if the solutions are difficult in themselves or are made difficult by the clues. Sorry. Anyway...

Take the puzzle and shuffle rows and columns. That guarantees that the random puzzle solution you have is correct. Every row and column and box will be correct.

Also translate at random (encrypt) so that every digit equals a unique other digit. 123456789 might be 586129437.

Now select a number of random cells to display.

That's it. Works pretty well!

I'm also not sure, but am suspicious that all SuDoku solutions available via that logic. If I were an expert mathematician, maybe I could prove that any two solutions are equal by shuffling this way and substuting that way. So again, I am not sure the easy-hard distinction holds perfectly.

My guess is that a good generator would use a technique as I mentioned, perhaps always starting with the same original puzzle solution, then pick the digits to be displayed (i.e. the puzzle) and automatically solve it and determine what kind of tricks are needed to solve it and whether a duplicate solution exists. If a duplicate exists, display another digit. Then you have a puzzle and know how complex it is.

For fun, try the program. I hope DOS works on your machine.

(Ignore the SuDoku Scratch Pad program - it does not generate puzzles.)

Mac
Back to top
View user's profile Send private message Visit poster's website
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Fri Sep 02, 2005 6:36 pm    Post subject: Reply with quote

qbasicmac wrote:
Now select a number of random cells to display.
At random? But this is the bit that is crucial to ensuring the puzzle only has one solution. If you don't choose these cells carefully, you'll end up with loads of solutions.

S
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
qbasicmac

Joined: 26 Jul 2005
Posts: 27
:
Location: Washington DC

Items
PostPosted: Fri Sep 02, 2005 6:40 pm    Post subject: Reply with quote

Hi, Ola

To add to my previous response to you, I tried The SuDoku Companion, asking for a hard puzzle. I got

<code>
-7- 3-- --5
--- 7-- 34-
-3- -62 8--
--3 -9- 4--
56- -4- --1
--9 --- -76
9-- 5-- ---
-1- -7- ---
--4 --1 ---
</code>

It was kind of hard. But there were no real complications like X-Trees. Just straightforward candidate elimination. There were just many of them to do.

Mac
Back to top
View user's profile Send private message Visit poster's website
qbasicmac

Joined: 26 Jul 2005
Posts: 27
:
Location: Washington DC

Items
PostPosted: Fri Sep 02, 2005 7:23 pm    Post subject: Reply with quote

Hi, Simes,

Yeah, that's why I imagined that an advanced generator must test solutions and, as I posted above
>If a duplicate exists, display another digit.

Interestingly, so far, my generator has never made a program with multiple solutions. Luck, I guess.

Thanks for the input.

Mac
Back to top
View user's profile Send private message Visit poster's website
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Fri Sep 02, 2005 8:16 pm    Post subject: Reply with quote

qbasicmac wrote:
if a duplicate exists, display another digit.
Sorry Mac, I missed that bit.
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
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