Under these conditions if you are doing a DFS over positions then you need to store O(n^2) positions in memory, considering that a position takes O(n) memory, you are using O(n^3) memory in total.
I guess chess (without the 50-move rule), checkers, and go (with a certain ruleset) can go on for longer.