# 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. Jan 24, 2019 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. Jan 24, 2019 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. Jan 24, 2019 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? Jan 24, 2019 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. Jan 24, 2019 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()


# 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?