I have a problem with a puzzle game like pcross in which I have a nxn square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that row/col. The question is Exist an algorithm that tells me the maximum number of placed points (no interest where they are exactly placed) that runs in linear time? and what is?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ i don't understand your question. what are the placed points? $\endgroup$– JMPCommented Dec 3, 2015 at 17:54
-
$\begingroup$ If you see en.m.wikipedia.org/wiki/Discrete_tomography the problem is right that. Now the question is: exists an algorithm that say me the maximum number of admissible point (according to the rule) that runs in linear or near-linear time? I see erdos-gallai but works only with one sequence of integers. In this case I have two sequence (row and col) and they are bipartite. $\endgroup$– Steve Xibalba RivieccioCommented Dec 3, 2015 at 18:04
-
$\begingroup$ so like conceptispuzzles.com/index.aspx?uri=puzzle/pic-a-pix; but the problems there have a unique solution, and you want to know given U,V vectors how many solutions there are? $\endgroup$– JMPCommented Dec 3, 2015 at 18:15
Add a comment
|