


--
-- Copyright (C) 2023  <fastrgv@gmail.com>
--
-- This program is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You may read the full text of the GNU General Public License
-- at <http://www.gnu.org/licenses/>.
--


-- Breadth First (now A*) Search cube.adb puzzle solver...
--
-- Uses a splaytree, to test whether a given config was seen before.  
-- Extremely fast access.
--
-- Uses a fullproof Key-type, for which we must define
-- operators "<" and ">".

-- To Do: understand why [pri := nt+dist2sol] WORKS for fbfs7.adb
-- and FAILS here, yet [pri := nt/2 + dist2sol] works fine!







with splaypq0;
with splaytree;
with text_io;

with Ada.Strings.Unbounded;
with Ada.Strings.Unbounded.Text_IO;

with ada.command_line;
with ada.calendar;

with utils4;


package body utils4 is



	use Ada.Strings.Unbounded;
	use Ada.Strings.Unbounded.Text_IO;

	use text_io;



function i2ch( i: integer ) return character is
begin
	case i is
		when 0=> return '0';
		when 1=> return '1';
		when 2=> return '2';
		when 3=> return '3';
		when 4=> return '4';
		when 5=> return '5';
		when 6=> return '6';
		when 7=> return '7';
		when 8=> return '8';
		when 9=> return '9';
		when others => return ' ';
	end case;
end i2ch;



function key2str( key: keytype ) return string is
	ich: integer;
	str: string(1..45);
begin
	str(1):=' ';
	for id in rngp loop --0..10
		for j in 1..3 loop
			ich:=key(id)(j); --note: in 0..9
			str( 1+4*id + j ) := i2ch(ich);
		end loop; --j
		str(1+4*id+4):=' ';
	end loop; --id
	return str;
end key2str;




procedure test4winner( icentro: in iparray ) is
begin

	winner := (icentro=centroidMid);

end test4winner;





--------------------------------------------------------------------------


function trynear(ii: rngp; centro: in iparray; empt:in emptytype) return boolean is -- +Z
	ix,iy,iz : integer;
	ox,oy,oz : integer;
	sx,sy,sz : integer;
	ok, leadingVoid : boolean;
begin
	ox:=centro(ii)(1);
	oy:=centro(ii)(2);
	oz:=centro(ii)(3);

	sx:=space(ii)(1);
	sy:=space(ii)(2);
	sz:=space(ii)(3);

	leadingVoid := (sz=1);


	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sz=1)

		if    i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	else -- trailing void (sz=0)

		if   i/=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;



	-- next centro:
	ix:=ox;
	iy:=oy;
	iz:=oz+1;

	-- next test location
	--iz:=iz+1;

	if iz>mz then
		return false;

	elsif ii<=5 and iz+1<=mz then --typical 4-cubelet corner piece

		ok:=true;
		for i in 0..1 loop
		for j in 0..1 loop
		for k in 0..1 loop
			if probe(i,j,k) and not empt(ix+i,iy+j,iz+k) then
				ok:=false;
			end if;
		end loop;
		end loop;
		end loop;

		return ok;

	elsif ii=10 and iz+1<=mz then --2x2x2 skull

		if
			empt( ix+0,iy+0,iz+1 ) and
			empt( ix+1,iy+0,iz+1 ) and
			empt( ix+1,iy+1,iz+1 ) and
			empt( ix+0,iy+1,iz+1 )
		then
			return true;
		else
			return false;
		end if;


	elsif (ii=6 or ii=9) and iz+1<=mz then --L-shaped pieces

		if
			empt( ix,iy+0,iz+1 ) --botFront clear
				and
			empt( ix,iy+1,iz+1 ) --topFront clear
		then
			return true;
		else
			return false;
		end if;


	elsif ii=7 or ii=8 then -- 1x1 pieces
		if empt(ix,iy,iz) then
			return true;
		else
			return false;
		end if;


	else
		return false;

	end if;

end trynear;









function tryaway(ii: rngp; centro: in iparray; empt:in emptytype) return boolean is -- -Z
	ix,iy,iz : integer;
	ox,oy,oz : integer;
	sx,sy,sz : integer;
	ok, leadingVoid : boolean;
