Two-Dimensional Array Searching Algorithm Optimisation

I have been given a "Sand box" of variable length and width. I've been given instructions to find a "shovel" of static size, which may be oriented either horizontally or vertically. I implement the following algorithm in order to search the least amount of times to find one valid location (one which corresponds to a "part of the object") in the grid:

found = false;
nShift = 0;
shovelSize = 4;
for(int i = 0; i < SandBoxRows; i++) {
    for(int j = 0; j < SandBoxColumns; j+=shovelSize) {
        found = probeSandBoxTwo(('A' + i), (j + 1 + nShift));
    }

    if(nShift >= shovelSize - 1 || nShift > SandBoxColumns) {
        nShift = 0;
    } else {
        nShift++;
    }
}

In this case, the "Sand box" will be tested by the function as described below.

I completely recreate this scenario with a "Sand box" whose size is fixed (though easily manipulated) whose shovel is still randomly placed and oriented within the following code:

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

const int ROW = 12;
const int COL = 16;
char sandbox[ROW][COL];

bool probeSandBoxTwo(char c, int i);
void displayResults(int sCount, bool found, int x, int y);
void displaySandbox();
void displaySearchPattern();
void fillSandbox();
void placeShovel();

int main() {
    fillSandbox();
    placeShovel();
    displaySandbox();

    //define your variables here
    bool found;
    int nShift,
        sCount,
        shovelSize,
        x,
        y;


    found = false;
    nShift = 0;
    shovelSize = 4;
    sCount = 0;
    for(int i = 0; i < ROW && !found; i++) {
        for(int j = 0; j < COL && !found; j+=shovelSize) {
            found = probeSandBoxTwo(('A' + i), (j + 1 + nShift));
            x = i;
            y = j + nShift;
            sCount++;
            cout << "Search conducted at (" << i << ", " << (j + nShift) << ")" << endl;
        }

        if(nShift >= shovelSize - 1 || nShift > ROW) {
            nShift = 0;
        } else {
            nShift++;
        }
    }
    displayResults(sCount, found, x, y);
    displaySearchPattern();
}

bool probeSandBoxTwo(char c, int i) {
    if(sandbox[c-'A'][i-1] == 'X') {
        return true;
    } else {
        return false;
    }
}

void displayResults(int sCount, bool found, int x, int y) {
    cout << endl;
    cout << "Total searches: " << sCount << endl;
    cout << endl;
    if(found) {
        cout << "Shovel found at coordinates: (" << x << ", " << y << ")" << endl;
    }
}

void displaySandbox() {
    cout << "  ";
    for(int i = 0; i < COL; i++) {
        cout << (i % 10); //show index numbers [col]
    }
    cout << endl;
    for(int i = 0; i < ROW; i++) {
        cout << (i % 10) << " "; //show index numbers [row]
        for(int j = 0; j < COL; j++) {
            cout << sandbox[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

void displaySearchPattern() {
    int nShift = 0;
    int shovelSize = 4;

    cout << endl << "  ";
    for(int i = 0; i < COL; i++) {
        cout << (i % 10); //show index numbers [col]
    }
    cout << endl;
    for(int i = 0; i < ROW; i++) {
        cout << (i % 10) << " "; //show index numbers [row]
        for(int j = 0; j < COL; j++) {
            if(!((j + nShift) % shovelSize)) {
                cout << 'o';
            } else {
                cout << '.';
            }
        }

        if(nShift >= shovelSize - 1 || nShift > COL) {
            nShift = 0;
        } else {
            nShift++;
        }
        cout << endl;
    }
}

void fillSandbox() {
    for(int i = 0; i < ROW; i++) {
        for(int j = 0; j < COL; j++) {
            sandbox[i][j] = '.';
        }
    }
}

void placeShovel() {
    srand(time(NULL));
    int shovelRow,
        shovelCol,
        shovelSize = 4;
    if(rand() % 2) {
        //horizontal
        shovelRow = rand() % ROW + 1;
        shovelCol = rand() % (COL - (shovelSize - 1)) + 1;
        for(int i = shovelCol - 1; i < shovelSize + (shovelCol - 1); i++) {
            sandbox[shovelRow - 1][i] = 'X';
        }
    } else {
        //vertical
        shovelRow = rand() % (ROW - (shovelSize - 1)) + 1;
        shovelCol = rand() % COL + 1;
        for(int i = shovelRow - 1; i < shovelSize + (shovelRow - 1); i++) {
            sandbox[i][shovelCol - 1] = 'X';
        }
    }
}

In this code, I also graphically display the pattern (when run) with which my algorithm searches.

My questions are: is this truly the optimal search pattern for such a scenario, is my implementation correct, and if so, why might I be having incorrect results returned?

A given test driver reports the following results:

The source code for this result (and its test driver).