# PSPACE-hardness of the unbounded puzzle

Given a board of size $$n \times 1$$ where $$n=\infty$$ (basically a tape, one way infinite), and a set of colors $$C$$, some starting color $$c_{start} \in C$$, a set of templates $$T$$ in a form $$(c_k, i, c_i, j, c_j)$$ (meaning if on some position on the board there is a color $$c_k$$ then $$i$$ steps to the right of $$c_k$$ there is a color $$c_i$$, and $$j$$ steps to the right of $$c_i$$ there is a color $$c_j$$).

Prove that if we put $$c_{start}$$ on the board in position $$(1,1)$$ (furthest to the left), the answer to the question below is PSPACE-hard

Can we fill the board with $$c \in C$$ in such a way that we use all the elements from $$T$$?

I attempted to reduce TQBF to this problem, however if I construct a gadget where I say that each variable is a color, I have a trouble encoding $$i$$ and $$j$$ with clauses. Also, I'm not sure if it's the right direction (maybe try reducing from GG? but I would have the same problem).

Any help is appreciated.