begin
	ox:=centro(ii)(1);
	oy:=centro(ii)(2);
	oz:=centro(ii)(3);

	sx:=space(ii)(1);
	sy:=space(ii)(2);
	sz:=space(ii)(3);

	leadingVoid := (sz=0);



	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sz=0)

		if    i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	else -- trailing void (sz=1)

		if   i/=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;




	-- next centro:
	ix:=ox;
	iy:=oy;
	iz:=oz-1;

	-- next test location
	--iz:=iz+0;


	if iz<1 then
		return false;

	elsif ii<=5  then --typical 4-cubelet piece

		ok:=true;
		for i in 0..1 loop
		for j in 0..1 loop
		for k in 0..1 loop
			if probe(i,j,k) and not empt(ix+i,iy+j,iz+k) then
				ok:=false;
			end if;
		end loop;
		end loop;
		end loop;

		return ok;

	elsif ii=10 then -- 2x2x2 skull

		if
			empt( ix+0,iy+0,iz ) and
			empt( ix+1,iy+0,iz ) and
			empt( ix+1,iy+1,iz ) and
			empt( ix+0,iy+1,iz )
		then
			return true;
		else
			return false;
		end if;


	elsif ii=6 or ii=9 then -- L-shaped pieces

		if
			empt( ix,iy+1,iz+1 ) --topFront clear
				and
			empt( ix,iy+0,iz+0 ) --botRear clear
		then
			return true;
		else
			return false;
		end if;


	elsif ii=7 or ii=8 then -- 1x1x1
		if empt(ix,iy,iz) then
			return true;
		else
			return false;
		end if;


	else
		return false;


	end if;

end tryaway;














function tryup(ii: rngp; centro: in iparray; empt:in emptytype) return boolean is -- +Y
	ix,iy,iz : integer;
	ox,oy,oz : integer;
	sx,sy,sz : integer;
	ok, leadingVoid : boolean;
begin


	ox:=centro(ii)(1);
	oy:=centro(ii)(2);
	oz:=centro(ii)(3);

	sx:=space(ii)(1);
	sy:=space(ii)(2);
	sz:=space(ii)(3);

	leadingVoid := (sy=1);




	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sy=1)

		if    i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	else -- trailing void (sy=0)

		if   i/=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;





	-- next centro:
	ix:=ox;
	iy:=oy+1;
	iz:=oz;

	-- next test location
	--iy:=iy+1;


	--if iy+1>my and ii/=7 and ii/=8 then --?wrong?
	if iy>my then
		return false;

	elsif ii<=5  and iy+1<=my then --typical 4-cubelet pieces

		ok:=true;
		for i in 0..1 loop
		for j in 0..1 loop
		for k in 0..1 loop
			if probe(i,j,k) and not empt(ix+i,iy+j,iz+k) then
				ok:=false;
			end if;
		end loop;
		end loop;
		end loop;

		return ok;

	elsif ii=10  and iy+1<=my then --2x2x2 skull

		if
			empt( ix+0,iy+1,iz+0 ) and
			empt( ix+1,iy+1,iz+0 ) and
			empt( ix+1,iy+1,iz+1 ) and
			empt( ix+0,iy+1,iz+1 )
		then
			return true;
		else
			return false;
		end if;



	elsif (ii=6 or ii=9) and iy+1<=my then -- L-shaped pieces


		if
			empt( ix,iy+1,iz+1 ) --topFront clear
				and
			empt( ix,iy+0,iz+0 ) --botRear clear
		then
			return true;
		else
			return false;
		end if;


	elsif ii=7 or ii=8 then

		if empt(ix,iy,iz) then
			return true;
		else
			return false;
		end if;


	else

		return false;


	end if;


end tryup;












function trydown(ii: rngp; centro: in iparray; empt:in emptytype) return boolean is -- -Y
	ix,iy,iz : integer;
	ox,oy,oz : integer;
	sx,sy,sz : integer;
	ok, leadingVoid : boolean;
begin
	ox:=centro(ii)(1);
	oy:=centro(ii)(2);
	oz:=centro(ii)(3);

	sx:=space(ii)(1);
	sy:=space(ii)(2);
	sz:=space(ii)(3);

	leadingVoid := (sy=0);



	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sy=0)

		if    i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	else -- trailing void (sy=1)

		if   i/=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;





	-- next centro:
	ix:=ox;
	iy:=oy-1;
	iz:=oz;

	-- next test location
	--iy:=iy+0;


	if iy<1 then

		return false;

	elsif ii<=5  then --typical 4-cubelet piece

		ok:=true;
		for i in 0..1 loop
		for j in 0..1 loop
		for k in 0..1 loop
			if probe(i,j,k) and not empt(ix+i,iy+j,iz+k) then
				ok:=false;
			end if;
		end loop;
		end loop;
		end loop;

		return ok;

	elsif ii=10 then --2x2x2 skull

		if
			empt( ix+0,iy,iz+0 ) and
			empt( ix+1,iy,iz+0 ) and
			empt( ix+1,iy,iz+1 ) and
			empt( ix+0,iy,iz+1 )
		then
			return true;
		else
			return false;
		end if;



	elsif ii=6 or ii=9 then

		if
			empt( ix,iy+0,iz+1 ) --botFront clear
				and
			empt( ix,iy+0,iz+0 ) --botRear clear
		then
			return true;
		else
			return false;
		end if;


	elsif ii=7 or ii=8 then
		if empt(ix,iy,iz) then
			return true;
		else
			return false;
		end if;



	else
		return false;


	end if; -- leadingVoid

