Human-like solver

Fourier · Posted: Fri Jul 08, 2005 7:23 pm Post subject: Human-like solver

Hi guys,

I'm interested in writing computer code to solve SuDoku problems with textual user feedback. I'm only interested in logical solution steps - i.e. I don't want to brute-force search the entire solution space. I've already had a lot of great suggestions from the community, but I thought I'd throw out the problem in case anyone else would like to help. The executable is available here:

http://www.frayn.net/sudoku/

For the next version I've already got it writing out a textual description of the logical steps it's making. I'm also hoping to add in as many new tricks as possible. So if you have any good ones that I've not already included I'd love to hear them. Especially if you can give me an example of a problem that the current code can't solve, but which you *can* solve using a logical algorithm.

Thanks a lot!

Colin

P.S. I am a computer science researcher, so don't hold back on the details Wink

Simes · Posted: Fri Jul 08, 2005 10:09 pm Post subject:

Fourier · Posted: Sat Jul 09, 2005 7:41 pm Post subject:

klaas

Hi;

a bit off-topic maybe,

the online applet at http://sudoku.klaas.nl can work in a
more 'human' way if you turn on optimization. Which the speed-slider
to 'slow', you can actually watch as progress is made...

dukuso · Posted: Thu Jul 28, 2005 6:47 am Post subject:

Colin wrote:_

>Hi guys,
>
>I'm interested in writing computer code to solve SuDoku problems
>with textual user feedback. I'm only interested in logical solution
>steps - i.e. I don't want to brute-force search the entire solution
>space.

I assume you mean, that you _do_ want to search the whole
solution space but you want to cut off as many branches as possible
as early as possible, which can be excluded to contain a solution.

>I've already had a lot of great suggestions from the community,
>but I thought I'd throw out the problem in case anyone else would
>like to help. The executable is available here:
>
>http://www.frayn.net/sudoku/
>
>For the next version I've already got it writing out a textual
>description of the logical steps it's making. I'm also hoping
>to add in as many new tricks as possible. So if you have any
>good ones that I've not already included I'd love to hear them.
>Especially if you can give me an example of a problem that the
>current code can't solve, but which you *can* solve using a
>logical algorithm.

for any set of "rules", which you give, I can construct an example
which can't be solved by that set of rules. (..given enough time ;-))
Note, that I'm not restricted to 9*9-sudokus here,
the example could be a 16*16 or higher.
I don't know, how many of the currently formulated "rules"
we need to solve all 9*9 sudokus. Is there a sudoku known,
which can't be solved by one of the rules ?
Of course, I could just claim that a forced-moves lookahead
of level 3 will solve all 9*9-sudokus (very likely).
If you accept that as a valid "rule".

>Thanks a lot!
>
>Colin
>
>P.S. I am a computer science researcher, so don't hold back on the details

Simes wrote:

> readme wrote:
>> Welcome to one of the most powerful SuDoku tools on the web.
>
>Hey don't hold back!
>
>readme wrote:
>>...based on the explanations given on the following web page:
>>http://www.simes.clara.co.uk/programs/sudokutechniques.htm
>
>I thought some of the text sounded a little familiar!
>
>Since you're looking for puzzles it can't solve, have
>you tried some of the examples from my site? Like the
>X-Wings for example? they have a well defined mechanism
>for solving. Or the forcing chains?
>_________________
>Simes
>http://www.simes.clara.co.uk/programs/sudoku.htm

Fourier replied:
>Yep I'll take a look at those. Thanks.
>(and thanks for the site!)

hmm.
Looking at the sadman-webpage I finally found:

>Copyright Notice
>The text and graphic content of SadMan Software's World Wide Web
>site may be used, printed and distributed only under the following
>conditions:

_all_ "text and graphic contents" from that sites ??

>Permission is first obtained from Simon Armstrong.
>The content is used for non-commercial purposes only.
>Copyright information is displayed (Copyright © 2000-2005 Simon
>Armstrong. All Rights Reserved.)
>The content is not modified.

"may not be used" just only because you say so, or is there some
law which supports that claim ?
Can this law be enforced in Germany ?
Suppose, you find a puzzle in my database which I got from your
page (downloaded before having noticed that you have this
"Copyright Notice", which you keep silent about in your
advertisements and links, and which only appears as a small
link on the bottom of your page...)
or which someone else (illegally ?) got from your page or your program,
which then he posted and I copied it into my database of puzzles -
would I violate some law then ? Would you sue me (at last)
on some German court ?
Could you make a list of all puzzles which you
claim copyright for, so I could compare it with my database
and eventually delete those ? - (in case your Copyright-claim
should be supported by some other "legacy-experts" from
usenet which I might consult)

