17
\$\begingroup\$

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 solution

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.

\$\endgroup\$
  • \$\begingroup\$ This was inspired by this Math Stack Exchange question. \$\endgroup\$ – Peter Kagey Jan 24 at 1:07
  • \$\begingroup\$ @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. \$\endgroup\$ – Peter Kagey Jan 24 at 1:10
  • \$\begingroup\$ 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. \$\endgroup\$ – Arnauld Jan 24 at 1:16
  • \$\begingroup\$ 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? \$\endgroup\$ – Olivier Grégoire Jan 24 at 7:30
  • \$\begingroup\$ 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. \$\endgroup\$ – Arnauld Jan 24 at 13:50
10
\$\begingroup\$

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()
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.