I am trying to write an algorithm that produces a solution to a modified n by n sliding puzzle (assuming that a final state is accessible from the given starting state). The change is as follows: the tiles can belong to sets with other tiles and can also occupy any of their positions, and the sets are disjoined. The image below shows an example on the right which is in one of the many final states. A tile labeled with x numbers can be in any of the x positions with which it is labeled. For example:

on the left we have 3×3 of: $ left lbrace1 right rbrace, left lbrace2 right rbrace, left lbrace3 right rbrace, left lbrace4 right rbrace, left lbrace5 right rbrace, left lbrace6 right rbrace, left lbrace7 right rbrace, left lbrace8 right rbrace, $ and

right we have a 3×3 $ left lbrace1,4,6 right rbrace, left lbrace2,8 right rbrace, left lbrace3 right rbrace, left lbrace5 right rbrace, left lbrace7 right rbrace. $

My current thinking is to treat each tile as being in its own set and to exhaustively check if the initial state is solvable – in this example, labeling the tiles in positions $ 1 $ (on the top corner left)$, 2, 4, 6, $ and $ 8 as respectively $ left lbrace1 right rbrace, left lbrace2 right rbrace, left lbrace4 right rbrace, left lbrace6 right rbrace, left lbrace8 right rbrace $, then $ left lbrace4 right rbrace, left lbrace2 right rbrace, left lbrace6 right rbrace, left lbrace1 right rbrace, left lbrace8 right rbrace $, etc. and running an existing algorithm for the original puzzle if a solvable state is found.