Divide a board of size n x m into k equal contiguous groups. The groups are randomly allocated every time.
-
A 9x9 board divided into 9 equal contiguous groups as demonstrated below
-
A 6x6 board divided into 9 equal and contiguous groups as demonstrated below
The problem can be easily solved using a Depth First Search. However, the constraint that all cells in a group need to be contiguous poses a challenge that randomly selecting a neighbouring cell can end up blocking cells at the corner.
To solve that, let's first assign degree to every cell of the board. Degree is the number of free neighbours a cell has. The lower the cell degree, the higher it's chances to be blocked.
Degree of cells in a 4x4 board:
|2|3|3|2|
|3|4|4|2|
|3|4|4|2|
|2|3|3|2|
One approach to achieve a sure-shot solution is to ensure that the cell being assigned always has the lowest degree i.e. 2. An algorithm would look as follows:
- Start from any corner since they have the lowest degree on the entire board.
- Assign a group to the current cell and mark it as assigned.
- Decrease degree of neighbouring cells by 1.
- Select the next neighbour with the lowest degree i.e. 2
- Repeat 2-4 until all cells are assigned.
The entrypoint of the code is located at src/python/board.py
. Below is a code snippet to execute it.
nrows = 9
ncols = 10
ngroups = 15
b = Board(nrows, ncols) # initialize the board
b.divide_board(ngroups) # main algorithm
b.display_board() # display gui of divided board
Example output: