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

Question

我正在尝试用p5.js (Javascript)创建一个棋盘游戏。

要设置游戏板，它是一个6乘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

谢谢你的建议！我试图找到一个与发布的解决方案平行的解决方案。现在使用这段代码，它运行得很好：

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 2

一种看待这一点的方法是寻找一条穿过树的路径，在树中，每个节点都有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);

​

到目前为止，这与原始代码存在相同的问题--如果它碰到了死胡同，它就不知道该怎么做了。要解决这个问题，我们可以使用回溯算法。这样做的想法是，如果没有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);

​

Answer 3

一种简单的方法是从一个有效的着色开始(例如，任何6x6的拉丁方格都是有效的着色)，然后他们通过找到一对可以交换的东西混合起来，并交换它们。

一个改进(以提高混合速度，并防止算法被卡住)是允许最多一个单元格无效(即，如果删除一个单元格，则剩下的单元格将处于有效的着色状态)。如果没有无效的单元格，那么交换两个随机单元，如果其中至少有一个在交换后是有效的。如果有一个无效的单元格，选择这个单元格和另一个要交换的随机单元，假设再次交换至少有一个单元格有效。同样，重复大量的时间，只有在着色有效时才停止。

这个想法的一个实现(抱歉，不是Javascript)在这里：https://go.dev/play/p/sxMvLxHfhmC