用 6 种颜色填充 6x6 网格，且相同颜色彼此不接触
Fill a 6x6 grid with 6 colors without same colors touching each other
我正在尝试使用 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;
}
一种看待这个问题的方法是在一棵树中搜索一条路径，其中每个节点都有 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，如果序列遇到死胡同，它可以return 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);
感谢您的建议！我试图找到一个与发布的解决方案平行的解决方案。现在使用这段代码，它工作正常：
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;
}
一个简单的方法是从有效的着色开始（例如，任何 6x6 拉丁方块都是有效的着色），然后他们通过找到一对可以交换的东西来混合它，然后交换它们。
一项改进（以提高混合速度，并防止算法卡住）是允许最多一个单元格无效（即：一个单元格如果被移除，其余单元格将保持有效着色）。如果没有无效单元格，则交换两个随机单元格（如果其中至少一个单元格在交换后有效）。如果有一个无效单元格，则选择该单元格和另一个要交换的随机单元格，假设再次交换至少使其中一个有效。再次重复很多次，只有在着色有效时才停止。
这个想法的实现（抱歉，不是 Javascript）在这里：https://go.dev/play/p/sxMvLxHfhmC
我正在尝试使用 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;
}
一种看待这个问题的方法是在一棵树中搜索一条路径，其中每个节点都有 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，如果序列遇到死胡同，它可以return 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);
感谢您的建议！我试图找到一个与发布的解决方案平行的解决方案。现在使用这段代码，它工作正常：
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;
}
一个简单的方法是从有效的着色开始（例如，任何 6x6 拉丁方块都是有效的着色），然后他们通过找到一对可以交换的东西来混合它，然后交换它们。
一项改进（以提高混合速度，并防止算法卡住）是允许最多一个单元格无效（即：一个单元格如果被移除，其余单元格将保持有效着色）。如果没有无效单元格，则交换两个随机单元格（如果其中至少一个单元格在交换后有效）。如果有一个无效单元格，则选择该单元格和另一个要交换的随机单元格，假设再次交换至少使其中一个有效。再次重复很多次，只有在着色有效时才停止。
这个想法的实现（抱歉，不是 Javascript）在这里：https://go.dev/play/p/sxMvLxHfhmC