% % ECLiPSe Nonogram Solver % using lib(gfd) interface to Gecode solver. % % Joachim Schimpf, Coninfer Ltd % % Problem: % % Nonograms are a popular puzzle, which goes by different names in % different countries. The player has to shade in squares in a grid so % that blocks of consecutive shaded squares satisfy constraints given % for each row and column. Constraints typically indicate the sequence % of shaded blocks (e.g. [3,1,2] means that there is a block of 3, then % a gap of unspecified size, a block of length 1, another gap, and then % a block of length 2). Data for sample problems is at the end of this file, % % Example run: % % ?- go(n4). % * * * % * % * * % * * % * % * * * % Yes (0.01s cpu, solution 1, maybe more) % No (0.01s cpu) % :- lib(gfd). go(Name) :- data(Name, M, N, RowBlocks, ColBlocks, Blacks), dim(Board, [M,N]), Board #:: 0..1, ( foreach([I,J],Blacks), param(Board) do Board[I,J] #= 1 ), ( for(I,1,M), foreach(RB,RowBlocks), param(Board,N) do sequence_of_blocks(RB, Board[I,1..N]) ), ( for(I,1,N), foreach(CB,ColBlocks), param(Board,M) do sequence_of_blocks(CB, Board[1..M,I]) ), search(Board, 0, input_order, indomain_max, complete, []), pretty_print(Board). % Pretty print the board pretty_print(Board) :- dim(Board, [M,N]), ( for(I,1,M), param(Board,N) do ( for(J,1,N), param(Board,I) do X is Board[I,J], ( X==0 -> write(" ") ; X==1 -> write("*") ; write(" ?") ) ), nl ), nl. % Translate to a regular expression and impose a regular/2 constraint sequence_of_blocks([N1|Ns], Collection) :- collection_to_list(Collection, Vars), RE = *(0) + (1,{N1,N1}) + RE1, ( foreach(N,Ns), fromto(RE1, +(0)+(1,{N,N})+RE3, RE3, *(0)) do true ), regular(Vars, RE). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %---------------------------------------------------------------------- % sample problems % % data(ProblemName, NRows, NColumns, RowBlocks, ColumnBlocks, BlackFields) %---------------------------------------------------------------------- % from http://www-lp.doc.ic.ac.uk/UserPages/staff/ft/alp/humour/visual/nono.html data(ps, 9, 8, [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]], % row blocks [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]], % column blocks [] % given black coordinates ). % from http://www.pro.or.jp/~fuji/java/puzzle/nonogram/index-eng.html data(n2, 10, 10, [[1],[3],[1,3],[2,4],[1,2],[2,1,1],[1,1,1,1],[2,1,1],[2,2],[5]], [[4],[1,3],[2,3],[1,2],[2,2],[1,1,1],[1,1,1,1],[1,1,1],[1,2],[5]], [] ). data(n3, 10, 15, [[4],[1,1,6],[1,1,6],[1,1,6],[4,9],[1,1],[1,1],[2,7,2],[1,1,1,1],[2,2]], [[4],[1,2],[1,1],[5,1],[1,2],[1,1],[5,1],[1,1],[4,1],[4,1],[4,2],[4,1],[4,1],[4,2],[4]], [] ). data(n4, 6, 6, [[2,1],[1],[2],[2],[1],[1,2]], [[1,2],[1],[2],[2],[1],[2,1]], [] ). data(n5, 10, 10, [[3],[3],[1],[3],[6],[3],[3],[3,3],[2,2],[2,1]], [[1],[1,2],[1,2],[1,1],[2,5],[7],[2,5],[1],[2],[2]], [] ). data(n6, 15, 15, [[5],[2,2],[1,1],[1,1],[4,4],[2,2,1,2],[1,3,1],[1,1,1,1],[2,7,2],[4,1,5],[2,1,1],[1,1,2],[1,1,1],[2,5,2],[3,4]], [[4],[2,2],[1,5],[1,2,2],[5,2,1],[2,1,1,2],[1,3,1],[1,1,6],[1,3,1],[2,1,2,2],[4,2,1],[1,1,1],[1,3,2],[2,2,3],[4]], [] ). data(n16, 15, 15, [[4],[2,2],[2,2],[2,4,2],[2,1,1,2],[2,4,2],[1,2],[4,4,4],[1,1,1,1,1,1],[4,1,1,4],[1,1,1],[1,1,3],[10],[2,1],[4,1]], [[5,1],[2,1,1,1],[2,1,1,2],[2,3,3],[2,1],[2,3,6],[1,1,1,1,1],[1,1,1,1,1],[2,3,6],[2,1],[2,3,1],[2,1,1,1],[2,1,1,4],[7],[1,1]], [] ). data(n19, R, C, RB, CB, Bs) :- data(p199, R, C, RB, CB, Bs). % from http://www.puzzle.gr.jp/nonogram/prob/0200_e.html data(p197, 20, 15, % difficulty 7 [[3],[1,2],[1,4],[1,1,2],[1,1,1,1],[1,3,2],[2,3,1],[1,1,1,2],[2,2,2],[1,1,2,2],[1,1,2,2],[1,1,1,1],[4,1,1],[2,2,2,1],[2,3,3],[2,2,3],[1,3,1,1],[2,1,1,1,2],[1,2,3],[1,6]], [[4,3],[6,1,2,3],[2,3],[6],[1,2,2],[1,1,2],[2,4,1,1],[1,1,2,2,2,1],[1,1,1,2,1,1],[1,3,2,3],[3,2,2],[4,3,4,2],[1,3,4,5],[2,2],[3]], [] ). data(p199, 20, 20, % difficulty 8 [[1,1,4],[1,6],[1,1,1,1,2,3],[1,1,2,3],[3,1,2,3],[4,5,2,2],[7,3,2],[3,5,1,2],[2,2,4,1],[2,2,3,4],[2,5,2],[2,1,5,1],[2,2,3,1],[6,2,2],[1,7],[2,2,2],[1,4],[3,1,1],[1,1],[1,1]], [[6,1],[8,3],[3,2,1],[1,1,2,2,1],[1,2,2,1,1],[1,1,1,1],[2,3],[4,1,2,2],[5,2,1],[8,1,1],[7,2],[3,5,2],[2,5],[2,1,4],[2,2,2,2],[2,2,1,1,1],[3,1,1,1,1],[5,4,2,1],[7,4,1,1],[4]], [] ). data(p200, 25, 25, % difficulty 9 [[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]], [[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]], [] ). % the example quoted in Optima#65, Mathematical Programming Society Newsletter data(optima, 20, 20, [[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(cast, 60, 35, [[2,3,1,5,1,7,1], [2,4,2,3,2,3,5], [2,6,3,1,1,5,1,5], [2,4,2,1,1,1,4,1,1,2], [2,8,2,1,5,2,5], [3,1,6,2,5,1,5], [3,3,3,1,1,6,1,1,1], [3,2,2,2,2,8,1,1,3], [1,4,4,3,7,1,1], [1,2,2,2,3,7,9], [1,2,3,1,1,5,2,2], [2,2,3,1,1,6,1], [1,3,1,5,4,1], [1,3,1,1,6,1,3,1], [3,3,4,5,1,4,2,1], [2,3,3,9,7,1], [2,3,2,2,1,1,3,5], [4,2,1,1,1,1,2,3], [4,2,2,1,4,3,2], [4,3,16,2], [1,2,5,7,1], [4,3,2,2,7,1], [2,3,1,10,1], [2,4,2,1,4,1], [1,6,7,3,1], [3,11,3,1], [7,1,11,2,1], [2,2,2,2,2,2,2], [3,1,1,1,1,2,1], [2,2,2,2,1,1,1], [1,1,1,1,2,1,2], [2,2,2,2,1,1,1,1], [4,1,1,2,2], [5,2,17,2,1], [9,2,3,1,4,2], [9,4,2,1,1,1], [5,4,2,1,4], [11,1,2,1,4,1,2], [3,4,2,4,4], [2,1,4,1,2,1,5,2], [8,4,1,1,2], [1,1,3,2,3], [1,3,1,8,1,6], [2,1,7,14], [1,2,4,4,1,2,3], [1,1,4,2,1,1,1,1,1,4], [3,5,3,1,1,4], [2,4,2,2,1,2], [4,2,3,8,4], [4,15,2,2,4], [4,1,10,2,1,2], [2,12,6,1,2,4], [3,1,3,1,3,3,4], [3,1,2,3,4,1], [5,2,2,2,3,3,3], [1,2,2,2,2,4,1,1,3], [2,1,4,2,7,1,1], [5,2,2,3,6,3], [3,3,2,2,3,2,3], [4,1,2,1,1,2,1]], [[12,1,1,1], [8,6,3,1,3], [5,8,4,3,1,5], [7,3,4,1,3,5,1,7], [2,2,4,9,1,5,1,1,1,1,1,1,1], [4,5,10,2,1,8,7,1], [5,1,3,3,16,1,2], [8,5,1,2,4,9,1,3], [4,5,3,14,1,1,1,1,4,1,1,3], [3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2], [8,2,7,2,1,1,2,1,1,3,3], [1,5,9,12,2,1,1,3,1,1,2,2,1], [3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2], [5,2,2,2,2,1,5,2,1,1,2,5], [3,5,9,2,1,1,6,3,1,3,2,3], [1,4,1,1,1,4,1,5,5,3,3,3], [4,1,1,1,1,3,4,6,6,3], [3,1,3,1,1,3,3,1,1,4,6,1], [3,1,5,1,1,3,1,1,9,4,1], [2,1,1,7,1,4,1,1,1,1,1,1,3,5], [9,2,1,3,1,1,1,1,4,2,1], [1,14,1,1,2,2,2,10,1,2], [1,9,2,1,2,6,1,5,3,2], [1,9,9,1,2,2,3,1,1,4,3,1], [10,1,3,4,1,3,2,1,2,8], [9,1,3,5,1,1,1,2,7], [4,5,1,2,5,1,3,1,1,2,1,3], [1,1,1,1,2,6,2,3,2,1,1,2,3,1], [1,6,1,5,7,1,3,3,2,4,3], [1,2,1,2,9,1,5,2,6,2], [10,2,2,13,1,3,3,1], [2,2,1,6,2,3,3,2,2,2,1], [2,2,1,1,12,2,2,9,2,2,2,2], [5,1,2,4,1,5,11,2,2], [15,6,18]], [] ). % from http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx data(gchq, 25, 25, [ [7,3,1,1,7], [1,1,2,2,1,1], [1,3,1,3,1,1,3,1], [1,3,1,1,6,1,3,1], [1,3,1,5,2,1,3,1], [1,1,2,1,1], [7,1,1,1,1,1,7], [3,3], [1,2,3,1,1,3,1,1,2], [1,1,3,2,1,1], [4,1,4,2,1,2], [1,1,1,1,1,4,1,3], [2,1,1,1,2,5], [3,2,2,6,3,1], [1,9,1,1,2,1], [2,1,2,2,3,1], [3,1,1,1,1,5,1], [1,2,2,5], [7,1,2,1,1,1,3], [1,1,2,1,2,2,1], [1,3,1,4,5,1], [1,3,1,3,10,2], [1,3,1,1,6,6], [1,1,2,1,1,2], [7,2,1,2,5] ], [ [7,2,1,1,7], [1,1,2,2,1,1], [1,3,1,3,1,3,1,3,1], [1,3,1,1,5,1,3,1], [1,3,1,1,4,1,3,1], [1,1,1,2,1,1], [7,1,1,1,1,1,7], [1,1,3], [2,1,2,1,8,2,1], [2,2,1,2,1,1,1,2], [1,7,3,2,1], [1,2,3,1,1,1,1,1], [4,1,1,2,6], [3,3,1,1,1,3,1], [1,2,5,2,2], [2,2,1,1,1,1,1,2,1], [1,3,3,2,1,8,1], [6,2,1], [7,1,4,1,1,3], [1,1,1,1,4], [1,3,1,3,7,1], [1,3,1,1,1,2,1,1,4], [1,3,1,4,3,3], [1,1,2,2,2,6,1], [7,1,3,2,1,1] ], [ [4,4],[4,5], [4,13],[4,14],[4,22], [9,7],[9,8],[9,11],[9,15],[9,16],[9,19], [17,7],[17,12],[17,17],[17,21], [22,4],[22,5],[22,10],[22,11],[22,16],[22,21],[22,22] ]). % simple check for typos in the data check_data(M, N, RowBlocks, ColBlocks) :- length(RowBlocks, M), length(ColBlocks, N), ( foreach(Blocks,RowBlocks), fromto(0,S0,S1,RowTotal) do S1 is S0+sum(Blocks) ), ( foreach(Blocks,ColBlocks), fromto(0,S0,S1,ColTotal) do S1 is S0+sum(Blocks) ), RowTotal = ColTotal, !. check_data(_,_,_,_) :- writeln("Inconsistent input data!"), abort.