is prolog a good language to solve sudoku or minesweeper-like puzzle

Question

I realise I've written this like a homework question, but that's because it's the simplest way for me to understand and try to relay the problem. It's something I want to solve for a personal project.

I have cards laid out in a grid, I am starting with a simple case of a 2x2 grid but want to be able to extrapolate to larger n×n grids eventually.

The cards are all face down, and printed on the faces of the cards are either a:

positive non-zero integer, representing the card's 'score'
or the black spot.

I am given the information of the sum of the scores of each row, the number of black spots in each row, and the sum of the scores of each column, and the number of black spots in each column.

So the top row must have a sum score of 1, and exactly one of the cards is a black spot.

The rightmost column must have a sum score of 2, and exactly one of the cards is a black spot.

Etc.

Of course we can see the above grid will "solve" to

Now I want to make a function that inputs the given information and produces the grid of cards that satisfies those constraints.

I am thinking I can use tuple-like arguments to the function.

And then every "cell" or card in the grid is itself a tuple, the first element of the tuple will be the score of the card there (or 0 if it is a black spot) and the second element will be a 1 if the card is a black spot or a 0 otherwise.

So the grid will have to resemble that ^^

I can find out what all the a, b, variables are by solving this system of equations:

(Knowing also that all of these numbers are integers which are ≥0).

I wanted to use this problem as a learning exercise in prolog, I think it seems like a problem Prolog will solve elegantly.

Have I made a good decision or is Prolog not a good choice?

I wonder how I can implement this in Prolog.

firefrorefiddle firefrorefiddle · Accepted Answer · 2019-03-13T12:37:18

Prolog is very good for this kind of problems. Have a look clp(fd), that is Constraint Logic Programming in Finite Domains.

This snippet shows a primitive way how to solve your initial 2x2 example in SWI Prolog:

:- use_module(library(clpfd)).

 test(Vars) :-
    Vars = [TopLeft, TopRight, BottomLeft, BottomRight],
    global_cardinality([TopLeft, TopRight],       [0-1,1-_,2-_]), TopLeft + TopRight #= 1,
    global_cardinality([TopLeft, BottomLeft],     [0-1,1-_,2-_]), TopLeft + BottomLeft #= 1,
    global_cardinality([BottomLeft, BottomRight], [0-1,1-_,2-_]), BottomLeft + BottomRight #= 2,
    global_cardinality([TopRight, BottomRight],   [0-1,1-_,2-_]), TopRight + BottomRight #= 2,
    label(Vars).

Query:

?- test(Vars).
Vars = [1, 0, 0, 2].

You can take this as a starting point and generalize. Note that the black dot is represented as 0, because clp(fd) deals only with integers.

Here is the documentation: http://www.swi-prolog.org/man/clpfd.html

is prolog a good language to solve sudoku or minesweeper-like puzzle

1 Answers