<p>The phrase you are looking for is &quot;system of distinct representatives&quot;. A stone placement represents its set of candidate locations, and all sets must have distinct placements.</p>
<p>It is more or less the same as bipartite matching, on a graph connecting each stone to each location where it may be placed, and can be solved in polynomial time using matching algorithms.</p>

CC BY-SA 4.0
2023-08-17T19:05:01.050Z
2023-08-17T19:05:01.050Z
David Eppstein
<p>Consider the puzzle comprised of <span class="math-container">$N$</span> stones. Each stone is given a set of candidate locations. The goal is to put each stone in one of its candidate locations such that no two stones are put in the same place.</p>
<p>Has this problem and its complexity been studied in the literature somewhere? If so, what is it called?</p>
<p>The puzzle is more or less similar to the exact cover problem.</p>

CC BY-SA 4.0
2023-08-17T14:58:25.507Z
Is there something missing from the description? The way it is written, it is completely irrelevant that it is played on a grid. It could just be any set of a given size.
Emil Jeřábek
CC BY-SA 4.0
2023-08-17T14:59:33.383Z
You are correct, the grid part is irrelevant. I will edit the question.
TRP
CC BY-SA 4.0
2023-08-17T15:24:03.027Z
It's equivalent to left-total bipartite matching, hence in polynomial time. The left partition are the stones, the right partition the locations, and there is an edge from any stone to each of its candidate locations.
Emil Jeřábek
<cc.complexity-theory><puzzles>
Name and complexity of a stone placement puzzle
TRP
# Name and complexity of a stone placement puzzle

(Asked by: username_0 on 2023-08-17)

Consider the puzzle comprised of $N$ stones. Each stone is given a set of candidate locations. The goal is to put each stone in one of its candidate locations such that no two stones are put in the same place.

Has this problem and its complexity been studied in the literature somewhere? If so, what is it called?

The puzzle is more or less similar to the exact cover problem.

**Tags:** cc.complexity-theory, puzzles
> **Comments:**
> **username_1**: Is there something missing from the description? The way it is written, it is completely irrelevant that it is played on a grid. It could just be any set of a given size.  
> **username_0**: You are correct, the grid part is irrelevant. I will edit the question.  
> **username_1**: It's equivalent to left-total bipartite matching, hence in polynomial time. The left partition are the stones, the right partition the locations, and there is an edge from any stone to each of its candidate locations.  

---

## 1 answers

### Answer by username_2 on 2023-08-17. Score: 3 | Accepted answer

The phrase you are looking for is "system of distinct representatives". A stone placement represents its set of candidate locations, and all sets must have distinct placements.

It is more or less the same as bipartite matching, on a graph connecting each stone to each location where it may be placed, and can be solved in polynomial time using matching algorithms.


---

