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

Question

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;
}

Answer 1

One way to look at this would be as searching for a path through a tree where each node has 6 possible children for the six colours which could come next. Ignoring all the constraints initially, you pick one of these at random 36 times, and have your order of placements.

Using a recursive function (which will be useful in a moment), an unconstrained search would look like this:

function randomChoice(list) {
  return list[Math.floor(Math.random() * list.length)];
}

function placeNext(sequenceSoFar) {
    const availableColours = [0,1,2,3,4,5];
    let chosenColour = randomChoice(availableColours);
    sequenceSoFar = [...sequenceSoFar, colourToAdd];
    
    if ( sequenceSoFar.length == 36 ) {
        // Completed sequence!
        return sequenceSoFar;
    }
    else {
        // Recurse to make next choice
        return placeNext(sequenceSoFar);
    }
}
 
// Start with an empty array
let sequence = placeNext([]);
console.log(sequence);

Next, we need to eliminate choices that would violate the constraints of the problem:

• The cell to the left isn't the same colour, i.e. chosenColour !== sequenceSoFar[nextIndex-1]
• The cell above isn't the same colour, i.e. chosenColour !== sequenceSoFar[nextIndex-6]
• The colour doesn't already occur six times in the sequence, i.e. sequenceSoFar.filter((element) => element === chosenColour).length < 6

If the chosen colour doesn't meet these requirements, we remove it from the list of candidates and try again:

function randomChoice(list) {
  return list[Math.floor(Math.random() * list.length)];
}

function newColourIsValid(sequenceSoFar, chosenColour) {
   // We haven't added the next colour yet, but know where it *will* be
   let nextIndex = sequenceSoFar.length;
   
   return (
       // The cell to the left isn't the same colour
       ( nextIndex < 1 || chosenColour !== sequenceSoFar[nextIndex-1] )
       &&
       // The cell above isn't the same colour
       ( nextIndex < 6 || chosenColour !== sequenceSoFar[nextIndex-6] )
       &&
       // The colour doesn't already occur six times in the sequence
       sequenceSoFar.filter((element) => element === chosenColour).length < 6
   );
}

function placeNext(sequenceSoFar) {
    let availableColours = [0,1,2,3,4,5];
    let chosenColour;
    
    do {
        // If we run out of possible colours, then ... panic?
        if ( availableColours.length === 0 ) {
            console.log(sequenceSoFar);
            throw 'No sequence possible from here!';
        }
    
        chosenColour = randomChoice(availableColours);
        
        // Eliminate the colour from the list of choices for next iteration
        availableColours = availableColours.filter((element) => element !== chosenColour);
    } while ( ! newColourIsValid(sequenceSoFar, chosenColour) );       

    sequenceSoFar = [...sequenceSoFar, colourToAdd];

    if ( sequenceSoFar.length == 36 ) {
        // Completed sequence!
        return sequenceSoFar;
    }
    else {
        // Recurse to make next choice
        return placeNext(sequenceSoFar);
    }
}
 
// Start with an empty array
let sequence = placeNext([]);
console.log(sequence);

So far, this has the same problem as your original code - if it hits a dead end, it doesn't know what to do. To solve this, we can use a backtracking algorithm. The idea is that if we run out of candidates for position n, we reject the choice at position n-1 and try a different one.

Instead of placeNext, we need our function to be tryPlaceNext, which can return false if the sequence hits a dead end:

function randomChoice(list) {
  return list[Math.floor(Math.random() * list.length)];
}

function newColourIsValid(sequenceSoFar, chosenColour) {
   // We haven't added the next colour yet, but know where it *will* be
   let nextIndex = sequenceSoFar.length;
   
   return (
       // The cell to the left isn't the same colour
       ( nextIndex < 1 || chosenColour !== sequenceSoFar[nextIndex-1] )
       &&
       // The cell above isn't the same colour
       ( nextIndex < 6 || chosenColour !== sequenceSoFar[nextIndex-6] )
       &&
       // The colour doesn't already occur six times in the sequence
       sequenceSoFar.filter((element) => element === chosenColour).length < 6
   );
}

function tryPlaceNext(sequenceSoFar, colourToAdd) {
    let availableColours = [0,1,2,3,4,5];
    
    if ( ! newColourIsValid(sequenceSoFar, colourToAdd) ) {
        // Invalid choice, indicate to caller to try again
        return false;
    }
    
    // Valid choice, add to sequence, and find the next
    sequenceSoFar = [...sequenceSoFar, colourToAdd];
    
    if ( sequenceSoFar.length === 36 ) {
        // Completed sequence!
        return sequenceSoFar;
    }
    
    while ( availableColours.length > 0 ) {
        // Otherwise, pick one and see if we can continue the sequence with it
        let chosenColour = randomChoice(availableColours);
        
        // Recurse to make next choice
        let continuedSequence = tryPlaceNext(sequenceSoFar, chosenColour);
        
        if ( continuedSequence !== false ) {
            // Recursive call found a valid sequence, return it
            return continuedSequence;
        }
        
        // Eliminate the colour from the list of choices for next iteration
        availableColours = availableColours.filter((element) => element !== chosenColour);
    }

    // If we get here, we ran out of possible colours, so indicate a dead end to caller
    return false;
}
 
// Root function to start an array with any first element
function generateSequence() {
    let availableColours = [0,1,2,3,4,5];
    let chosenColour = randomChoice(availableColours);
    return tryPlaceNext([], chosenColour);
}

let sequence = generateSequence();
console.log(sequence);

Answer 2

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;
}

Answer 3

An easy approach is to start with a valid coloring (for example, any 6x6 latin square is a valid coloring) and them mix it up by finding a pair of things that can be swapped, and swap them.

An improvement (to increase mixing speed, and to prevent the algorithm getting stuck) is to allow at most one cell to be invalid (ie: one cell which if removed leaves the remainder in a valid coloring). If there's no invalid cell, then swap two random cells if at least one of them will be valid after the swap. And if there's one invalid cell, pick that cell and one other random cell to be swapped, assuming again swapping leaves at least one of them valid. Again repeat lots of time, stopping only when the coloring is valid.

An implementation of this idea (sorry, not Javascript) is here: https://go.dev/play/p/sxMvLxHfhmC