17
2
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 code-golf, so shortest code wins.
This was inspired by this Math Stack Exchange question.
– Peter Kagey – 2019-01-24T01:07:45.213@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 – 2019-01-24T01:10:10.047
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 – 2019-01-24T01:16:25.077
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 – 2019-01-24T07:30:21.037
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 – 2019-01-24T13:50:41.627
@Arnauld, not necessarily. In principle, the marked cell could be at the center of a T-tetromino. I'll add an example.
– Peter Kagey – 2019-01-24T19:15:45.970@OlivierGrégoire, the array of coordinates gives the coordinates of each particular part (in this case in lexicographic order), for example
[(0,0), (0,1), (0,2), (1,2), (1,3)]
refers to the red region in the picture. However, any reasonable format that clearly shows that you have solved the puzzle is fine. – Peter Kagey – 2019-01-24T19:18:10.767Can we take the length as a second input? – lirtosiast – 2019-01-26T22:50:38.787
@lirtosiast, you cannot take the length as a second input because it is easily derivable from the (first) input. – Peter Kagey – 2019-01-29T16:54:56.123