# Partition a square grid into parts of equal area

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:

# 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 , so shortest code wins.

• This was inspired by this Math Stack Exchange question. – Peter Kagey Jan 24 at 1:07
• @Arnauld, it looks like for Shikaku puzzles, "the objective is to divide the grid into rectangular and square pieces". In this case, there is no such constraint. – Peter Kagey Jan 24 at 1:10
• Sorry for the confusion. I think there might be a Shikaku challenge somewhere in the sandbox, or maybe I was planning to make one myself at some point -- I can't remember for sure. Either way, I thought it was the same thing at first glance. – Arnauld Jan 24 at 1:16
• Why is the result a 2d array of coordinates? I don't understand what is being expressed there... Can't it be a 2d array of the index of the array? For instance row 3, column 2 contains partition with coordinates at index 4? – Olivier Grégoire Jan 24 at 7:30
• May we assume that each area can be drawn by starting from the reference coordinates, as the example suggests? I've just realized that I've unconsciously taken this for granted. – Arnauld Jan 24 at 13:50

# 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()