Sokoban

Omdat de puzel net ienfâldich fysyk makke wurde kin, wurdt it meast as kompjûterspul oanbean.

Sokoban is yn 1982 útfûn troch Hiroyuki Imabayashi, en it spul is doe útjûn troch Thinking Rabbit, in softwarefirma út Takarazuka, Japan. Troch Thinking Rabbit binne letter moch ferskate ferfolgen útjûn lykas Boxxle, Sokoban Perfect en Sokoban Revenge.

Op ynternet binne ûntelbere kloanen fan Sokoban te finen, foar hast elk kompjûterplatform.

Der besteane ek inkele farianten fan it spul Sokoban, lykas Hexoban, Trioban en Multiban.

 Wiskundige analyze 
Sokoban kin bestudearre wurde middels de kompjûtasjonele kompleksiteitsteory. It is bewiisd dat it oplossen fan in spulnivo fan Sokoban in probleem is mei kompleksiteitsgraad NP-slim; it is ek bewiisd dat Sokoban PSPACE-kompleet is.J. Culberson, "Sokoban is PSPACE-complete". Technical Report TR97-02, Department of Computing Science, University of Alberta, 1997

It probleem fan Sokoban is in planningsprobleem, fergelykber mei dat fan in robot dy't doazen yn in magazyn oarderje moat. De fertakkingsfaktor fan Sokoban is te fergelykjen  mei dy fan skaak, mar de djipte fan de sykbeam kin by Sokoban enoarm grut wêze: yn guon niveaus binne mear as 1000 bewegingen nedich. Sykmetoaden út de keunstmjittige yntelliginsje, lykas it A*-algoritme, kinne brûkt wurde om in kompjûterprogramma te meitsjen dat Sokobanniveaus oplosse kin. Mar om effisjint te wêzen moatte dy metoaden ferfine wurde mei domeinspesifike kennis, krektas minsklike spilers heuristiken brûke en by it spyljen fan Sokoban. In foarbyldd fan in automatyske Sokobanoplosser is Rolling Stone'', ûntwikkele troch de GAMES-groep oan de Universiteit fan Alberta yn Kanada. En dôchs is dat programma net by steat om alle 90 standertniveaus fan Sokoban op te lossen.Rolling StoneAndreas Junghanns, Jonathan Schaeffer: "Sokoban: A Challinging Single-Agent Search Problem."

Kategory:Puzel