Due: Sat, 2022/3/19 23:59
For BFS algorithm
Intel TBB provide thread-safe concurrent access containers. You may find them useful for parallelizing your code. They are installed on apollo31. To use them, include the correspond header files and compile with ltbb.
Note: In the oneAPI document, it use #include "oneapi/tbb/xxx.h to inlclude TBB container. On our server, replace it with #include <tbb/xxx.h>.
boost::functional::hash can be used to hash more STL containers.https://www.techiedelight.com/use-std-pair-key-std-unordered_map-cpp/
(easy) Try to avoid/detect dead states, e.g.:
###### ######
# .### # .###
# ### # ###
#X # #X #
#xo # # ox#
# ### # ###
###### ######
(medium-hard) Reduce the number of states by combining person move only states.
(hard) Use an efficient state representation to reduce memory usage
“Sokoban (倉庫番, sōko-ban, “warehouse keeper”) is a puzzle video game in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations.” – Wikipedia
You are asked to implement a solver for Sokoban and parallelize it with threads(either pthread or OpenMP; you can use std::thread as a pthread wrapper).
Input is given in an ASCII text file. The filename is given from the command linein argv[1].
Every line ends with a newline character \n.Each line represents a row of tiles; every character in the line represents a tilein the game.
The tiles are listed as follows:
o: The player stepping on a regular tile.O: The player stepping on a target tile.x: A box on a regular tile.X: A box on a target tile.