Surfing on ... the Ripple Effect

Yves Papegay - October 15, 2006

Instructions and Examples

Material in this section is extracted from an article in The Mathematica Journal, volume 10, issue 2, “Beyond Sudoku: Ripple Effect,” by Ed Pegg Jr.

Instructions

In Ripple Effect puzzles, a grid is divided into polyomino-shaped rooms.

Each room contains consecutive numbers starting from 1. Thus, a domino will always have 1 and 2. A triomino will always have 1, 2, and 3, and so on.

If a number is duplicated in a row or a column, the space between the duplicated numbers must be equal to or larger than the value of the number. Thus, there will always be at least one digit between 1s, at least two digits between 2s, and so on.

Solving Example

Here is a solved example puzzle. The first grid is the puzzle itself. In the second, some preliminary logic has been done. To start, all single squares need a 1. Ones cannot be adjacent, which forces a few more placements. The square marked “9” cannot be a 2, since the domino above it could not be filled. With further logic, the entire puzzle is solved.

$TextStyle={FontFamily->"Helvetica",FontSize->12};

{RippleEffectPuz01,RippleEffectPuz01a,RippleEffectPuz01b}//View

Puzzles

Puzzles sources

Please note the use of the inert Puzzle head used in the representation of puzzles. This will help in making the solver code easier to read.

RippleEffectPuz01=Puzzle[{7,7},{4454,8518,10370,5281,1711,1039,10277},{0,0,6000,4000,1000,0,0}];

RippleEffectPuz01a=Puzzle[{7,7},{4454,8518,10370,5281,1711,1039,10277},{1200121,2100010,1306100,4001,1000,0,9000121}];

RippleEffectPuz01b=Puzzle[{7,7},{4454,8518,10370,5281,1711,1039,10277},{1213121,2142312,1326143,3214521,1431214,2152432,1213121}];

RippleEffectPuz02=Puzzle[{7,7},{9569,8489,8736,8544,5361,9268,10992},{0,0,3,0,3000000,0,0}];

RippleEffectPuz03=Puzzle[{7,7},{1105,5153,8291,11107,11055,775,981},{0,10,0,1000,0,100000,0}];

RippleEffectPuz04=Puzzle[{10,10},{332800,435607,984244,269044,670208,438746,327930,615680,27801,305173},{0,0,4000003,0,5000,2,500100000,0,0,50000000}];

RippleEffectPuz05=Puzzle[{10,10},{5384,177960,342948,592661,664832,142117,23141,547917,656394,329066},{0,0,0,0,0,0,0,0,0,0}];

RippleEffectPuz06=Puzzle[{10,10},{589994,666178,610565,32842,102747,742507,774167,525443,611999,3606},{0,0,0,0,0,0,0,0,0,0}];

RippleEffectPuz07=Puzzle[{17,17},{5727850576,11335128144,8651428956,2511352415,384843266,441456262,374822582,5907107862,2688544789,269963280,374822588,10105820847,1526366396,721065200,353359509,11125387926,11386421910},{1000007010000010,30000100000300003,20009210001000,205000000060500,40020001003000,6000000000000070,3000000050000,10100000000000402,00200000000000200,50300000000000503,3000000040000,4000000000000030,20030004006000,601000000030200,50004820002000,10000300000100001,4000005040000010}];

Warm-up puzzles

{RippleEffectPuz02,RippleEffectPuz03}//View

Intermediate

{RippleEffectPuz04,RippleEffectPuz05,RippleEffectPuz06}//View

Challenge

RippleEffectPuz07//View

Solver Code

To illustrate the functions defined in this section, the following example is extensively used.

RippleEffectPuz01

In such a puzzle representation, the first list contains the number of lines and the number of columns, the second is an encoding of the polyomino-shape of the rooms, and the last an encoding of the values already affected to cells.

Visualization

Code from Ed Pegg Jr article

This code is decoding the puzzle representation and computing the corresponding graphics objects.

