
"hbox4" : commandline sokoban solver using Ada

4 PQs collapsed into 1 splaytree + queue structures
memory control via user-defined Gb limit;

	3 algorithmic versions:
	.) focus on speed,  default
	.) focus toward optimal pushes + better moves...
		still far from optimal solutions
	.) Non Hungarian, occasionally faster...
		eg on small dense puzzles
		
-----------------------------------------------------------

Reverse Sokoban Solver using
.) Single Step Box Search
.) 4 "orthogonal" primary priority measures,
	smaller values => higher priority,
	with round robin sequencing:
	.) pri1 = #boxes - #boxesOnGoals
	.) pri2 = #corrals - 1
	.) pri3 = #room-blocking-boxes
	.) pri4 = #blockedBoxes
.) Optional Hungarian Matching Algorithm is used to generate
	a secondary priority that breaks-ties among primaries:
	total box moves so far, plus the estimated box
	moves yet to come:  TotPulz+HunEstPulz
	Otherwise TotPulz is used alone (like Festival).
-----------------------------------------------
.) NO box sort;
.) drops to single priority, pri1, when 
	#boxes-on-goals > #boxes*3/4 [loosely speaking]

====================================================
ToDo:

.) 12jul22: consider adding a 5th measurand to xbox4
	based on ease/convenience of measurement...
	Perhaps only by trial/error can we establish 
	its actual utility.

.) ?why does init value of robin make such a crazy
	difference in runtime:
	t7: 0=>2.5, 1,2,3=>4.4
	o2: 0,4=>18, 1,2,3>37
	.) ?skip pri#1 at startup? No: FAIL.

.) to get possible speedup...
	focus on alternate ways to apportion
	all 4 measures, NOT which ones to omit...
	testing showed all 4 measures have proven useful,
	yet #4 might be omittable.

=========================================================
note: to run Windows EXE under linux type:
	wine cmd /c hbox4_64.exe games/takaken_14.sok 7
or more generally
	wine cmd /c hbox4_64.exe <gameFileName> <level-number>
==========================================================
xboxDLs: 
sf:
	7+2
GH:
	44 12feb
	63 10feb (3)
====================================================

7nov22
.) enhanced README.md with additional details.

24sep22
.) upgraded to new, simpler Win64 GNU Ada,
	that does not require mingw or msys.

###########################################################
22sep22: uploaded v1.0.5 to SourceForge, GitHub
###########################################################

20sep22:
.) updated 64-bit Windows build to use the MSYS2/mingw64
	system setup. This provides full memory access.

18sep22:
.) can now use mingw32 GNU Ada. HOWEVER, this probably would
	severely limit memory available to the Windows EXE
	since it would be 32-bit only !!!
	Thus, I'm not sure I should update???

7jan22:
.) moved scripts into ./build/.
.) moved source into ./src/.

5mar21:
.) updated iplr3r, ibox3r to have command lines
	similar to hbox4 (no maxlevels parm).
.) updated emutils.adb
.) updated asok,sban,coterm APPs...
	all now have 3rd solver using (,)-key.


###########################################################
3mar21: uploaded to SourceForge, GitHub
###########################################################

3mar21:
.) updated per damgaard's requests.

18feb21:
.) note that solvers embedded in my apps (WorldCupSokerban, RufaSok)
	are currently hardcoded to limit memory at 1.5 Gb.

14feb21:
.) completed batch runs on xsokoban 1..90
	about 36/90 solved (20/50).

13feb21:
.) added a 600 second time limit
	to facilitate batch runs.
.) changed emutils.ads: maxrows=maxcols=50 to match
	asok, sban, coterm codes.

12feb21:
.) increased utiltypes.maxpri0 to 600
	and removed hardcoded 700 in *saveif*
.) added details on splaypq to README.md
	added xsokoban90 successes and times.
.) removed unused fields from hashrectype.
.) removed "put" from emutils.hsave0 so it
	would not mess up the coterm.csok screen.

###########################################################
12feb21: uploaded to SourceForge, GitHub
###########################################################

11feb21:
.) replaced splaylist with splaytree, since the list
	was not needed.
.) needed to enlarge hashrec size to recover lost speed.
	Purely an Ada representation versus compiler issue.
	See utils.adb::99 =>
	for hashrectype'size use 2400 = 300*8 ...
	default was 297*8.
.) Separated emutils from utils because I wanted a
	clean and minimal utils.adb. I use emutils for other
	solvers like ibox3r and embedded ones.

10feb21:
.) updated README.md and uploaded to S.F. & G.H.

