Fill a 6x6 grid with 6 colors without same colors touching each other

I'm trying to create a board game with p5.js (Javascript)

To set up the game board which is a 6 by 6 grid, I have to fill the grid with 6 colors in a way that no horizontal or vertical touching cells have the same color. And all 6 colors have to be used in 6 cells.

But now I'm struggling a bit creating an algorithm that places the colors randomly but keeping the rules.

I tried to start at the top left corner, filling with a random color. Then I start to fill the cell to the left and the bottom with a different color.

The problem is, that when the script wants to fill the last few cells, there are no colors left to use (either already 6 cells filled or a remaining color is a neighbor)

Example: Still two cells need to be red, but only one place is left for red (under white):

//fill placedColors Array with zeros
placedColors = [];
for(let i=0; i<6; i++) {
    placedColors[i] = 0;
}

//fill allIndexes Array with indizies to keep control of visited cells
let allIndexes = [];
for(let i=0; i<36; i++) {
    allIndexes.push(i);
}

//build board
//when I set the limit to 36 the script runs forever because no solution is found
for(let i=0; i<33; i++) {
    fillCells(i);
}

function fillCells(index) {
    //get top and left color
    let topColor = false;
    //index is in the second row
    if(index >= 6) {
        topColor = cells[index-6].color;
    }
    
    let leftColor = false;
    //index is not in the first column
    if(index % 6 > 0 && index > 0) {
        leftColor = cells[index-1].color;
    }
    
    if(allIndexes.indexOf(index) > -1) {
        cells.push(new Cell(index, pickColor(topColor, leftColor)));
    }
    
    //mark index as visited
    var allIndexesIndex = allIndexes.indexOf(index);
    if (allIndexesIndex !== -1) {
        allIndexes.splice(allIndexesIndex, 1);
    }
}

function pickColor(invalidColor1,invalidColor2) {
    let colorFound = false;
    do {
        randColor = floor(random(6));
        
        if(placedColors[randColor] < 6 && randColor!=invalidColor1 && randColor!=invalidColor2) {
            placedColors[randColor]++;
            colorFound = true;
        }
    } while(!colorFound);
    
    return randColor;
}

Thanks for your suggestions! I tried to find an own solution parallel to the posted one. Now with this code, it works fine:

function buildBoard() {
    cells = [];

    for(let i=0; i<gameSize; i++) {
        placedColors[i] = 0;
    }
    
    for(var i=0; i<gameSize*gameSize; i++) {
        cells.push(new Cell(i, pickColor()));
    }

    do {
        invalidFields = [];
        findInvalidFields();
        
        if(invalidFields.length > 0) {
            let cell1index = Math.floor(Math.random() * invalidFields.length);
            cell1 = invalidFields[cell1index];
            //check, if cell in different color available
            let otherColorAvailable = false;
            for(cell of invalidFields) {
                if(cell.color != cell1.color) {
                    otherColorAvailable = true;
                    break;
                }
            }
    
            if(otherColorAvailable) {
                //pick invalid cell
                do {
                    let cell2index = Math.floor(Math.random() * invalidFields.length);
                    cell2 = invalidFields[cell2index];
                } while (cell2.color == cell1.color)
            } else {
                //pick random cell
                do {
                    let cell2index = Math.floor(Math.random() * cells.length);
                    cell2 = cells[cell2index];
                } while (cell2.color == cell1.color)            
            }
            
            //switch colors of cells
            let tempColor = cell1.color;
            cell1.color = cell2.color;
            cell2.color = tempColor;
        }
    } while (!checkStartField());   
}

function findInvalidFields() {
    for(let index=0; index<cells.length; index++) {
        let thisColor = cells[index].color;

        //right
        if(index%gameSize < gameSize-1 && cells[index+1].color == thisColor) {
            if(invalidFields.indexOf(cells[index+1])) {
                invalidFields.push(cells[index+1]);
            }
        }
        
        //bottom
        if(index < gameSize*gameSize-gameSize && cells[index+gameSize].color == thisColor) {
            if(invalidFields.indexOf(cells[index+gameSize])) {
                invalidFields.push(cells[index+gameSize]);
            }
        }
    }
}

function checkStartField() {
    for(let index=0; index<cells.length; index++) {
        let thisColor = cells[index].color;
        
        //top
        if(index >= gameSize && cells[index-gameSize].color == thisColor) {
            //console.log(index+'top');
            return false;
        }
        
        //right
        if(index%gameSize < gameSize-1 && cells[index+1].color == thisColor) {
            //console.log(index+'right');
            return false;
        }
        
        //bottom
        if(index < gameSize*gameSize-gameSize && cells[index+gameSize].color == thisColor) {
            //console.log(index+'bottom');
            return false;
        }
        
        //left
        if(index%gameSize > 0 && cells[index-1].color == thisColor) {
            //console.log(index+'left');
            return false;
        }
    }
    
    return true;
}