sudoku solver in prolog

sdk_resolvido.pl

%% -----------------------------------------------------------------------------
%% PROLOG program to solve SUDOKU puzzles
%% gerardo.lima<AT>gmail.com 2007-07-02
%%
%% usage:
%% edit the initial state predicate 'numlist_init' and run the following
%% ?- numlist_init(L), sudoku_solve(L).
%%
%% see also this good site:
%% http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/pt_framer.html
%% -----------------------------------------------------------------------------

%% initial state predicate
%% -----------------------------------------------------------------------------

numlist_init(L) :-
  L = [
    _,_,8, 5,3,_, _,_,4,
    _,_,_, _,_,_, _,_,_,
    _,_,_, _,_,9, 1,2,_,

    _,6,2, 1,_,_, 8,_,_,
    _,8,_, _,6,_, _,9,_,
    _,_,7, _,_,3, 4,5,_,

    _,7,1, 4,_,_, _,_,_,
    _,_,_, _,_,_, _,_,_,
    4,_,_, _,5,7, 6,_,_
  ].

numlist_init_20070704(L) :-
  L = [
    9,4,_, _,2,_, 6,_,_,
    _,_,2, _,_,_, _,4,_,
    6,_,5, _,7,_, 9,2,_,

    2,_,_, 3,_,9, _,_,_,
    4,6,_, _,_,_, _,8,9,
    _,_,_, 1,_,8, _,_,4,

    _,7,6, _,9,_, 8,_,2,
    _,5,_, _,_,_, 7,_,_,
    _,_,9, _,8,_, _,1,6
  ].


numlist_init_20070702(L) :-
  L = [
    _,_,_, 8,_,_, 3,_,_,
    _,_,_, _,_,6, _,_,2,
    _,8,9, _,_,1, _,_,7,

    8,_,_, _,9,4, _,_,5,
    _,_,_, 1,_,2, _,_,_,
    1,_,_, 7,5,_, _,_,6,

    3,_,_, 9,_,_, 4,7,_,
    9,_,_, 6,_,_, _,_,_,
    _,_,5, _,_,7, _,_,_
  ].
  
