Due: Sat, 2022/3/19 23:59

Hint

For BFS algorithm

  1. 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>.

  2. boost::functional::hash can be used to hash more STL containers.https://www.techiedelight.com/use-std-pair-key-std-unordered_map-cpp/

  3. (easy) Try to avoid/detect dead states, e.g.:

    ######       ######
    # .###       # .###
    #  ###       #  ###
    #X   #       #X   #
    #xo  #       #  ox#
    #  ###       #  ###
    ######       ######
    
  4. (medium-hard) Reduce the number of states by combining person move only states.

  5. (hard) Use an efficient state representation to reduce memory usage

Problem Description

“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 Format

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: