Prolog Sudoku Solver, Solve any quadratic Sudoku, elements not distinct

Question

Solving any quadratic Sudoku, so Sudoku of sizes 4,9,16,25... without the need of hard-coding those "blocks", the sub-units of your normal Sudoku field.

Using SWI-Prolog and the clp(FD) library.

Sudokus given in a format like this (list of lists):

[[_,1,3,_],
 [2,_,_,_],
 [_,_,_,3],
 [_,2,1,_]]

Program called using:

solve_sudoku([[_,1,3,_],[2,_,_,_],[_,_,_,3],[_,2,1,_]],L).
L = [[4, 1, 3, 2], [2, 3, 4, 1], [1, 4, 2, 3], [3, 2, 1, 4]]

Answer 1

Top-level from this link.

sudoku(Rows) :-
  length(Rows,N),
  D is integer(sqrt(N)),
  append(Rows,Vs),Vs ins 1..N,
  maplist(all_distinct,Rows),
  transpose(Rows,Columns),
  maplist(all_distinct,Columns),
  check_blocks(Rows,D),
  maplist(label,Rows).

After checking that the rows and columns have no repetitions, we need to check the blocks, which are D by D squares.

The procedure check_blocks/2 takes D rows at a time and passes them to block_columns/4.

check_blocks(Rows,D) :-
  length(BlockRows,D), append(BlockRows,Rest,Rows),
  block_columns(BlockRows,D,[],[]),
  check_blocks(Rest,D).
check_blocks([],_).

Now we have D rows, which are assumed to each contain some number (ie D) of D columns. But we need to get hold of the first D columns of all the rows in order to check the block.

So the first clause in block_columns/4 loops over all the rows and splits them into the prefix (D columns) and the rest. When Rows is empty, Bs is the current block, and Rs the rest of the columns in each row.

block_columns([Row|Rows],D,Bs,Rs) :-
  length(Cols,D), append(Cols,Rest,Row),
  block_columns(Rows,D,[Cols|Bs],[Rest|Rs]).
block_columns([],D,Bs,Rs) :-
  flatten(Bs,Ns), all_distinct(Ns),
  flatten(Rs,Xs),
  ( Xs = [] ->
    true
  ; block_columns(Rs,D,[],[]) ).

The second clause checks the block, and then starts over again. When we have reached the end of the columns, Rs will not be empty but contain D empty lists, so we have to flatten it before checking for termination.