# 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 '14 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 '14 at 13:33
• @NathanMerrill: The problem is reducible to SAT and thus NP hard. – COTO Oct 1 '14 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. – cardboard_box Oct 2 '14 at 14:47
• @VisualMelon Digit color is the wrong word. Each color is represented by a different number, not digit. – Nathan Merrill Apr 16 '15 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)