Is this a solvable Numberlink?

Question

Challenge

Per Wikipedia:

Numberlink is a type of logic puzzle involving finding paths to connect numbers in a grid.

The player has to pair up all the matching numbers on the grid with single continuous lines (or paths). The lines cannot branch off or cross over each other, and the numbers have to fall at the end of each line (i.e., not in the middle).

For example, consider this numberlink puzzle:

This puzzle is solvable, see the solution below:

But some numberlink puzzle is unsolvable, like for this one when it's obvious

Another one where it is unsolvable

Your challenge is, given a numberlink puzzle, decide whether it is solvable or not. (A solution doesn't need to fill the entire grid.)

Input / Output

Input / Output can be taken in any reasonable format for taking in a rectangle numberlink puzzle, and deciding whether it is solvable or not. A dot . is used for blank space.

You may assume there are exactly two of any of the non-zero endpoint values and that the set of these form a prefix of the positive integers \$[1,n] , n \in \Bbb{N^+} \$.

You may assume at least one pair of endpoint values present - you won't be given an empty puzzle.

Example testcases:

Input -> Output
[[1, 3, ., ., ., ., .], 
 [., 2, ., 4, 6, ., .], 
 [., ., ., ., 5, ., .],
 [., ., 1, ., ., ., .], -> True
 [., ., ., ., ., ., .],
 [., 2, ., ., 5, 6, .],
 [., ., ., 3, 4, ., .]]

[[., 2, 3, 4, .], 
 [1, ., ., ., 1],       -> False
 [., 2, 3, 4, .]]

[[1, ., 2, ., 4], 
 [., ., 3, ., 5],       
 [., ., ., ., .],       -> False
 [., 2, ., 5, .],
 [., 1, 3, 4, .]]

Alternatively, you can take the width and height of the puzzle, and the two coordinates of each number.

Example testcases (like the above):

Input -> Output:


7 7                // denote the size of the puzzle
[[[1, 1], [3, 4]], // two coordinates of each number 
 [[2, 2], [2, 6]], 
 [[2, 1], [7, 4]],
 [[4, 2], [5, 7]],  --> True
 [[5, 3], [5, 6]],
 [[5, 2], [6, 6]],

5 3
[[[1, 2], [5, 2]], 
 [[2, 1], [2, 3]], --> False
 [[3, 1], [3, 3]],
 [[4, 1], [4, 3]]]

5 5        
[[[1, 1], [2, 5]], 
 [[1, 3], [2, 4]], 
 [[3, 2], [3, 5]], --> False
 [[5, 1], [4, 5]],
 [[4, 4], [5, 2]]]

This is code-golf, so shortest answer (in bytes) wins!

---

_{You probably know this from the game Flow Free. Finding a solution to a Numberlink puzzle is NP-complete, see this video}

Answer 1

JavaScript (ES7), 122 bytes

Expects a matrix of integers with 0's for empty cells. Returns 0 or 1.

This is 100% brute-force, but fast enough to solve the test cases in ~2 sec. on TIO.

f=(m,X,Y,n)=>~n&&m.some((r,y)=>r.some((v,x)=>f(m,x,y,n?(x-X)**2+(y-Y)**2^1?-1:v?v^n&&-1:n:+v?n=v:-1,r[x]=f)|![r[x]=v]))|!n

Try it online!

Commented

f = (                  // f is a recursive function taking:
  m,                   //   m[] = input matrix
  X, Y,                //   (X, Y) = position of previous cell
  n                    //   n = target cell value, or -1 if we must abort,
) =>                   //       or falsy when looking for a source
~n &&                  // abort right away if n = -1
m.some((r, y) =>       // otherwise, for each row r[] at index y in m[]:
  r.some((v, x) =>     //   for each value v at index x in r[]:
    f(                 //     do a recursive call:
      m, x, y,         //       pass m[] and the current position
      n ?              //       if n is defined and not zero:
        (x - X) ** 2 + //         if the squared Euclidean distance
        (y - Y) ** 2   //         between (x, y) and (X, Y)
        ^ 1 ?          //         is not equal to 1:
          -1           //           force the call to abort
        :              //         else:
          v ?          //           if v != 0:
            v ^ n      //             if v is not equal to n,
            && -1      //             force the call to abort
                       //             (otherwise: target found -> we call
                       //             with 0 to look for another source)
          :            //           else:
            n          //             keep looking for the target cell n
      :                //       else (looking for a source square):
        +v ?           //         if v > 0:
          n = v        //           set n = v and launch the target search
        :              //         else:
          -1,          //           force the call to abort
      r[x] = f         //       invalidate the cell
    ) |                //     end of recursive call
    ![r[x] = v]        //     restore the cell
  )                    //   end of inner some()
) | !n                 // end of outer some(); n = 0 -> all paths found

Answer 2

Python 3.8 (pre-release), 151 bytes

f=lambda x,y,a,*v:len({*zip(*a)})<2|any(f(x,y,l|{(k,j)},*v,i)for i,j in a for k in{i+1,i+1j,i-1,i-1j}if(k in sum(l:=a-{(i,j)},v))==k.real//x+k.imag//y)

Try it online!

Very slow recursive brute-force solution

Answer 3

Jelly,  28  26 bytes

ṁŻŒĠḊµŒ!ạƝ€§ṂỊ)Ȧ
FoṀrƊŒpçƇ

A monadic Link that accepts a list of lists containing any number of zeros and exactly two each of a non-empty^* prefix of the natural numbers and yields an empty list (falsey) if unsolvable and a non-empty list (truthy) if solvable.

(The contents of the resulting list are flattened versions of all solutions along with any "extra" solutions that continue past the end-points which would not be possible without a solution.)

^{* A blank puzzle, if it were given, would be identified as unsolvable.}

Try it online! Note, however, this is horribly brute force so can't handle any decent test cases!

How?

Form all possible fills of the input allowing any of [0..maxN] at zeros, but only allowing the endpoint values where endpoints are given. Filter to keep those which are valid or "extra" solutions by checking that the set of the locations of each non-zero number can be ordered such that every neighbouring pair is orthogonally adjacent (i.e. they can form a "line").

ṁŻŒĠḊµŒ!ạƝ€§ṂỊ)Ȧ - Helper Link - isSolutionOrExtraSolution?: FlatFill; Puzzle
ṁ                - mould {FlatFill} like {Puzzle}
 Ż               - prefix a zero (in case there are no zeros anywhere)
  ŒĠ             - multidimensional indices grouped by their values
    Ḋ            - dequeue (remove the group of zero value locations)
     µ        )  - for each SetOfLocationsOfN:
      Œ!         -   all permutations
         Ɲ€      -   for the neighbouring pairs of each permutation:
        ạ        -     absolute difference -> deltas
           §     -   sums -> list of Manhatten distances for each permutation
            Ṃ    -   minimum -> minimal list of Manhatten distances
             Ị   -   insignificant? -> [1 if m=1 else 0 for m in {that}]
               Ȧ - any and all? -> 0 if empty or a 0 is present else 1

