image thumbnail

Mathworks Rubik version 2

by

 

04 Apr 2013 (Updated )

Display, tester and solver of the Rubik's game, including "full cubes".

... MyColor(:,iCube); if N(iFace)>4 error('!!Impossible cube!!! - full cube with impossible mid cube colors!!') end end end if any(N) if any(N==2) i=find(N==2); Cube=RotateTo(i(1),23,[],hAxes,[],Cube,Anime);
function [sol,Nparts]=SSSsolver(varargin)
% SSSsolver - Singmasters Step by Step Solution
%    sol=SSSsolver[(Cube)]
%
%  One of the many "step-by-step" solution where each step
%  solves one layer.
%  Some changes to the method from the book were done.

% too much calls of CheckCube --- a problem?
%    also a lot of RotateCube's for "easy alignment"

% when looking for a starting layer, with possible layer rotations:
%     getting a full layer, only turned is a fully bad layer
%       while it is "almost good"
%     ?a test to be added in CheckCube?
%     or using the loops


options=varargin;
hAxesBase=[];
if nargin&isstruct(varargin{1})
	Cube=varargin{1};
	options(1)=[];
else
	hAxesBase=FindRubikAxes;
	Cube=get(hAxesBase,'UserData');
end

NbfMax=1;
Anime=0;
bAnimeSepWin=1;
bCloseWin=1;
iAltSol=1;
bPostOptim=true;

% if ~isempty(varargin)
% 	setoptions({'NbfMax','Anime','bAnimeSepWin','iAltSol','bPostOptim'},options)
% end

if Anime
	if bAnimeSepWin
		f=findobj('Tag','SSSshow');
		if isempty(f)
			[f,hAxes]=Rubik;
			set(f,'Tag','SSSshow','Name','Singmasters Step by Step');
			set(hAxes,'Tag','SSSshowAxes')
		else
			hAxes=findobj(f,'Tag','SSSshowAxes');
		end
		PlotCube(hAxes,Cube);
	else
		hAxes=FindRubikAxes;
	end
else
	hAxes=[];
end

Cube.sol=[];
Nparts=zeros(1,9);

%%%% check for some easy to find solutions.
OK=false;
n=0;
while ~OK
	n=n+1;
	[sol,OK]=solverbbf(Cube,n);	% search by a "brute force" method
	if n>=NbfMax
		break;
	end