end trydown;

















function tryright(ii: rngp; centro: in iparray; empt:in emptytype) return boolean is -- +X
	ix,iy,iz : integer;
	ox,oy,oz : integer;
	sx,sy,sz : integer;
	ok, leadingVoid : boolean;
begin
	ox:=centro(ii)(1);
	oy:=centro(ii)(2);
	oz:=centro(ii)(3);

	sx:=space(ii)(1);
	sy:=space(ii)(2);
	sz:=space(ii)(3);

	leadingVoid := (sx=1);



	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sx=1)

		if    i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	else -- trailing void (sx=0)

		if   i/=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;





	-- next centro:
	ix:=ox+1;
	iy:=oy;
	iz:=oz;

	-- next test location
	--ix:=ix+1;


	if ix>mx then
		return false;

	elsif ii<=5 and ix+1<=mx then --typical 4-cubelet piece

		ok:=true;
		for i in 0..1 loop
		for j in 0..1 loop
		for k in 0..1 loop
			if probe(i,j,k) and not empt(ix+i,iy+j,iz+k) then
				ok:=false;
			end if;
		end loop;
		end loop;
		end loop;

		return ok;

	elsif ii=10 and ix+1<=mx then --2x2x2 skull

		if
			empt( ix+1,iy+0,iz+0 ) and
			empt( ix+1,iy+1,iz+0 ) and
			empt( ix+1,iy+1,iz+1 ) and
			empt( ix+1,iy+0,iz+1 )
		then
			return true;
		else
			return false;
		end if;



	elsif ii=6 or ii=9 then -- L-shaped pieces

		if
			empt( ix,iy+0,iz+1 ) --botFront clear
				and
			empt( ix,iy+1,iz+1 ) --topFront clear
				and
			empt( ix,iy+0,iz+0 ) --botRear clear
		then
			return true;
		else
			return false;
		end if;


	elsif ii=7 or ii=8 then -- 1x1x1 pieces
		if empt(ix,iy,iz) then
			return true;
		else
			return false;
		end if;



	else
		return false;


	end if;

end tryright;
















function tryleft(ii: rngp; centro: in iparray; empt:in emptytype) return boolean is -- -X
	ix,iy,iz : integer;
	ox,oy,oz : integer;
	sx,sy,sz : integer;
	ok, leadingVoid : boolean;
