4
\$\begingroup\$

I was wondering if there's any way I can improve this code's execution. I want to use it on a 9*9 grid, but it takes too long to solve this as 4*4. This program takes as input a 4*4 matrix represented as a 1D matrix and returns the solution to the puzzle in the variable solution. Any comments?

subset([],_).
subset([H|T],List):-
    !,
    member(H,List),
    subset(T,List).

different([]).
different([H|T]):-
\+member(H,T),
different(T),!.

valid([]).
valid([Head|Tail]) :- 
    different(Head), 
    valid(Tail),!.

sudoku(Puzzle, Solution) :-
    Solution = Puzzle,
    Puzzle = [S11, S12, S13, S14, 
              S21, S22, S23, S24, 
              S31, S32, S33, S34, 
              S41, S42, S43, S44], 

    subset(Solution, [1,2,3,4]), 

    Row1 = [S11, S12, S13, S14],
    Row2 = [S21, S22, S23, S24],
    Row3 = [S31, S32, S33, S34],
    Row4 = [S41, S42, S43, S44],

    Col1 = [S11, S21, S31, S41],
    Col2 = [S12, S22, S32, S42],
    Col3 = [S13, S23, S33, S43],
    Col4 = [S14, S24, S34, S44],

    Square1 = [S11, S12, S21, S22],
    Square2 = [S13, S14, S23, S24],
    Square3 = [S31, S32, S41, S42],
    Square4 = [S33, S34, S43, S44], 

    valid([Row1, Row2, Row3, Row4, 
           Col1, Col2, Col3, Col4, 
           Square1, Square2, Square3, Square4]).
\$\endgroup\$
  • 1
    \$\begingroup\$ Just so you know, sudoku is a 9x9 grid ... ;-) just saying. \$\endgroup\$ – rolfl Nov 30 '13 at 0:49
  • \$\begingroup\$ I'm trying to do it 9X9, the problem is that the 4X4 solution is too slow \$\endgroup\$ – user1730250 Nov 30 '13 at 0:56
  • \$\begingroup\$ Your question says you want to do it on 10x10.... \$\endgroup\$ – rolfl Nov 30 '13 at 1:00
  • \$\begingroup\$ I take it my advice was too abstract. \$\endgroup\$ – Daniel Lyons Nov 30 '13 at 2:57
  • 1
    \$\begingroup\$ sudoku([,9,,,,5,,,4,4,2,1,,,,,,9,8,,5,4,9,2,,,6,,,,,1,4,,,2,,,8,7,,9,6,,,1,,,6,2,,,,,7,,,2,4,6,9,,8,5,,,,,,2,6,1,9,,,8,,,,3,_],Solution). \$\endgroup\$ – user1730250 Nov 30 '13 at 3:01
2
\$\begingroup\$

Well, copying my answer from SO.

Think about the number of outputs of subset/4, if every cell of Solution is unbound in the beginning. There are 44*4 = 4,294,967,296 outputs. Now you might know why your code is so slow.

You should call valid/1 inside of subset/2. Test if the puzzle is still valid after inserting one number:

subset(_,[],_).
subset(RCS,[H|T],List):-
    member(H,List),
    valid(RCS),
    subset(RCS,T,List).

% Like \+member(H,T) but unbound cells are ignored
nonmember(_, []).
nonmember(H1, [H2|T]) :-
    (var(H2); H1 \= H2),
    nonmember(H1, T).

different([]).
different([H|T]):-
    (var(H); nonmember(H,T)),
    different(T),!.

valid([]).
valid([Head|Tail]) :- 
    different(Head), 
    valid(Tail),!.

sudoku(Puzzle) :-
    Puzzle = [S11, S12, S13, S14,
              S21, S22, S23, S24,
              S31, S32, S33, S34,
              S41, S42, S43, S44],

    Row1 = [S11, S12, S13, S14],
    Row2 = [S21, S22, S23, S24],
    Row3 = [S31, S32, S33, S34],
    Row4 = [S41, S42, S43, S44],

    Col1 = [S11, S21, S31, S41],
    Col2 = [S12, S22, S32, S42],
    Col3 = [S13, S23, S33, S43],
    Col4 = [S14, S24, S34, S44],

    Square1 = [S11, S12, S21, S22],
    Square2 = [S13, S14, S23, S24],
    Square3 = [S31, S32, S41, S42],
    Square4 = [S33, S34, S43, S44], 

    RCS = [Row1, Row2, Row3, Row4, 
           Col1, Col2, Col3, Col4, 
           Square1, Square2, Square3, Square4],

    subset(RCS, Puzzle, [1,2,3,4]).

