0
329
VistasFill 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;
}
2 Respuestas
Responde la pregunta0
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;
}
0
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