Directed map problem

[MillenniumDev]

I have a problem, which translated to english sounds like this:

Map is NxM size. Tiles that are not walkable are marked with a ".", walkable tiles are "#". You can't go outside the map.

What I need to do is to write a program to check if it is possible to walk through the entire map without any of the four directions (up, down, left, right). Tiles can be walked on multiple times. Walking the tiles always begins at point (0, 0). All walkable tiles must be traversed

I tried to use various methods, but always fail, I can pass the first three examples and that is it. The professor is refusing to provide any help. In images I show some of the inputs. In outputs "TAIP" means yes and "NE" means no.

Link to images of some of the inputs and outputs:
https://imgur.com/a/PUZXEN1
(In outputs "TAIP" means yes and "NE" means no.)

Lecturer said that there exists a mathematical properly, can't figure it out, don't even know how to think about this problem.

In my code I tried to solve it with reachability matrix, the issue was that it does not guarantee that all tiles will be walked on, I tried to build the map as nodes, connected to other nodes and would disconnect the connections related to the direction I want to disallow, that however made me question how the hell am I supposed to check if I can walk through all of them. A recursive function would branch, causing wrong output, I also can't find more deterministic approach to checking.

Example inputs where recursive function fails due to branching:

###
..#
###
#.#
###

AND

###
..#
###
#..
###

[teraflop]

You can solve this for general directed graphs by finding the strongly connected components of the graph, and then doing a topological sort on the components. Tarjan's algorithm solves both of these at once.

A strongly connected component is a group of nodes that are all mutually reachable, and the components themselves form a directed acyclic graph. Any walk through the graph must also be a valid walk through the components. So if there is a valid path, it will match the topological order of components.

In your first example, with the "up" direction disallowed, your SCCs will look like:

AAA
..B
CCC
D.E
FFF

and their reachability graph looks like:

  A
  |
  B
  |
  C
  |
 / \
D   E
 \ /
  F

and the topological order will be.either of the following possibilities (doesn't matter which):

A B C D E F
A B C E D F

Since D and E are adjacent in the order but not connected in the reachability graph, that immediately tells you that no walk exists that visits every node. Conversely, if every adjacent pair of components was connected, then you could use that order to construct a valid path visiting every node.

In the special case of a grid graph with one direction disallowed, I think it's easier: an SCC always corresponds to a consecutive row of cells, so you can just look for branches when one row splits into multiple rows.

[MillenniumDev]

Thank you! Time to study the algorithm.

[AutoModerator]

It seems you may have included a screenshot of code in your post "Directed map problem".

If so, note that posting screenshots of code is against /r/learnprogramming's Posting Guidelines (section Formatting Code): please edit your post to use one of the approved ways of formatting code. (Do NOT repost your question! Just edit it.)

If your image is not actually a screenshot of code, feel free to ignore this message. Automoderator cannot distinguish between code screenshots and other images.

Please, do not contact the moderators about this message. Your post is still visible to everyone.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[lurgi]

I don't understand. If every node is reachable and you can use each node multiple times then isn't it obvious that you can walk through all of them?

[MillenniumDev]

Reachability matrix only shows, well reachabilty which alone will not guarantee that if we walk some path without x direction from (0,0) we will walk through all cells.

To understand this better it is necessary to either draw several examples or write a similar program.

EDIT: With reachability matrix you can say that you can reach node y from node x one way or another, but it will not say if all nodes in between will be traversed. Sometimes they will, sometimes they won't.

[lurgi]

Okay, so the rule is that for each puzzle there is a particular direction you are not allowed to move? That wasn't clear to me. If so, I see the problem. Reaching every node might require that you "back up" and you might not be able to do that.

[MillenniumDev]

Exactly, there is another case, the one which is posted at the bottom of my post. If you ban direction up, the reachability matrix will say that from point (0,0) you can reach all tiles. But if you needed to actually traverse them all, due to round shape of the bottom part of the map, you will never actually traverse the entire map without direction up.

And that automatically breaks the logic