> I actually now disagree that a an algorithm based puzzle solver was ever referred to as AI,

"Artificial Intelligence: A Modern Approach" was published in 1995 and included Sokoban as a search-problem example.