[Question]
  [
This challenge is based on the following puzzle: You are given an `n` by `n` grid with `n` cells marked. Your job is to the partition the grid into `n` parts where each part consists of exactly `n` cells, each containing exactly one marked cell.
# Example
Here is a puzzle on the left and its (unique) solution on the right:
[![puzzle](https://i.stack.imgur.com/tYDYT.png)](https://i.stack.imgur.com/tYDYT.png)
[![solution](https://i.stack.imgur.com/3BHUo.png)](https://i.stack.imgur.com/3BHUo.png)
# Challenge
You will be given a set of `n` zero-indexed coordinates in any reasonable format.
```
[(0,0), (0,3), (1,0), (1,1), (2,2)]
```
And your job is to write a program that returns any valid parition (again, in any reasonable format).
```
[
  [(0,0), (0,1), (0,2), (1,2), (1,3)],
  [(0,3), (0,4), (1,4), (2,4), (3,4)],
  [(1,0), (2,0), (3,0), (4,0), (4,1)],
  [(1,1), (2,1), (3,1), (3,2), (4,2)],
  [(2,2), (2,3), (3,3), (4,3), (4,4)]
]
```
If the puzzle has no solution, the program should indicate that by throwing an error or returning an empty solution.
# Input/Output Examples
```
[(0,0)]               => [[(0,0)]]
[(0,0), (1,1)]        => [
                          [(0,0), (1,0)], 
                          [(0,1), (1,1)]
                         ]
[(0,0), (0,1), (1,0)] => [] (no solution)
[(0,0), (0,1), (0,2)] => [
                          [(0,0), (1,0), (2,0)], 
                          [(0,1), (1,1), (2,1)],
                          [(0,2), (1,2), (2,2)],
                         ]
[(0,0), (0,2), (1,2)] => [
                          [(0,0), (1,0), (2,0)], 
                          [(0,1), (0,2), (1,1)],
                          [(1,2), (2,1), (2,2)],
                         ]
```
# Scoring
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so shortest code wins.
  
[Answer]
# JavaScript (ES7), 166 bytes
Outputs a matrix of integers that describe the partition, or \$false\$ if there's no solution.
```
a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m
```
[Try it online!](https://tio.run/##dY3NboMwEITveQqfyDpeLJveqBbOfYNEllVZKUGgYBBQBGr67BTSVOpPetqd@WZnSze47tgWTR/6@iWbTzQ7SqAiJyvXwDMlRkrpLMecwOMeD1iSwoJT4oy3qTOlTSvZ1VUG0OK0@O1NDTguSojhAvtw5LtdJOAQTusS6lTFObRmtORxxAlLobG4jMLgZInWap7q@BoYOI@LIMjBC81jzUHxIKjmPut6RswxStgbO9a@q8@ZPNc5bJ9889rHW2SOP/4gJ3D8l7XI981mLQNjFCpr@XeFzGjUf021mFem/mUKo3ss@ry7yx6@Om9vlxFdk/MH "JavaScript (Node.js) – Try It Online")
### How?
We first build a square matrix \$m\$ of size \$N\times N\$, where \$N\$ is the length of the input:
```
m = a.map(_ => [...a])
```
Each row of \$m\$ consists of a copy of the input, i.e. an array of \$N\$ coordinate pairs. The important point here is that all cells of \$m\$ are initialized to non-numeric values. We'll be able to detect them by applying the prefix increment operator `++`.
The recursive function \$g\$ takes a pointer \$n\$ into the input, the coordinates \$(X,Y)\$ of the previous cell, a counter \$j\$ that holds the number of filled cells in the current area, and a flag \$i\$ that is set when the marked cell is found in the area:
```
g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1
```
We test \$a[n]\$ to know if all areas have been processed and we test \$a[j]\$ to know if enough cells have been filled in the current area.
The main part of \$g\$ looks for the next cell of \$m\$ to fill by iterating on all of them:
```
m.some((r, y) =>          // for each row r[] at position y in m[]:
  r.some((v, x) =>        //   for each cell of value v at position x in r[]:
    ++v |                 //     if this cell is already filled (i.e. v is numeric)
    (X - x) ** 2 +        //     or the squared Euclidean distance between
    (Y - y) ** 2 -        //     (X, Y) and (x, y)
    1 ?                   //     is not equal to 1:
      0                   //       this is an invalid target square: do nothing
    :                     //     else:
      g(                  //       do a recursive call to g:
        r[x] = n,         //         pass n unchanged and fill the cell with n
        x, y,             //         pass the coordinates of the current cell
        j + 1,            //         increment j
        i |               //         update i:
        x + [,y] == a[n]  //         set it if (x, y) = a[n]
      ) ?                 //       if the result of the call is truthy:
        1                 //         return 1
      :                   //       else:
        r[x] = v          //         reset the cell to NaN
  )                       //   end of inner map()
)                         // end of outer map()
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 26 bytes
```
Jṗ2Œ!s€L_/ƝÆḊ€ỊẠƲ€Ạ$Ƈi"Ạ¥Ƈ
```
[Try it online!](https://tio.run/##y0rNyan8/9/r4c7pRkcnKRY/alrjE69/bO7htoc7uoCch7u7Hu5acGwTiLlrgcqx9kwlIH1o6bH2/48aZhxuf9QwU@HQVoUsoDwINe7TUQASGppZjzauAyIFb6CoQqQmUEHjvkPbDm37/z9aw0DHQFNHQcNQx1AzFgA "Jelly – Try It Online")
This is *wildly* inefficient, around \$O({n^2}!)\$ for an input of \$n\$ co-ordinates. As such, it times out on TIO for \$n \ge 3\$. I've tested it locally for the other test cases and it works as expected.
This takes input 1 indexed, and it returns a list of valid partitions. The Footer adjusts the output for you.
## How it works
```
Jṗ2Œ!s€L_/ƝÆḊ€ỊẠƲ€Ạ$Ƈi"Ạ¥Ƈ - Main link. Takes a list of n coordinates on the left
J                          - [1, 2, ..., n]
 ṗ2                        - All pairs; [[1, 1], [1, 2], ..., [n, n]]
   Œ!                      - All permutations
       L                   - Yield n
     s€                    - Split each permutation into n parts
                   $Ƈ      - Keep the matrices for which the following is true:
                Ʋ€         -   Over each row:
          Ɲ                -     For each overlapping pair:
        _/                 -       Get the successive differences
           ÆḊ€             -     Get the norm for each
              ỊẠ           -     All are between -1 and 1?
                  Ạ        -   This is true for all rows?
                             This filters out matrices of non-adjacent coordinates
                        ¥Ƈ - Keep the matrices for which the following is true:
                     i"    -   Get the indices of each coordinate, or 0, if not in each row
                       Ạ   -   All non-zero?
```
]