javascript - 用 6 种颜色填充 6x6 网格，相同颜色不相互接触

Question

我正在尝试使用 p5.js (Javascript) 创建棋盘游戏
要设置 6 x 6 网格的游戏板，我必须用 6 种颜色填充网格，使水平或垂直接触的单元格不具有相同的颜色。并且所有 6 种颜色都必须在 6 个单元格中使用。
但现在我正在努力创建一个随机放置颜色但保持规则的算法。
我尝试从左上角开始，填充随机颜色。
然后我开始用不同的颜色填充左侧和底部的单元格。
问题是，当脚本想要填充最后几个单元格时，没有颜色可以使用(已经填充了 6 个单元格或者剩余的颜色是邻居)
例子:
仍然有两个单元格需要是红色的，但只剩下一个地方是红色的(在白色下):

//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

一种看待这种情况的方法是在树中搜索一条路径，其中每个节点都有 6 个可能的子节点，用于接下来可能出现的六种颜色。最初忽略所有约束，您随机选择其中一个 36 次，并拥有您的展示位置顺序。
使用递归函数(稍后会有用)，不受约束的搜索将如下所示:

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

接下来，我们需要消除会违反问题约束的选择:

左边的单元格颜色不同，即 chosenColour !== sequenceSoFar[nextIndex-1]

上面的单元格颜色不同，即 chosenColour !== sequenceSoFar[nextIndex-6]

颜色在序列中尚未出现六次，即 sequenceSoFar.filter((element) => element === chosenColour).length < 6

如果所选颜色不符合这些要求，我们会将其从候选列表中删除并重试:

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

到目前为止，这与您的原始代码存在相同的问题 - 如果它遇到死胡同，它不知道该怎么做。为了解决这个问题，我们可以使用 backtracking algorithm .这个想法是，如果我们用完职位 n 的候选人。 , 我们拒绝位置 n-1 的选择并尝试不同的。
而不是 placeNext ，我们需要我们的函数是 tryPlaceNext , 可以返回 false如果序列遇到死胡同:

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