Simes, please stop encouraging people to download puzzle-examples
or solving-descriptions from your page, without clearly
pointing them to the Copyright-restrictions ! (or modify
those accordingly)

BTW. I asked this in another post earlier:
"can a sudoku be copyrighted at all" ?
I mean, it's just a mathematical entity you can't copyright
special latin-squares, magic squares, permutations, prime numbers,
algorithms, .. either (IMHO. Or can you ?)
I'd like to see a list of all copyrighted sudokus.
I'd like to see a list of all copyrighted numbers.
I'd like to see a list of representatives who voted
for that copyright law, when it was passed.

regards, Guenter.

Simes · Posted: Thu Jul 28, 2005 8:51 am Post subject:

hmmm good point dukuso.

It's the usual copyright notice intended to stop people copying substantial portions of the site and claiming it as their own material, or copying it for publication elsewhere. You'll find similar notices on many other sites.

I'm happy for anybody to use the puzzles from my site in anyway they like. I won't be suing anybody for using a puzzle I posted. If I originated the puzzle, then an acknowledgement would be nice, but is not required. If somebody else originated it, acknowledge them instead - you'll notice that I acknowledge rubylips as the creator of some of the puzzles.

(I know of a site that has copied a couple of my examples (http://www.gatsby.ucl.ac.uk/~turner/sudoku/Sudoku.html) but there's also a link to my site, and I'm not too bothered.)

But here's the disclaimer... I'm not a lawyer, if you're still worried that I might sue you if I discover one of "my" puzzles in your collection, please get professional advice.
_________________
Simes
www.sadmansoftware.com/sudoku

dukuso · Posted: Thu Jul 28, 2005 10:48 am Post subject:

>hmmm good point dukuso.
>
>It's the usual copyright notice intended to stop people
>copying substantial portions of the site and claiming it as
>their own material, or copying it for publication elsewhere.
>You'll find similar notices on many other sites.

yes, many of these are doubtful or even offensive.
So it's not against you but against this practice in general.
Copyrighting sudokus would be a good examples to discuss this.

>I'm happy for anybody to use the puzzles from my site in
>anyway they like. I won't be suing anybody for using a puzzle
>I posted.

but you claim that you _could_, if you wanted to ?
You might use this as a threat later, if there are
differences with someone about some other issue
and you find out that he might have violated
your copyright this way.

>If I originated the puzzle, then an acknowledgement
>would be nice, but is not required.

Agreed, but I can't include acknowledgements in a large database
of thousands of gathered sudokus. That's _tedious_.

>If somebody else
>originated it, acknowledge them instead - you'll notice that I
>acknowledge rubylips as the creator of some of the puzzles.
>
>(I know of a site that has copied a couple of my examples
>(http://www.gatsby.ucl.ac.uk/~turner/sudoku/Sudoku.html) but
>there's also a link to my site, and I'm not too bothered.)

so, there is no clear law/rule and it just depends on your
degree of being bothered, which is hard to predict.

>But here's the disclaimer... I'm not a lawyer, if you're still
>worried that I might sue you if I discover one of "my" puzzles
>in your collection, please get professional advice.

you're not a lawyer, you're not sure about the legal situation,
still you claim copyright about sudokus and other stuff on your
pages ?
And you want to keep your practice to advertise and link to
your page encouraging people to download text and/or graphics
without giving a warning about the copyright issue
except just a small link on the bottom which most people
supposedly won't see ?
I see it this way: you want to create a situation where
you might be able to sue people which you don't like for
some reason.And you don't want people becoming aware of this.
But you tell us that you are a nice guy and
you won't do this in normal circumstances, OK.
But note: once realizing, people might become unsecure and doubtful
or even offended by this. I recommend to reformulate and
being more precise about what's copyright and what not.
Adding something like this
>intended to stop people
>copying substantial portions of the site and claiming it as
>their own material, or copying it for publication elsewhere.
which you said above would be a start.

And again,it's not against you but against this practice in general.
And as a mathematician I don't like the idea of latin squares or
sudokus or magic cubes or such being copyrighted.

Cheers, Guenter.

Simes · Posted: Thu Jul 28, 2005 11:57 am Post subject:

dukuso · Posted: Thu Jul 28, 2005 1:37 pm Post subject: copyright for sudokus

dukuso wrote:
>>yes, many of these are doubtful or even offensive.

simes:
>Offensive? Too strong surely. They are present to protect
>the work of an individual or company, nothing more.

they are not formulated like this. You won't find words like
"protect the work". Instead you usually find a list of
what's forbidden. (even though it's not by law)

>dukuso wrote:
>>so, there is no clear law/rule and it just depends on your
>>degree of being bothered, which is hard to predict.

simes:
>I believe the law is clear. If I write it, I own the copyright.

no. Not everything can be copyrighted. What e.g. if 2 people
claim copyright for the same thing because they _both_ wrote it ?
(independently of each other)

>>I can assign the copyright to others, or revoke it entirely.
>>If I judge my copyright has been infringed than I can, if I
>>want to, take legal action to try to stop it.

you even can do this, if you think it hasn't been infringed.
But you probably won't succeed.

>dukuso wrote:
>>you're not a lawyer, you're not sure about the legal situation,
>>still you claim copyright about sudokus and other stuff on your
>>pages ?
>>Other stuff certainly. Like you, I don't know whether machine
>>generated puzzles can be copyrighted - I suspect hand-made ones
>>can be though, as they're original work.

hard to prove that a sudoku was "hand-made"

>I'm not about to start a legal test case to find out either.

then why don't you clearly say this on the webpage ?
Instead you are trying to make the reader think that you would.

>dukuso wrote:
>>And you want to keep your practice to advertise and link to your
>>page encouraging people to download text and/or graphics without
>>giving a warning about the copyright issue except just a small
>>link on the bottom which most people supposedly won't see ?

simon
>I encourage people to visit my site, and that obviously involves
>a download of the text and graphics. There isn't a copyright issue
>to warn about. The site exists to be read, I won't complain when
>people read it. The files are there to be downloaded, I won't
>complain when people download them.

it often happens that people post parts of the downloaded things
to a forum. You don't mention when in this (common) case you will
complain and when not.

>dukuso wrote:
>>I see it this way: you want to create a situation where
>>you might be able to sue people which you don't like for
>>some reason.And you don't want people becoming aware of this.
>
>lol, Are you serious? I want visitors to my site. If they buy
>my software, or click on an advert, even better. End of story.

yes, I'm serious. I don't think this is your primary intend, of course.
But you tolerate this situation (and maybe enjoy it)
Story only ends, when everyone stops posting.

>dukuso wrote:
>>intended to stop people
>>copying substantial portions of the site and claiming it as
>>their own material, or copying it for publication elsewhere.
>which you said above would be a start.
>I'll take another look at it and consider adding something
>like this. I'm wary of watering down any legal protection though.

that's a bad legal system, if it supports/encourages unclear formulations
but waters specifications (good English?)

>dukuso wrote:
>And again,it's not against you but against this practice in general.
>phew! I thought I was being picked on for a moment there

No, everyone is welcome to jump in.
I had other copyright discussions before. Lastly with someone who
claimed copyright for magic cubes (phew) And I i.e. hate the
Terms and Conditions of ATT for the oeis.

>Here's that disclaimer again... I'm not a lawyer. So my legal
>opinion counts for nought.
>_________________
>Simes
>http://www.simes.clara.co.uk/programs/sudoku.htmo
>Copyright Notice
>The text and graphic content of SadMan Software's World Wide Web
>site may be used, printed and distributed only under the following
>conditions:
>Permission is first obtained from Simon Armstrong.
>The content is used for non-commercial purposes only.
>Copyright information is displayed (Copyright © 2000-2005 Simon
>Armstrong. All Rights Reserved.)
>The content is not modified.

I assume, these points are connected by logical "and".
And "text and graphic content" also refers to portions
of it, as long as it's unique and not commonly used
anywhere else.
Now, I strongly assume that this copyright has been violated
by posters - according to the exact above wording.
But of course without "unprotecting your work", as you would
interpret it. So it's OK for you but you still make it
illegal by that Copyright Notice.

Guenter.

kudosu · Site Admin

Doug · Posted: Fri Aug 05, 2005 7:50 am Post subject:

wft kids?
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

dukuso · Posted: Fri Aug 05, 2005 10:27 am Post subject:

sudokus are not like literature, musik,paintings etc.
This would be art and not a mathematical entity.

Which sudokus would you allow for copyright ?
e.g. yesterday I posted a 18-clue sudoku in a proof
that 18 was the minimum number of clues for that grid.
Could I claim copyright ?
But the grid was the "most canonical sudokugrid" already
used by others e.g. in the paper which proved that
sudoku-solving is NP-complete.
So it's not so unlikely that someone else will come up
with the same sudoku and use it as an example.
Could I claims copyright and sue that person then ?

Suppose someone uses a computer-program to generate
copyrighted puzzles for a newspaper with an improper random-seed.
Then someone else uses the same algo and comes up with the
same puzzle. Would you forbid him to publish it ?
How can you ever prove that your sudoku is "special"
enough so it's unlikely enough that someone else will find
it independently too ?

G.