frieze
@frieze

I made this short TAS a while back to tease something I've been kind of working on

After pages of notes I think I have finally convinced myself that finding an optimal TAS for solving Mario's Super Picross puzzles (not finding the solution but rather finding the inputs to carve out that solution on the screen) is NP-hard by a series of reductions to the classic Traveling Salesman Problem.

I don't want to spoil too much of it because I want to make a video about it, but essentially I can translate a Picross puzzle's solution into a graph that corresponds to button inputs that move the cursor across the board, and can find an optimal series of inputs by finding a path on this graph that is sort of a TSP variant: given a graph G and any number of disjoint subsets of G, find a path of minimal weight that visits at least one node of every subset.

I can reduce that to another TSP variant: given a graph G and a subset of G, find a path of minimal weight that visits every vertex in that subset. This is actually a pretty common problem that reduces to a non-returning TSP variant, where you don't have to start and stop at the same vertex. In this case I define the starting point (top left corner), but the end location is arbitrary.

Then to handle two players, I add a node P connecting the two starting positions of the two players (top left and bottom right), and then a node S that connects to every vertex so that it reduces to the classic TSP (finding a cycle). Then, instead of using a heuristic to find the minimal weighted cycle, I instead find the sum of the weights of edges between P and S (for player one), and between S and P (for player two). The heuristic would try to minimize the maximum of these two numbers, which corresponds to trying to get both players to pull equal weight, therefore ending the level quicker.

Yeah sure the biggest puzzles in the game might come down to solving TSP with >2000 nodes and over 2 million edges, but a reduction is a reduction!


Stevoisiak
@Stevoisiak

I discovered Picross speedruns and thoughy I might want to try TASing it. I found this while searching to see how the traveling salesman problem would apply to Picross.


You must log in to comment.

in reply to @frieze's post:

To be a bit pedantic, finding a (polynomial) reduction from Picross to TSP doesn't mean it's NP-hard—it just means it's in NP. It could still theoretically have a much easier solution than reducing it to TSP and solving that. The real test of whether a problem is NP-hard is if you can reduce an NP-complete problem to it.

Do you mean reduce an NP-hard problem to it? As in go the other direction? I am confused by the NP-complete because I am fairly convinced it's not in NP at all. Verifying that my picross maneuver is the fastest maneuver for a given puzzle would require checking all maneuvers, which is factorial time on the number of squares in the puzzle.

Basically right now with what I've got, if I was given a fast way to solve TSP, I could solve the picross maneuver fast. I suppose I would need a way to do the opposite--convert a TSP into a picross puzzle and claim if there was a fast way to maneuver that puzzle, that the original TSP could be solved fast?

Basically right now with what I've got, if I was given a fast way to solve TSP, I could solve the picross maneuver fast.

Right—this means the challenge is in NP, because NP is the class of all problems that are solvable by a nondeterministic Turing machine in polynomial time. Since TSP is in NP, and given a program that solves TSP you could easily solve Picropt (yuk yuk yuk), that means Picropt must be in NP.

I suppose I would need a way to do the opposite--convert a TSP into a picross puzzle and claim if there was a fast way to maneuver that puzzle, that the original TSP could be solved fast?

Exactly. Since all problems in NP can be polynomial-time reduced to TSP, this would prove that Picropt is also NP-complete.

As far as I know, TSP is NP-hard, not NP. NP problems aren't solvable in polynomial time, but answers can be verified in polynomial time. Answers to NP-hard problems can't even be verified in polynomial time. TSP is NP-hard because in order to verify a solution, you would essentially need to calculate the solution (non-polynomial) and compare answers.

To be clear, I've been talking about the TSP-optimization problem, not the TSP-decision problem. (Looking up stuff online it seems there is a lot of confusion between the two.)

TSP-decision (is there a path at least this good) is in NP because answering that question is still hard. But verifying an answer (yes/no) can be done in polynomial time.

It's the TSP-optimization problem that is NP-hard.

Yeah, I've been mixing up TSP-dec and TSP-opt here as well. But the underlying point remains: a reduction from Picropt to a very hard problem doesn't give you a lot of information about the bounds of how difficult Picropt is, only that it's no more difficult than TSP-opt.

"no one asked for this". On the contrary, I recently discovered Picross speedruns, thought I might want to try TASing it, and found this while searching to see how the traveling salesman problem would apply to Picross.