|
|
发表于 2005-4-29 01:29:55
|
显示全部楼层
< >function fiver(n,tag);
%
% Usage: fiver(n) for n >= 3
% This function run the game of fiver, where
% N is the size of chess,
% tag is any kind of input, solve the game when it is given
% play the game with no second input
% Only a possible solution is given. Actually there are many solutions and
% there is a best one which has least ones.
% The first one is solve by Gauss Elimination in GF[2], and
% the latter should be formed as a discrete optimization problem, which is an NP one!
%
% TANJOHN, 2002(C)
%
X = 0.4*sin(0:0.1:2*pi)-0.5; % data for draw a circle
Y = 0.4*cos(0:0.1:2*pi)-0.5; %
c = [0 0 1;1 0 0]; % 2 colors: black and green
hold on;
axis('off'); %
axis('equal'); % axis properties
axis([0 n 0 n]); %
plot([0,0,n,n,0],[0,n,n,0,0],'g-'); % outside square
for i=1:n-1, % inside grid
plot([i,i],[0,n],'r-.');
plot([0,n],[i,i],'r-.');
end
% % end of initial part
if nargin == 1, % for one input, play the game
if n<3,
error('too small size of the problem!!');
end
M = zeros(n); % data for the initial chess
j = 0;
for i = 1:n, % draw the initial chess
for k = 1:n,
patch(i+X,k+Y,c(1+M(i,k), );
end
end
while 1, % play the game without rest,
if all(M==1),
fprintf('\n *** Great! ***\n');
fprintf('\n *** use %3d steps ***\n',j);
return;
end
[x,y] = ginput(1); % choose one switch
j = j + 1;
if (0<=x & x<=n & 0<=y & y<=n), % check your input point
x1 = (x - floor(x) - 0.5); % the decimal parts
y1 = (y - floor(y) - 0.5);
if x1^2+y1^2<=0.4^2, % is that point in a circle?
x = ceil(x);
y = ceil(y);
ZZ = [x x x x+1 x-1 % data for all neighbours and itself
y y-1 y+1 y y ];
for alpha = 0:1/18:1,
for pp = ZZ, % switch all neighbours and itself
if all(pp<=n) & all(pp>=1),
tx = pp(1);
ty = pp(2);
M(tx,ty)=~M(tx,ty);
nc = alpha*c(1+M(tx,ty),+(1-alpha)*c(1+(~M(tx,ty)),:);
patch(tx+X,ty+Y,nc);
end
end
pause(0.01);
end
else
fprintf('\n*** outside the circle ***\n');
end
else
fprintf('\n*** outside the board ***\n');
return;
end
end % end of while 1
close; % close if game is done
elseif nargin == 2, % for 2 inputs, solve the game
M = reshape(sol(n),n,n); % solve it and shape it to matrix
for i = 1:n, % draw the solution
for k = 1:n,
patch(i+X,k+Y,c(1+M(i,k),:));
end
end
title('press the button of green one by one, and you got it!!');
% change word 'green' if c is changed
end % end of check nargin
%%% end of fiver</P><>function p = sol(n) % solve the fiver game
In = eye(n); % data to be filled in M
e1 = ones(n-1,1);
T = In + diag(e1,-1) + diag(e1,1);
M = zeros(n*n);
for j = 1:n, % fill the block of matrix M
M((j-1)*n+1:j*n,(j-1)*n+1:j*n) = T;
if j<n,
M(j*n+1 j+1)*n,(j-1)*n+1:j*n) = In;
end
if j>1,
M((j-2)*n+1j-1)*n,(j-1)*n+1:j*n) = In;
end
end
p = gf2(M,ones(n*n,1)); % solve the game by M*x=(1,1,...1)^T
%%% end of sol</P><>function x = gf2(M,rhs) % mod 2 Guass Elimination
% A x == b (mod 2)
% i.e., in GF[2]
A = M;
n = size(A,1);
b = rhs; % copy all inputs
for j = 1:n,
if A(j,j) ~= 1,
tag = 1;
k = j + 1;
while tag & k<=n, % choose a pivot
if A(k,j)==1,
tag = 0; % find a pivot, change rows
tmp = A(k,:); stmp = b(k);
A(k,:) = A(j,:); b(k) = b(j);
A(j,:) = tmp; b(j) = stmp;
else
k = k + 1; % step next row
end
end
end
if A(j,j) == 1, % Guass Elimination
for k = [1:j-1 j+1:n], % for upper and lower parts both
if A(k,j)~=0, % only for the nonzero A(k,j)
A(k,:) = abs(rem(A(k,:) + A(j,:), 2));
b(k) = abs(rem(b(k) + b(j), 2));
end
end
end
end % end of Elimination
for j = 1:n,
if A(j,j) == 0,
if b(j) == 1, % no solution
error('no solution!!');
end
end
end
x = b; % return the solution
%%% end of gf2</P> |
|
楼主