CODEWITHSUNDEEP
algorithmuser-interface
barndog
barndog

Reputation: 7163

Given a grid, subdivide into n pieces of different shapes and sizes algorithm

There's a game for iOS, Unblock Me, that takes a given grid/board and subdivides that grid into blocks of different sizes and shapes.

Could someone give me a push as to what the algorithm to accomplish such a task would look like? Given a grid, subdivide the grid into smaller pieces, like the blocks in Unblock Me but also include squares as well as rectangles. I still want to figure it out myself but I'm having some trouble getting started.

EDIT:

Also ideally the solution would leave no empty space within the original grid, it would have been subdivided in such a way that all spots are being used given a certain # of subdivisions.

Upvotes: 0

Views: 226

Answers (1)

barsha
barsha

Reputation: 61

You can have a few standard block sizes and a defined grid size. For instance, going by the Unblock Me example: grid_size can be 4*4, block_size1 can be 3*1, block_size2 can be 2*1 etc. You can then define, or alternatively take as input, the number of blocks you want in the grid. Use dynamic programming or recursive backtracking to fill in the grid with these many blocks.

Upvotes: 1

Related Questions