Partition a square grid into parts of equal area
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!
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()
Jelly, 26 bytes
Jṗ2Œ!s€L_/ƝÆḊ€ỊẠƲ€Ạ$Ƈi"Ạ¥Ƈ
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?