Path: ...!news.misty.com!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.prolog
Subject: Re: The road to Artificial Intelligence
Date: Sun, 24 Mar 2024 01:32:42 +0100
Message-ID: <utnsb9$1o5dp$1@solani.org>
References: <b406aa35-c39b-46f3-862f-1cc4b75143ae@googlegroups.com>
 <338dc0fb-4a93-405f-99da-7799d25ddc91n@googlegroups.com>
 <url15e$m5i4$3@solani.org> <ut45h5$1efic$1@solani.org>
 <ut45uc$1efp6$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 24 Mar 2024 00:32:41 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="1840569"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.1
Cancel-Lock: sha1:kr6KebFdbAHn2s8eEKs2tY8j+T0=
In-Reply-To: <ut45uc$1efp6$1@solani.org>
X-User-ID: eJwNyckRACEIBMCUlmsYwlGU/ENYq58dBkGnI+Axz0fuIldnlODluGVRtI+5iUrUPSLr+Ci8ljfBvMXeTe0fGvUUZg==
Bytes: 3559
Lines: 76

Now I have the feeling there are no difficult 9x9
Sudokus for the computer. At least not for computers
running SWI-Prolog and using CLP(FD) with the global
constraint all_distinct/1.

I was fishing among the 17-clue Sudokus, and the
hardest I could find so far was this one:

/* Gordon Royle #3668 */
problem(11,[[_,_,_,_,_,_,_,_,_],
             [_,_,_,_,_,_,_,1,2],
             [_,_,3,_,_,4,_,_,_],
             [_,_,_,_,_,_,_,_,3],
             [_,1,_,2,5,_,_,_,_],
             [6,_,_,_,_,_,7,_,_],
             [_,_,_,_,2,_,_,_,_],
             [_,_,7,_,_,_,4,_,_],
             [5,_,_,1,6,_,_,8,_]]).

But SWI-Prolog still does it in around 3 seconds.
SWI-Prolog does other 17-clue Sudokus in less than 100ms.

Are there any 17-clue Sudokus that take more time?

Mild Shock schrieb:
> 
> Or a more striking example, Peter Norvig's impossible
> Sudoku, which he claims took him 1439 seconds
> to show that it is unsolvable:
> 
> /* Peter Norvig */
> problem(9, [[_,_,_,_,_,5,_,8,_],
>              [_,_,_,6,_,1,_,4,3],
>              [_,_,_,_,_,_,_,_,_],
>              [_,1,_,5,_,_,_,_,_],
>              [_,_,_,1,_,6,_,_,_],
>              [3,_,_,_,_,_,_,_,5],
>              [5,3,_,_,_,_,_,6,1],
>              [_,_,_,_,_,_,_,_,4],
>              [_,_,_,_,_,_,_,_,_]]).
> 
> https://norvig.com/sudoku.html
> 
> whereby SWI-Prolog with all_distinct/1 does
> it in a blink, even without labeling:
> 
> ?- problem(9, M), time(sudoku(M)).
> % 316,054 inferences, 0.016 CPU in 0.020 seconds
>   (80% CPU, 20227456 Lips)
> false.
> 
> Pretty cool!
> 
> Mild Shock schrieb:
>> I didn't make all my homework yet.
>> For example just fiddling around with CLP(FD), I get:
>>
>> ?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4,
>>            1..3, 1..3, 1..6]), all_distinct(Vs).
>> false.
>>
>> Does Scryer Prolog CLP(Z) have some explanator for that?
>> What is exactly the conflict that it fails?
>>
>> Mild Shock schrieb:
>>>
>>> Terence Tao, "Machine Assisted Proof"
>>> https://www.youtube.com/watch?v=AayZuuDDKP0
>>>
>>> Mostowski Collapse schrieb:
>>>> Don't buy your Pearls in Honk Kong. They are all fake.
>>>>
>>>> So what do you prefer, this Haskell monster:
>>>> https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf
>>
>