Line Tracing robot when sensors are behind the robot
You haven't seen an algorithm for this before because it's silly! :)  That's why dogs have their sensor package up front!

The problem is that by the time you have detected leaving the line, it is too late to correct for it.  Further, if your robot is anything like other line-following robots, when you rotate to get back on course the sensors will actually move in the wrong direction-- causing further confusion and sensing issues.

Your "back up and try again" method is on the right track, but not perfect.  Let me suggest a couple of things.  Keep in mind that what follows is pure speculation.  While I have written autonomous vehicle navigation software this might not be 100% right, or even be possible with your hardware.

What your robot needs is a map.  Basically, an internal model of the playing field (a.k.a. the floor with a line).  It also needs good enough dead-reckoning accuracy to be able to create this map and navigate within it.

Initially the map is empty and as the robot moves around it fills in the map with where it finds the line and where it doesn't.  If the robot drives off of the line it will have to back up to get back on it.  This maneuver might be a little more than a simple reverse.  It could include some spinning or whatever to help relocate the line easier and fill more of the map in.

At some point the map is complete enough to contain the entire line.  I assume that the line is one giant loop.  The robot can switch modes where it tries to navigate around the course based mostly on the map.  It uses the sensors to determine when it deviates from what was expected, and then corrects itself.  In this way it can compensate for some slippage of the wheels or inaccuracy in its dead-reckoning.

This type of software is non-trivial, but not impossible.  You will need a good amount of RAM to store the map, and your motors/wheels will need some rotary encoders on them.  But it can be a fun and rewarding project!