enum Dir {
    NORTH, SOUTH, EAST, WEST
}

class Cell {
    public Map<Dir, Cell> neighbors = Collections
            .synchronizedMap(new EnumMap<Dir, Cell>(Dir.class));
    public Map<Dir, Boolean> walls = Collections
            .synchronizedMap(new EnumMap<Dir, Boolean>(Dir.class));

    public boolean Visited;

    public Cell() {
        Visited = false;
        for (Dir direction : Dir.values()) {
            walls.put(direction, true);
        }
    }

    // Randomly select an unvisited neighbor and tear down the walls
    // between this cell and that neighbor.
    public Cell removeRandomWall() {
        List<Dir> unvisitedDirections = new ArrayList<Dir>();
        for (Dir direction : neighbors.keySet()) {
            if (!neighbors.get(direction).Visited)
                unvisitedDirections.add(direction);
        }

        Random randGen = new Random();
        Dir randDir = unvisitedDirections.get(randGen
                .nextInt(unvisitedDirections.size()));
        Cell randomNeighbor = neighbors.get(randDir);

        // Tear down wall in this cell
        walls.put(randDir, false);
        // Tear down opposite wall in neighbor cell
        randomNeighbor.walls.put(randDir, false); // <--- instead of randDir, it needs to be it's opposite.

        return randomNeighbor;
    }
}

enum Dir {
    NORTH,
    SOUTH,
    EAST,
    WEST;

    public Dir opposite() {
        switch(this) {
            case NORTH: return Dir.SOUTH;
            case SOUTH: return Dir.NORTH;
            case EAST: return Dir.WEST;
            case WEST: return Dir.EAST;
            default: throw new IllegalStateException("This should never happen: " + this + " has no opposite.");
        }
    }
}

randomNeighbor.walls.put(randDir.opposite(), false);

public enum Dir {
   NORTH { @Override public Dir opposite() { return SOUTH; }},
   EAST  { @Override public Dir opposite() { return WEST;  }},
   SOUTH { @Override public Dir opposite() { return NORTH; }},
   WEST  { @Override public Dir opposite() { return EAST;  }},
   ;

   abstract public Dir opposite();
}

public enum Direction
{
    NORTH,EAST,SOUTH,WEST;

    public Direction opposite()
    {
        return Direction.values()[ (this.ordinal() + 2) & 3 ];
    }
}