CODEWITHSUNDEEP
javascriptp5.js
maratom
maratom

Reputation: 47

3 Coloring two dimensional array with javascript

I'm trying to paint figures with 5 cells in three colors.

5 x 5 rectangular

Now, they are just colored in different colors. But, I'm trying to paint them in only three colors such as red, blue, yellow. I think this is similar with Four color theorem, but I have a problem with implementing it.

let board = [
  [1,1,2,2,2],
  [1,3,3,2,2],
  [1,3,3,4,4],
  [1,3,4,4,4],
  [5,5,5,5,5]
] // set board

let w = 30 // width

function setup() {
  createCanvas(500, 500);

  // loop through every element in array a
  for (let i = 0; i < 5; i++) {

    // loop through every element in array a[i]
    for (let j = 0; j < 5; j++) {
      fill("white")
      rect(i * w, w * j, w, w);
    }
  }

}

function draw(){

  for(let i =0; i< 5; i++){
      for(let j =0; j< 5; j++){
        if(board[i][j] == 1){
          fill("red")
          rect(i * w, w * j, w, w);
        }

        if(board[i][j] == 2){
          fill("blue")
          rect(i * w, w * j, w, w);
        }

        if(board[i][j] == 3){
          fill("yellow")
          rect(i * w, w * j, w, w);
        }

        if(board[i][j] == 4){
          fill("green")
          rect(i * w, w * j, w, w);
        }

        if(board[i][j] == 5){
          fill("orange")
          rect(i * w, w * j, w, w);
        }
    }
  } 
}

I was testing size 15 x 15 and tried to compare lines one by one, but I don't think it's right. For now, I'm testing it in small rectangle, how should I implement this? Any helps would be appreciated.

Upvotes: 2

Views: 689

Answers (1)

Etienne Ott
Etienne Ott

Reputation: 676

Just for clarification, in summary the four color theorem states that four colors are sufficient for coloring 2D maps with some additional constraints on what is considered a border. It doesn't correspond to an algorithm to determine a coloring.

Now, a coloring works on regions that border each other, not so much on individual cells. However the cells are necessary to figure out these borders. So the first step is to calculate an adjacency matrix from the cells on the board. This is as simple as checking to which region each of the four neighbors of each cell belongs. There is a necessary middle step to check if the current cell is at the side or corner of the board.

let SIZE = 5
let regions = {}
for (let i = 0; i < SIZE; i++) {
    for (let j = 0; j < SIZE; j++) {
        region = board[i][j]
        if (region not in regions) {regions[region] = {}}
        if (i > 0) {
            if (board[i-1][j] != region) {
                regions[region][board[i-1][j]] = true
            }
        }
        if (i < SIZE - 1) {
            if (board[i+1][j] != region) {
                regions[region][board[i+1][j]] = true
            }
        }
        if (j > 0) {
            if (board[i][j-1] != region) {
                regions[region][board[i][j-1]] = true
            }
        }
        if (j < SIZE - 1) {
            if (board[i][j+1] != region) {
                regions[region][board[i][j+1]] = true
            }
        }
    }
}

Now regions tells you which neighbors each region has. One way to get a coloring is to consider this a constraint satisfaction problem and solve it by keeping track of possible values for each region, take a guess at a color for a region, perform constraint propagation, check for inconsistencies and backtrack if constraints are violated.

The full algorithm and implementation is out of the scope of this question. But figuring out the connections between regions is a necessary step in any case. You can also try to solve the CSP by simply trying all combinations, although I wouldn't expect this to scale very well.

Upvotes: 1

Related Questions