I was presented with the following Backtracking/Seating problem:
Assume you have a room of size k * k, meaning you have exactly k * k seats available and an n amount of people you have to seat. Furthermore, every person has their own specific radius in which they really don't want anyone else to sit in.
The assignment is to write an algorithm in pseudocode or pure text form to find any seating plan (not necessarily perfectly optimal) through backtracking in which every person is not within someone else's radius or indicate that such a seating plan is not possible. Note that the time complexity of the algorithm is not of importance.
To further illustrate this, assume we are given k = 8, meaing we have a total of 8x8 seats. For people n=3 we have Red with a radius of 3, Blue with a radius of 2 and Yellow with a radius of 1. In the following picture we have an example of an invalid seating plan, because Blue is clearly within Red's radius. One of the many possible valid seating plans for this would be Red at seat (0,0), Blue at seat (4,0) and Yellow at seat (7,0).
Where I'm stuck:
My attempt/pseudocode assumes that an array of n people is an array of radii, sorted by their size in descending order. We then iterate over the x and y coordinates in respective for loops. We place the largest Element at (0,0) and then pick the next element/radius and check if we can place it in the next (x,y). If person 1 is within person 2's radius or vice-versa, the position is invalid and we move on to the next (x,y). If the position is valid, we move on to the next element/radius and repeat that process until we exhausted all radii/people in n.
Even though this might even work in actual code, I fail to understand how I should implement the required backtracking aspect of my pseudocode. I do believe I understand the basics of how backtracking works but I just can't seem to figure out how I can implement that process into this problem.