GMS 2 Need Help Optimizing A Puzzle Generator

Greetings, members of the GM community.

I need some help optimizing a puzzle generator.

This thread will be divided into two parts: the game's design and my issue and proposed solution to the generation system.

I am working on a puzzle game prototype which involves swapping blocks with color-coded shapes. There are two ways to swap blocks. The first is to swap two blocks that are adjacent cardinal neighbors. The second is to swap ANY two blocks that share the same color regardless of their placement, which could be cardinal, diagonal or even far away from each other. The player can even move a block onto any empty cardinal neighbor to move it across gaps. If the player matches three or more blocks of the same shape in a row or column, those blocks disappear. Once no more blocks are on the puzzle, the player deals 1 damage to the enemy and a new puzzle is generated. Each puzzle also has a recommended swap count which the player cannot go over without taking 1 damage for each additional swap the player makes. Once the player clears a puzzle, the swap count resets but the player's health does not. A picture of the prototype is below:

I already coded a functional random puzzle generation system with solvable puzzles. The generator basically backtracks how a player would best solve the puzzle. In doing this, a system of horizontal and vertical lines 3-5 blocks long and 1 block wide with identical shapes one or two at a time. After each line is created, various swaps are made before creating a new horizontal or vertical line(s), which I find to be inefficient. It immediately generates a 4x4 grid. However, it takes more time to generate a larger puzzle to the point where it hangs for a while. My solution to this problem is to build the arrangement of horizontal and vertical lines in its entirety before filling them with colored shape blocks. However, I need some insight on coding an optimized grid line generation system which intelligently builds the arrangement of lines until there is not any unused space without having to clear the grid and keep rebuilding the puzzle.

Here's the main question: what are some good linear grid splitting (line forming) algorithms that would be helpful with the above scenario?

I thank any one in advance that looks at this and/or helps me out.
Last edited: