Snow Blow My Driveway!

Question

There has recently been a big snow, and my driveway needs snow-blowing. If the snow-blower goes over some area that it has already snow-blowed, then that area will have snow blown onto it and need to be blown again. And of course, the snow-blower cannot start in the middle of the driveway, it needs to start from my garage, where it is stored.

More formally:

Your program takes a standard form of input as a string or multidimensional array that looks like the following:

XXXXOOOOXXXX
X          X
X          X
XXXXXXXXXXXX

X represents an area that cannot be snow-blowed, O represents an area where the snow-blower can be deployed, and empty spaces represent areas where there is snow. You can chose different values if you wish.

Your program must output something like the following:

XXXX*%OOXXXX
Xv<<<^<<<<<X
X>>>>>>>>>^X
XXXXXXXXXXXX

The snow-blower starts at the *. The * always points to the nearest non-garage space. The <,>,v, and ^ all represent pointers of where the next direction is. They point the snow-blower where to go. Once a pointer points to the %, the blower has re-arrived into the garage, and the whole driveway should be clear.

The snow blower must go over the whole driveway. The snowblower's path can never overlap itself. Impossible input must not be given.

Because I don't want to be outside any longer than I need to be, and not need to spend a lot of time typing, the program should be as short as possible. Shortest code wins!

Test Cases:

These test cases may have multiple correct answers. I have provided possible solutions below each test case.

Test case 1: The one given in the example.

Test case 2:

XOOOOOX
X     X
X     X
X     XXXXXXXX
X            X
X            X
XXXXXXXXXXXXXX

X*OOO%X
Xv>>>^X
Xv^<<<X
Xv>>>^XXXXXXXX
Xv^<<<<<<<<<<X
X>>>>>>>>>>>^X
XXXXXXXXXXXXXX

Test case 3:

XOOOOX
X    X
X    X
X  XXX
X    X
X    X
XXXXXX

XOO%*X
X>>^vX
X^v<<X
X^vXXX
X^>>vX
X^<<<X
XXXXXX

Test case 4:

XXXXXXXXXXXXX
O           X
O    X      X
O    X      X
O           X
XXXXXXXXXXXXX

XXXXXXXXXXXXX
*>>>>>>>>>>vX
Ov<v<Xv<<<<<X
Ov^v^X>>>>>vX
%<^<^<<<<<<<X
XXXXXXXXXXXXX

Answer 1

JavaScript (ES6), 346 310 299 298 297 296 283 bytes

f=(a,y=0,x=0)=>(a[y][x]?a[y][x]=='O'&&(a[y][x]='*',(g=w=>(w=a[y])&&w[x]&&(w[x]<'!'?g(w[x]='v',y++)||g(w[x++]='>',y--)||g(w[--x]='^',y--)||g(w[x--]='<',y++)||+(w[++x]=' '):w[x]=='O'&&!/ /.test(a)?w[x]='%':0))(y++)||g(y-=2)||g(y++,x++)||g(x-=2)||+(a[y][++x]='O'))||f(a,y,x+1):f(a,y+1))

<textarea id="tests">XXXXOOOOXXXX&#10;X          X&#10;X          X&#10;XXXXXXXXXXXX&#10;&#10;XOOOOOX&#10;X     X&#10;X     X&#10;X     XXXXXXXX&#10;X            X&#10;X            X&#10;XXXXXXXXXXXXXX&#10;&#10;XOOOOX&#10;X    X&#10;X    X&#10;X  XXX&#10;X    X&#10;X    X&#10;XXXXXX&#10;&#10;XXXXXXXXXXXXX&#10;O           X&#10;O    X      X&#10;O    X      X&#10;O           X&#10;XXXXXXXXXXXXX</textarea><br><button onclick="for(test of document.getElementById('tests').value.split('\n\n')){console.log(test);arr=test.split('\n').map(line=>line.split(''));f(arr);console.log(arr.map(line=>line.join('')).join('\n'))}">Run</button>

Quite hacky in some places, but I wanted to get the code out there. Input as a 2D character array, output by modifying said array.

Ungolfed version

This is the same exact algorithm, save for some truthy/falsy magic with +' ' being NaN being falsy (and some more), some golf variables and using ifs instead of ?:, || and &&.

f = (a, y = 0, x = 0) => {         // main function
  if (!a[y][x])                    // check for end of line
    return f(a, y + 1);            // end of line, recursively check next
  if (a[y][x] == 'O') {            // check for valid start position
    a[y][x] = '*';                 // set the start position
    function g() {                 // pathfinder function
      if (!a[y] || !a[y][x])       // check for out of bounds
        return 0;
      if (a[y][x] == ' ') {        // check for snow
        a[y][x] = 'v';             // set current cell to 'down'
        y++;                       // move position down
        if (g()) return 1;         // see if a valid route is found from there
        y--;                       // if not, reset position and try again
        a[y][x] = '>';             // repeat for other directions
        x++;
        if (g()) return 1;
        x--;
        a[y][x] = '^';
        y--;
        if (g()) return 1;
        y++;
        a[y][x] = '<';
        x++;
        if (g()) return 1;
        x++;
        a[y][x] = ' ';             // no route found, reset cell to snow
        return 0;
      }
      if (a[y][x] == 'O'           // check for valid exit
          && !/ /.test(a)) {       // and that no snow is left
        a[y][x] = '%';             // set the exit
        return 1;
      }
    }
    y++;                           // move a cell down from the start position
    if (g()) return 1;             // see if a valid route starts there
    y -= 2;                        // repeat for other directions
    if (g()) return 1;
    y++; x++;
    if (g()) return 1;
    x -= 2;
    if (g()) return 1;
    x++;
    a[y][x] = 'O';                 // no route found, continue on
  }
  return f(a, y, x + 1);           // check the next cell
}