Generate N * N board with given set of colors randomly.
Such that no 3 cells adjancent to each other vertically and horizontally should have the same color (diagonals are not considered, and regardless of the size of the grid only 3 cells shouldn't be same.)
N = 3 , colors = 0,1,2
[0 1 2
1 2 0
0 2 1]
the board generated above is correct
N = 4 , colors = 0,1,2
[0 0 0 2
1 2 0 1
0 0 1 1
0 2 1 1]
the board generated above is wrong, because the 1st row has three 0's and and last columns has three 1's
I will write my psuedo code for this below (in interview I wrote the full code), but would like to know if there is a better optimized approach with time complexity, appreciate your help and feedback.
Random rand = new Random();
int [][] generateBoad(int n,int colorSize)
{
for(int i=0;i<n,i++)
{
for(int j=0;j<n,i++)
{
int color = rand.next(colorSize);
while(!isValid(board,i,j,color,1,1))
{
color = rand.next(colorSize);
}
board[i][j]=color;
}
}
return board;
}
boolean isValid(board,i,j,color,coumt,state)
{
if(count==3)
return false;
if(state==3&&count!=3)
return true
boolean rowCheck = true, colCheck = true;
if(border case) //check if i & j is inside the 2d board border
if(board[i][j]==board[i-1][j])
rowCheck = isValid(board,i-1,j,color,count+1,state+1)
if( rowCheck && board[i][j]==board[i][j-1])
colCheck = isValid(board,i,j-1,color,coumt+1,state+1)
return rowCheck && colCheck;
}Comments (12)