FoṀrƊŒpçƇ - Link: list of lists of [0..maxN], Puzzle
F         - flatten {Puzzle}
    Ɗ     - last three links as a monad f(FlatPuzzle):
  Ṁ       -   maximum -> maxN
 o        -   {FlatPuzzle} logical OR {that} -> replace zeros with maxN
   r      -   {that} inclusive range {FlatPuzzle} -> list of lists of possible fills
     Œp   - Cartesian product -> All possible flattened fills of the Puzzle
                                 allowing any of [maxN..0] at zeros
                                 but only allowing the existing values elsewhere
        Ƈ - keep those for which:
       ç  -   call the Helper Link as a dyad - f(FlatFill, Puzzle)

Answer 4

05AB1E, 71 (or 72^†) bytes

˜©þàÝ®ð¢ã.Δð®r.;IgäDUàLεXQDV˜ƶIgäΔ2Fø0δ.ø}2Fø€ü3}Y*εεÅsyøÅs«à}}}˜0KÙg}P

Inputs-matrix uses spaces as blank cells.
Outputs a valid list of replacements for the blank cells as truthy, with 0 as blank output-cells (will be truthy for an empty input-matrix), or -1 if there is no solution as falsey.
†: If this is not allowed, the .Δ can be replaced with ε and a trailing }à can be added, to output 1 as truthy or 0 (or nothing for an empty input-matrix) as falsey. (Although this causes the program to become even slower than it already is..)
Also assumes the numbered input-pairs will be consecutive going upwards starting at \$1\$. If an input that skips numbers is allowed, an ! can be added after the Ùg to fix that for +1 byte.

Try it online. (I'm using a very slow brute-force approach, so it'll timeout for all given test cases.)

Explanation:

Step 1: Create a list of all possible replacements for the blank spaces:

˜                     # Flatten the (implicit) input-matrix
 ©                    # Store this list in variable `®` (without popping)
  þ                   # Pop and remove the spaces (by only keeping numbers)
   à                  # Pop and keep the maximum number
    Ý                 # Pop and push a list in the range [0,max]
     ®                # Push flattened input-list `®` again
      ð¢              # Pop and count how many spaces are in it
        ã             # Take the cartesian product of the [0,max] and this count

