/*
 * SICSTUS CLPFD DEMONSTRATION PROGRAM
 * Purpose   : Nonograms
 * Author    : Mats Carlsson
 *
 * | ?- starpic(sheepdog).
 */
 
:- module(starpic, [
	starpic/1
	]).

:- use_module(library(lists)).
:- use_module(library(clpfd)).

starpic(ID) :-
	data(ID, RowData, ColData),
	length(RowData, NRows),
	length(ColData, NCols),
	length(Rows, NRows),
	(   foreach(Row,Rows),
	    param(NCols)
	do  length(Row, NCols),
	    domain(Row, 0, 1)
	),
	transpose(Rows, Cols),
	constrain(Rows, RowData),
	constrain(Cols, ColData),
	heur_order(Rows, RowData, Cols, ColData, Vars),
	labeling([down], Vars),
	append(Rows, DrawVars),
	draw(DrawVars, NCols).

heur_order(Rows, RowData, Cols, ColData, Vars) :-
	length(RowData, NRows),
	length(ColData, NCols),
	tag_vars(Rows, RowData, NCols, S0, S1),
	tag_vars(Cols, ColData, NRows, S1, []),
	keysort(S0, S2),
	(   foreach(_-V,S2),
	    foreach(V,S3)
	do  true
	),
	append(S3, Vars).

tag_vars([], [], _) --> [].
tag_vars([R|Rows], [D|Data], N) --> [Tag-R],
	{sumlist(D, Sum)},
	{Tag is N-Sum},
	tag_vars(Rows, Data, N).

constrain([], []).
constrain([Row|Rows], [Datum|Data]) :-
	build_automaton(Datum, Source, Sink, Auto, []),
	automaton(Row, [source(Source),sink(Sink)], Auto),
	constrain(Rows, Data).

build_automaton([], S, S) --> [arc(S,0,S)].
build_automaton([C|Cs], S0, S) -->  [arc(S0,0,S0)],
	build_ones(C, S0, S1),
	build_cont(Cs, S1, S).

build_cont([], S, S) --> !, [arc(S,0,S)].
build_cont([C|Cs], S0, S) -->  [arc(S0,0,S1),arc(S1,0,S1)],
	build_ones(C, S1, S2),
	build_cont(Cs, S2, S).

build_ones(0, S, S) --> !.
build_ones(I, S0, S) --> [arc(S0,1,S1)],
	{J is I-1},
	build_ones(J, S1, S).

