Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14022

Re: The road to Artificial Intelligence

Show all headers | View raw

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
>>
> 

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 03:28 -0800
  Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 04:15 -0800
    Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 04:47 -0800
      Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 08:10 -0800
        Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-18 08:24 -0800
          Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-20 08:47 -0800
            Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-20 08:50 -0800
              Re: The road to Artificial Intelligence Mostowski Collapse <bursejan@gmail.com> - 2023-02-20 11:12 -0800
  Was it worth the wait? [gemini by Google] Mild Shock <janburse@fastmail.fm> - 2024-02-22 16:49 +0100
    Pulverizer against Delhi Belly? (Was: Was it worth the wait? [gemini by Google]) Mild Shock <janburse@fastmail.fm> - 2024-02-22 19:11 +0100
  Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-02-27 17:03 +0100
    Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-03-16 14:06 +0100
      Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-03-16 14:13 +0100
        Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-03-24 01:32 +0100
          Re: The road to Artificial Intelligence Mild Shock <janburse@fastmail.fm> - 2024-03-24 18:26 +0100
            Re: The road to Artificial Intelligence Mikko <mikko.levanto@iki.fi> - 2024-03-25 09:59 +0200

csiph-web