WordPress Rewrite rule is not working

In the tags of your answer there is <plugins> so I think you are trying to add custom rewrite rules from a plugin.

In your question you say something about page template that is (generally) a theme-related matter.
Of course you can create rewrite rules from a plugin and use them for a page template defined in a theme, but probably is not a good idea: your plugin functionalities will depend on theme.

Moreover, if you create a page template than you have to create a page, assign the page template and use a defined slug or your plugin rewrite rules will not work.
So your plugin also depend from content, and this, again, is not a good idea.

So, how make your plugin functionalities indipendent from page templates in theme and from content but mantaining wordpress standards and functionalities?

A method is create a file in the plugin folder and redirect the rewrite rule to the url of this file instead to index.php.
Doing so, if you need wordpress environment you need to manual require the file wp_load.php that resides on the root of worpress installation. But this path must be hardcoded and a lot of times this is not a good idea and can bring problems when migrating server. In addition this is a very bad idea if you plan to distribuite your plugin.

There is another solution?

For a plugin I developed I’ve used a sort of ‘virtual page’ where redirect the requests.

First of all, in the main plugin file, we define the virtual slug for the page.
Is a good idea create a setting page for the plugin where this slug can be changed, but for semplicity I will put it in a constant:

define('MY_VIRTUAL_PAGENAME', 'a-strange-slug-for-places-to-visit-fake-page');

After that, in the same file, we define the custom rewrite rules and register the custom query vars:

add_action('init', 'add_my_rules');

function add_my_rules() {
  add_rewrite_rule('state/([^/]+)/([^/]+)/page/([^/]+)', 'index.php?pagename=" . MY_VIRTUAL_PAGENAME . "&name_state=$matches[1]&arg_second=$matches[2]&paged=$matches[3]', 'top');
  add_rewrite_rule('state/([^/]+)/([^/]+)', 'index.php?pagename=" . MY_VIRTUAL_PAGENAME . "&name_state=$matches[1]&arg_second=$matches[2]', 'top');
}

add_filter( 'query_vars', 'add_my_vars' );

function add_my_vars( $vars ) {
  $vars[] = 'name_state';
  $vars[] = 'arg_second';
  return $vars;
}

Now we have to flush rewrite rules. In your code you do this on init, so rules are flushed for every page request: this is absolutely not a good idea. We use the registration hook to run this only one time:

register_activation_hook( __FILE__, 'my_flush_rewrite_rules' );

function my_flush_rewrite_rules() {
  add_my_rules();
  flush_rewrite_rules();
}

At this moment when a particular url is required we tell wordpress to load a page that have a slug we saved on the constant MY_VIRTUAL_PAGENAME, but this page does not exist.

So now we cheat wordpress and make it shows our virtual page.

add_action( 'pre_get_posts', 'show_places_to_visit', 1 );

function show_places_to_visit( $wp_query ) {
  $pagename = isset($wp_query->query['pagename']) ? $wp_query->query['pagename'] : NULL;
  if ( ! is_admin() && is_main_query() && $pagename == MY_VIRTUAL_PAGENAME ) {

    // get our custom vars
    $name_state = $wp_query->get('name_state');
    $arg_second = $wp_query->get('arg_second');
    $paged = $wp_query->get('paged') ? : 1;

    // now I require the file that contain our business logic
    require( plugin_dir_path(__FILE__) . 'places-to-visit.php' );

    exit(); // stop default wordpress behavior
  }
}

With the above code we run a function before the wp main query is fired. In this function we check if the pagename requested (if exists) is the one we saved in the constant and if so we require a file called places-to-visit.php that is located in the same folder of main plugin file.

Now we have to just create file places-to-visit.php and there we have all wordpress environment and we can use as we like.

If you plan to run a WP_Query in this file, probably this is one of the rare case in which is better make use of query_posts instead of using a WP_Query instance: in this way you will replace the original main query that is not useful because it is just a fake query.

The following is just an example for places-to-visit.php file, I bet you can do something more useful in it:

/**
* in places-to-visit.php file I can simply use the variables defined in
* show_places_to_visit() function in main plugin file
*/
$args = array(
  'post_type' => 'places',
  'posts_per_page' => $arg_second,
  'category_name' => $name_state,
  'paged' => $paged
);
query_posts($args);

/**
* If in your theme is present a file called places-to-visit.php or a file called 
* archive-places it will be used to handle the query.
* If not you have to output the page content from plugin.
*/

if ( locate_template( array('places-to-visit.php','archive-places.php'), true ) == '' ) {

  /**
  * Code that generate page content goes here.
  * If you want, you can use template functions like
  * get_header(); get_footer(); get_template_part(); and so on.
  */

}