Riplines[Puzzle[s_,b_,v_]] := {GrayLevel[.8],
Table[Line[{{n,0},{n,s[[2]]}}],{n,1,s[[1]]}],
Table[Line[{{0,m},{s[[1]],m}}],{m,1,s[[2]]}],GrayLevel[0],
DeleteCases[{With[{A = Reverse[PadLeft[Map[
IntegerDigits[#,4,s[[1]]]&,b],s+2,5,1]]},
Table[{
If[A[[m,n]]≠A[[m,n+1]],Line[{{n,m-1},{n,m}}-1] ],If[A[[m,n]]≠A[[m+1,n]],Line[{{n,m},{n-1,m}}-1] ]},
{m,1,s[[1]]+1},{n,1,s[[2]]+1}]],
With[{A=Reverse[Map[IntegerDigits[#,10,s[[1]]]&,v]]},
Table[If[A[[m,n]]≠ 0,Text[A[[m,n]],{n,m}-{.5,.5}]],{n,1,s[[1]]},{m,1,s[[2]]}]]},Null,4]}

Viewer

View[p_Puzzle]:=Show[Graphics[Riplines[p]],AspectRatio->Automatic]

View[{p__Puzzle}]:=Grid[{Map[Graphics[Riplines[#],AspectRatio->Automatic]&,{p}]}]

RippleEffectPuz01//View

Getting Rooms

Encoding of the rooms in the puzzle representation is a nice encoding of the corresponding colored matrix. This matrix is obtained by giving a color to each room of the puzzle, making sure that two adjacent rooms have different colors. A well-known (but recently demonstrated) theorem establishes that four colors are sufficient for this coloring. Hence the colored puzzle can be mapped into a matrix of integers smaller than 4, the colored matrix. Lines of the matrix are then considered as base 4 numbers encoded as decimal numbers.

Colored matrix representation

When computing the colored matrix, two extra lines and two extra columns are added. It is a classical way to avoid special treatment for borders and corners in the computation of rooms.

ColorMatrix[Puzzle[{l_,c_},b_,v_]]:=PadLeft[Map[IntegerDigits[#,4,l]&,b],{l,c}+2,4,1]

ColorMatrix[RippleEffectPuz01]//MatrixForm

Getting a room

To get the room enclosing a given position (i.e., the neighbours’ positions with the same color), we use a fixed-point algorithm applied to a neighbourhood extension function.

Neighbours[p_]:=Map[Plus[p,#]&,{{0,1},{1,0},{0,-1},{-1,0}}]

Room[p_,cm_]:=FixedPoint[Function[y,Union[y,Apply[Union,Map[Select[Neighbours[#],Function[x,Extract[cm,x]==Extract[cm,First[y]]]]&,y]]]],{p}]

Room[{2,4},ColorMatrix[RippleEffectPuz01]]

Note that positions returned by Room are positions in the colored matrix, not in the puzzle.

Getting all the rooms

The method used here to get all the rooms is somehow similar in “folding” the Room functions on the list of all the cell positions. But it is a bit quicker (theoretically) because the cells of the room computed at each step are removed from the list of remaining cells for the next step.

GetRooms[cm_,{rl_List,{}}]:=rl
GetRooms[cm_,{{rl___},{p_,op___}}]:=Module[{r=Room[p,cm]},GetRooms[cm,{{rl,r},Complement[{p,op},r]}]]
GetRooms[p_Puzzle]:=GetRooms[ColorMatrix[p],{{},Flatten[Outer[List,Range[2,p[[1,1]]+1],Range[2,p[[1,2]]+1]],1]}]/.{x_Integer,y_Integer}:>{x-1,y-1}

GetRooms[RippleEffectPuz01]

Getting Cells Values

Values are encoded by considering lines of the puzzle as decimal numbers with a zero instead of missing number. Note that this encoding limits the maximal integer appearing in the puzzle to 9 and hence the maximal size of a room.

GetValues[Puzzle[s_,b_,v_]]:=Map[IntegerDigits[#,10,s[[2]]]&,v]

GetValues[RippleEffectPuz01]//MatrixForm

Set of Possibilities

The basic idea to solve a puzzle is to consider the set of possible integers for each of its cells and to try to reduce, by filtering, those sets by applying lines, columns, and rooms constraints repeatedly. Along with the solving process, we will manipulate this set of possibilities that has its own representation, instead of the puzzle itself.

Generation

To generate the set of possibilities, only the size of the rooms and known values are taken into account. No logic is involved at this stage.

ToPossible[Puzzle[s_,b_,v_]]:=Module[{r=GetRooms[Puzzle[s,b,v]]},Possible[s,b,r,MapThread[If[MemberQ[#1,#2],{#2},#1]&,{Table[Range[Length[r[[Position[r,{i,j}][[1,1]]]]]],{i,s[[1]]},{j,s[[2]]}],GetValues[Puzzle[s,b,v]]},2]]]

ToPossible[RippleEffectPuz01]
Last[%]//MatrixForm

Number of possibilities

The number of possibilities is huge at the beginning, but decreases very quickly during the solving process. When this number is 1, the puzzle is solved. If it turns out to be 0, then the puzzle was not a valid one, or a bad assumption has been made on the value of a cell.

SizeOf[Possible[__,p_]]:=Apply[Times,Flatten[Map[Length,p,{2}]]]

SizeOf[ToPossible[RippleEffectPuz01]]

Representation

The representation of the set of possibilities derives from the representation of the puzzle, the inert head Possible is used instead of Puzzle, the explicit list of rooms is added, and the list of values is replaced by a matrix of sets of possible values.

Alternative representations with Solved or Failed as head instead of Possible are included for better readability of the code. Conversion functions to puzzles are provided and the visualisation function is extended.

ToPuzzle[Possible[sb__,r_,p_]]:=Puzzle[sb,Map[FromDigits,p/.{{x_Integer}:>x,{y__Integer}:>0}]]
ToPuzzle[Solved[sbrp__]]:=ToPuzzle[Possible[sbrp]]

View[p_Possible]:=View[ToPuzzle[p]]
View[s_Solved]:=View[ToPuzzle[s]]
View[l_List]:=View[Map[ToPuzzle,l]]

ToPossible[RippleEffectPuz01]//View

SizeOf[f_Failed]:=0
SizeOf[s_Solved]:=1

Only Once Filter

The Only Once filter implements the constraint that in a room it is not possible to have twice the same digits. So, if a value is known, it is removed for the set of possibilities of the cells of the corresponding room.

OnlyOnce[p_Puzzle]:=OnlyOnce[ToPossible[p]]
OnlyOnce[f_Failed,___]:=f
OnlyOnce[s_Solved,___]:=s

One room

Complement1[{x_},y_List]:={x}
Complement1[x_List,y_List]:=Complement[x,y]

HasMultipleQ[l_List]:=Length[Union[l]]≠Length[l]

OnlyOnce[Possible[sbr__,p_],l_]:=Module[{k=Cases[Map[p[[Apply[Sequence,#]]]&,l],{x_}->x]},If[HasMultipleQ[k],Failed[sbr,p],Module[{c=MapAt[Complement1[#,k]&,p,l]},If[SizeOf[Possible[sbr,c]]==0,Failed[sbr,c],Possible[sbr,c]]]]]

All rooms

Here the Only Once filter is applied successively to all rooms.

OnlyOnce[Possible[sb__,r_,p_]]:=Fold[OnlyOnce,Possible[sb,r,p],r]

(RippleEffectPos01a=OnlyOnce[RippleEffectPuz01])//Last//MatrixForm

Not Too Close Filter

NotTooClose[p_Puzzle]:=NotTooClose[ToPossible[p]]
NotTooClose[f_Failed,___]:=f
NotTooClose[s_Solved,___]:=s

The Not Too Close filter implements the constraint that in each line and in each column, numbers that are the same have to be separated by at least their value of cells.

One position

NotTooClose[Possible[s_,br__,p_],{l_,c_}]:=Module[{v=p[[l,c]]},If[Length[v]==1,Possible[s,br,MapAt[Complement[#,v]&,p,Complement[Union[Map[{#,c}&,Range[Max[1,l-v[[1]]],Min[s[[1]],l+v[[1]]]]],Map[{l,#}&,Range[Max[1,c-v[[1]]],Min[s[[2]],c+v[[1]]]]]],{{l,c}}]]],Possible[s,br,p]]]

All positions

NotTooClose[Possible[s_,brp__]]:=Fold[NotTooClose,Possible[s,brp],Flatten[Outer[List,Range[s[[1]]],Range[s[[2]]]],1]]

(RippleEffectPos01b=NotTooClose[RippleEffectPos01a])//View

At Least Once Filter

The At Least Once filter implements the constraint that a room of size S should contain all the integers from 1 to S. So, if a value has only one possible location in a room, it should be there.

AtLeastOnce[p_Puzzle]:=AtLeastOnce[ToPossible[p]]
AtLeastOnce[f_Failed,___]:=f
AtLeastOnce[s_Solved,___]:=s

One room

Reduce1[{x___,y_,z___},y_Integer]:={y}
Reduce1[x_List,y_Integer]:=x
Reduce1[x_List,y_List]:=Fold[Reduce1,x,y]

AtLeastOnce[Possible[sbr__,p_],l_List]:=Module[{sq=Map[p[[Apply[Sequence,#]]]&,l]},Module[{k=Select[Range[9],Length[Position[sq,#]]==1&]},Possible[sbr,MapAt[Reduce1[#,k]&,p,l]]]]

All rooms

AtLeastOnce[Possible[sb__,r_,p_]]:=Fold[AtLeastOnce,Possible[sb,r,p],r]

(RippleEffectPos01c=AtLeastOnce[RippleEffectPos01b])//View

Naive Complete Filter

The Naive complete filter is an iterated application of the One Time filter that is just a combination of the three previous filters.

One Time filter

OneTimeFilter[p_Puzzle]:=OneTimeFilter[ToPossible[p]]
OneTimeFilter[f_Failed,___]:=f
OneTimeFilter[s_Solved,___]:=s

OneTimeFilter[p_Possible]:=AtLeastOnce[NotTooClose[OnlyOnce[p]]]

OneTimeFilter[RippleEffectPos01c]//View

Naive filter

NaiveFilter[p_Puzzle]:=NaiveFilter[ToPossible[p]]
NaiveFilter[f_Failed]:=f
NaiveFilter[s_Solved]:=s

NaiveFilter[p_Possible]:=Module[{pp=FixedPoint[OneTimeFilter,p]},If[SizeOf[pp]==1,Apply[Solved,pp],pp]]

(RippleEffectPos01d=NaiveFilter[RippleEffectPuz01])//View

Results

Note that in several cases, this naive filter is powerful enough to solve the puzzle; however, some of them are not totally solved! To achieve the resolution, the usual constraint programming technique consists in making an assumption and trying to solve by filtering again, assuming this assumption, and backtracking in case of detected failure.

But it is also possible to use enhanced filtering, which will better reduce the set of possibilities.

Map[NaiveFilter,{RippleEffectPuz02,RippleEffectPuz03}]//View

Map[NaiveFilter,{RippleEffectPuz04,RippleEffectPuz05,RippleEffectPuz06}]//View

One Step Further Filter

The One Step Further filter is also referred to as a shaving method. It consists of exploring all the cells where several values are possible, fixing the value repeatedly to all the possibilities, and in each case performing a Naive filter. In case of detected failure, the corresponding value is removed from the set of possibilities.

OSFFilter[p_Puzzle]:=OSFFilter[ToPossible[p]]
OSFFilter[f_Failed,___]:=f
OSFFilter[s_Solved,___]:=s

AmbiguousPosition[v_]:=Module[{p=Join[Position[v,{x_,y_},{2}],Position[v,{x_,y_,z_},{2}],Position[v,{x_,y_,z_,t__},{2}]]},Map[{#,Extract[v,#]}&,p]]

AmbiguousPosition[Last[RippleEffectPos01d]]

NewGuess[Possible[sbr__,v_],h_]:=Possible[sbr,Apply[ReplacePart[v,#2,#1]&,h]]

NewGuess[RippleEffectPos01d,{{3,3},1}]//View

OneStepFurther[f_Failed,Possible[sbr__,v_],{p_,vf_}]:=Possible[sbr,ReplacePart[v,Complement[Extract[v,p],vf],p]]
OneStepFurther[s_Solved,___]:=s
OneStepFurther[p1_Possible,p2_Possible,_]:=p2

OSFFilter[Possible[sbr__,v_]]:=Fold[OSFFilter,Possible[sbr,v],AmbiguousPosition[v]]

OSFFilter[g_Possible,{p_,lv_List}]:=Fold[OSFFilter[#1,{p,#2}]&,g,lv]

OSFFilter[g_Possible,{p_,v_Integer}]:=OneStepFurther[NaiveFilter[NewGuess[g,{p,{v}}]],g,{p,{v}}]

View[OSFFilter[RippleEffectPuz01]]

Results

As the following results show, the use of OSFFilter after a first step of NaiveFilter is powerful enough to solve all the examples. My experience with Sudoku is that the same combinations of filters solved around 90% of the challenges considered as diabolical.

I would be glad to get further examples and namely those where the filtering does not succeed in solving the puzzle, as the OSFFilter could be enhanced in terms of reducing the possibilities at a slight computational cost.

Result[x_]:=(With[{r=Timing[OSFFilter[NaiveFilter[x]]]},Print[r[[1]]];View[r[[2]]]];)

First Example

Result[RippleEffectPuz01]

Warm-Up Puzzles

Result[RippleEffectPuz02]

Result[RippleEffectPuz03]

Intermediate

Result[RippleEffectPuz04]

Result[RippleEffectPuz05]

Result[RippleEffectPuz06]

Challenge

Result[RippleEffectPuz07]