Next optimization would be not to test all rows, columns and squares after every insert, but only the affected ones (3 instead of 12):

subset([], _).
subset([(P,RCS) | T], List):-
    member(P, List),
    valid(RCS),
    subset(T, List).

% Like \+member(H,T) but unbound cells are ignored
nonmember(_, []).
nonmember(H1, [H2|T]) :-
    (var(H2); H1 \= H2),
    nonmember(H1, T).

different([]).
different([H|T]):-
    (var(H); nonmember(H,T)),
    different(T),!.

valid([]).
valid([Head|Tail]) :- 
    different(Head), 
    valid(Tail),!.

sudoku(Puzzle) :-
    Puzzle = [S11, S12, S13, S14,
              S21, S22, S23, S24,
              S31, S32, S33, S34,
              S41, S42, S43, S44],

    Row1 = [S11, S12, S13, S14],
    Row2 = [S21, S22, S23, S24],
    Row3 = [S31, S32, S33, S34],
    Row4 = [S41, S42, S43, S44],

    Col1 = [S11, S21, S31, S41],
    Col2 = [S12, S22, S32, S42],
    Col3 = [S13, S23, S33, S43],
    Col4 = [S14, S24, S34, S44],

    Square1 = [S11, S12, S21, S22],
    Square2 = [S13, S14, S23, S24],
    Square3 = [S31, S32, S41, S42],
    Square4 = [S33, S34, S43, S44],

    RCS11 = (S11, [Row1, Col1, Square1]),
    RCS12 = (S12, [Row1, Col2, Square1]),
    RCS13 = (S13, [Row1, Col3, Square2]),
    RCS14 = (S14, [Row1, Col4, Square2]),
    RCS21 = (S21, [Row2, Col1, Square1]),
    RCS22 = (S22, [Row2, Col2, Square1]),
    RCS23 = (S23, [Row2, Col3, Square2]),
    RCS24 = (S24, [Row2, Col4, Square2]),
    RCS31 = (S31, [Row3, Col1, Square3]),
    RCS32 = (S32, [Row3, Col2, Square3]),
    RCS33 = (S33, [Row3, Col3, Square4]),
    RCS34 = (S34, [Row3, Col4, Square4]),
    RCS41 = (S41, [Row4, Col1, Square3]),
    RCS42 = (S42, [Row4, Col2, Square3]),
    RCS43 = (S43, [Row4, Col3, Square4]),
    RCS44 = (S44, [Row4, Col4, Square4]),

    RCS = [RCS11, RCS12, RCS13, RCS14,
           RCS21, RCS22, RCS23, RCS24,
           RCS31, RCS32, RCS33, RCS34,
           RCS41, RCS42, RCS43, RCS44],

    subset(RCS, [1,2,3,4]).

Now you should be able to increase the puzzle size to 9×9 and still have a reasonably fast solver.

\$\endgroup\$
1
\$\begingroup\$

This is blazing fast version of your code which finds solution in miliseconds:

sudoku(Puzzle, Solution) :-
    Solution = Puzzle,
    Puzzle = [S11, S12, S13, S14,
              S21, S22, S23, S24,
              S31, S32, S33, S34,
              S41, S42, S43, S44],

    Row1 = [S11, S12, S13, S14],
    Row2 = [S21, S22, S23, S24],
    Row3 = [S31, S32, S33, S34],
    Row4 = [S41, S42, S43, S44],

    Col1 = [S11, S21, S31, S41],
    Col2 = [S12, S22, S32, S42],
    Col3 = [S13, S23, S33, S43],
    Col4 = [S14, S24, S34, S44],

    Square1 = [S11, S12, S21, S22],
    Square2 = [S13, S14, S23, S24],
    Square3 = [S31, S32, S41, S42],
    Square4 = [S33, S34, S43, S44],

    Sets = [Row1, Row2, Row3, Row4,
           Col1, Col2, Col3, Col4,
           Square1, Square2, Square3, Square4],

    maplist(permutation([1,2,3,4]), Sets).

Firstly, I removed all your predicates. Not only they do what you can accomplish with maplist/2 (your valid(X) is equivalent to maplist(difference, X) and subset(Solution, [1,2,3,4]) is equivalent to maplist(between(1,4), Solution)), but their combination is just VERY inefficent equivalent of permutation/2.

I don't know if permutation/2 is ISO-Prolog, but can be found in SWI-Prolog, GNU Prolog and others. What's more, permutation/2 can be replaced with even more efficent permute/2 (which doesn't follow lexicographic order):

permute([], []).
permute([X|Rest], L) :-
    permute(Rest, L1),
    select(X, L, L1).
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.