draw(Cells, NC) :-
	format('+~*c+\n', [NC,0'-]),
	draw_lines(Cells, NC),
	format('+~*c+\n', [NC,0'-]).


draw_lines([], _) :- !.
draw_lines(Cells, NC) :-
	asciify(0, NC, Cells, Cells1, String, "|\n"),
	format([0'||String], []),
	draw_lines(Cells1, NC).

asciify(NC, NC, S, S) --> !.
asciify(I, NC, [0|S0], S) --> " ", !,
	{J is I+1},
	asciify(J, NC, S0, S).
asciify(I, NC, [1|S0], S) --> "#", !,
	{J is I+1},
	asciify(J, NC, S0, S).

:- dynamic
	data/3.
data(pinwheel,
    [[2, 1], [1], [2], [2], [1], [1, 2]],
    [[1, 2], [1], [2], [2], [1], [2, 1]]).
data(doggie,
     [[1],[4],[3],[3,1],[7],[7],[1,4],[2,4]],
     [[2,1],[7],[6],[1,3,1],[4],[4],[4],[4]]).
data(heart,
     [[2, 2], [4, 4], [1, 3, 1], [2, 1, 2], [1, 1], [2, 2], [2, 2], [3], [1]],
     [[3], [2, 3], [2, 2], [2, 2], [2, 2], [2, 2], [2, 2], [2, 3], [3]]).
data(strange,
     [[3], [2, 1], [1, 1], [1, 4], [1, 1, 1, 1], [2, 1, 1, 1], [2, 1, 1], [1, 2], [2, 3], [3]],
     [[3], [2, 1], [2, 2], [2, 1], [1, 2, 1], [1, 1], [1, 4, 1], [1, 1, 2], [3, 1], [4]]).
data(bunny,
    [[1], [2], [4, 4], [12], [8], [9], [3, 4], [2, 2]],
    [[2], [2, 1], [3, 2], [6], [1, 4], [3], [4], [4], [4], [5], [4], [1, 3], [2]]).
data(spaceman,
     [[3,6],[1,4],[1,1,3],[2],[3,3],[1,4],[2,5],[2,5],[1,1],[3]],
     [[2,3],[1,2],[1,1,1,1],[1,2],[1,1,1,1],[1,2],[2,3],[3,4],[8],[9]]).
data(crocodile,
    [[3], [2, 3, 2], [10, 3], [15], [1, 1, 1, 1, 6], [1, 7], [1, 4], [1, 4], [4]],
    [[3], [4], [2, 2], [3, 1], [2, 3], [3, 2], [2, 3], [4, 2], [3, 2], [6], [1, 3], [1, 3], [1, 4], [5], [5]]).
data(non_unique,
    [[2, 2], [2, 2], [4], [1, 1], [1, 1], [1, 1, 1, 1], [1, 1], [1, 4], [1, 1, 1], [1, 1, 4], [1, 3], [1, 2], [5], [2, 2], [3, 3]],
    [[5], [1, 2, 4], [2, 1, 3], [2, 2, 1, 1], [1, 1, 1, 1], [1, 5], [2, 1, 1, 3, 2], [2, 1, 1, 1, 1], [1, 4, 1], [1, 1], [1]]).
data(difficult,
    [[3], [1, 1], [1, 1], [1, 1], [1, 2], [5], [1], [2], [1], [1], [1, 2], [1, 2], [2, 1], [2, 2], [3]],
    [[3], [2], [2], [1], [2], [3], [2], [4], [3], [4], [2, 1], [1, 1], [1, 1], [1, 1], [3]]).
data(bigbunny,
     [[1,1],[1,2],[1,2],[3],[3,7],[16],[2,6,5],[12,5],[18],[16],
      [2,10],[13],[11],[2,2,3],[2,2,4]],
     [[2],[4],[2,2],[9],[7,1],[2,6,2],[2,9],[2,6,2,1],[6,4],[2,3,3],
      [2,6],[2,6,1],[2,5,1],[3,7],[10],[9],[8],[6],[5],[2]]).
data(dragonfly,
    [[7, 1], [1, 1, 2], [2, 1, 2], [1, 2, 2], [4, 2, 3], [3, 1, 4], [3, 1, 3], [2, 1, 4], [2, 9], [2, 1, 5], [2, 7], [14], [8, 2], [6, 2, 2], [2, 8, 1, 3], [1, 5, 5, 2], [1, 3, 2, 4, 1], [3, 1, 2, 4, 1], [1, 1, 3, 1, 3], [2, 1, 1, 2]],
    [[1, 1, 1, 2], [3, 1, 2, 1, 1], [1, 4, 2, 1, 1], [1, 3, 2, 4], [1, 4, 6, 1], [1, 11, 1], [5, 1, 6, 2], [14], [7, 2], [7, 2], [6, 1, 1], [9, 2], [3, 1, 1, 1], [3, 1, 3], [2, 1, 3], [2, 1, 5], [3, 2, 2], [3, 3, 2], [2, 3, 2], [2, 6]]).
data(p56,
     [[6],[1,11],[4,5],[11],[11],[3,8],[3,6],[3,5,3],[3,3,8],[6,4,3],
      [5,3,3],[2,2,3],[1,2,1],[4,1],[4,1],[9],[3,6,1],[4,1,3],[7],[8],
      [8],[2,2],[2,2],[3,3],[3,3]],
     [[8],[1,8],[9],[3,2],[10],[9],[2,6,2],[2,5,8],[2,5,10],[2,4,4,8,2],
      [2,3,13],[6,4,4,7],[3,3,1,4,7],[2,2,3,6,2],[2,4,1,2],
      [1,3,3],[2,2],[2],[1],[2]]).
data(p99,
     [[6], [8], [10], [12], [7,6],
      [6,3,2], [7,2,2,3], [3,2,1,1,6], [3,1,1,6], [2,5],
      [2,3], [1,3,1], [20], [1,1], [2,3,2],
      [2,3,2], [2,2,2], [3,1,3], [3,3], [6],
      [7,1,1,12], [5,2,2,10], [3,6,3,8], [2,3,3,7], [2,14,7]],
     [[3,5], [5,2,5], [5,1,2,3], [5,1,1,2,2,2], [5,1,2,1,2,2],
      [5,1,2,2,1,3], [7,1,2,1,1,1,1], [9,1,1,2,2,1], [7,1,1,4,1], [5,1,1,1,1],
      [4,1,1,1,1], [7,1,3,1], [9,2,2,2,1], [5,2,1,1,1,1], [3,3,2,1,3],
      [3,2,1,1,2,2], [3,2,1,2,2,2], [4,1,2,3], [2,2,2,5], [3,3,5],
      [2,5], [2,5], [3,5], [2,5], [2,5]]).
data(p200,
     [[2,2,3], [4,1,1,1,4], [4,1,2,1,1], [4,1,1,1,1,1,1], [2,1,1,2,3,5], [1,1,1,1,2,1], [3,1,5,1,2], [3,2,2,1,2,2], [2,1,4,1,1,1,1], [2,2,1,2,1,2], [1,1,1,3,2,3], [1,1,2,7,3], [1,2,2,1,5], [3,2,2,1,2], [3,2,1,2], [5,1,2], [2,2,1,2], [4,2,1,2], [6,2,3,2], [7,4,3,2], [7,4,4], [7,1,4], [6,1,4], [4,2,2], [2,1]],
     [[1,1,2,2], [5,5,7], [5,2,2,9], [3,2,3,9], [1,1,3,2,7], [3,1,5], [7,1,1,1,3], [1,2,1,1,2,1], [4,2,4], [1,2,2,2], [4,6,2], [1,2,2,1], [3,3,2,1], [4,1,15], [1,1,1,3,1,1], [2,1,1,2,2,3], [1,4,4,1], [1,4,3,2], [1,1,2,2], [7,2,3,1,1], [2,1,1,1,5], [1,2,5], [1,1,1,3], [4,2,1], [3]]).
data(kabuki,
     [[5,2,2],[5,7,3,3,2],[10,4,2,1,1],[12,3,1,2,2],[16,12],[16],[4,9,12],[2,1,1,7,2],[1,1,1,5,11],[1,1,1,4,1,1,1,1,1,1],[1,2,2,4,1,1,1,1,1,1],[2,1,1,3,3,1,1,1,1,1,1],[4,1,1,3,1,3,1,1,1,1,1,1],[1,3,3,2,1,1,1,1,1],[3,2,2,4,1,1,4,1,1],[1,3,3,1,1,1,8,1],[2,1,1,1,1,1,1,1,11],[1,4,4,2,13],[1,1,2,4,1,7],[1,1,1,1,1,2,3,1,8],[2,1,1,1,2,2,3,1,7],[2,5,2,1,2,2,1,8],[2,1,1,2,13],[3,4,3,2,13],[6,2,2,1,2,13],[9,2,1,2,13],[8,1,2,6,1,2,1],[11,2,2,1,2,5,1,3,1],[8,13,3,6,1,2,1],[3,2,8,5,3,5,1,3,1],[2,1,6,3,3,3,11,2],[1,1,3,3,3,2,3,11,2],[1,2,5,3,3,15],[1,8,3,3,8,1],[1,10,1,3,12],[1,1,7,3,2,1,3],[1,4,1,3,2,2,1,8],[5,1,4,2,3,1,3],[3,1,2,2,3,1,8],[8,1,3,2,11]],
     [[9],[4],[4],[4,1],[7,1],[6,1,1],[6,2,1],[10,7,2,2,1,1],[3,2,1,1,9,3,2,1,1],[3,1,1,1,2,7,2,2,1],[3,2,3,1,1,4,3,4],[8,3,1,2,13],[4,8,3,2,9,1],[4,1,1,3,5,1,1],[5,1,1,4,5,1],[5,8,2,2,4,3,1,1],[10,3,1,1,2,1,3,6],[6,2,3,1,2,3,5],[6,1,1,1,1,4,3,2],[6,2,1,1,2,5,1,2],[7,1,3,1,3,1,4,6],[9,4,2,3,2,6],[2,8,4,1,6,2],[3,16,6,4],[13,15,6],[5,10,10,4,1,1],[3,3,5,1,2],[20,1,1],[2,2,20,1,2],[1,1,7,4,1,18],[2,1,1,1,4,1,19],[1,2,1,5,5,1,18],[2,2,1,1,4,1,6,1,5,1,2],[1,1,1,1,5,12,1,4,1,1,1],[1,1,1,1,12,1,3,1,1,1],[1,1,1,6,11,1,4,1,1,1],[1,1,1,1,17],[1,1,1,1,7,14,1],[2,2,1,1,9,3],[1,2,1,8,16]]).
data(sheepdog,
     [[3,4], [3,5], [4,5], [4,6], [5,7], [2,3,8], [2,3,8], [2,3,3,3], [2,4,4,4], [3,10,4], [1,12,3], [14,4], [17,4], [18,4], [26], [26], [28], [28], [1,8,16], [1,7,2,14], [9,4,13], [9,2,15], [11,17], [33], [34], [37], [38], [1,36], [39], [16,18], [14,3,19], [11,4,2,17], [6,4,2,18], [6,3,3,5,7], [5,2,3,1,7], [4,3,4,6], [7,4,6], [1,5,5,7], [2,4,6,7], [3,4,6,7], [3,4,5,8], [4,4,5,8], [4,3,6,8], [6,2,6,9], [8,8,9], [19,10], [21,11], [40], [41], [40], [41], [42], [43], [42], [43], [43], [43], [44], [45], [46], [46], [47], [47], [47], [48], [26,22], [27,17,2], [28,17,2], [29,15,2], [30,15,2], [18,12,14,2], [19,7,2,13,2], [20,5,2,12,3], [21,4,1,11,2], [21,4,1,10,1,2], [22,3,1,8,1,3], [23,3,1,7,1,3], [23,3,1,6,1,3], [24,2,1,4,1,3], [25,3,1,3,1,3], [18,4,2,1,1,1,3], [18,4,2,3,1,4], [18,4,2,3,1,4], [17,5,1,3,1,4], [17,5,1,3,1,5], [17,5,2,3,1,5], [16,6,1,4,1,5], [15,6,2,4,1,6], [15,7,1,4,1,6], [14,9,1,4,1,6], [12,9,1,4,1,6], [11,9,1,5,3,1,6], [5,3,10,1,5,5,1,6], [2,8,1,9,2,10,1,6], [2,15,1,5,1,5,4,1,6], [2,26,2,1,5,4,1,6], [1,32,1,5,1,2,1,6], [1,31,1,5,2,2,5], [1,29,1,6,1,1,5], [1,23,1,4,2,2,6], [2,14,2,3,1,1,4], [2,9,1,4,2,6], [3,1,5,1,4,2], [1,5,1,8,1,3,1], [3,11,1,10,2,1,1], [7,24,2,2,2,2,1,2,3], [17,2,3,2,1,2], [39,2,1,1,1,9], [39,3,1,1,3,2,2], [40,9,15]],
     [[6,7], [2,2,6], [2,2,6], [2,1,5], [1,2,2,5], [15,1,5], [19,1,5], [22,1,4], [19,5,2,4], [21,6,1,4], [22,6,1,4], [23,6,1,4], [24,6,1,4], [26,5,1,4], [27,5,1,4], [28,6,1,4], [27,6,1,4], [27,6,1,3], [28,6,2,3], [28,5,1,3], [27,5,1,3], [27,5,1,3], [25,5,1,3], [25,5,1,3], [24,7,1,3], [26,1,6,1,3], [28,1,6,1,3], [29,5,6,1,3], [20,9,6,6,1,3], [24,19,6,1,3], [2,29,17,6,1,3], [1,3,34,15,6,1,3], [2,4,37,14,6,1,3], [7,40,12,6,1,3], [9,34,4,9,6,1,3], [10,34,5,5,7,1,3], [10,34,3,7,1,3], [11,28,7,4,1,3], [17,7,27,4,1,1,3], [4,13,10,28,4,1,1], [19,11,37,2,8], [20,9,21,18,4], [11,20,5,57,1], [10,20,3,1,42,18,3,2], [5,1,20,2,2,42,20,1], [5,1,20,3,1,42,12,1], [5,20,2,2,41,2,8,2], [14,7,2,2,42,6,5,1], [11,3,6,2,1,5,33,5,2,3,1], [9,3,6,1,2,3,31,9,3,2], [10,1,7,2,3,29,6,3,1], [10,1,10,3,28,1,3], [11,10,3,27,2,1], [26,26,24,4], [29,25,3,1], [33,24,9,3,4], [34,23,13,4,2], [7,22,21,17,3,1], [7,21,21,19,2,1], [9,20,20,23,1,1], [31,21,26,1,1,1], [28,23,11,5,2,1,1], [25,38,5,1,1], [24,36,2,1,1,1], [49,2,3,1], [46,1,1,1], [39,1,2,1], [33,2,3,1], [28,1,1,2], [19,3,2]]).
