Ripple Effect

Here's a solver for Nikoli's Ripple Effect puzzle.

% Usage: clingo < rippleffect.lp
%
% Download clingo 4 from http://sourceforge.net/projects/potassco/files/clingo/

% The example puzzle used is from http://en.wikipedia.org/w/index.php?title=Ripple_Effect_(puzzle)&oldid=598393777

% +---+---+---+---+---+---+---+---+---+
% |       |       |                 2 |
% +   +---+---+   +---+---+---+---+   +
% |   |   |   |       |   |       |   |
% +   +   +---+---+   +   +   +   +---+
% |   |           |   |   |           |
% +---+---+---+   +---+---+---+   +---+
% |           |   |           |   |   |
% +---+---+---+---+   +   +---+---+---+
% |   |   |       | 5     |   |       |
% +---+   +   +   +---+---+   +   +   +
% |   |   |       |           |       |
% +   +---+---+---+---+---+---+   +---+
% |       |       |       |       |   |
% +---+---+---+---+   +   +---+---+   +
% |               |       |   |       |
% +---+---+---+---+---+---+   +   +   +
% | 4             |           |       |
% +---+---+---+---+---+---+---+---+---+

%%% inputs

#const size = 9.

% n(S,N) = square S has number N. (0 for blank)

n(11,0). n(12,0). n(13,0). n(14,0). n(15,0). n(16,0). n(17,0). n(18,0). n(19,2).
n(21,0). n(22,0). n(23,0). n(24,0). n(25,0). n(26,0). n(27,0). n(28,0). n(29,0).
n(31,0). n(32,0). n(33,0). n(34,0). n(35,0). n(36,0). n(37,0). n(38,0). n(39,0).
n(41,0). n(42,0). n(43,0). n(44,0). n(45,0). n(46,0). n(47,0). n(48,0). n(49,0).
n(51,0). n(52,0). n(53,0). n(54,0). n(55,5). n(56,0). n(57,0). n(58,0). n(59,0).
n(61,0). n(62,0). n(63,0). n(64,0). n(65,0). n(66,0). n(67,0). n(68,0). n(69,0).
n(71,0). n(72,0). n(73,0). n(74,0). n(75,0). n(76,0). n(77,0). n(78,0). n(79,0).
n(81,0). n(82,0). n(83,0). n(84,0). n(85,0). n(86,0). n(87,0). n(88,0). n(89,0).
n(91,4). n(92,0). n(93,0). n(94,0). n(95,0). n(96,0). n(97,0). n(98,0). n(99,0).

% r(S,R) = square S is in region R. Region symbols are arbitrary.

r(11,a). r(12,a). r(13,b). r(14,b). r(15,c). r(16,c). r(17,c). r(18,c). r(19,c).
r(21,a). r(22,d). r(23,e). r(24,b). r(25,b). r(26,f). r(27,g). r(28,g). r(29,c).
r(31,a). r(32,d). r(33,d). r(34,d). r(35,b). r(36,f). r(37,g). r(38,g). r(39,g).
r(41,h). r(42,h). r(43,h). r(44,d). r(45,i). r(46,i). r(47,i). r(48,g). r(49,j).
r(51,k). r(52,m). r(53,n). r(54,n). r(55,i). r(56,i). r(57,o). r(58,p). r(59,p).
r(61,q). r(62,m). r(63,n). r(64,n). r(65,o). r(66,o). r(67,o). r(68,p). r(69,p).
r(71,q). r(72,q). r(73,r). r(74,r). r(75,s). r(76,s). r(77,p). r(78,p). r(79,t).
r(81,v). r(82,v). r(83,v). r(84,v). r(85,s). r(86,s). r(87,u). r(88,t). r(89,t).
r(91,w). r(92,w). r(93,w). r(94,w). r(95,u). r(96,u). r(97,u). r(98,t). r(99,t).

%%% Solver

% sz(S,C) = the count of the number of squares in the region enclosing square S is C.
sz(S,C) :- C = #count { T : r(T, R) }, r(S,R).

% row(R) = R is a row index (1..size)
row(1..size).

% col(C) = C is a column index (1..size)
col(1..size).

% sq(Y,X,S) - the square at (Y,X) is S. Example: the square at (3,2) is 32.
sq(Y,X,10*Y+X) :- row(Y), col(X).

% nbetween(A,B,N) = A & B are in the same row or column, with N squares in between them.
nbetween(A,B,X2-X1-1) :- row(Y), col(X1), col(X2), X1 < X2, sq(Y,X1,A), sq(Y,X2,B).
nbetween(A,B,Y2-Y1-1) :- col(X), row(Y1), row(Y2), Y1 < Y2, sq(Y1,X,A), sq(Y2,X,B).

% m(S,N) :- in the solution, square S contains the number N.
m(S,N) :- n(S,N), N != 0.

% chose one value for each initially-empty square that does not exceed the size of its region.
1 { m(S,N) : N = 1..C } 1 :- n(S,0), sz(S,C).

% no duplicate values in the same region.
:- m(S1,N), m(S2,N), r(S1,R), r(S2,R), S1 < S2.

% Whenever the number N occurs twice in the same row or column, there must be at least N squares
% between those two occurrences
:- m(S1,N), m(S2,N), nbetween(S1,S2,M), M < N.

#show m/2.

---

And here's an encoding for the neat puzzle with no numeric clues at http://puzzleparasite.blogspot.com/2011/12/puzzle-71-ripple-effect.html:

% size of board
#const size = 8.

% n(S,N) = square S has number N. (0 for blank)

n(11,0). n(12,0). n(13,0). n(14,0). n(15,0). n(16,0). n(17,0). n(18,0).
n(21,0). n(22,0). n(23,0). n(24,0). n(25,0). n(26,0). n(27,0). n(28,0).
n(31,0). n(32,0). n(33,0). n(34,0). n(35,0). n(36,0). n(37,0). n(38,0).
n(41,0). n(42,0). n(43,0). n(44,0). n(45,0). n(46,0). n(47,0). n(48,0).
n(51,0). n(52,0). n(53,0). n(54,0). n(55,0). n(56,0). n(57,0). n(58,0).
n(61,0). n(62,0). n(63,0). n(64,0). n(65,0). n(66,0). n(67,0). n(68,0).
n(71,0). n(72,0). n(73,0). n(74,0). n(75,0). n(76,0). n(77,0). n(78,0).
n(81,0). n(82,0). n(83,0). n(84,0). n(85,0). n(86,0). n(87,0). n(88,0).

% r(S,R) = square S is in region R. Region symbols are arbitrary.

r(11,a). r(12,a). r(13,b). r(14,c). r(15,c). r(16,c). r(17,d). r(18,d).
r(21,a). r(22,b). r(23,b). r(24,e). r(25,f). r(26,c). r(27,d). r(28,d).
r(31,b). r(32,b). r(33,e). r(34,e). r(35,f). r(36,g). r(37,h). r(38,h).
r(41,i). r(42,i). r(43,e). r(44,k). r(45,k). r(46,g). r(47,g). r(48,j).
r(51,m). r(52,n). r(53,n). r(54,k). r(55,k). r(56,o). r(57,g). r(58,j).
r(61,m). r(62,p). r(63,q). r(64,q). r(65,o). r(66,o). r(67,j). r(68,j).
r(71,m). r(72,p). r(73,p). r(74,q). r(75,o). r(76,r). r(77,s). r(78,j).
r(81,m). r(82,m). r(83,p). r(84,p). r(85,r). r(86,r). r(87,r). r(88,r).