end
if ~OK
	sol=zeros(0,2);
	D=CheckCube(Cube);
		% Since brute force methods are checkd, D.OK will be false
	
	Rstart=[2 1;2 -1;1 -1;1 1;1 2;1 0];
	MidLayer=[10 12 16 18];
	%%Which layer to start with?
	iStart=find(D.NOK(:,1)==8);
	if isempty(iStart)
		% dummy search for a better start after one turn
		[mx,iStart]=FindBestStart(D);
		R=[1 0 0];
		while R(1)&mx<8
			R(1)=0;
			for Axe=1:3
				for Side=[-1 1]
					for Direction=[-1 1 2]
						C1=RotateLayer([],Cube,Axe,Side,Direction,0);
						D1=CheckCube(C1);
						[mx1,iMx1]=FindBestStart(D1);
						mx1=floor(mx1);	%!!!!no rotation only for corner
						if mx1>mx
							R(:)=[Axe Side Direction];
							mx=mx1;
							iStart=iMx1;
							if mx>=4
								% also here it is better to look to "the best second layer"!
								break
							end
						end
					end	% for Direction
					if mx>=4
						break
					end
				end	% for Side
				if mx>=4
					break
				end
			end	% for Axe
			if R(1)
				Cube=RotateLayer(hAxes,Cube,R(1),R(2),R(3),Anime);
				sol(end+1,:)=FRU2Color(R,Cube);
			end
		end
	else
		mx=5;
		if length(iStart)>1
			% A complex method to look for the best starting layer.
			%  The best mid layer is searched by a lot of rotations and CheckCubes!
			Cube1=Cube;
			Nok=zeros(1,length(iStart));
			for i=1:length(iStart)
				if Rstart(iStart(i),2)
					Cube1=RotateCube(hAxes,Cube,Rstart(iStart(i),1),Rstart(iStart(i),2),0);
				else
					Cube1.Color=Cube.Color;
				end
				D=CheckCube(Cube1);
				Nok(i)=sum(D.P(MidLayer)==-10);
			end
			[n,i]=max(Nok);
			iStart=iStart(i);
		end
	end
	Nparts(1)=size(sol,1);
	% Rotate cube to set starting layer to the top (Up)
	%   (this is in fact only necessary if mx<4)
	if Rstart(iStart,2)
		Cube=RotateCube(hAxes,Cube,Rstart(iStart,1),Rstart(iStart,2),Anime);
	end
	
	% !!!!!behoud zoveel mogelijk tweede laag bij opbouwen eerste laag
	
	RrotToDF=[1 2 0 -1];
	RrotToRU=[2 1 -1 0];
	RrotToFU=[-1 2 0 1];
	
	SetTitle(hAxes,'Correct edges of first layer');
	Clayer1=Cube.Color(6,Cube.RotLayerCube(6,5));
	while mx<4	% edges to do
		% (by the selection of the starting layer, there are no easy
		%  turns to get edges at the right position)
		% from bottom (with top color at the bottom)
		iC=find(Cube.Color(5,Cube.RotLayerCube(5,2:2:8))==Clayer1);
		D=CheckCube(Cube);
		% ?first test if an edge of the second layer needs only one turn?
		if ~isempty(iC)
			iCube=Cube.RotLayerCube(5,iC*2);
			if any(D.P(iCube)==iCube+18)	% right above
					% this is not possible the first time, but maybe after some rotations
				iCube=iCube(find(D.P(iCube)==iCube+18));
			else
				% just take the first (for now), a better choice can be made
				%   (this is done always, so don't do anything)
			end
			% to make it easy, the cube is rotated to an easy position.
			iCube=iCube(1);
			[Cube,iCube]=RotateTo(D.P(iCube),24,iCube,hAxes,3,Cube,Anime);
			R=[3,-1,RrotToDF(iCube/2);1 1 2];
			mx=mx+1;
		elseif any(D.P(2:2:8)>19)	% from bottom layer (but rotated)
			iCube=find(D.P(2:2:8)>19)*2;
			iCube=iCube(1);
			[Cube,iCube]=RotateTo(D.P(iCube),24,iCube,hAxes,3,Cube,Anime);
			R=[3 -1 RrotToDF(iCube/2);1,1,-1;3,1,-1;2,1,1;3,1,1];
			mx=mx+1;
		elseif any(D.P(MidLayer)>19)	% from middle layer
			iC=find(D.P(MidLayer)>19);
			iC=iC(1);
			iCube=MidLayer(iC);
			[Cube,iNew]=RotateTo(iCube,18,D.P(iCube),hAxes,3,Cube,Anime);
			if Cube.Color(2,18)==Clayer1
				n=RrotToRU((iNew-18)/2);
				A=[2 1 1];
			else
				n=RrotToFU((iNew-18)/2);
				A=[1 1 -1];
			end
			R=[3 1 n;A;3 1 -n];
			mx=mx+1;
		else	% from top layer
			% just rotate (!without looking to a possible best solution!)
			iCube=find(D.P(20:2:26)>19|D.P(20:2:26)==-5)*2+18;
			iSurf=find(Cube.Color(:,iCube(1))>0);
			iSurf=iSurf(1);
			R=[floor((iSurf+1)/2) rem(iSurf-1,2)*2-1 1];
		end
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		R=FRU2Color(R,Cube);
		sol(end+1:end+size(R,1),:)=R;
	end
	Nparts(2)=size(sol,1);
	
	SetTitle(hAxes,'Correct corners of first layer');
	%% now the corners of the first layer
	RrotToFRD=[2 0 1 0 0 0 -1 0 0];
	D=CheckCube(Cube);
	nOK=sum(D.P(19:27)==-10);
	while nOK<8
		iC=find(D.P(1:9)>18);
		if ~isempty(iC)
			iCube=find(Cube.Color(5,iC)~=Clayer1);
			if isempty(iCube)
				iCube=iC(1);
			else
				iCube=iC(iCube(1));
			end
			[Cube,iCube]=RotateTo(D.P(iCube),27,iCube,hAxes,3,Cube,Anime);
			R=[3 -1 RrotToFRD(iCube)];
			if R(3)
				Cube=RotateLayer(R,Anime,hAxes,Cube);
				R=FRU2Color(R,Cube);
				sol(end+1,:)=R;
			end
			if Cube.Color(2,9)==Clayer1
				R=[1 1 1;3 -1 1;1 1 -1];
			elseif Cube.Color(4,9)==Clayer1
				R=[2 1 -1;3 -1 -1;2 1 1];
			else
				R=[1 1 1;3 -1 2;1 1 -1;3 -1 2;2 1 -1;3 -1 1;2 1 1];
			end
			nOK=nOK+1;
		else	% all corners in upper layer
			iC=find(D.P(19:27)==-5|D.P(19:27)>18);
			iC=iC(1)+18;
			Cube=RotateTo(iC,27,[],hAxes,3,Cube,Anime);
			R=[2 1 -1;3 -1 -1;2 1 1];
			if Cube.Color(2,27)==Clayer1
				R(2,3)=1;
			end
		end
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		R=FRU2Color(R,Cube);
		sol(end+1:end+size(R,1),:)=R;
		D=CheckCube(Cube);
	end
	Nparts(3)=size(sol,1);
	
	if iAltSol==0
		% Rotate cube with full layer to the bottom (Down)
		Cube=RotateCube(hAxes,Cube,1, 2,Anime);
		D=CheckCube(Cube);
		Rmid={string2hist('LU''F2U2F2U2F2U''L'''),	...
			string2hist('B''UR2U2R2U2R2UB')};
		RrotForMiddle=[0 -1 1 2;	% if F-side on top
			1 0 2 -1];
	else
		Rmid={string2hist('F''D''FDLDL'''),	...
			string2hist('FDF''D''R''D''R')};
		RrotToBack=[-1 0 2 1];
	end
	
	SetTitle(hAxes,'Correct middle layer');
	% middle layer
	nOK=sum(D.P(MidLayer)==-10);
	while nOK<4
		if iAltSol==0
			iC=find(D.P(20:2:26)<19&D.P(20:2:26)>0);
			if ~isempty(iC)
				iCube=iC(1)*2+18;
				[Cube,iCube]=RotateTo(D.P(iCube),18,iCube,hAxes,3,Cube,Anime);
				i=(Cube.Color(6,iCube)~=Cube.Color(2,Cube.RotLayerCube(2,5)))+1;
				R=[3 1 RrotForMiddle(i,(iCube-18)/2);
					Rmid{i}];
				nOK=nOK+1;
			elseif any(D.P(MidLayer)==-5)
				iC=find(D.P(MidLayer)==-5);
				iCube=MidLayer(iC(1));
				Cube=RotateTo(iCube,18,[],hAxes,3,Cube,Anime);
				R=[Rmid{2};3 1 -1;Rmid{1}];
				nOK=nOK+1;
			else % change from one mid-edge to another
				iC=find(D.P(MidLayer)~=-10);
				iCube=MidLayer(iC(1));
				[Cube,iCube]=RotateTo(D.P(iCube),18,iCube,hAxes,3,Cube,Anime);
				R=Rmid{1};
			end
		else	% iAltSol
			iC=find(D.P(2:2:8)>9);
			if isempty(iC)
				iC=find(D.P(MidLayer)~=-10);
				Cube=RotateTo(MidLayer(iC(1)),18,[],hAxes,3,Cube,Anime);
				R=Rmid{2};
			else
				iCube=iC(1)*2;
				i=1;
				c=Cube.Color(Cube.Color(:,iCube)>0,iCube);
				while Cube.Color(2,15)~=c(2)
					Cube=RotateCube(hAxes,Cube,3,-1,Anime);
					iCube=Cube.RotCubeCube(6,iCube);
				end
				if c(1)==Cube.Color(3,11)
					i=1;
				else
					i=2;
				end
				R=[3 -1 RrotToBack(iCube/2);Rmid{i}];
				nOK=nOK+1;
			end
		end
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		R=FRU2Color(R,Cube);
		sol(end+1:end+size(R,1),:)=R;
		D=CheckCube(Cube);
	end
	Nparts(4)=size(sol,1);
	
	if iAltSol>0
		% Rotate cube with full layer to the bottom (Down)
		Cube=RotateCube(hAxes,Cube,1, 2,Anime);
	end
	
	Rorient1=string2hist('BLUL''U''B''');
	Rorient2=string2hist('BULU''L''B''');
	
	SetTitle(hAxes,'Correct orientation of edges of last layer');
	Clayer3=Cube.Color(6,Cube.RotLayerCube(6,5));
	iC=find(Cube.Color(6,20:2:26)~=Clayer3);
	if ~isempty(iC)
		if length(iC)==4
			Cube=RotateLayer(Rorient1,Anime,hAxes,Cube);
			R=FRU2Color(Rorient1,Cube);
			sol(end+1:end+size(R,1),:)=R;
			Cube=RotateCube(hAxes,Cube,3,2,Anime);
			R=Rorient2;
		else
			iCube=iC*2+18;
			[Cube,iCube]=RotateTo(iCube(1),22,iCube(2),hAxes,3,Cube,Anime);
			if iCube==24
				R=Rorient1;
			else
				if iCube==26
					Cube=RotateCube(hAxes,Cube,3,1,Anime);
				end
				R=Rorient2;
			end
		end
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		R=FRU2Color(R,Cube);
		sol(end+1:end+size(R,1),:)=R;
	end
	Nparts(5)=size(sol,1);
	
	RotEdges1=string2hist('R2D''U2R''LF2RL''DR2');
	RotEdges2=string2hist('R2D''R''LF2RL''U2DR2');
	RotEdges3=string2hist('R2D2B2D,(L2F2)3,D''B2D2R2');
	
	SetTitle(hAxes,'Correct positions of edges of last layer');
	D=CheckCube(Cube);
	iNOK=find(D.P(20:2:26)>0);
	while length(iNOK)==4
		R=[3 1 1];
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		R=FRU2Color(R,Cube);
		sol(end+1,:)=R;
		D=CheckCube(Cube);
		iNOK=find(D.P(20:2:26)>0);
	end
	if length(iNOK)==2
		R=[3 1 1];
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		R=FRU2Color(R,Cube);
		sol(end+1,:)=R;
		D=CheckCube(Cube);
		iNOK=find(D.P(20:2:26)>0);
	end
	if length(iNOK)	% because of not working RotEdges3
		if length(iNOK)==3
			iCube=find(D.P(20:2:26)<0)*2+18;
			[Cube,D]=RotateTo(iCube,20,[],hAxes,3,Cube,Anime);
			if D.P(22)==26
				R=RotEdges1;
			else
				R=RotEdges2;
			end
		else
			if D.P(20)==24
				Cube=RotateCube(hAxes,Cube,3,1,Anime);
			end
			R=RotEdges3;
		end
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		R=FRU2Color(R,Cube);
		sol(end+1:end+size(R,1),:)=R;
	end
	Nparts(6)=size(sol,1);
	
	Corners=[19 21 25 27];
	Rcorners1=string2hist('L'',URU''R'',L,RUR''U''');
	Rcorners2=string2hist('URU''R'',L'',RUR''U'',L');
	Rcorners3=string2hist('B,LUL''U'',LUL''U'',LUL''U'',B''');
	Rcorners4=string2hist('R''B2,FRF''R'',FRF''R'',FRF''R'',B2R');
	
	SetTitle(hAxes,'Correct positions of corners of last layer');
	D=CheckCube(Cube);
	iNOK=find(D.P(Corners)>0);
	if length(iNOK)
		if length(iNOK)==3
			iCube=Corners(D.P(Corners)<0);
			[Cube,D]=RotateTo(iCube,27,[],hAxes,3,Cube,Anime);
			if D.P(21)==19
				R=Rcorners1;
			else
				R=Rcorners2;
			end
		elseif length(iNOK)==4
			if D.P(21)==19|D.P(21)==27
				if D.P(21)==19
					Cube=RotateCube(hAxes,Cube,3,1,Anime);
				end
				R=Rcorners3;
			else
				R=Rcorners4;
			end
		else
			error('Impossible cube')
		end
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		R=FRU2Color(R,Cube);
		sol(end+1:end+size(R,1),:)=R;
	end
	Nparts(7)=size(sol,1);
	
	RRcornersPart1=string2hist('(FDF''D'')2');
	RRcornersPart2=string2hist('(DFD''F'')2');
	
	SetTitle(hAxes,'Correct orientation of corners of last layer');
	nUp=0;
	nNOK=sum(Cube.Color(6,Corners)~=Clayer3);
	%!!!!!bij het volgende is ook 3 x CW of 3 x CCW mogelijk!!!!
	while ~all(Cube.Color(6,Corners)==Clayer3)
		while Cube.Color(6,27)==Clayer3
			Cube=RotateCube(hAxes,Cube,3,1,Anime);
		end
		Rtop=FRU2Color([3 1 1],Cube);
		if Cube.Color(2,27)==Clayer3
			R=RRcornersPart1;
			iSide=4;
			R2=RRcornersPart2;
		else
			R=RRcornersPart2;
			iSide=2;
			R2=RRcornersPart1;
		end
		Cube=RotateLayer(R,Anime,hAxes,Cube);
		sol(end+1:end+size(R,1),:)=FRU2Color(R,Cube);
		nNOK=nNOK-1;
		while Cube.Color(iSide,27)~=Clayer3&(nNOK~=2|Cube.Color(6,27)==Clayer3)
			Cube=RotateLayer(Rtop,Anime,hAxes,Cube);
			sol(end+1,:)=Rtop;
			nUp=nUp+1;
		end
		if Cube.Color(iSide,27)==Clayer3
			nNOK=nNOK-1;
		end
		Cube=RotateLayer(R2,Anime,hAxes,Cube);
		sol(end+1:end+size(R2,1),:)=FRU2Color(R2,Cube);
	end
	nUp=rem(nUp,4);
	if nUp>1
		nUp=nUp-4;
	end
	if nUp
		nUp=-nUp;
		Cube=RotateLayer(hAxes,Cube,3,1,nUp,Anime);
		sol(end+1,:)=FRU2Color([3 1 nUp],Cube);
	end
	Nparts(8)=size(sol,1);
	
	if Cube.bFullCube
		SetTitle(hAxes,'Correct orientations of middle cubes');
		% combinations from Mark Jeays
		Rmid180=string2hist('URLU2R''L''URLU2R''L''');
		RmidUF=string2hist('FB''LR''UD''F''U''DL''RF''BU');
		RmidUD=string2hist('RL''F2B2RL''URL''F2B2RL''D''');
		% Full cube solver added, just at the end of the real Singmaster-solution!!!
		loop=true;
		while loop
			N=zeros(1,6);
			MyColor = Cube.Color;
			for iFace=1:6
				iCube=Cube.iMid(iFace);
				z=Cube.iExtraFaces(iFace,1);
				c=Cube.Color(Cube.iMidInd(z));
				% count needed rotations
				while MyColor(z,iCube)~=c
					N(iFace)=N(iFace)+1;
					MyColor(Cube.RotCubeFlat(iFace,:),iCube) = ...
						MyColor(:,iCube);
					if N(iFace)>4
						error('!!Impossible cube!!! - full cube with impossible mid cube colors!!')
					end
				end
			end
			if any(N)
				if any(N==2)
					i=find(N==2);
					Cube=RotateTo(i(1),23,[],hAxes,[],Cube,Anime);
					R=Rmid180;
				else
					if all(N<2)|all(N<1|N>2)	% oorspronkelijk niet voorzien!!!
						i=find(N);
						N(i(1))=0;
						j=find(N);
					else
						i=find(N==1);
						j=find(N==3);	% normaal altijd (toch als er geen 2's meer zijn)
					end
					i=i(1);
					j=j(1);
					[Cube,iCube]=RotateTo(i,23,Cube.iMid(j),hAxes,[],Cube,Anime);
					if floor((i-1)/2)==floor((j-1)/2)
						R=RmidUD;
					else
						Cube=RotateTo(iCube,15,[],hAxes,3,Cube,Anime);
						R=RmidUF;
					end
				end
				Cube=RotateLayer(R,Anime,hAxes,Cube);
				sol(end+1:end+size(R),:)=FRU2Color(R,Cube);
			else
				loop=false;
			end
		end
	end
	Nparts(9)=size(sol,1);
	SetTitle(hAxes,'');
	
	if bPostOptim
		sol=optimhist(sol,Cube);
	end
end

if Anime
	Cube.sol=sol;
	set(hAxes,'UserData',Cube)
end
if Anime&bAnimeSepWin&bCloseWin
	close(f)
end

function [mx,i]=FindBestStart(D)
% not really finding the best, but an easy guess:
%     as much edges as possible, and then the maximum number of corners
%   (it is possible that "good corners" have to be removed to set the
%    right edges, and therefore this method is too easy)
[mx,i]=max(D.NOK(:,2));
j=find(D.NOK(:,2)==mx);
if length(j)>1
	[mx2,k]=max(D.NOK(j,3));
	i=j(k);
	mx=mx+mx2/5;
else
	mx=mx+D.NOK(i,3)/5;
end

function [Cube,iCubes]=RotateTo(iCube0,toCube,iCubes,hAxes,Axe,Cube,Anime)
n=0;
if isempty(Axe)	% search for a direction
	%!!!!only for mid cubes, assigned by an index rather than a cube number!
	%  and only for rotating mid cube to upper layer
	a1=floor((iCube0-1)/2);
	a2=2;
	if a1==a2
		Axe=3-a1;
	else
		Axe=setdiff(0:2,[a1 a2])+1;
	end
	iCube0=Cube.iMid(iCube0);
end
i=Axe*2;
while iCube0~=toCube
	n=n+1;
	iCube0=Cube.RotCubeCube(i,iCube0);
	if n>3
		error('Something is wrong ---- no rotation exist for requested search')
	end
	iCubes=Cube.RotCubeCube(i,iCubes);
end
switch n
case 1
	Cube=RotateCube(hAxes,Cube,Axe,-1,Anime);
case 2
	Cube=RotateCube(hAxes,Cube,Axe,2,Anime);
case 3
	Cube=RotateCube(hAxes,Cube,Axe,1,Anime);
end
if nargout>1&isempty(iCubes)
	iCubes=CheckCube(Cube);
end

function SetTitle(hAxes,s)
if ~isempty(hAxes)
	set(get(hAxes,'Title'),'String',s)
end

Contact us