randomIsNotRandom's blog

Is this NP HARD? Is it possible to solve in any complexity?
By randomIsNotRandom, history, 10 months ago, In English

we have some n*m table(labyrinth) and two positions first is the position of the player and the second is the position of the Robot(R) the player wants to reach the red doors. player and monster cannot stay in the same square at the same time. both should play optimal always the player do the first move We need to determine whether player can win

Here answer is YES

This is not a standard bfs problem
example Explanation

the player can go up whereas the Robot doesn't know where to go (left or right) if the Robot hurries to get to one end the player can easily go to the other end

I want to know if it is possible to solve this problem

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by randomIsNotRandom (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by randomIsNotRandom (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

NO

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try to rephrase the task as such: let graph node be the tuple (player position, robot position, turn parity) and edge be the possible move.

Then, you need to topologically sort the graph nodes. Mark the nodes where player is at red doors as winning; mark the nodes where it is player's turn and player can reach winning node as winning; mark the nodes where it is robot's turn and there is possibility to reach losing node as losing.

The algorithm has polynomial bound on complexity and is thus P.

Then, you'll only have problems if going in loops becomes optimal somewhy.

→ Reply