W3C home > Mailing lists > Public > semantic-web@w3.org > January 2006

Re: Solving Sudoku with OWL

From: Aditya Kalyanpur <swap_adityak@yahoo.com>
Date: Mon, 9 Jan 2006 23:39:56 -0800 (PST)
Message-ID: <20060110073956.96971.qmail@web31105.mail.mud.yahoo.com>
To: (wrong string) 黃泓量" <jeremy@miko.hk>, Danny Ayers <danny.ayers@gmail.com>, Jeremy Wong "黃泓量" <jeremy@1980.hk>
Cc: Semantic Web <semantic-web@w3.org>

I've come up with a way to represent the Sudoku puzzle
in OWL using nominals:

http://www.mindswap.org/~aditkal/sudoku

On the page, I've used a rather simple example to
describe how one can generate an OWL ontology
corresponding to a Sudoku grid that encodes the puzzle
constraints. 

Also, there is a link on the page to run the sample
Sudoku OWL ontology through the online version of our
OWL DL reasoner, Pellet, to get the correct inferred
solution to the puzzle.

Cheers,
Aditya

--- Jeremy Wong 黃泓量 <jeremy@miko.hk> wrote:

> 
> Not all sudoku puzzles can be solved by solely
> inference. I expect that any 
> OWL implementation is an inference engine. It means
> that if a sudoku puzzle 
> can be solved by 100% logical inference, then OWL
> engine can solve the 
> puzzle as well. Any sudoku puzzle having unique
> solution could then be 
> solved by OWL engine.
> 
> The ability to solve different levels of sudoku
> puzzles can be an indicator 
> of the intelligence of OWL implementation. From
> another view sudoku can be a 
> mean to improve the intelligence of OWL engine.
> 
> The techniques used in solving sudoku puzzles can
> apply on OWL 
> implementation. In addition to simple scanning the
> cardinality constraints, 
> there are multiple contingency and force chaining.
> They are advanced sudoku 
> techniques that OWL implementation can include.
> 
> Using rules is more flexible than relying on OWL
> engine, at least you can 
> enter new rules any time you like. However, rules is
> not computing efficient 
> sometimes. It is better to have OWL engine performs
> the inference anyway.
> 
> BTW, solving most sudoku puzzles should not take
> more than tenth second with 
> today's computer. You might go to a wrong direction
> if the engine ran as 
> long as 5 hours. Even if it used brute-force,
> dancing-link algorithm already 
> greatly reduced the time for the first solution.
> 
> Anyway,.. I don't have time to implement the above
> concepts in OWL, either.
> 
> 
> Jeremy Wong 黃泓量
> --
> Miko-Kings Instruments Ltd.
> Web: http://www.miko.com.hk/
> ----- Original Message ----- 
> From: "Danny Ayers" <danny.ayers@gmail.com>
> To: "Jeremy Wong 黃泓量" <jeremy@1980.hk>
> Cc: "Semantic Web" <semantic-web@w3.org>
> Sent: Tuesday, January 10, 2006 12:54 AM
> Subject: Re: Solving Sudoku with OWL
> 
> 
> > On 1/9/06, Jeremy Wong 黃泓量 <jeremy@1980.hk>
> wrote:>> I attempt to model 
> > the popular game Sudoku in OWL. Could someone help
> me> to see whether this 
> > work is correct or not.
> > I had a go a little while back, but not had time
> to go further. I'mstill 
> > not really sure whether they can be solved using
> RDFS/OWLinference alone 
> > or whether rules would be needed (I suspect
> thelatter).
> > Code's
>
at:http://pragmatron.org/trac/browser/pragmatron/sudoku/
> > The files called sudoku*, lots of failed attempts!
> > Notes (slightly older) 
> >
>
at:http://dannyayers.com/?s=Sudoku&submit=Search+Archives
> >
> > Cheers,Danny.
> > --
> > http://dannyayers.com
> > 
> 
> 
> 
> 





		
__________________________________________ 
Yahoo! DSL – Something to write home about. 
Just $16.99/mo. or less. 
dsl.yahoo.com 
Received on Tuesday, 10 January 2006 07:40:12 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 19:47:11 UTC