0

Concider I have an incomplete 2d array, with some of it's cells blocked, like this:

enter image description here

I want to fill that array with given tetris like shapes (perfect solution not guaranteed), those are the rules:

  • Path always connected, no "holes"
  • Pieces are pre-known and are enough to cover exactly 100% of path (if fitting)
  • Pieces can be rotated and flipped, makes it 8 different ways to place each piece

My question is, how can I brute-force it and ensure I actually checked all the variations?

My plan was to start from left top corner and seek for the next empty cell in a loop.

But then I don't know what to do when i get stuck. Maybe store placed pieces in a stack and try different ways but the fact I can both rotate pieces and change their places was too much for me. Working with java in case that's matter. thanks!

junior_developer181
  • 105
  • 7
  • The typical technique is a recursive backtracking solution. You call the function with the original array, and the original list of pieces. Then for each piece that can cover the first open cell you 1) mark the cells that the piece covers 2) remove the piece from the list of pieces 3) call the function recursively with the updated array and list. – user3386109 Apr 20 '20 at 19:53
  • See for example, the [answer to this question](https://stackoverflow.com/questions/39911652/dont-understand-recursive-backtracking) – user3386109 Apr 20 '20 at 19:55

0 Answers0