% "structures"
%% -----------------------------------------------------------------------------
grid_init(IN_numlist, OUT_grid, OUT_lin, OUT_col, OUT_qua) :-
  IN_numlist = [ % identify each number in the list
    N11, N12, N13, N14, N15, N16, N17, N18, N19,
    N21, N22, N23, N24, N25, N26, N27, N28, N29,
    N31, N32, N33, N34, N35, N36, N37, N38, N39,
    N41, N42, N43, N44, N45, N46, N47, N48, N49,
    N51, N52, N53, N54, N55, N56, N57, N58, N59,
    N61, N62, N63, N64, N65, N66, N67, N68, N69,
    N71, N72, N73, N74, N75, N76, N77, N78, N79,
    N81, N82, N83, N84, N85, N86, N87, N88, N89,
    N91, N92, N93, N94, N95, N96, N97, N98, N99
  ],
  OUT_grid = [ % identify each cell in the grid
    C11, C12, C13, C14, C15, C16, C17, C18, C19,
    C21, C22, C23, C24, C25, C26, C27, C28, C29,
    C31, C32, C33, C34, C35, C36, C37, C38, C39,
    C41, C42, C43, C44, C45, C46, C47, C48, C49,
    C51, C52, C53, C54, C55, C56, C57, C58, C59,
    C61, C62, C63, C64, C65, C66, C67, C68, C69,
    C71, C72, C73, C74, C75, C76, C77, C78, C79,
    C81, C82, C83, C84, C85, C86, C87, C88, C89,
    C91, C92, C93, C94, C95, C96, C97, C98, C99
  ],
  % unify each number to a cell
  C11 = cell(N11, lin1, col1, qua1),  C12 = cell(N12, lin1, col2, qua1),  C13 = cell(N13, lin1, col3, qua1),
  C14 = cell(N14, lin1, col4, qua2),  C15 = cell(N15, lin1, col5, qua2),  C16 = cell(N16, lin1, col6, qua2),
  C17 = cell(N17, lin1, col7, qua3),  C18 = cell(N18, lin1, col8, qua3),  C19 = cell(N19, lin1, col9, qua3),
  C21 = cell(N21, lin2, col1, qua1),  C22 = cell(N22, lin2, col2, qua1),  C23 = cell(N23, lin2, col3, qua1),
  C24 = cell(N24, lin2, col4, qua2),  C25 = cell(N25, lin2, col5, qua2),  C26 = cell(N26, lin2, col6, qua2),
  C27 = cell(N27, lin2, col7, qua3),  C28 = cell(N28, lin2, col8, qua3),  C29 = cell(N29, lin2, col9, qua3),
  C31 = cell(N31, lin3, col1, qua1),  C32 = cell(N32, lin3, col2, qua1),  C33 = cell(N33, lin3, col3, qua1),
  C34 = cell(N34, lin3, col4, qua2),  C35 = cell(N35, lin3, col5, qua2),  C36 = cell(N36, lin3, col6, qua2),
  C37 = cell(N37, lin3, col7, qua3),  C38 = cell(N38, lin3, col8, qua3),  C39 = cell(N39, lin3, col9, qua3),
  C41 = cell(N41, lin4, col1, qua4),  C42 = cell(N42, lin4, col2, qua4),  C43 = cell(N43, lin4, col3, qua4),
  C44 = cell(N44, lin4, col4, qua5),  C45 = cell(N45, lin4, col5, qua5),  C46 = cell(N46, lin4, col6, qua5),
  C47 = cell(N47, lin4, col7, qua6),  C48 = cell(N48, lin4, col8, qua6),  C49 = cell(N49, lin4, col9, qua6),
  C51 = cell(N51, lin5, col1, qua4),  C52 = cell(N52, lin5, col2, qua4),  C53 = cell(N53, lin5, col3, qua4),
  C54 = cell(N54, lin5, col4, qua5),  C55 = cell(N55, lin5, col5, qua5),  C56 = cell(N56, lin5, col6, qua5),
  C57 = cell(N57, lin5, col7, qua6),  C58 = cell(N58, lin5, col8, qua6),  C59 = cell(N59, lin5, col9, qua6),
  C61 = cell(N61, lin6, col1, qua4),  C62 = cell(N62, lin6, col2, qua4),  C63 = cell(N63, lin6, col3, qua4),
  C64 = cell(N64, lin6, col4, qua5),  C65 = cell(N65, lin6, col5, qua5),  C66 = cell(N66, lin6, col6, qua5),
  C67 = cell(N67, lin6, col7, qua6),  C68 = cell(N68, lin6, col8, qua6),  C69 = cell(N69, lin6, col9, qua6),
  C71 = cell(N71, lin7, col1, qua7),  C72 = cell(N72, lin7, col2, qua7),  C73 = cell(N73, lin7, col3, qua7),
  C74 = cell(N74, lin7, col4, qua8),  C75 = cell(N75, lin7, col5, qua8),  C76 = cell(N76, lin7, col6, qua8),
  C77 = cell(N77, lin7, col7, qua9),  C78 = cell(N78, lin7, col8, qua9),  C79 = cell(N79, lin7, col9, qua9),
  C81 = cell(N81, lin8, col1, qua7),  C82 = cell(N82, lin8, col2, qua7),  C83 = cell(N83, lin8, col3, qua7),
  C84 = cell(N84, lin8, col4, qua8),  C85 = cell(N85, lin8, col5, qua8),  C86 = cell(N86, lin8, col6, qua8),
  C87 = cell(N87, lin8, col7, qua9),  C88 = cell(N88, lin8, col8, qua9),  C89 = cell(N89, lin8, col9, qua9),
  C91 = cell(N91, lin9, col1, qua7),  C92 = cell(N92, lin9, col2, qua7),  C93 = cell(N93, lin9, col3, qua7),
  C94 = cell(N94, lin9, col4, qua8),  C95 = cell(N95, lin9, col5, qua8),  C96 = cell(N96, lin9, col6, qua8),
  C97 = cell(N97, lin9, col7, qua9),  C98 = cell(N98, lin9, col8, qua9),  C99 = cell(N99, lin9, col9, qua9),
  OUT_lin = [ % unify each cell to its line
    cnj(lin1, [C11, C12, C13, C14, C15, C16, C17, C18, C19]),
    cnj(lin2, [C21, C22, C23, C24, C25, C26, C27, C28, C29]),
    cnj(lin3, [C31, C32, C33, C34, C35, C36, C37, C38, C39]),
    cnj(lin4, [C41, C42, C43, C44, C45, C46, C47, C48, C49]),
    cnj(lin5, [C51, C52, C53, C54, C55, C56, C57, C58, C59]),
    cnj(lin6, [C61, C62, C63, C64, C65, C66, C67, C68, C69]),
    cnj(lin7, [C71, C72, C73, C74, C75, C76, C77, C78, C79]),
    cnj(lin8, [C81, C82, C83, C84, C85, C86, C87, C88, C89]),
    cnj(lin9, [C91, C92, C93, C94, C95, C96, C97, C98, C99])
  ],
  OUT_col = [ % unify each cell to its column
    cnj(col1, [C11, C21, C31, C41, C51, C61, C71, C81, C91]),
    cnj(col2, [C12, C22, C32, C42, C52, C62, C72, C82, C92]),
    cnj(col3, [C13, C23, C33, C43, C53, C63, C73, C83, C93]),
    cnj(col4, [C14, C24, C34, C44, C54, C64, C74, C84, C94]),
    cnj(col5, [C15, C25, C35, C45, C55, C65, C75, C85, C95]),
    cnj(col6, [C16, C26, C36, C46, C56, C66, C76, C86, C96]),
    cnj(col7, [C17, C27, C37, C47, C57, C67, C77, C87, C97]),
    cnj(col8, [C18, C28, C38, C48, C58, C68, C78, C88, C98]),
    cnj(col9, [C19, C29, C39, C49, C59, C69, C79, C89, C99])
  ],
  OUT_qua = [ % unify each cell to its frame
    cnj(qua1, [C11, C12, C13, C21, C22, C23, C31, C32, C33]),
    cnj(qua2, [C14, C15, C16, C24, C25, C26, C34, C35, C36]),
    cnj(qua3, [C17, C18, C19, C27, C28, C29, C37, C38, C39]),
    cnj(qua4, [C41, C42, C43, C51, C52, C53, C61, C62, C63]),
    cnj(qua5, [C44, C45, C46, C54, C55, C56, C64, C65, C66]),
    cnj(qua6, [C47, C48, C49, C57, C58, C59, C67, C68, C69]),
    cnj(qua7, [C71, C72, C73, C81, C82, C83, C91, C92, C93]),
    cnj(qua8, [C74, C75, C76, C84, C85, C86, C94, C95, C96]),
    cnj(qua9, [C77, C78, C79, C87, C88, C89, C97, C98, C99])
  ]
  .