begin
	ox:=centro(ii)(1);
	oy:=centro(ii)(2);
	oz:=centro(ii)(3);

	sx:=space(ii)(1);
	sy:=space(ii)(2);
	sz:=space(ii)(3);

	leadingVoid := (sx=0);



	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sx=0)

		if    i=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	else -- trailing void (sx=1)

		if   i/=sx and j/=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then probe(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then probe(i,j,k):=true;
		else probe(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;





	-- next centro:
	ix:=ox-1;
	iy:=oy;
	iz:=oz;

	-- next test location
	--ix:=ix+0;


	if ix<1 then
		return false;

	elsif ii<=5  then --typical 4-cubelet pieces

		ok:=true;
		for i in 0..1 loop
		for j in 0..1 loop
		for k in 0..1 loop
			if probe(i,j,k) and not empt(ix+i,iy+j,iz+k) then
				ok:=false;
			end if;
		end loop;
		end loop;
		end loop;

		return ok;

	elsif ii=10 then -- 2x2x2 skull

		if
			empt( ix,iy+0,iz+0 ) and
			empt( ix,iy+1,iz+0 ) and
			empt( ix,iy+1,iz+1 ) and
			empt( ix,iy+0,iz+1 )
		then
			return true;
		else
			return false;
		end if;



	elsif ii=6 or ii=9 then -- L-shaped pieces

		if
			empt( ix,iy+0,iz+1 ) --botFront clear
				and
			empt( ix,iy+1,iz+1 ) --topFront clear
				and
			empt( ix,iy+0,iz+0 ) --botRear clear
		then
			return true;
		else
			return false;
		end if;


	elsif ii=7 or ii=8 then
		if empt(ix,iy,iz) then
			return true;
		else
			return false;
		end if;



	else
		return false;


	end if;

end tryleft;


---------------------------------------------------------------------------




function movenear( 
	ikk: in integer;
	centro: in out iparray;
	empt:in out emptytype;
	track:boolean:=false) return boolean is -- +Z

	ix,iy,iz : integer;
	sx,sy,sz : integer;
	leadingVoid : boolean;
	kk: integer := ikk;
begin


if  not track and not trynear(kk,centro,empt) then -- pick one that might make sense
	for i in 0..10 loop
		if trynear(i,centro,empt) then
			kk:=i;
			exit;
		end if;
	end loop;
end if;


if not trynear(kk,centro,empt) then
	return false;

else

	--if kk/=ikk then --WARNING: this disables autoselect
	--	return false;
	--end if;

	if not bfsWorking then
	append(restoreBuf, integer'image(kk) & " n ");
	end if;

	oxc:=centro(kk)(1);
	oyc:=centro(kk)(2);
	ozc:=centro(kk)(3);

	sx:=space(kk)(1);
	sy:=space(kk)(2);
	sz:=space(kk)(3);

	ix:=oxc;
	iy:=oyc;
	iz:=ozc;

	leadingVoid := (sz=1);

	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sz=1)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	else -- trailing void (sz=0)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;




	if kk=10 then -- (easy) 2x2x2 skull

		-- trailing face wake:
		empt( ix+0,iy+0,iz+0 ):=true;
		empt( ix+1,iy+0,iz+0 ):=true;
		empt( ix+1,iy+1,iz+0 ):=true;
		empt( ix+0,iy+1,iz+0 ):=true;

		-- make the move:
		centro(kk)(3):=centro(kk)(3)+1;
		iz:=centro(kk)(3);

		-- leading face probe:
		empt( ix+0,iy+0,iz+1 ):=false;
		empt( ix+1,iy+0,iz+1 ):=false;
		empt( ix+1,iy+1,iz+1 ):=false;
		empt( ix+0,iy+1,iz+1 ):=false;



	elsif kk=6  or kk=9 then -- L-shaped pieces

		-- trailing face:
		empt( ix,iy+0,iz+0 ):=true; --bottom-rear-cubelet leaves a space
		empt( ix,iy+1,iz+1 ):=true; --top-front-cubelet leaves a space

		-- make the move:
		centro(kk)(3):=centro(kk)(3)+1;
		iz:=centro(kk)(3);

		-- leading face:
		empt( ix,iy+0,iz+1 ):=false; --bottom-front-cubelet moves forward
		empt( ix,iy+1,iz+1 ):=false; --top-front-cubelet moves forward
		--bottom-rear cubelet moves into old pos of bottom-front cubelet


	elsif kk=7 or kk=8 then -- single cubelets

		empt(ix,iy,iz):=true;
		centro(kk)(3):=centro(kk)(3)+1;
		iz:=centro(kk)(3);
		empt(ix,iy,iz):=false;


	else -- we have a typical 4-cubelet corner piece

		-- trailing face wake:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if wake(i,j,k) then
						empt(ix+i,iy+j,iz+k):=true;
					end if;
				end loop;
			end loop;
		end loop;

		-- make the move:
		centro(kk)(3):=centro(kk)(3)+1;
		iz:=centro(kk)(3);

		-- leading face probe:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if probe(i,j,k) then
						empt(ix+i,iy+j,iz+k):=false;
					end if;
				end loop;
			end loop;
		end loop;

	end if;

	if track then
	myassert(kk=ikk,1,"moveNear");
	ntrail:=ntrail+1;
	trailsel(ntrail):=kk;
	trailchr(ntrail):='n';
	trailenc(ntrail):=centro;
	end if;

	test4winner(centro);


	grinding(kk):=true;
	return true;

end if; --trynear

end movenear;
-----------------------------------------------------------



function moveaway( 
	ikk: in integer ; 
	centro: in out iparray;
	empt:in out emptytype;
	track:boolean:=false) return boolean is -- -Z
	ix,iy,iz : integer;
	sx,sy,sz : integer;
	leadingVoid : boolean;
	kk: integer := ikk;
begin

if   not track and not tryaway(kk,centro,empt) then -- pick one that might make sense
	for i in 0..10 loop
		if tryaway(i,centro,empt) then
			kk:=i;
			exit;
		end if;
	end loop;
end if;




if not tryaway(kk,centro,empt) then
	return false;

else

	--if kk/=ikk then
	--	return false;
	--end if;


	if not bfsWorking then
	append(restoreBuf, integer'image(kk) & " a ");
	end if;

	oxc:=centro(kk)(1);
	oyc:=centro(kk)(2);
	ozc:=centro(kk)(3);

	sx:=space(kk)(1);
	sy:=space(kk)(2);
	sz:=space(kk)(3);

	ix:=centro(kk)(1);
	iy:=centro(kk)(2);
	iz:=centro(kk)(3);

	leadingVoid := (sz=0);


	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sz=0)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	else -- trailing void (sz=1)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;




	if kk=10 then -- (easy)

		-- trailing face:
		empt( ix+0,iy+0,iz+1 ):=true;
		empt( ix+1,iy+0,iz+1 ):=true;
		empt( ix+1,iy+1,iz+1 ):=true;
		empt( ix+0,iy+1,iz+1 ):=true;

		-- make the move:
		centro(kk)(3):=centro(kk)(3)-1;
		iz:=centro(kk)(3);

		-- leading face:
		empt( ix+0,iy+0,iz+0 ):=false;
		empt( ix+1,iy+0,iz+0 ):=false;
		empt( ix+1,iy+1,iz+0 ):=false;
		empt( ix+0,iy+1,iz+0 ):=false;



	elsif kk=6  or kk=9 then -- L-shaped pieces

		-- trailing face:
		empt( ix,iy+0,iz+1 ):=true; --botfront leaves a space
		empt( ix,iy+1,iz+1 ):=true; --topfront leaves a space

		-- make the move:
		centro(kk)(3):=centro(kk)(3)-1;
		iz:=centro(kk)(3);

		-- leading face:
		empt( ix,iy+0,iz+0 ):=false; --botrear moves back
		empt( ix,iy+1,iz+1 ):=false; --topfront moves back
		--botfront cubelet moves into old pos of botrear


	elsif kk=7 or kk=8 then -- singles
		empt(ix,iy,iz):=true;
		centro(kk)(3):=centro(kk)(3)-1;
		iz:=centro(kk)(3);
		empt(ix,iy,iz):=false;


	else --typical 4-cubelet pieces

		-- trailing face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if wake(i,j,k) then
						empt(ix+i,iy+j,iz+k):=true;
					end if;
				end loop;
			end loop;
		end loop;

		-- make the move:
		centro(kk)(3):=centro(kk)(3)-1;
		iz:=centro(kk)(3);

		-- leading face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if probe(i,j,k) then
						empt(ix+i,iy+j,iz+k):=false;
					end if;
				end loop;
			end loop;
		end loop;

	end if;


	if track then
	myassert(kk=ikk,2,"moveAway");
	ntrail:=ntrail+1;
	trailsel(ntrail):=kk;
	trailchr(ntrail):='a';
	trailenc(ntrail):=centro;
	end if;

	test4winner(centro);


	grinding(kk):=true;
	return true;

end if; --tryaway


end moveaway;




function moveleft( 
	ikk: in integer ; 
	centro: in out iparray;
	empt:in out emptytype;
	track:boolean:=false) return boolean is -- -X
	ix,iy,iz : integer;
	sx,sy,sz : integer;
	leadingVoid : boolean;
	kk: integer := ikk;
begin

if   not track and not tryleft(kk,centro,empt) then -- pick one that might make sense
	for i in 0..10 loop
		if tryleft(i,centro,empt) then
			kk:=i;
			exit;
		end if;
	end loop;
end if;



if not tryleft(kk,centro,empt) then
	return false;

else

	--if kk/=ikk then
	--	return false;
	--end if;


	if not bfsWorking then
	append(restoreBuf, integer'image(kk) & " l ");
	end if;

	oxc:=centro(kk)(1);
	oyc:=centro(kk)(2);
	ozc:=centro(kk)(3);

	sx:=space(kk)(1);
	sy:=space(kk)(2);
	sz:=space(kk)(3);

	ix:=centro(kk)(1);
	iy:=centro(kk)(2);
	iz:=centro(kk)(3);

	leadingVoid := (sx=0);


	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sx=0)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	else -- trailing void (sx=1)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;




	if kk=10 then -- (easy) skull

		-- trailing face:
		empt( ix+1,iy+0,iz+0 ):=true;
		empt( ix+1,iy+0,iz+1 ):=true;
		empt( ix+1,iy+1,iz+0 ):=true;
		empt( ix+1,iy+1,iz+1 ):=true;

		-- make the move:
		centro(kk)(1):=centro(kk)(1)-1;
		ix:=centro(kk)(1);

		-- leading face:
		empt( ix+0,iy+0,iz+0 ):=false;
		empt( ix+0,iy+0,iz+1 ):=false;
		empt( ix+0,iy+1,iz+0 ):=false;
		empt( ix+0,iy+1,iz+1 ):=false;



	elsif kk=6 or kk=9 then -- L-shaped pieces

		-- trailing face wake:
		empt( ix,iy+0,iz+0 ):=true; --botrear leaves a space
		empt( ix,iy+0,iz+1 ):=true; --botfront leaves a space
		empt( ix,iy+1,iz+1 ):=true; --topfront leaves a space

		-- make the move:
		centro(kk)(1):=centro(kk)(1)-1;
		ix:=centro(kk)(1);

		-- leading face probe:
		empt( ix,iy+0,iz+0 ):=false; --botrear moves left
		empt( ix,iy+0,iz+1 ):=false; --botfront moves left
		empt( ix,iy+1,iz+1 ):=false; --topfront moves left


	elsif kk=7 or kk=8 then --singles
		empt(ix,iy,iz):=true;
		centro(kk)(1):=centro(kk)(1)-1;
		ix:=centro(kk)(1);
		empt(ix,iy,iz):=false;



	else -- typical 4-cubelet pieces

		-- trailing face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if wake(i,j,k) then
						empt(ix+i,iy+j,iz+k):=true;
					end if;
				end loop;
			end loop;
		end loop;

		-- make the move:
		centro(kk)(1):=centro(kk)(1)-1;
		ix:=centro(kk)(1);

		-- leading face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if probe(i,j,k) then
						empt(ix+i,iy+j,iz+k):=false;
					end if;
				end loop;
			end loop;
		end loop;

	end if;


	if track then
	myassert(kk=ikk,3,"moveLeft");
	ntrail:=ntrail+1;
	trailsel(ntrail):=kk;
	trailchr(ntrail):='l';
	trailenc(ntrail):=centro;
	end if;

	test4winner(centro);


	grinding(kk):=true;
	return true;

end if; --tryleft


end moveleft;




function moveright( 
	ikk: in integer ; 
	centro: in out iparray;
	empt:in out emptytype;
	track:boolean:=false) return boolean is -- +X
	ix,iy,iz : integer;
	sx,sy,sz : integer;
	leadingVoid : boolean;
	kk: integer := ikk;
begin

if   not track and not tryright(kk,centro,empt) then -- pick one that might make sense
	for i in 0..10 loop
		if tryright(i,centro,empt) then
			kk:=i;
			exit;
		end if;
	end loop;
end if;




if not tryright(kk,centro,empt) then
	return false;

else

	--if kk/=ikk then
	--	return false;
	--end if;

	if not bfsWorking then
	append(restoreBuf, integer'image(kk) & " r ");
	end if;

	oxc:=centro(kk)(1);
	oyc:=centro(kk)(2);
	ozc:=centro(kk)(3);

	sx:=space(kk)(1);
	sy:=space(kk)(2);
	sz:=space(kk)(3);

	ix:=centro(kk)(1);
	iy:=centro(kk)(2);
	iz:=centro(kk)(3);

	leadingVoid := (sx=1);


	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sx=1)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	else -- trailing void (sx=0)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;




	if kk=10 then -- (easy) skull

		empt( ix+0,iy+0,iz+0 ):=true;
		empt( ix+0,iy+0,iz+1 ):=true;
		empt( ix+0,iy+1,iz+0 ):=true;
		empt( ix+0,iy+1,iz+1 ):=true;

		-- make the move:
		centro(kk)(1):=centro(kk)(1)+1;
		ix:=centro(kk)(1);

		empt( ix+1,iy+0,iz+0 ):=false;
		empt( ix+1,iy+0,iz+1 ):=false;
		empt( ix+1,iy+1,iz+0 ):=false;
		empt( ix+1,iy+1,iz+1 ):=false;



	elsif kk=6 or kk=9 then -- L-shaped pieces

		-- trailing face wake:
		empt( ix,iy+0,iz+0 ):=true; --botrear cubelet leaves a space
		empt( ix,iy+0,iz+1 ):=true; --botfront
		empt( ix,iy+1,iz+1 ):=true; --topfront

		-- make the move:
		centro(kk)(1):=centro(kk)(1)+1;
		ix:=centro(kk)(1);

		-- leading face probe:
		empt( ix,iy+0,iz+0 ):=false; --botrear moves right
		empt( ix,iy+0,iz+1 ):=false; --botfront
		empt( ix,iy+1,iz+1 ):=false; --topfront


	elsif kk=7 or kk=8 then --singles
		empt(ix,iy,iz):=true;
		centro(kk)(1):=centro(kk)(1)+1;
		ix:=centro(kk)(1);
		empt(ix,iy,iz):=false;



	else -- typical 4-cubelet pieces

		-- trailing face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if wake(i,j,k) then
						empt(ix+i,iy+j,iz+k):=true;
					end if;
				end loop;
			end loop;
		end loop;

		-- make the move:
		centro(kk)(1):=centro(kk)(1)+1;
		ix:=centro(kk)(1);

		-- leading face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if probe(i,j,k) then
						empt(ix+i,iy+j,iz+k):=false;
					end if;
				end loop;
			end loop;
		end loop;

	end if;



	if track then
	myassert(kk=ikk,4,"moveRight");
	ntrail:=ntrail+1;
	trailsel(ntrail):=kk;
	trailchr(ntrail):='r';
	trailenc(ntrail):=centro;
	end if;

	test4winner(centro);


	grinding(kk):=true;
	return true;

end if; --tryright


end moveright;






function movedown( 
	ikk: in integer; 
	centro: in out iparray;
	empt:in out emptytype;
	track:boolean:=false ) return boolean is -- -Y
	ix,iy,iz : integer;
	sx,sy,sz : integer;
	leadingVoid : boolean;
	kk: integer := ikk;
begin
 
if   not track and not trydown(kk,centro,empt) then -- pick one that might make sense
	for i in 0..10 loop
		if trydown(i,centro,empt) then
			kk:=i;
			exit;
		end if;
	end loop;
end if;




if not trydown(kk,centro,empt) then
	return false;

else

	--if kk/=ikk then
	--	return false;
	--end if;

	if not bfsWorking then
	append(restoreBuf, integer'image(kk) & " d ");
	end if;

	oxc:=centro(kk)(1);
	oyc:=centro(kk)(2);
	ozc:=centro(kk)(3);

	sx:=space(kk)(1);
	sy:=space(kk)(2);
	sz:=space(kk)(3);

	ix:=centro(kk)(1);
	iy:=centro(kk)(2);
	iz:=centro(kk)(3);

	leadingVoid := (sy=0);


	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sy=0)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	else -- trailing void (sy=1)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;




	if kk=10 then -- (easy) skull

		empt( ix+0,iy+1,iz+0 ):=true;
		empt( ix+0,iy+1,iz+1 ):=true;
		empt( ix+1,iy+1,iz+0 ):=true;
		empt( ix+1,iy+1,iz+1 ):=true;

		-- make the move:
		centro(kk)(2):=centro(kk)(2)-1;
		iy:=centro(kk)(2);

		empt( ix+0,iy+0,iz+0 ):=false;
		empt( ix+0,iy+0,iz+1 ):=false;
		empt( ix+1,iy+0,iz+0 ):=false;
		empt( ix+1,iy+0,iz+1 ):=false;


	elsif kk=6 or kk=9 then -- L-shaped pieces

		empt( ix,iy+1,iz+1 ):=true; --topfront cubelet leaves a space
		empt( ix,iy+0,iz+0 ):=true; --botrear leaves space

		-- make the move:
		centro(kk)(2):=centro(kk)(2)-1;
		iy:=centro(kk)(2);

		empt( ix,iy+0,iz+1 ):=false; --botfront moves down
		empt( ix,iy+0,iz+0 ):=false; --botrear moves down
		--topfront moves down into old pos of botfront


	elsif kk=7 or kk=8 then --singles
		empt(ix,iy,iz):=true;
		centro(kk)(2):=centro(kk)(2)-1;
		iy:=centro(kk)(2);
		empt(ix,iy,iz):=false;



	else --typical 4-cubelet pieces

		-- trailing face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if wake(i,j,k) then
						empt(ix+i,iy+j,iz+k):=true;
					end if;
				end loop;
			end loop;
		end loop;

		-- make the move:
		centro(kk)(2):=centro(kk)(2)-1;
		iy:=centro(kk)(2);

		-- leading face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if probe(i,j,k) then
						empt(ix+i,iy+j,iz+k):=false;
					end if;
				end loop;
			end loop;
		end loop;

	end if;




	if track then
	myassert(kk=ikk,5,"moveDown");
	ntrail:=ntrail+1;
	trailsel(ntrail):=kk;
	trailchr(ntrail):='d';
	trailenc(ntrail):=centro;
	end if;

	test4winner(centro);


	grinding(kk):=true;
	return true;

end if; --trydown


end movedown;



function moveup( 
	ikk: in integer ; 
	centro: in out iparray;
	empt:in out emptytype;
	track:boolean:=false) return boolean is -- +Y
	ix,iy,iz : integer;
	sx,sy,sz : integer;
	leadingVoid : boolean;
	kk: integer := ikk;
begin


if   not track and not tryup(kk,centro,empt) then -- pick one that might make sense


	for i in 0..10 loop


		if tryup(i,centro,empt) then
			kk:=i;
			exit;
		end if;


	end loop;
end if;



if not tryup(kk,centro,empt) then
	return false;

else


	--if kk/=ikk then
	--	return false;
	--end if;

	if not bfsWorking then
	append(restoreBuf, integer'image(kk) & " u ");
	end if;

	oxc:=centro(kk)(1);
	oyc:=centro(kk)(2);
	ozc:=centro(kk)(3);

	sx:=space(kk)(1);
	sy:=space(kk)(2);
	sz:=space(kk)(3);

	ix:=centro(kk)(1);
	iy:=centro(kk)(2);
	iz:=centro(kk)(3);

	leadingVoid := (sy=1);



	for i in 0..1 loop
	for j in 0..1 loop
	for k in 0..1 loop
	if leadingVoid then -- (sy=1)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	else -- trailing void (sy=0)

		if   i/=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=false;
		elsif i=sx and j/=sy and k/=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		elsif i/=sx and j=sy and k/=sz then 
			probe(i,j,k):=false;
			wake(i,j,k):=true;
		elsif i/=sx and j/=sy and k=sz then 
			probe(i,j,k):=true;
			wake(i,j,k):=true;
		else 
			probe(i,j,k):=false;
			wake(i,j,k):=false;
		end if;

	end if;
	end loop;
	end loop;
	end loop;





	if kk=10 then -- (easy) skull

		-- trailing face:
		empt( ix+0,iy+0,iz+0 ):=true;
		empt( ix+0,iy+0,iz+1 ):=true;
		empt( ix+1,iy+0,iz+0 ):=true;
		empt( ix+1,iy+0,iz+1 ):=true;

		-- make the move:
		centro(kk)(2):=centro(kk)(2)+1;
		iy:=centro(kk)(2);

		-- leading face:
		empt( ix+0,iy+1,iz+0 ):=false;
		empt( ix+0,iy+1,iz+1 ):=false;
		empt( ix+1,iy+1,iz+0 ):=false;
		empt( ix+1,iy+1,iz+1 ):=false;


	elsif kk=6 or kk=9 then -- L-shaped pieces

		empt( ix,iy+0,iz+1 ):=true; --botfront cubelet leaves a space
		empt( ix,iy+0,iz+0 ):=true; --botrear leaves space

		-- make the move:
		centro(kk)(2):=centro(kk)(2)+1;
		iy:=centro(kk)(2);

		empt( ix,iy+1,iz+1 ):=false; --topfront cubelet moves up
		empt( ix,iy+0,iz+0 ):=false; --botrear moves up
		--botfront moves up into old pos of topfront


	elsif kk=7 or kk=8 then --singles
		empt(ix,iy,iz):=true;
		centro(kk)(2):=centro(kk)(2)+1;
		iy:=centro(kk)(2);
		empt(ix,iy,iz):=false;



	else -- typical 4-cubelet pieces

		-- trailing face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if wake(i,j,k) then
						empt(ix+i,iy+j,iz+k):=true;
					end if;
				end loop;
			end loop;
		end loop;

		-- make the move:
		centro(kk)(2):=centro(kk)(2)+1;
		iy:=centro(kk)(2);

		-- leading face:
		for i in 0..1 loop
			for j in 0..1 loop
				for k in 0..1 loop
					if probe(i,j,k) then
						empt(ix+i,iy+j,iz+k):=false;
					end if;
				end loop;
			end loop;
		end loop;

	end if;





	if track then
	myassert(kk=ikk,6,"moveUp");
	ntrail:=ntrail+1;
	trailsel(ntrail):=kk;
	trailchr(ntrail):='u';
	trailenc(ntrail):=centro;
	end if;


	test4winner(centro);



	grinding(kk):=true;
	return true;

end if; --tryup


end moveup;











end utils4; --package
