I manually define the following 16 matrices in Python :
matrices = {
"Simulation 1": [
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 2, 3, 2],
[1, 1, 1, 1, 3, 3],
[1, 1, 1, 1, 3, 3]
],
"Simulation 2": [
[1, 1, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 2, 2, 3],
[1, 1, 1, 3, 3, 3]
],
"Simulation 3": [
[1, 1, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 2, 3, 3],
[1, 1, 2, 2, 3, 3],
[1, 1, 1, 3, 3, 3],
[1, 1, 3, 3, 3, 3]
],
"Simulation 4": [
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 2, 2, 2],
[3, 1, 3, 3, 3, 2],
[3, 3, 3, 3, 3, 2],
[3, 3, 3, 3, 3, 2],
[3, 3, 3, 3, 3, 3]
],
"Simulation 5": [
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 3, 2],
[1, 3, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3]
],
"Simulation 6": [
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 2, 3],
[1, 3, 3, 3, 3, 3],
[1, 3, 3, 3, 3, 3]
],
"Simulation 7": [
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 3, 2, 2, 3],
[1, 1, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3]
],
"Simulation 8": [
[1, 1, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 3, 3],
[2, 2, 3, 3, 3, 3],
[2, 2, 2, 3, 3, 3]
],
"Simulation 9": [
[1, 1, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 3, 2],
[1, 1, 1, 1, 3, 3],
[1, 1, 3, 3, 3, 3]
],
"Simulation 10": [
[1, 1, 1, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 3],
[1, 1, 1, 1, 3, 3],
[1, 1, 1, 3, 3, 3]
],
"Simulation 11": [
[1, 1, 1, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 3],
[1, 1, 1, 2, 3, 3],
[1, 1, 1, 3, 3, 3],
[1, 1, 1, 3, 3, 3]
],
"Simulation 12": [
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 2, 2],
[3, 1, 1, 3, 3, 3],
[3, 3, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3]
],
"Simulation 13": [
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 3, 3, 3],
[1, 3, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3]
],
"Simulation 14": [
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 3, 3, 2],
[1, 3, 3, 3, 3, 3],
[1, 3, 3, 3, 3, 3]
],
"Simulation 15": [
[1, 1, 1, 2, 2, 2],
[1, 2, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 3, 3],
[1, 1, 1, 3, 3, 3],
[1, 1, 1, 3, 3, 3]
],
"Simulation 16": [
[1, 1, 3, 2, 2, 2],
[1, 1, 3, 2, 3, 3],
[1, 1, 3, 3, 3, 3],
[1, 1, 3, 3, 3, 3],
[1, 1, 3, 3, 3, 3],
[1, 1, 3, 3, 3, 3]
]
}
When visualized, these look like this:
Positions in the matrix are understood like this:
positions = [
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36]
]
These matrices have the following properties:
- 1 = Red, 2 = Blue, 3 = Green
- Position 1 is always Red, Position 6 is always Blue and Position 36 is always green
- All circles of the same color can reach all other circles of the same color without touching any other color
Here is an example of an invalid matrix (i.e. node 1 (red) can not reach the other red nodes without stepping on blue):
I have the following question: Is there some algorithm which can be used to rapidly generate (random) valid matrices for this problem? Can something like a tree/graph be used which can efficiently generate 100 hundred such solutions?
Updated version of trincot's answer to include visualization:
import random
import matplotlib.pyplot as plt
import numpy as np
def make_matrix(n):
mat = [[0] * n for _ in range(n)]
frontier = set()
def place(row, col, color):
mat[row][col] = color
frontier.discard((row, col, 1))
frontier.discard((row, col, 2))
frontier.discard((row, col, 3))
for next_row, next_col in (row-1, col), (row+1, col), (row, col-1), (row, col+1):
if 0 <= next_row < n and 0 <= next_col < n and mat[next_row][next_col] == 0:
frontier.add((next_row, next_col, color))
place(0, 0, 1)
place(0, n-1, 2)
place(n-1, n-1, 3)
while frontier:
place(*random.choice(list(frontier)))
return mat
def visualize_matrix(mat):
n = len(mat)
colors = np.zeros((n, n, 3))
for i in range(n):
for j in range(n):
if mat[i][j] == 1:
colors[i, j] = [1, 0, 0] # Red for 1
elif mat[i][j] == 2:
colors[i, j] = [0, 0, 1] # Blue for 2
elif mat[i][j] == 3:
colors[i, j] = [0, 1, 0] # Green for 3
plt.figure(figsize=(5, 5))
plt.imshow(colors)
plt.grid(True, color='black', linewidth=0.5)
plt.xticks(np.arange(-0.5, n, 1), [])
plt.yticks(np.arange(-0.5, n, 1), [])
plt.tick_params(length=0)
for i in range(n):
for j in range(n):
plt.text(j, i, str(mat[i][j]), ha="center", va="center", color="white")
plt.tight_layout()
plt.show()
plt.figure(figsize=(15, 10))
for i in range(4):
plt.subplot(2, 2, i+1)
mat = make_matrix(6)
n = len(mat)
colors = np.zeros((n, n, 3))
for r in range(n):
for c in range(n):
if mat[r][c] == 1:
colors[r, c] = [1, 0, 0] # Red for 1
elif mat[r][c] == 2:
colors[r, c] = [0, 0, 1] # Blue for 2
elif mat[r][c] == 3:
colors[r, c] = [0, 1, 0] # Green for 3
plt.imshow(colors)
plt.grid(True, color='black', linewidth=0.5)
plt.title(f"Matrix #{i+1}")
plt.xticks([])
plt.yticks([])
for r in range(n):
for c in range(n):
plt.text(c, r, str(mat[r][c]), ha="center", va="center", color="white")
plt.tight_layout()
plt.show()
for i in range(5):
print(f"Matrix #{i+1}:")
mat = make_matrix(6)
for row in mat:
print(row)
print()
visualize_matrix(mat)
I manually define the following 16 matrices in Python :
matrices = {
"Simulation 1": [
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 2, 3, 2],
[1, 1, 1, 1, 3, 3],
[1, 1, 1, 1, 3, 3]
],
"Simulation 2": [
[1, 1, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 2, 2, 3],
[1, 1, 1, 3, 3, 3]
],
"Simulation 3": [
[1, 1, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 2, 3, 3],
[1, 1, 2, 2, 3, 3],
[1, 1, 1, 3, 3, 3],
[1, 1, 3, 3, 3, 3]
],
"Simulation 4": [
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 2, 2, 2],
[3, 1, 3, 3, 3, 2],
[3, 3, 3, 3, 3, 2],
[3, 3, 3, 3, 3, 2],
[3, 3, 3, 3, 3, 3]
],
"Simulation 5": [
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 3, 2],
[1, 3, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3]
],
"Simulation 6": [
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 2, 3],
[1, 3, 3, 3, 3, 3],
[1, 3, 3, 3, 3, 3]
],
"Simulation 7": [
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 3, 2, 2, 3],
[1, 1, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3]
],
"Simulation 8": [
[1, 1, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 3, 3],
[2, 2, 3, 3, 3, 3],
[2, 2, 2, 3, 3, 3]
],
"Simulation 9": [
[1, 1, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 3, 2],
[1, 1, 1, 1, 3, 3],
[1, 1, 3, 3, 3, 3]
],
"Simulation 10": [
[1, 1, 1, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 3],
[1, 1, 1, 1, 3, 3],
[1, 1, 1, 3, 3, 3]
],
"Simulation 11": [
[1, 1, 1, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 3],
[1, 1, 1, 2, 3, 3],
[1, 1, 1, 3, 3, 3],
[1, 1, 1, 3, 3, 3]
],
"Simulation 12": [
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 2, 2],
[3, 1, 1, 3, 3, 3],
[3, 3, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3]
],
"Simulation 13": [
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 3, 3, 3],
[1, 3, 3, 3, 3, 3],
[3, 3, 3, 3, 3, 3]
],
"Simulation 14": [
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 3, 3, 2],
[1, 3, 3, 3, 3, 3],
[1, 3, 3, 3, 3, 3]
],
"Simulation 15": [
[1, 1, 1, 2, 2, 2],
[1, 2, 2, 2, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 1, 1, 3, 3],
[1, 1, 1, 3, 3, 3],
[1, 1, 1, 3, 3, 3]
],
"Simulation 16": [
[1, 1, 3, 2, 2, 2],
[1, 1, 3, 2, 3, 3],
[1, 1, 3, 3, 3, 3],
[1, 1, 3, 3, 3, 3],
[1, 1, 3, 3, 3, 3],
[1, 1, 3, 3, 3, 3]
]
}
When visualized, these look like this:
Positions in the matrix are understood like this:
positions = [
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36]
]
These matrices have the following properties:
- 1 = Red, 2 = Blue, 3 = Green
- Position 1 is always Red, Position 6 is always Blue and Position 36 is always green
- All circles of the same color can reach all other circles of the same color without touching any other color
Here is an example of an invalid matrix (i.e. node 1 (red) can not reach the other red nodes without stepping on blue):
I have the following question: Is there some algorithm which can be used to rapidly generate (random) valid matrices for this problem? Can something like a tree/graph be used which can efficiently generate 100 hundred such solutions?
Updated version of trincot's answer to include visualization:
import random
import matplotlib.pyplot as plt
import numpy as np
def make_matrix(n):
mat = [[0] * n for _ in range(n)]
frontier = set()
def place(row, col, color):
mat[row][col] = color
frontier.discard((row, col, 1))
frontier.discard((row, col, 2))
frontier.discard((row, col, 3))
for next_row, next_col in (row-1, col), (row+1, col), (row, col-1), (row, col+1):
if 0 <= next_row < n and 0 <= next_col < n and mat[next_row][next_col] == 0:
frontier.add((next_row, next_col, color))
place(0, 0, 1)
place(0, n-1, 2)
place(n-1, n-1, 3)
while frontier:
place(*random.choice(list(frontier)))
return mat
def visualize_matrix(mat):
n = len(mat)
colors = np.zeros((n, n, 3))
for i in range(n):
for j in range(n):
if mat[i][j] == 1:
colors[i, j] = [1, 0, 0] # Red for 1
elif mat[i][j] == 2:
colors[i, j] = [0, 0, 1] # Blue for 2
elif mat[i][j] == 3:
colors[i, j] = [0, 1, 0] # Green for 3
plt.figure(figsize=(5, 5))
plt.imshow(colors)
plt.grid(True, color='black', linewidth=0.5)
plt.xticks(np.arange(-0.5, n, 1), [])
plt.yticks(np.arange(-0.5, n, 1), [])
plt.tick_params(length=0)
for i in range(n):
for j in range(n):
plt.text(j, i, str(mat[i][j]), ha="center", va="center", color="white")
plt.tight_layout()
plt.show()
plt.figure(figsize=(15, 10))
for i in range(4):
plt.subplot(2, 2, i+1)
mat = make_matrix(6)
n = len(mat)
colors = np.zeros((n, n, 3))
for r in range(n):
for c in range(n):
if mat[r][c] == 1:
colors[r, c] = [1, 0, 0] # Red for 1
elif mat[r][c] == 2:
colors[r, c] = [0, 0, 1] # Blue for 2
elif mat[r][c] == 3:
colors[r, c] = [0, 1, 0] # Green for 3
plt.imshow(colors)
plt.grid(True, color='black', linewidth=0.5)
plt.title(f"Matrix #{i+1}")
plt.xticks([])
plt.yticks([])
for r in range(n):
for c in range(n):
plt.text(c, r, str(mat[r][c]), ha="center", va="center", color="white")
plt.tight_layout()
plt.show()
for i in range(5):
print(f"Matrix #{i+1}:")
mat = make_matrix(6)
for row in mat:
print(row)
print()
visualize_matrix(mat)
1 Answer
Reset to default 3One way is to perform a random flood-fill out of the three initial coloured corners.
Here is a possible implementation:
import random
def make_matrix(n):
mat = [[0] * n for _ in range(n)]
frontier = set()
def place(row, col, color):
mat[row][col] = color
frontier.discard((row, col, 1))
frontier.discard((row, col, 2))
frontier.discard((row, col, 3))
for next_row, next_col in (row-1, col), (row+1, col), (row, col-1), (row, col+1):
if 0 <= next_row < n and 0 <= next_col < n and mat[next_row][next_col] == 0:
frontier.add((next_row, next_col, color))
place(0, 0, 1)
place(0, n-1, 2)
place(n-1, n-1, 3)
while frontier:
place(*random.choice(list(frontier)))
return mat
Here is an example run:
mat = make_matrix(6)
for row in mat:
print(row)
The principle variable is frontier which has a set of possible next actions. An action consists of coloring a cell, so it defines the coordinates of the cell and the color code (1, 2 or 3).
Each iteration one action is randomly chosen from that set, and the action is applied. This means also that the set of possible actions is adapted: some are no longer possible, while others become possible.
And so this repeats until there is no more cell that can be coloured.