CODEWITHSUNDEEP
prolog
user1730250
user1730250

Reputation: 592

sudoku on prolog taking too long to solve

I was wondering if there's a good way to use the cut symbol in prolog to solve a 9x9 sudoku
puzzle in a fast way. I'm currently solving the puzzle without using the ! symbol, but it is
taking too long.
Any suggestions?

Upvotes: 3

Views: 2474

Answers (2)

mat
mat

Reputation: 40768

Consider using finite domain constraints. They are available in almost all modern Prolog systems and allow for declarative formulations of many combinatorial problems, including Sudoku.

If you model this problem with finite domain constraints, you will not need any !/0 and still obtain a very efficient solution.

From the documentation of SWI-Prolog's library(clpfd):

:- use_module(library(clpfd)).

sudoku(Rows) :-
        length(Rows, 9), maplist(length_(9), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [A,B,C,D,E,F,G,H,I],
        blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).

length_(L, Ls) :- length(Ls, L).

blocks([], [], []).
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
        all_distinct([A,B,C,D,E,F,G,H,I]),
        blocks(Bs1, Bs2, Bs3).

problem(1, [[_,_,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,9]]).

Sample query and its result:

?- problem(1, Rows), sudoku(Rows), maplist(writeln, Rows).
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[2, 4, 6, 1, 7, 3, 9, 8, 5]
[3, 5, 1, 9, 2, 8, 7, 4, 6]
[1, 2, 8, 5, 3, 7, 6, 9, 4]
[6, 3, 4, 8, 9, 2, 1, 5, 7]
[7, 9, 5, 4, 6, 1, 8, 3, 2]
[5, 1, 9, 2, 8, 6, 4, 7, 3]
[4, 7, 2, 3, 1, 9, 5, 6, 8]
[8, 6, 3, 7, 4, 5, 2, 1, 9]

Upvotes: 5

Daniel Lyons
Daniel Lyons

Reputation: 22803

Without seeing the code, nobody can really help you, but here is some generic advice you may find useful.

Prolog programs work by searching a solution space. Most of the time, you will follow a generate-and-test paradigm. The sexy example code that gets us interested in Prolog is sexy and exciting usually because so little time is spent generating. In reality, Prolog performance is just like marketing. Generating better leads is worth more than speeding up the rest of the process. This is where the cut comes into play.

The cut does a lot less than you'd think. It is only useful if you know your first solution is as good or better than the rest. It commits you to your first guess.

In a problem like Sudoku, it's very easy to naively generate many more solutions than you need. If you just pick a digit, you're going to generate 9^9 potential solutions for a 3x3 grid, but you already know that a sequence like [9,9,9,9,9,9,9,9,9] is useless to you. Most of the solutions you generate with that approach are going to be worthless. So it's much better to just ask for a permutation of [1,2,3,4,5,6,7,8,9]—it winds up being three orders of magnitude better! But it turns out with Sudoku, you can do even better, because you aren't going to want more than some number of 9s or 1s in the same row of 9.

In this light, it should be clear that the general idea of "just use a cut" is a bit like handing a child a scalpel or asking a surgeon to use one to carve the Thanksgiving turkey. It may be a great tool, but not in the wrong hands or for the wrong job. For it to do you any good, you first have to know something about what order you're generating potential solutions. If you're not generating them in the right order, it's going to harm you. It's like marketing. You want highly qualified leads, but if you throw all your money at the wrong expensive leads you're dead in the water.

Often, if you trace through a Prolog program, you can see why it is wasting time generating things inefficiently. If you ever think to yourself, "it should have given up already!" then you know exactly where to put the cut. It's more likely that you'll think "why are you being so stupid, trying that one before this one?" If you find yourself thinking that, formalize your thought. Go back and write a smarter generator and your code performance will improve dramatically.

An anecdote from my personal experience. A friend's son was trying to beat some online game. To that end he had to solve a bunch of anagrams. This is very tedious for long words. I wrote a Prolog program that used WordNet as its database. I would take the letters and permute them until I found a word in the database, and then I'd print it out. It worked for smallish words, say 5 letters, but it was just painfully slow with 7 or 8. Several years go by and I'm in the shower when suddenly I realize: I can make an index. If I just take all the words in the dictionary and sort their characters, then I can take the anagram characters, sort them, and look up all the words that match that in the index. Building the index takes time, but not much compared to performing billions of permutations, and I only have to do that once to enable fast lookups. The original program looked more like the Prolog we dream about and the wizards can write, but the second one made it possible to find anagrams of enormous words and was not much harder to read (albeit much less "declarative"). The moral of the story is that the cut would never have gotten me to this realization or to an algorithm that performed as well as this one. Algorithm quality still matters the most.

Upvotes: 11

Related Questions