Protip: That problem *would* be hard (NP Hard actually) IF the island wasn't static. But it is static. You can pre-map these areas without the use of a walkable tile search algorithm.
Instead use an unwalkable tile search algorithm and identify unpassable zones.
Basically, find all tiles that are not walkable (easy if walkable is easy) then iterate all adjacent tiles of unwalkable tiles that are also unwalkable. Construct a graph containing tile coordinates for nodes and adjacent tiles as adjacent nodes in the graph. Essentially you'll have a graph containing only unwalkable tiles. Once graph is constructed, identify circular loops in graph (pretty easy DFS algorithm with a "isVisited" flag). Once circular loop is found mark out a big f'king rectangle containing the coordinate set of all the coordinates in the discovered loop. This will implicitly filter all tiles INSIDE the unpassable zone. That's your blacklist.
Modify your artifact generation algorithm to never spawn artifacts in aforementioned rectangles.