arcpy - Minimising number of dynamic pages to map scattered points using ArcGIS Desktop?

From time to time I have to produce mapbook to show points of interest. First step to create pages, using regular mesh:

I don't like the solution because a) there are some pages with single points (e.g. page 25) sitting on the edge and b) too many pages.

First issue is easy to fix using code, - move rectangle of page extent to center of relevant points extent:

I still don't like it, it looks very crowded because number of pages remains the same. Remember, they all end up being actual A3 paper pages in multiple copies of report !.

So I've cooked a code that reduce number of pages. In this example from 45 to 34.

I am not sure if this the best result that can be achieved,

What is the best strategy (pseudo code, publication, Python library) to shuffle through points in order to minimise number of given size rectangles to capture all of the points? Surely, someone discovered it in game theory, military art or fishing industry

This is update to original question:

This shows real extent and page size required:

Closer zoom showing 10 out of 164 pages:

Sample Point Feature Class

Rectangle size can change as soon as it stays within the limits, i.e. smaller is fine.