Ensure neighbor nodes do not share same value

I'm creating a game- a grid of colors that the player can navigate either up, down, left, or right. If the direction says "go to red square", the player must do this.

I am generating a grid of randomized colors. Of course, this means it can't be totally random because I need to ensure the player can't have more than one of the same colors as a neighbor to choose from.

This image describes it: The grey cell is the player start location... the north, east, and south neighbors all share same color... this is bad.

The grid is a grid of color tile images. Therefore the tile "colors" shouldn't be changed after I generate the grid. During grid creation, each new cell, I create a random index, and set the cell color equal to colorsObject[randomIndex] to ensure a random color is assigned

To try and solve this, I attempt to store the last used color... and on the next iteration of cell creation, I remove that stored last used color from the colors object (need an object for my own reasons, otherwise would use array), set the random to choose from shortened list of colors, and use that color. Then add that lastUsedColor back to the object:

    var lastUsedColor = "";
    for (var row = 0; row <= totalRows; row++) {
        this.containerOfGrids[i][row] = []; 
        for (var col = 0; col <= totalCols; col++) {                
            if (lastUsedColor != "") delete this.colors[lastUsedColor];
            var colorIndex = Math.floor(Math.random() * (Object.keys(this.colors).length - 0) + 0);
            var keyName = Object.keys(this.colors)[colorIndex]; 
            image = keyName;

            if (lastUsedColor != "") this.colors[lastUsedColor] = lastUsedColor;
            lastUsedColor = keyName;

            ...then code to generate cell image entity

This works on a row-by-row basis (meaning 2 neighboring columns won't share the same color), but on the next row, there can be neighboring nodes with same colors.

My next thought was to first generate all tile images with colors... then iterate again to check for neighboring colors... if there are, swap out for a new image. But I wanted to get this done on generate of set of tiles without having to do another nested for loop.