User:Puzl bustr

From Sokoban Wiki

I'm a Sokoban enthusiast - I like solving and creating puzzles. In the past I've helped program Sokoban games and a generator (backward solver), and maintained a website with my puzzles for download, but due to getting Repetitive Strain Injury (RSI) from typing am unable to do these things involving frequent typing. I've an adapted mouse and am able to write this with an onscreen keyboard. Am able to solve and recently started designing more puzzles.

I'm interested in computer Sokoban solving in terms of artificial intelligence. I believe that, using domain-specific knowledge and a combination of limited searches using heuristics (for example, identifying free space, empty squares which you could imagine adding a box to without creating an obvious deadlock or a new blocked-in area and variations to reach it via single-box push routes) and conventional tree search, it is possible to substantially improve on conventional computer solvers.

Since I cannot program my ideas, I'd like to make them available here for others to implement; I'd like to be credited with my name David Holland and for these ideas to be freely available (with any implementation open-source). I'll try to update these ideas as I can and include descriptions of algorithms (as I've already done for the main limited search identifying free space and computing single-box push routes and "shuffling") but as I have to rest my hands frequently would prefer "able-handed" programmers to do the coding. Several of the algorithms can also be used in conventional Sokoban solvers.

David Holland's computer Sokoban solving ideas Section 3 contains the algorithms and the most precise descriptions.