%% sudoku_solve
%% -----------------------------------------------------------------------------
%% build the sudoku objects from a list of numbers, solve the sudoku and
%% print the results

sudoku_solve(IN_numlist) :-
  grid_init(IN_numlist, AUX_grid, AUX_lin, AUX_col, AUX_qua),
  grid_solve(AUX_grid, AUX_lin, AUX_col, AUX_qua),
  numlist_format(IN_numlist),
  !
  .


%% grid_solve
%% -----------------------------------------------------------------------------
%% get the "head" cell, solve it and repeat for the next "head", until the
%% grid is empty

grid_solve([], _, _, _).

grid_solve(IN_grid, IN_lin, IN_col, IN_qua) :-
  IN_grid = [AUX_cell | AUX_grid_rest],
  cell_solve(AUX_cell, IN_lin, IN_col, IN_qua),
  grid_solve(AUX_grid_rest, IN_lin, IN_col, IN_qua)
  .


%% cell_solve
%% -----------------------------------------------------------------------------
%% for cells whose value is NOT UNIFIED, assign a possible value and remove it
%% from the line, column and frame

cell_solve(IN_cell, _, _, _) :-
  IN_cell = cell(AUX_num, _, _, _),
  \+ var(AUX_num)
  .

cell_solve(IN_cell, IN_Lin, IN_Col, IN_Qua) :-
  IN_cell = cell(AUX_num, AUX_idLin, AUX_idCol, AUX_idQua),
  var(AUX_num),

  % get the set of cells for each "dimension"
  cnj_get_cells(IN_Lin, AUX_idLin, AUX_lin_cells),
  cnj_get_cells(IN_Col, AUX_idCol, AUX_col_cells),
  cnj_get_cells(IN_Qua, AUX_idQua, AUX_qua_cells),
  !,

  % resolve the domain of numbers that can be assigned to the cell
  AUX_domain_0 = [1, 2, 3, 4, 5, 6, 7, 8, 9],
  domain_delete_values(AUX_domain_0, AUX_lin_cells, AUX_domain_1),
  domain_delete_values(AUX_domain_1, AUX_col_cells, AUX_domain_2),
  domain_delete_values(AUX_domain_2, AUX_qua_cells, AUX_domain_3),
  !,

  select(AUX_num, AUX_domain_3, _)
  .