9feb21:
.) at yaron shoham's suggestion I double checked the
	effect of omitting pri#4=NboxesBlocked and found
	VERY MUCH reduced speed versis o2 and t7,
	for all 3: Q,E,Nh. Conclusion: I believe #4
	is advantageous for some puzzles, although not
	absolutely necessary...I believe #3 & #4 are
	not strictly orthogonal and can be somewhat 
	complementary when needed. Also #4 is cheap.

9feb21:
.) now using NonHungarian as the 2nd embedded solver.
.) wrote letter to sokoban group.

###########################################################
9feb21: uploaded to SourceForge, GitHub
###########################################################

8feb21:
.) added a Non-Hungarian option.


###########################################################
7feb21: uploaded to SourceForge, GitHub
###########################################################

5feb21:
.) collapsed 4PQs into One...
	Memory savings allows more solved puzzles.
.) also updated embedded solver.


4feb21:
.) hbox4q, hbox4e : quick/efficient methods;
	hbox4e is default within embedded solver.
	Still makes stupid moves!
.) changed standalone solvers to output into
	solutionPath unbounded_string rather than
	a file.
.) updated asok,sban,coterm embedded solvers.


3feb21:
.) added use of totmovz within hsaveifnew4, BUT...
	it runs o2 in 31 sec now rather than 17 sec ???
	see utils.adb::2488
	Original is called hboxq; this is hbox.
	But note that solns are more efficient.

1feb21:
.) added hbox4 to emsolvers; so now there are 3.
.) removed emutils; emsolvers now uses utils.
.) needs some more testing. hbox4 solns are often
	far from efficient. Thus needed to retain
	puller and ibox.


29jan21:
.) fixed foghNum_11, #8,9. These were initially solved!!!
	I believe intent was to move pusher to other corral.
.) FAILed @ reallocation of round-robin cycles to most
	needy parameter. No way to asses relative merits.

27jan21:
.) Conclusion: neither DP-pull-sweeps nor a full puller 
	search algorithm suffices to elliminate puller-deadlocks.
	So I'm staying with DP and accepting imperfection.
	Reverse solving still elliminates box deadlocks,
	which is a very big deal. See: dpbox [hungarian / utils]

27jan21:
.) removed a few myasserts from utils.adb.
.) removed restore; now use restore2.
.) updated hungarian.inithun with additional or-condition
	to admit ff=2 goals to the valid set to check.
	Also ensured hungarian.dpbox uses pull-feasibility.
	Used asok to verify.
.) finalized utils.dpbox to use only 2nd condition.

26jan21:
.) found/fixed error in utils.dpbox. Now I start DP sweeps
	from goals only...revert if problem...

.) slight improvement in hungarian.init;
	Check if bvalid is different...
	YES, but perfect results. Make sure all versions
	of hungarian.adb have this code!

24jan21:
.) changed utils.adb::2815 remdead...
	need to test...FAILs on t7, reverted.

23jan21:
.) Fixed hungarian error on MP21, although it is beyond
	my capability to solve. Raised pri0 limit from
	500 to 700. Changed back AND put critical constants
	into utiltypes.ads.
.) tried w/o Hungarian. Amazing!!! solver is almost
	useless! Proves what an incredible contribution 
	that the Hungarian Algorithm provides.

22jan21:
.) changed definitions of boxes blocking rooms
	or boxes that are themselves blocked so that
	we do NOT count them if they are on a goal. DONE,
	however blocking boxes that are on goals are
	counted as 1/2 box. Improved 3 puzzle solns.

21jan21:
.) New Leader "aboxa" uses the 3 reversed count ftns.
	and solves o4 in 17 sec, which was unsolvable
	using forward count ftns. Several others were
	improved. Seems to imply it must be right. BUT,
	two anomalies remain. t7, is very much slower,
	and x81 is now unsolvable. Both are solved
	easily using forward count ftns.

20jan21:
.) bumped maxbx from 24 to 34 (o48). Speeds SEEM
	unaffected, so I'll leave it there.
.) DROPPED 3 expensive function evaluations when no longer
	needed: countCorrals, countBlockedRooms, countBlockedBoxes.
	Saves noticeable time on many puzzles.

19jan21:
.) created abox.adb = Advisory version...
	slightly modifies round robin regimen when
	advantageous.
.) fixed bestbog.
.) added 1 extra count to visit pri#1 twice
	per circuit: 0,1=>pri1, 2=>pri2, 3=>pri3
	4=>pri4. This because I saw how critical
	was a single extra [first] visit to pri1... 
	it halved the runtime in one case.
.) added "abox0" version that never shortcuts
	round robin to try on stubborn puzzles.

17jan21:
.) converted to use "mem4ada_hpp" (linux-only)
	Readings are more recent, and very quick
	and more conservative because it measures 
	free memory, not available memory. Thus, the
	threshold is now lowered to 10%.

