Sokoban_Brute_Solver_2.java

//  Sokoban brute solver.
//  2021, May, B@R5uk
//  Discussion: https://dxdy.ru/topic144781.html
//          Solver looks for an optimal solution using one of two modes:
//              1) move-primary, push-secondary or
//              2) push-primary, move-secondary.
//          (See second argument of method run() in the StateProcessor class).
//          In the process solver counts a total number of optimal different
//          solutions available with selected search mode and chooses one at
//          random with equal probability (as far as "randomness" of pseudo-random
//          generator allows, see State class, selectRandomState() method) as long
//          as the total number of solutions lies within the Integer.MAX_VALUE limit.
//              A solver's algorithm is essentially the Dijkstra's search algorithm
//          on a graph of Sokoban puzzle states that's using one of the two comparators
//          (see State class, MovePriorityComparator and PushPriorityComparator nested
//          classes) for a composite node distances which is a move and push pair.
//          Solver starts with all the final states and expands them backward to
//          avoid as much problems with dead states as possible without, in fact,
//          implementing deadlocks detection (see State class, expandBack() method).
//          Some preprocessing (MapHandler class, findActiveCells() method) and
//          the network graph representation of a puzzle maze (CellsAdjacency class
//          and MapHandler class, getCellsAdjacency() method) also helps to speed up
//          things.
//              If program runs out of memory than enlarging Java VM Heap Size
//          by adding -Xmx2048m key in Run -> Run Configurations... -> Arguments ->
//          VM Arguments (Eclipse) or in the command line can help.

import java.util.*;

public class Sokoban_Brute_Solver_2 {

    private static final long randomSeed = System .currentTimeMillis ();
    private static final Random rng = new Random (randomSeed);
    //private static final Random rng = null;
    private static final MapAccess mapAccess =
            new MapAccess ( 0, "..\\test.txt");
            //new MapAccess ( 5, "..\\Microban.txt");
            //new MapAccess ( 0, "..\\Original.txt");
            //new MapAccess ( 2, "..\\Yoshio52.txt");
            //new MapAccess (13, "..\\YoshioHM.txt");
            //new MapAccess (17, "..\\Nabokosmos.txt");
            //new MapAccess ( 5, "..\\Nabokosmos.txt");
            //new MapAccess (44, "..\\Sokwhole.txt");
            //new MapAccess ( 3, "..\\Yoshio52.txt");

    public static void main (String [] args) {
        String []  mapLines;
        MapLoader  mapLoader     = new MapLoader ();
        MapHandler mapHandler    = new MapHandler ();
        StateProcessor processor = new StateProcessor ();

        if (!mapLoader .openFile (mapAccess .fileName)) {
            return;
        }

        mapLoader .skip (mapAccess .mapIndex);
        mapLoader .loadNext ();
        mapLoader .closeFile ();

        if (!mapLoader .hasLines ()) {
            System .out .println ("No map.");
            return;
        }

        mapLines = mapLoader .getMapLines ();
        mapAccess .display ();
        MapLoader .displayLines (mapLines);

        if (mapHandler .process (mapLines)) {
            System .out .println (mapHandler .getErrorMessage ());
            return;
        }

        System .out .println ();
        System .out .println ("________________________");
        System .out .println ("Move-priority solution:");
        if (processor .run (mapHandler, false, rng)) {
            System .out .println ("Search is incomplete.");
        }
        processor .displaySolution ();

        System .out .println ();
        System .out .println ("________________________");
        System .out .println ("Push-priority solution:");
        if (processor .run (mapHandler, true, rng)) {
            System .out .println ("Search is incomplete.");
        }
        processor .displaySolution ();
    }

    private static class MapAccess {
        public int    mapIndex;
        public String fileName;

        public MapAccess (int mapIndex, String fileName) {
            this .mapIndex = mapIndex;
            this .fileName = fileName;
        }

        public void display () {
            System .out .println (fileName + "  #" + (mapIndex + 1));
        }
    }
}