Sujet : Re: The road to Artificial Intelligence
De : janburse (at) *nospam* fastmail.fm (Mild Shock)
Groupes : comp.lang.prologDate : 24. Mar 2024, 02:32:42
Autres entêtes
Message-ID : <utnsb9$1o5dp$1@solani.org>
References : 1 2 3 4 5
User-Agent : Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Firefox/91.0 SeaMonkey/2.53.18.1
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
>