2
$\begingroup$

This question already has an answer here:

There is a house with 5 room and one door with every single wall as shown in following figure. You have to visit every door exactly once but there is a condition that you cannot cross the path.

enter image description here

I tried hard to get a path but i failed. Is there any solution exist ??

$\endgroup$

marked as duplicate by Bailey M, Mike Earnest, Philipp, CodeNewbie, Rand al'Thor Jul 1 '15 at 15:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I think it is a wicked problem. There is no solution $\endgroup$ – java guy Jul 1 '15 at 15:00
  • $\begingroup$ I also think so. May be there is a solution !!! $\endgroup$ – kavi temre Jul 1 '15 at 15:02
  • $\begingroup$ No, sadly there is not. Here you can find out why: Click me! $\endgroup$ – Cristian Marian Jul 1 '15 at 15:04
3
$\begingroup$

Assuming you can't walk through walls, you can only cross through a given door one time, and you have to cross through a door to "visit" it, this is impossible. Because...

enter image description here

Rooms 1, 2, and 4 have odd numbers of doors. Logically, if a room has an odd number of doors with our rules, if you start outside the room, you must end inside the room. Similarly, if you start inside the room, you must end outside of it. Draw some lines and you'll see what I mean -- no matter what, for each time you enter a room, you must leave it unless you are ending in that room.

Here's an image demonstrating this (left - start in, end out; right - start out, end in)

enter image description here

Because there are three different rooms that have odd numbers of doors, no matter where you start you logically need to end in multiple rooms to be able to solve the puzzle, making it impossible.

$\endgroup$
  • 1
    $\begingroup$ just read up on this on this page: en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg. there can only be zero or one odd-vertex nodes in the whole map for it to be traversable. this map has three odd nodes. $\endgroup$ – dfperry Jul 1 '15 at 15:13
  • $\begingroup$ @dperry zero or two, surely? $\endgroup$ – frodoskywalker Jul 1 '15 at 15:25
  • $\begingroup$ yes, typing without thinking again $\endgroup$ – dfperry Jul 1 '15 at 15:26
  • $\begingroup$ A graph with one odd-vertex node is also traversable, if you are sufficiently patient. $\endgroup$ – Anon Jul 1 '15 at 15:38
  • $\begingroup$ @Anon I am intrigued, please give an example of a traversable graph with a single odd-vertex node. $\endgroup$ – Taemyr Jul 2 '15 at 13:04
1
$\begingroup$

I don't think this is possible!

for every room, there should be an even number of doors in order to get in and out without crossing ( you have to get in through one door and out through the other). Which is not the case here!

$\endgroup$
  • 1
    $\begingroup$ There could be one or two rooms with odd numbers of doors -- if there was just one, it's easily solvable so long as you start or end in the odd room, if there are two, you must start in one of the odd rooms and end in the other one. $\endgroup$ – Curmudgeon Jul 1 '15 at 15:24

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