Gerrymandering can be made impossible by using a specific unchanging district-drawing rule that has no human input. Typically it’s automated, but not necessarily.  I’ll briefly describe two: Shortest-Splitline, and Band-Rectangle.

Shortest-Splitline:

Divide the state into two parts, each with a whole number of district populations, and with those two whole numbers as nearly equal to eachother as possible.  Do so in the way that uses the shortest possible straight dividing-line. I’ll call that process “halving”.  Then halve those two halves. Continue repeating the halving until none of the resulting subdivisions contain more than one district.

What I mean, above, by a straight line is a great-circle on a reference-sphere approximation of the Earth (an assumed exactly spherical earth). That line is also a straight line on a gnomonic projection based on that reference sphere.  A great circle on a sphere is the intersection of that sphere with a plane passing through the sphere’s center.

Band-Rectangle:

Map the state, on any map projection. A cylindrical projection would be best, but any will do.

Definitions:

Lines and measurements referred to are lines and measurements on the map. “Horizontal” means in some certain unchanging pre-decided direction (at least roughly) east-west on the map. “Vertical” means perpendicular to horizontal.  “Top” or “Topmost” means most northerly in the vertical dimension. “Bottom” or “bottom-most” means the opposite.  “District population” (sometimes abbreviated “district”) means a population of the size intended for districts. That’s the state  population divided by the number of districts. Divide the state into bands, and the bands into districts as follows:

Starting at the topmost end of the state, successively draw each band by drawing a horizontal straight line on the map, to define the bottom edge of the band. The vertical position of that horizontal line is chosen so that: 1) The band contains a whole number of districts; and 2) When the band is divided into districts, by vertical straight lines, the following quantity will be as close to 1 as possible:

The number of districts in the band, multiplied by the average of the band’s greatest and least vertical measurements, divided by the average of the lengths of the band’s top and bottom straight lines.  Continue till the desired number of districts have been drawn, and the entire state is districted. Those two things will happen at the same time.

Effects of some map projections on the state’s internal district boundaries: 

If the map on which the band-rectangle districting is based is cylindrical, then the internal district boundaries will all be either north-south or east-west. They’ll all be parallels or meridians.  If the map on which the band-rectangle districting is based is gnomonic, then the internal district boundaries will all be great circles (defined above) on an assumed spherical Earth.Those lines will be nearly identical with straight lines as measured on the Earth.

Shortest-splitline is due to Warren Smith. Band-rectangle is my proposal. But I don’t claim either of those proposals was never proposed before. As simple and obvious as they are, they probably have been proposed before.  Shortest-Splitline is more briefly defined. Band-Rectangle is much easier to implement, and needn’t require a computer.