Explainable Artificial Intelligence (XAI) for all_distinct/1

General
1

How would one write a “why” component for
SWI-Prolog CLP(FD) all_distinct/1 global constraint?
Maybe visualize the conflict in a GUI?

Here is a striking example, Peter Norvig’s impossible Sudoku,
which he claims took him 1439 seconds (ca. 24 minutes)
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],
            [_,_,_,_,_,_,_,_,_]]).

Solving Every Sudoku Puzzle
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
false.

A.9.7 Example: Sudoku
https://www.swi-prolog.org/pldoc/man?section=clpfd-sudoku

Pretty cool!

1 Like
2

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?