Sudoku solver in Prolog.

sudoku.pl

% vim: set syntax=prolog

:- use_module(library(clpfd)).

:- initialization(main, main).

main(_) :- main.

main :-
  current_input(S),
  read_input(S, Sudoku),
  solve(Sudoku),
  render(Sudoku).

solve(Grid) :-
  append(Grid, Cells),
  Cells ins 1..9,
  Rows = Grid,
  transpose(Grid, Columns),
  blocks(Grid, Blocks),
  maplist(all_distinct, Rows),
  maplist(all_distinct, Columns),
  maplist(all_distinct, Blocks).

blocks([A, B, C, D, E, F, G, H, I], Blocks) :-
  block_rows([A, B, C], X),
  block_rows([D, E, F], Y),
  block_rows([G, H, I], Z),
  append([X, Y, Z], Blocks).
block_rows([[], [], []], []).
block_rows([[A1, A2, A3 | As],
            [B1, B2, B3 | Bs],
            [C1, C2, C3 | Cs]],
           [[A1, A2, A3, B1, B2, B3, C1, C2, C3] | BlockRow]) :-
  block_rows([As, Bs, Cs], BlockRow).

read_input(S, Input) :-
  read_rows(S, Input).
read_rows(S, Rows) :-
  read_line_to_codes(S, Line),
  (
    Line = end_of_file
    ->  Rows = []
    ;   parse_row(Line, Row),
        read_rows(S, Rest),
        Rows = [Row | Rest]
  ).
parse_row(Line, Row) :-
  split_string(Line, " ", "", Strings),
  maplist(parse_cell, Strings, Row).
parse_cell("_", _).
parse_cell(String, Cell) :-
  string_codes(String, Codes),
  number_codes(Cell, Codes).

render(Puzzle) :-
  format("\n"),
  maplist(render_row, Puzzle).
render_row([Value]) :-
  render_cell(Value),
  format("\n").
render_row([Value | Rest]) :-
  render_cell(Value),
  format(" "),
  render_row(Rest).
render_cell(Value) :-
  format("~d", [Value]).

You can run this by creating a file representing a Sudoku problem, space-separated, with underscores in place of empty squares. It might look something like this:

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

And then running with swipl:

swipl sudoku.pl < example.txt

If you don't have SWI-Prolog installed, you can use Nix to acquire it easily:

nix run nixpkgs.swiProlog -c swipl sudoku.pl < example.txt