1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Aug 17, 2023 at 14:58
  • $\begingroup$ You are correct, the grid part is irrelevant. I will edit the question. $\endgroup$
    – TRP
    Aug 17, 2023 at 14:59
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 17, 2023 at 15:24

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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