Sudoku solver performance problems

1
votes

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.

2
performanceprologsolversudoku

2 Answers

3
votes

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.

2
votes

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)