CODEWITHSUNDEEP
performanceprologsolversudoku
bli77
bli77

Reputation: 55

Sudoku solver performance problems

I have a problem with my prolog solver for sudoku. It's working, but the performance is reeaaaaly bad. With small ones it's working just fine, but bigger ones like 9x9 or more take 10 minutes or more sadly. I want to leave it for an indefinite size like it is right now. Can anyone help?

solve_sudoku(Rows,Sol):-
    length(Rows,Max),
    maplist(same_length(Rows),Rows),
    append(Rows, List), List ins 1..Max,
    maplist(all_distinct, Rows),
    transpose(Rows, Columns),
    maplist(all_distinct,Columns),
    maplist(label,Rows),
    boxes(Boxes,Rows),
    maplist(all_distinct,Boxes),
    boxes_distinct(Boxes),
    Sol = Rows.

boxes(Bs,M) :-
    length(M,Len),
    Sq is round(sqrt(Len)),
    findall(B, (between(1, Sq, R),
            between(1, Sq, C),
            block(M, Sq, R, C, B)), Bs).

cell(M, R,C, V) :-
    nth1(R,M,Row), nth1(C,Row,V).

block(M, Sq, R,C, B) :-
    findall(V, (between(1, Sq, X),
            between(1, Sq, Y),
            I is (R-1) * Sq + X,
            J is (C-1) * Sq + Y,
            cell(M, I, J, V)), B).

boxes_distinct([]).
boxes_distinct([BH|BT]):-
    all_distinct(BH),
    boxes_distinct(BT).

The input is a list of lists with the sudoku to solve and the output is the solved sudoku as a list.

Upvotes: 1

Views: 268

Answers (2)

CapelliC
CapelliC

Reputation: 60014

boxes_distinct(Boxes) seems useless, being already covered by maplist(all_distinct,Boxes), and use label(List) (instead of maplist(label,Rows)) near the end of clause. Anyway, the main problem has been indicated by @gabrielte (+1)

Upvotes: 2

Taku Koyahata
Taku Koyahata

Reputation: 558

I think you shoud call 

maplist(label,Rows)

after

boxes_distinct(Boxes)

usually you should call label or labelling after declaring all constraint.

and use "labeling predicate with ff or ffc option" instead of "label" may increse efficiency.

Upvotes: 3

Related Questions