www.gusucode.com > 三维模仿源码程序 > 三维模仿源码程序/MathRubik2/SSSsolver.m
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