# Can you connect the dots?

This challenge is based off of Flow Free. An online version can be found here: http://www.moh97.us/

You will be given a puzzle, and you must return 1 if the puzzle is solvable, or 0 if it is not.

To solve a puzzle, the player must create a path to connect each pair of numbers using every empty square exactly once.

You are passed in the dimensions of the square, and then the x,y,c (where c is a number representing the color) of each dot. For example:

If 5,5 0,0,0 3,0,1 1,1,2 1,2,2 4,2,1 4,4,0 was passed to you, it would represent:

0..1.
.2...
.2..1
....0


And should return 1.

Here are some more test problems:

5,2 2,0,1 0,1,2 4,1,2 represents:

..1..
2...2


and is not solvable because there is only 1 1.

4,2 0,0,0 3,0,0 0,1,0 3,1,0 represents:

0..0
0..0


and is not solvable because it includes more than 2 0s.

8,6 0,0,1 7,5,1 represents:

1.......
........
........
........
........
.......1


and is not solvable (as you can't use every square).

2,5 0,0,1 2,0,6 4,0,6 0,1,4 3,1,4 4,1,1 represents:

1.6.6
4..41


and is not solvable because you cannot connect the 1s.

6,3 1,0,4 5,0,1 0,1,4 1,1,3 5,1,3 0,2,2 3,2,2 5,2,1 represents:

.4...1
43...3
2..2.1


and is not solvable because you cannot connect the 1s (or the 3s), as the two paths must necessarily cross.

5,2 0,0,1 3,0,1 0,1,3 4,1,1 represents:

1..1.
3...3


and is not solvable because you cannot use all of the squares in building a path.

2,2 0,0,0 1,1,0 represents:

1.
.1


and is not solvable because you can't use all of the squares here either

Here are some more tests:

5,5 0,3,0 0,4,1 1,2,2 1,3,1 2,0,0 3,0,4 3,1,2 3,3,5 3,4,4 4,4,5 should return 1

13,13 1,1,0 9,1,1 10,1,2 11,1,3 1,2,4 2,2,5 5,2,6 7,2,7 3,3,0 5,4,6 6,4,1 9,6,3 4,7,8 5,8,9 12,8,8 11,9,10 2,10,4 4,10,2 9,10,5 11,10,7 1,11,9 12,12,10 should return 1

7,7 0,0,0 0,1,1 1,1,2 2,1,3 4,2,4 0,3,1 5,3,3 0,4,4 2,4,5 5,4,2 0,5,0 1,5,5 3,5,6 3,7,6 should return 0

This is a code golf, and the standard rules apply.

• Does a solution have to be "realistically" correct or just theoretically correct? For instance, the state space can be broken down into assigning one of 6 possible input-to-input configurations to each empty cell. Solvability is easily determined by attempting all 6^N combinations and returning 1 if any one of them visits all cells and connects all terminals. Obviously this approach wouldn't complete in a reasonable amount of time for anything but the smallest N (number of empty cells), but we still have a mathematical guarantee that the algorithm would eventually return the correct value.
– COTO
Sep 30, 2014 at 17:46
• Perhaps if you came up with two huge sets of playing grids (one public for testing, one private for validation) using a common algorithm and deemed the winner to be the submission that correctly identified the solvability of the most grids in the private set in some reasonable amount of time per grid, with program size as a tiebreaker if two submissions had equal utility. I'd definitely try my hand at that.
– COTO
Oct 1, 2014 at 13:33
• @NathanMerrill: The problem is reducible to SAT and thus NP hard.
– COTO
Oct 1, 2014 at 17:13
• @NathanMerrill reducing a problem to SAT means that the problem is in NP, not that it is NP-hard -- it's reducing SAT to a problem that shows NP-hardness of the problem. The page you linked to does have a link to a proof of NP-completeness though. Oct 2, 2014 at 14:47
• @VisualMelon Digit color is the wrong word. Each color is represented by a different number, not digit. Apr 16, 2015 at 16:03

import Data.List.Split
import qualified Data.Sequence as Q
import Data.List

data A a = S a | E a | P a | X deriving Eq

sc = foldr1 (Q.><)
sp b x y p = Q.update y (Q.update x p $b Q.index y) b dt b c | S c elem sc b = E c | otherwise = S c ad b [x, y, c] = sp b x y (dt b c) ep b [x, y, c] = do let nps = filter ob [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] ns = map gp nps [b | E c elem ns] ++ do (x', y') <- filter ((== X) . gp) nps ep (sp b x' y' (P c)) [x', y', c] where ob (u, v) = 0 <= u && u < length (b Q.index 0) && 0 <= v && v < length b gp (u, v) = b Q.index v Q.index u rd i = let [c, r] : ps = (map read . splitOn ",") <$> words i :: [[Int]]
e = Q.replicate r $Q.replicate c X cs = map last ps ss = nubBy (\[_,_,c1] [_,_,c2] -> c1 == c2) ps b = foldl ad e ps bs = foldM ep b ss in if even (length cs) && length ss == length cs div 2 && (all (\[j,k] -> j==k) . chunksOf 2 . sort$ cs) &&
any (null . Q.elemIndicesL X . sc) bs
then 1
else 0

main = rd <\$> getContents >>= print


### Key

• sc: Seq concat
• sp: set position
• dt: dot type (ie, start or end of line)
• ep: extend path
• rd: run dots (primary pure algorithm)
• Thanks for the submission, and welcome to PPCG stack exchange. This is a code golf challenge, meaning the purpose is to write the shortest program which solves the challenge. You're in the lead, because you have the only answer, but you should try to shorten your program as much as possible. May 25, 2015 at 1:13
• I'm honestly impressed that you answered this question after all this time. Also, this problem was more of a code-challenge, but I used code-golf, as it was hard to come up with a different scoring basis. May 25, 2015 at 14:03
• Yes, I didn't worry too much about the "golf" aspect; I'm trying to learn Haskell and it seemed like a fun problem :-)
– Matt
May 26, 2015 at 15:46

# Python3, 538 bytes:

R=range
def f(x,y,v):
d={}
for j in R(x):
for k in R(y):d[r]=d.get(r:=v.get((j,k),-1),[])+[(j,k)]
if any(i!=-1 and len(d[i])!=2 for i in d):return 0
D=eval(str(d));del D[(M:=max(d))][0]
q=[(M,D,d[M][0],0)]
while q:
M,D,(j,k),C=q.pop(0)
if(j,k)in D[M]:
Y=eval(str(D));del Y[M]
if(M:=max(Y))!=-1:q+=[(M,Y,Y[M][0],0)];del Y[M][0]
if{-1:[]}==Y:return 1
continue
for J,K in[(-1,0),(1,0),(0,1),(0,-1)]:
if(T:=(j+J,k+K))in D[-1]:Y=eval(str(D));Y[-1].remove(T);q+=[(M,Y,T,C+1)]
elif T in D[M]and C:q+=[(M,D,T,C+1)]


Try it online!

• Btw, you can ident your code with a tab instead of 4 spaces. Its also 1 byte and more readable than indenting with 1 space Sep 27 at 17:39
• When there is a number and a letter after like 1 and and you can write 1and. In this case: -1and, 2for, Sep 27 at 17:42
• @TKirishima There is actually one exception, which is 0or - it gets confused with an octal literal. (10or works fine though.) Sep 28 at 3:23