Step 2: Actually replace them in the input-matrix:

.Δ                    # Find the first replacement-list for which the following
                      # is truthy:
                      #  (implicitly push the current replacement-list)
  ð                   #  Push a " "
   ®                  #  Push flattened input-list `®`
    r                 #  Reverse the order of the three values on the stack
     .;               #  Replace every first " " with the values of the
                      #  replacement-list in the flattened input-list
       Igä            #  Convert the list back to a matrix:
       Ig             #   Push the length of the input-matrix (amount of rows)
         ä            #   Split the list into that many equal-sized inner lists

Step 3: For each numbered value in the input-list, flood-fill the matrix of the previous step:

DU                    #  Duplicate, pop and store this matrix in variable `X`
à                     #  Pop and push its maximum
 L                    #  Pop and push a list in the range [1,max]
  ε                   #  Map over this list:
   X                  #   Push matrix `X`
    Q                 #   Check for each inner value whether it equals the
                      #   current value
     DV               #   Store a copy in variable `Y`
     ˜                #   Flatten the matrix to a list
      ƶ               #   Multiply each value by its 1-based index
       Igä            #   Convert it back to a matrix
          Δ           #   Loop until it no longer changes to flood-fill:
           2Fø0δ.ø}   #    Add a border of 0s around the matrix:
           2F     }   #     Loop 2 times:
             ø        #      Zip/transpose; swapping rows/columns
               δ      #      Map over each row:
              0 .ø    #       Add a leading/trailing 0
           2Fø€ü3}    #    Convert it into overlapping 3x3 blocks: 
           2F    }    #     Loop 2 times again:
             ø        #      Zip/transpose; swapping rows/columns
              €       #      Map over each inner list:
               ü3     #       Convert it to a list of overlapping triplets
           Y*         #    Multiply each 3x3 block by the value in matrix `Y`
                      #    (so the 0s remain 0s)
           εεÅsyøÅs«à #    Get the largest value from the horizontal/vertical
                      #    cross of each 3x3 block:
           εε         #     Nested map over each 3x3 block:
             Ås       #       Pop and push its middle row
               y      #       Push the 3x3 block again
                ø     #       Zip/transpose; swapping rows/columns
                 Ås   #       Pop and push its middle rows as well (the middle
                      #       column)
                   «  #       Merge the middle row and column together to a
                      #       single list
                    à #       Pop and push its maximum
           }}         #     Close the nested maps
          }           #   Close the changes-loop

Step 4: Check if the flood-fill was successful for all numbers for the current replacement, and output the result if it was:

           ˜          #   Flatten the flood-filled matrix
            0K        #   Remove all 0s
              Ù       #   Uniquify the other numbers
               g      #   Pop and push the length to get the amount of islands
                      #   (only 1 is truthy in 05AB1E)
  }                   #  Close the map
   P                  #  Product to check if all are truthy
                      # (after which the found replacement-list is output
                      # implicitly as result, or -1 if none were valid)

Answer 5

Charcoal, 103 87 bytes

ＷＳ⊞υι≔⪫υωη≔Ｉ⌈ηζＦＸζ№η.¿¬ⅈ«≔¹εＦζ«⪪⪫⪪⭆η∨Σλ⊕﹪÷ιＸζ№…ημ.ζＩ⊕κψＬθ≔⌕ηＩ⊕κδＪ﹪δＬθ÷δＬθ¤.≧×⁼ＬＫＡＬηε⎚»ε

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings and outputs a Charcoal boolean, i.e. - for solvable, nothing if not. Explanation: More brute force so only works for trivial puzzles on TIO.

ＷＳ⊞υι≔⪫υωη≔Ｉ⌈ηζ

Input the list of strings and join them back together on newlines and also extract the largest digit.

ＦＸζ№η.¿¬ⅈ«

Loop through all potential solutions until one is found.

≔¹ε

Assume that this is a correct solution for now.

Ｆζ«

Loop through each digit.

⪪⪫⪪⭆η∨Σλ⊕﹪÷ιＸζ№…ημ.ζＩ⊕κψＬθ

Write the solution to the canvas, but with the current digit replace with null characters.

≔⌕ηＩ⊕κδＪ﹪δＬθ÷δＬθ¤.

Try to fill the solution starting at the first occurrence of the digit.

≧×⁼ＬＫＡＬηε

If the fill didn't restore all occurrences of the digit then mark this as an incorrect solution.

⎚

Clear the canvas ready for the next pass or ready to output the solution state.

»ε

Output the solution state.