%% cnj_get_cells
%% -----------------------------------------------------------------------------
cnj_get_cells(IN_list, IN_id, OUT_cells) :-
  IN_list  = [ AUX_cnj | _],
  AUX_cnj  = cnj(IN_id, OUT_cells)
  .

cnj_get_cells(IN_list, IN_id, OUT_cells) :-
  IN_list  = [ AUX_cnj | AUX_list_rest],
  AUX_cnj  = cnj(AUX_id, _),
  AUX_id   \= IN_id,
  cnj_get_cells(AUX_list_rest, IN_id, OUT_cells)
  .


%% domain_delete_values
%% -----------------------------------------------------------------------------
%% removes the elements in domain that was assigned to any cell in the list

domain_delete_values([], _, _) :-
  fail.

domain_delete_values(IO_domain, [], IO_domain) :-
  IO_domain \= []
  .

domain_delete_values(IN_domain, IN_cells, OUT_domain) :-
  IN_domain \= [],
  IN_cells = [cell(AUX_num, _, _, _) | IN_cells_rest],
  \+ var(AUX_num),
  !,
  delete(IN_domain, AUX_num, AUX_domain),
  domain_delete_values(AUX_domain, IN_cells_rest, OUT_domain)
  .

domain_delete_values(IN_domain, IN_cells, OUT_domain) :-
  IN_domain \= [],
  IN_cells = [cell(AUX_num, _, _, _) | IN_cells_rest],
  var(AUX_num),
  !,
  domain_delete_values(IN_domain, IN_cells_rest, OUT_domain)
  .

%% numlist_format
%% -----------------------------------------------------------------------------

numlist_format(S) :-
  format("~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n~w,~w,~w,~w,~w,~w,~w,~w,~w~n", S)
  .


%% other initial state predicates for testing
%% -----------------------------------------------------------------------------

numlist_init_full(L) :-
  L = [
    1,2,3, 4,5,6, 7,8,9,
    4,5,6, 7,8,9, 1,2,3,
    7,8,9, 1,2,3, 4,5,6,

    5,6,7, 8,9,1, 2,3,4,
    8,9,1, 2,3,4, 5,6,7,
    2,3,4, 5,6,7, 8,9,1,

    9,1,2, 3,4,5, 6,7,8,
    3,4,5, 6,7,8, 9,1,2,
    6,7,8, 9,1,2, 3,4,5
  ].

numlist_init_empty(L) :-
  L = [
    _,_,_, _,_,_, _,_,_,
    _,_,_, _,_,_, _,_,_,
    _,_,_, _,_,_, _,_,_,
    
    _,_,_, _,_,_, _,_,_,
    _,_,_, _,_,_, _,_,_,
    _,_,_, _,_,_, _,_,_,
    
    _,_,_, _,_,_, _,_,_,
    _,_,_, _,_,_, _,_,_,
    _,_,_, _,_,_, _,_,_
  ].

Commenting out the line 159 (and its preceding comma), this code generates all valid sudokus constrained by its initial input:

sudoku_solve(IN_numlist) :-
  grid_init(IN_numlist, AUX_grid, AUX_lin, AUX_col, AUX_qua),
  grid_solve(AUX_grid, AUX_lin, AUX_col, AUX_qua),
  numlist_format(IN_numlist) %,
  % !
  .

Using this variation, the following code generates all valid sudokus, one at a time:

?- numlist_init_empty(L), sudoku_solve(L).