I'm working on implementing a puzzle board game called Double-Choco published by Nikoli magazine
Where the board is a 2-dimensional matrix with cells that are either white or gray. The goal is to divide the grid into blocks by drawing solid lines over the dotted lines. Each block must contain a pair of areas of white cells and gray cells having the same form (size and shape), one area can be rotated or mirror of the opposite area, an area could have a number indicates the number of cells of that color in the block.
I'm looking for help in choosing a data structure and forming an algorithm to automatically generate solvable puzzles for this game.
I am implementing using JavaScript and Here's the approach I'm currently considering:
Start with a blank 2-dimensional matrix with the desired size.
Choose a random area size for the white area, between 2 and half of the board size (rounded down to the nearest even number), where cells that form the area is available and not taken
Check if a matched opposite area can be acquired on the board with the same shape & size.
If not: check if there is a space for a rotated or mirrored area.
If not: return to step 2
If yes: recheck the whole board for violations (mainly if there is a surrounded odd-size block left
If there is a violation: go back to step 2
mark the cells of the block (of 2 areas) as taken
go to step 2 till board is filled
As for the data-structure I thought of using graph but I couldn't wrap it around my head. maybe deal with areas as it is as 2-dim matrix?
I'm not sure if this approach is optimal or if there are better data structures and algorithms to use. What data structure and algorithm would you recommend for generating solvable puzzles for this board game? Any help or suggestions would be greatly appreciated.
