# Generate Loopy puzzles

Loopy is a puzzle game from the collection of Simon Tatham. The previous link contains a javascript implementation of a Loopy puzzle generator. I suggest everybody who wants to attempt this challenge to solve a couple of puzzles manually to understand how they are supposed to work.

Here are instructions on how to solve a Loopy puzzle:

## Chapter 23: Loopy

You are given a grid of dots, marked with yellow lines to indicate which dots you are allowed to connect directly together. Your aim is to use some subset of those yellow lines to draw a single unbroken loop from dot to dot within the grid.

Some of the spaces between the lines contain numbers. These numbers indicate how many of the lines around that space form part of the loop. The loop you draw must correctly satisfy all of these clues to be considered a correct solution.

In the default mode, the dots are arranged in a grid of squares; however, you can also play on triangular or hexagonal grids, or even more exotic ones.

Credit for the basic puzzle idea goes to Nikoli [10].

Loopy was originally contributed to this collection by Mike Pinna, and subsequently enhanced to handle various types of non-square grid by Lambros Lambrou.

[10] http://www.nikoli.co.jp/puzzles/3/index-e.htm (beware of Flash)

The goal of this task is to write your own Loopy puzzle generator. Since graphics are way too complicated, you have to output a generated puzzle in ASCII like the example puzzle of size 7×7 below. The advantage of the output format described here is that you can output your puzzle into a line printer and solve it with a pen.

+ + + + + + + +
2 3
+ + + + + + + +
2       2   3
+ + + + + + + +
2   2 1 3
+ + + + + + + +
2         1 2
+ + + + + + + +
2 1 2 3 3
+ + + + + + + +
3 2   1
+ + + + + + + +
2 2
+ + + + + + + +


## Input specification

• An integer parameter in the range 2 to 99, x (width)
• An integer parameter in the range 2 to 99, y (height)
• An integer parameter in the range 0 to 9, d (difficulty)

If you choose to implement the deterministic option, your program shall further receive as input:

• A positive integer parameter, s (seed)

In submissions written in languages that have the notion of program or command line arguments, the input shall be provided as a set of program arguments. The invocation will be like this:

program <x> <y> <d> <s>


where <s> is left out if you do not choose to implement the deterministic option.

In submissions written in languages that have the concept of an invocation URL (i.e. the URL the program is called at), input shall be provided as a set of URL parameters like this:

http://site.example/program?x=<x>&y=<y>&d=<d>&s=<s>


where the &s=<s> part is left out if you do not choose to implement the deterministic option.

In languages that fit into neither category, input is to be received in an implementation defined way. Hard coding input is not an acceptable implementation defined way, except if your language provides no mean to receive input.

Your program shall terminate and generate output as specified below for each combination of parameters with meaningful values. The behavior of your program is unspecified if any parameter is missing, invalid, or outside of the specified range.

## Output specification

Your program shall output a square-grid Loopy puzzle formatted as described above with an implementation-defined line terminator. Your implementation may fill each line with an arbitrary amount of trailing whitespace characters.

The grid shall have x×y cells where x and y are the width and height parameters specified further above. The puzzle your program generates shall have exactly one solution.

The difficulty of the problems your program generates shall depend on the d parameter, where a d value of 0 shall generate easy problems and a d value of 9 shall generate hard problems. Please document how the difficulty of the problems you generate changes depending on the d parameter.

If you choose to implement the deterministic option, the output of your program shall only depend on the value of the input. Different values for s shall yield different puzzles with a high probability for the same combination of x, y, and d. If you do not choose to implement the deterministic option, the output of your program shall be different every time the program is executed with a high probability. You can assume that the program is not executed more than one time per second.

## Scoring

The score of your program is the number of characters in its source except for omittable whitespace characters and omittable comments. You are encouraged to indent your submission so it's easier to read for the others and to comment your solution so its easier to follow.

Your submission may violate some of the rules described above. Please document specific rule violations and add the corresponding penalty to your score. Rule violations not documented here make your submission invalid.

• Your program contains instances of undefined behavior or violations of your language's rules (128)
• Your program ignores the d parameter but generates hard puzzles (256)
• Your program does not terminate or crashes in rare cases (512)
• Your program ignores the d parameter but generates easy puzzles (1024)
• Your program generates puzzles with more than one solution (2048)
• Your program generates unsolvable puzzles in rare cases (4096)

## Judgement

The winner of this contest is the submission with least score. I reserve the right to disregard submissions that violate the spirit of this contest or that cheat.

• Those are interesting and rather harsh penalties ;-) Aug 16, 2014 at 21:42
• @JanDvorak The concept is to encourage people to post incomplete solutions but not to let them intentionally skip parts and take the penalty instead. Aug 16, 2014 at 21:44
• Ah I love those puzzles :). You might want to clarify in your post that the yellow lines referred to in the spec are in fact just the grid lines of the complete square grid (you mention the square grid but I don't see any link between that and the yellow lines in your post). Aug 16, 2014 at 21:49
• How are you going to decide which of the "ignores the d parameter" penalties applies? Is there a puzzle hardness checker? Aug 16, 2014 at 22:58
• @PeterTaylor Hm... You might be right. Still, I believe that it's the right thing to mandate a difficulty switch. After all, this is supposed to be a complex challenge. Aug 17, 2014 at 15:26

# Python3, 1004 bytes:

from random import*
from itertools import*
R=range
def U(D,B,x,y,X,Y):
try:D[B[x][y]]=D.get(B[x][y],[])+[B[X][Y]]
except:1
def O(b,s,e,x,y,n=[],r=[]):
if[]==s:yield e;return
j,k=s[0];J,X=j*(y+1)+k,(j+1)*(y+1)+k;K,Y=J+1,X+1
if len(p:={(J,X),(K,Y),(J,K),(X,Y)}-{*r})>=b[j][k]:
for i in combinations(p,b[j][k]):
T=p-{*i}
if all(q not in n for q in T):
E=eval(str(e))
for A,B in T:E[A].remove(B);E[B].remove(A)
if all(len(E[A])>1 for A in E):yield from O(b,s[1:],E,x,y,n+[*i],r+[*T])
def f(x,y,d):
while 1:
s=[0]*(x*y-(L:=int((x*y/2)*d/10)))+[randint(1,3)for _ in R(L)];shuffle(s);b=[s[i:i+y]for i in R(0,len(s),y)];k=-1
B=[[(k:=k+1)for _ in R(y+1)]for _ in R(x+1)];D={}
for Y in R(y+1):
for X in R(x+1):U(D,B,X,Y,X,Y+1);U(D,B,X,Y,X+1,Y);U(D,B,X,Y+1,X,Y);U(D,B,X+1,Y,X,Y)
for _ in O(b,[(X,Y)for X in R(x)for Y in R(y)if b[X][Y]],D,x,y):return'\n'.join([' '.join(['+']*len(H))+'\n'+' '+' '.join([' ',str(u)][u>0]for u in G)for H,G in zip(B,b)]+[' '.join(['+']*len(B[0]))])


Try it online!

As d increases, the number of numeric cells also increases.

• X=j*(y+1)+k,(j+1)*(y+1)+k; can be X=j*-~y+k,-~j*-~y+k;; '\n'+' ' can be '\n '; and in your bottom function you could add a default parameter ,t=' ' and replace the four ' ' with t. 993 bytes Jun 16 at 16:15