Wednesday, November 19, 2014

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).

0hh1

Here's a solver for the puzzles at 0hh1.com.

% USAGE: clingo -n 0 <thisfile.txt # show all solutions to puzzle
%
% Download from: http://sourceforge.net/projects/potassco/files/clingo/3.0.5/

% Two colors: 1 = red, 2 = blue.  (0 = empty)
color(1). color(2).

#const size = 6.
% coord(Y,X) = Y,X is a valid coordinate of a cell in the puzzle.
coord(0..size-1,0..size-1).

% p(Y,X,C) = cell [Y,X] is color C in the original puzzle.
%- X X - - -
%O - - - - -
%- - - - - -
%- - - - O -
%- - - - - O
%- X - - - -

color(1). color(2).

#const size = 6.
% coord(Y,X) = Y,X is a valid coordinate of a cell in the puzzle.
coord(0..size-1,0..size-1).

% p(Y,X,C) = cell [Y,X] is color C in the original puzzle.
%- X X - - -
%O - - - - -
%- - - - - -
%- - - - O -
%- - - - - O
%- X - - - -

p(0,0,2).  p(0,1,1).  p(0,2,0).  p(0,3,0).  p(0,4,1).  p(0,5,2).
p(1,0,1).  p(1,1,0).  p(1,2,0).  p(1,3,2).  p(1,4,0).  p(1,5,0).
p(2,0,0).  p(2,1,2).  p(2,2,1).  p(2,3,1).  p(2,4,2).  p(2,5,0).
p(3,0,0).  p(3,1,0).  p(3,2,2).  p(3,3,0).  p(3,4,0).  p(3,5,0).
p(4,0,1).  p(4,1,0).  p(4,2,2).  p(4,3,1).  p(4,4,2).  p(4,5,0).
p(5,0,1).  p(5,1,2).  p(5,2,0).  p(5,3,0).  p(5,4,2).  p(5,5,0).

% q(Y,X,C) = cell[Y,X] is color C in the solved puzzle.

% The colors in the original puzzle must not change in the solution.
q(Y,X,C) :- p(Y,X,C); C != 0.

% Each empty square in the original puzzle must be colored red or blue in the solution.
1 { q(Y,X,C) : color(C) } 1 :- p(Y,X,0).

% f(Y,X) = cell(Y,X) is filled with some color.
f(Y,X) :- q(Y,X,C); C != 0.

% Solution cannot have empty squares.
:- coord(Y,X); not f(Y,X).

% Solution cannot have three adjacent cells of the same color horizontally.
:- q(Y,X,C); q(Y,X+1,C); q(Y,X+2,C).

% Solution cannot have three adjacent cells of the same color vertically.
:- q(Y,X,C); q(Y+1,X,C); q(Y+2,X,C).

% Exactly half of the cells in every row in the solution must be red.
:-  coord(Y,_); {coord(Y,X) : q(Y,X,2) } != size/2.

% Exactly half of the cells in every column in the solution must be red.
:- coord(_,X); {coord(Y,X) : q(Y,X,1) } != size/2.

% diffrow(Y1, Y2) = rows Y1 and Y2 differ.
diffrow(Y1, Y2) :- q(Y1,X,C1); q(Y2,X,C2); C1 != C2; coord(Y1,_); coord(Y2,_); Y1 < Y2.

% diffcol(X1, X2) = columns X1 and X2 differ.
diffcol(X1, X2) :- q(Y,X1,C1); q(Y,X2,C2); C1 != C2; coord(_,X1); coord(_,X2); X1 < X2.

% Solution cannot have duplicate rows.
:- coord(Y1,_); coord(Y2,_); Y1 < Y2; not diffrow(Y1, Y2).

% Solution cannot have duplicate columns.
:- coord(_,X1); coord(_,X2); X1 < X2; not diffcol(X1, X2).

Followers

Contributors