68 lines
1.5 KiB
Prolog
68 lines
1.5 KiB
Prolog
/*
|
|
* Nonogram/paint-by-numbers solver in SWI-Prolog. Uses CLP(FD),
|
|
* in particular the automaton/3 (finite-state/RE) constraint.
|
|
* Copyright (c) 2011 Lars Buitinck.
|
|
* Do with this code as you like, but don't remove the copyright notice.
|
|
*/
|
|
|
|
:- use_module(library(clpfd)).
|
|
|
|
nono(RowSpec, ColSpec, Grid) :-
|
|
rows(RowSpec, Grid),
|
|
transpose(Grid, GridT),
|
|
rows(ColSpec, GridT).
|
|
|
|
rows([], []).
|
|
rows([C|Cs], [R|Rs]) :-
|
|
row(C, R),
|
|
rows(Cs, Rs).
|
|
|
|
row(Ks, Row) :-
|
|
sum(Ks, #=, Ones),
|
|
sum(Row, #=, Ones),
|
|
arcs(Ks, Arcs, start, Final),
|
|
append(Row, [0], RowZ),
|
|
automaton(RowZ, [source(start), sink(Final)], [arc(start,0,start) | Arcs]).
|
|
|
|
% Make list of transition arcs for finite-state constraint.
|
|
arcs([], [], Final, Final).
|
|
arcs([K|Ks], Arcs, CurState, Final) :-
|
|
gensym(state, NextState),
|
|
( K == 0
|
|
-> Arcs = [arc(CurState,0,CurState), arc(CurState,0,NextState) | Rest],
|
|
arcs(Ks, Rest, NextState, Final)
|
|
; Arcs = [arc(CurState,1,NextState) | Rest],
|
|
K1 #= K-1,
|
|
arcs([K1|Ks], Rest, NextState, Final)).
|
|
|
|
|
|
make_grid(Grid, X, Y, Vars) :-
|
|
length(Grid,X),
|
|
make_rows(Grid, Y, Vars).
|
|
|
|
make_rows([], _, []).
|
|
make_rows([R|Rs], Len, Vars) :-
|
|
length(R, Len),
|
|
make_rows(Rs, Len, Vars0),
|
|
append(R, Vars0, Vars).
|
|
|
|
print([]).
|
|
print([R|Rs]) :-
|
|
print_row(R),
|
|
print(Rs).
|
|
|
|
print_row([]) :- nl.
|
|
print_row([X|R]) :-
|
|
( X == 0
|
|
-> write(' ')
|
|
; write('x')),
|
|
print_row(R).
|
|
|
|
nonogram(Rows, Cols) :-
|
|
length(Rows, X),
|
|
length(Cols, Y),
|
|
make_grid(Grid, X, Y, Vars),
|
|
nono(Rows, Cols, Grid),
|
|
label(Vars),
|
|
print(Grid).
|