Non-Intersecting Grids: The Cantor Pairing Approach

A friend challenged me with the following constrained random problem.

The size of a frame is MxN Pixels ( pixels[(M-1:0),(N-1:0)])

create a grid of mxn pixels with horizontal skipping h_skip

and vertical skipping v_skip so that.

for (i = m_start; i < m_start + m; i++)

for (j = n_start; j < n_start + n; j++)

grid[i,j] = pixels[i*h_skip,j*v_skip];

You can consider M,N to be constants

Phase 1:

randomize m,n,v_skip,h_skip and create constraints that force the solution, for example.

Phase 2:

you are getting a list of coordinates

typedef struct { int x; int y;} coordinate;

coordinate coordinates_list[$]

the grid must not intersect the coordinates

Another requirement is that the solution as to be solved fast because typical frames size is for example 1200 X 1800.

My solution is based on Cantor Pairing Function which encode two natural numbers into a single natural number.

Following is two solution for this problem (for simplicity 16X16 frame).

The list of coordinates is represented by the character 'x'.

The grid is represented by the character 'P'.

Solution:

The variables for class frame are:

rand bit [(M-1):0] m; // Number of grid rows rand bit [(M-1):0] m0; // Grid first row rand bit [(N-1):0] n; // Number of grid columns rand bit [(N-1):0] n0; // Grid first column rand bit [(M-1):0] h_skip; // Grid horizontal skip rand bit [(N-1):0] v_skip; // Grid vertical skip

In addition 2 dynamic arrays are declared one for grid row coordinates and one for column coordinates.

rand int help_mtrx_x[]; rand int help_mtrx_y[];

for the coordinate list a struct type is defined, this list contains the coordinates that the grid must not intersect

typedef struct { rand int x; rand int y;} coordinate;

coordinate coordinates_list[$];

Phase 1 solution:

// Choose grid first row and column

constraint first_index_c { m0 inside {[0:(M-1)]}; n0 inside {[0:(N-1)]};

}

// Choose vertical and horizontal skip (you can start from 1 but it is less interesting case)

constraint skip_c { h_skip inside {[2:(M-1)]}; v_skip inside {[2:(N-1)]}; }

// Choose grid number of rows and columns

constraint mtrx_size_c { m inside {[2:(M-1)]}; n inside {[2:(N-1)]}; }

// Number of rows

constraint row_grid_c { m + ((m-1) * v_skip) < ((M-1) - m0);

}

// Number of columns

constraint col_grid_c { n + ((n-1) * h_skip) < ((N-1) - n0); }

// Build the column indexes help matrix

constraint help_mtrx_x_c { help_mtrx_x.size==n; foreach(help_mtrx_x[i]) { help_mtrx_x[i] == n0 + (i * h_skip); }

}

// Build the rows indexes help matrix

constraint help_mtrx_y_c { help_mtrx_y.size==m; foreach(help_mtrx_y[i]) { help_mtrx_y[i] == m0 + (i * v_skip); }

}

Phase 2 solution:

Because the Cantor Pairing Function encodes 2 natural numbers to unique natural number

this constraint will do the following

• Iterate through all grid coordinates, ensuring that the Cantor pairing function transformation for each grid coordinate differs from the transformation of the coordinates in the list.

constraint intersect_c { foreach (help_mtrx_x[i]) { foreach (help_mtrx_y[j]) { foreach (coordinates_list[k]) { // Cantor Pairing Function (help_mtrx_x[i] + help_mtrx_y[j]) * (help_mtrx_x[i] + help_mtrx_y[j] + 1) / 2 + help_mtrx_y[j] != (coordinates_list[k].x + coordinates_list[k].y) * (coordinates_list[k].x + coordinates_list[k].y + 1) / 2 + coordinates_list[k].y; } } } }

The printing feature in this code displays a capital 'F' when an intersection takes place. You can deactivate the 'intersect_c' constraint and run several seeds to observe intersecting nodes, as illustrated in the image below.

The code can be found here