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

Re: Solving Sudoku with OWL

From: Jeremy Wong 黃泓量 <jeremy@miko.hk>
Date: Tue, 10 Jan 2006 10:23:46 +0800
Message-ID: <001901c6158c$e29750d0$6802a8c0@miko.hk.local>
To: "Danny Ayers" <danny.ayers@gmail.com>, Jeremy Wong 黃泓量 <jeremy@1980.hk>
Cc: "Semantic Web" <semantic-web@w3.org>

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
> 
Received on Tuesday, 10 January 2006 02:25:14 UTC

This archive was generated by hypermail 2.4.0 : Tuesday, 5 July 2022 08:44:55 UTC