Sokoban is a puzzle game genre
When I had to add sub-genres to the puzzle games category, I really didn't know how to do it. I consulted Wikipedia, Home of the Underdogs (the original one) and a few other gaming sites. I thought a lot about it and then I came up with the current sub-genres: action puzzles, falling blocks (Tetris), multiple characters (Lemmings), physics based games, puzzle compilations, tile-matchin, word and math games.
At one point, I was unsure about how to categorize Soko-Ban. Soko-Ban is a really addictive puzzle game that spawned a few clones. The problem was that it didn't fit any of the sub-genres on Abandonware DOS. After searching on Mobygames and other online gaming databases, I found out that the sokoban-inspired games are quite a few, so I decided to create a whole genre called "sokoban".
Find out more about Soko-Ban