% domino tile dominos tiles matrix random snake worm snakes worms
%
% above are the keywords for this script, which can be searched for using "lookfor"
%{
% Ben Payne
% <ben.is.located@gmail.com>
% 20081101
% two headed snake AKA domino tile matrix
%
% Note: READ BELOW, but the primary instructions are that after each
% complete realization is found, the script PAUSES. To continue, press any
% key. When satisfied, CTRL-C to stop.
%
% For a visual example of what this script accomplishes, see the game
% http://www.snakegame.net/
% The output of this script is a matrix of a size defined by two
% parameters, "numrows" by "numcolumns". A boarder is placed around this
% matrix (the "-1000" value) by placing the original matrix into a larger
% matrix of dimension (numrows+2) by (numcolumns+2). The purpose behind
% this is to allow the user to specify an arbitrary shape other than just
% rectangles.
%
% Now that an arbitrarily shaped empty "matrix" is set up, start filling in
% the matrix with a sequence of integers such that at the end of the
% process the matrix is filled completely. To start, choose a random
% location for 1. Next, choose randomly a neighboring location to place 2. Then
% place 3 next to 2 in a random location. Each of this random choices has
% a maximum of four possible outcomes (up, down, left, right of the
% previous integer) but sometimes the number of choices is less (only up or
% down since left and right are occupied by integers. This restriction of
% choices is what makes the code long: the number of choices depends on the
% number of open neighboring elements in the matrix.
%
% In the end, the integers can no longer be incremented as there are no more open neighboring
% locations. This is due to either the matrix being filled or the "snake"
% of previous integers has "cut itself off." (There are open (zero-valued)
% elements, but they are inaccessible due to previous choices.) Normally
% this realization would then be discarded since it was not filled.
% However, the "snake" could possibly grow from the other end (start at 1
% and decrement). Thus this decreases the number of realizations one
% discards.
%
% More on the pausing and how to edit:
% -the relevant "pause" can be found near the bottom, line
%
% The purpose of this excercise was pure curiosity. I welcome suggestions
% and comments.
%
% to view previous successfully filled matrices, view
% suc(4,:,:) % where "4" is the realization number of the matrix.
% other recorded information includes
% numoftries
% numofsucesses
% times
%
%}
% for visual cleanliness, wipe the command window clean
clc % clear the command window
% I'll assume there are no pre-existing conflicts with variables. If you
% encounter any issues using this code, I recommend uncommenting the
% "clear" function below
%clear % remove all pre-existing variables in your environment
% warning: the following variable names are used in the script and will
% wipe out your pre-existing values!
clear coin counter dimofmatrix full g gwalled i i_headtwo j j_headtwo numcolumns
clear numofsuccesses numoftries numrows suc times tries x y
numoftries=0;
numofsuccesses = 0;
tic % start the stopwatch
for x = 1:1e100 % make many attempts before giving up. Better: put it in an infinite loop
% warning: the following variable names are used in the script and will
% wipe out your pre-existing values!
clear i j counter coin g gwalled numrows numcolumns dimofmatrix %clear variables
% how big is your tile floor? [can be rectangular]
numrows = 7;
numcolumns = 6;
g = zeros(numrows,numcolumns);
dimofmatrix = size(g); % dimofmatrix(1) = number of rows, dimofmatrix(2) = num of columns
%create a "walled" version
% initialize a matrix with 2 extra rows and 2 extra columns
gwalled = zeros(numrows+2,numcolumns+2);
%fill in gwalled with a not findable number
% Note: this is the only place this number gets used
gwalled(:,:)=-1000;
%place g in the walled garden
gwalled(2:numrows+1,2:numcolumns+1)=g;
% initial snake. Iterate up to fill the matrix
counter = 1;
% where to start the snake in the matrix
i = round(1 + (dimofmatrix(1)-1) * rand(1)); % row
j = round(1 + (dimofmatrix(2)-1) * rand(1)); % column
g(i,j)= counter; % put "1" in the randomly chosen i,j position
gwalled(2:numrows+1,2:numcolumns+1)=g;
i = i+1;
j = j+1;
% save the position of the "one" in gwalled for future use.
i_headtwo = i;
j_headtwo = j;
counter = counter +1; % next segment of the snake
% now we can figure out where the next position is going to be:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
while counter <= dimofmatrix(1)*dimofmatrix(2)
if (gwalled(i+1,j)==0) && (gwalled(i,j+1)==0) && (gwalled(i,j-1)==0) && (gwalled(i-1,j)==0)
coin = round( 1 + (4-1)*rand(1) ); %flip a 4 sided coin
if (coin==1)
i=i+1;
elseif (coin==2)
i=i-1;
elseif (coin==3)
j=j+1;
else
j=j-1;
end
elseif (gwalled(i+1,j)==0) && (gwalled(i,j+1)==0) && (gwalled(i,j-1)==0)
% the symbols below denote where your next possible move is, based on your current
% position. To choose, flip a three-sided coin and then move to that position.
%
% 0 0
% 0
coin = round( 1 + (3-1)*rand(1) ); % flip a 3-sided coin
if (coin==1)
j = j+1; % move right
elseif (coin==2)
j = j-1; % move left
else
i = i+1; % move down
end
elseif (gwalled(i-1,j)==0) && (gwalled(i,j+1)==0) && (gwalled(i,j-1)==0)
% 0
% 0 0
coin = round( 1 + (3-1)*rand(1) ); % flip a 3-sided coin
if (coin==1)
j = j+1; % move right
elseif (coin==2)
j = j-1; % move left
else
i = i-1; % move up
end
elseif (gwalled(i-1,j)==0) && (gwalled(i+1,j)==0) && (gwalled(i,j-1)==0)
% 0
% 0 x
% 0
coin = round( 1 + (3-1)*rand(1) ); % flip a 3-sided coin
if (coin==1)
j = j-1; % move left
elseif (coin==2)
i = i+1; % move down
else
i = i-1; % move up
end
elseif (gwalled(i-1,j)==0) && (gwalled(i+1,j)==0) && (gwalled(i,j+1)==0)
% 0
% x 0
% 0
coin = round( 1 + (3-1)*rand(1) ); % flip a 3-sided coin
if (coin==1)
j = j+1; % move right
elseif (coin==2)
i = i+1; % move down
else
i = i-1; % move up
end
elseif (gwalled(i-1,j)==0) && (gwalled(i+1,j)==0)
% 0
% x
% 0
if (round(rand(1)))
i = i-1;
else
i = i+1;
end
elseif (gwalled(i,j-1)==0) && (gwalled(i,j+1)==0)
% 0 x 0
if (round(rand(1)))
j = j+1;
else
j = j-1;
end
elseif (gwalled(i,j-1)==0) && (gwalled(i+1,j)==0)
% 0 x
% 0
if (round(rand(1)))
j = j-1;
else
i = i+1;
end
elseif (gwalled(i,j+1)==0) && (gwalled(i+1,j)==0)
% x 0
% 0
if (round(rand(1)))
j = j+1;
else
i = i+1;
end
elseif (gwalled(i,j+1)==0) && (gwalled(i-1,j)==0)
% 0
% x 0
if (round(rand(1)))
i = i-1;
else
j = j+1;
end
elseif (gwalled(i,j-1)==0) && (gwalled(i-1,j)==0)
% 0
% 0 x
if (round(rand(1)))
j = j-1;
else
i = i-1;
end
elseif (gwalled(i,j+1)==0)
j=j+1;
elseif (gwalled(i,j-1)==0)
j=j-1;
elseif (gwalled(i+1,j)==0)
i=i+1;
elseif (gwalled(i-1,j)==0)
i=i-1;
else
%'ATTENTION: THERE ARE NO MORE PLACES TO GO'
%'I GET TO START OVER'
% leave the while loop
numoftries=numoftries+1;
break
end
% to watch growth, take out the ";" and uncomment the "pause"
gwalled(i,j)=counter;
% pause
% OLD, NO LONGER APPLIES.
% if counter == dimofmatrix(1)*dimofmatrix(2)
% numofsuccesses = numofsuccesses+1;
% times(numofsuccesses) = toc;
% tries(numofsuccesses) = numoftries;
% % gwalled % display successful output
% % surf(gwalled(2:numrows+1,2:numcolumns+1))
% % pause
% clc
% tic % reset the stopwatch
% end
counter = counter+1;
end % end of the first while loop
% Welcome to the second try
% if you've reached this point, it means that you've cut your self off.
% so the next try works from the known position of g(i,j)=1 and
% then makes all the same tries looking for open spaces.
% with the exception that there will be no "four-choice" from 1
% reset the counter, will be decrementing
counter = -1;
% reset the initial position to where "1" is.
i = i_headtwo;
j = j_headtwo;
%'cut off'
%gwalled
%pause
%clc
% this "while" loop is going to have to change, but I don't know to what.
while counter >= -1*dimofmatrix(1)*dimofmatrix(2)
%note: there is no "four choice" from 1
if (gwalled(i+1,j)==0) && (gwalled(i,j+1)==0) && (gwalled(i,j-1)==0)
% 0 0
% 0
coin = round( 1 + (3-1)*rand(1) ); % flip a 3-sided coin
if (coin==1)
j = j+1; % move right
elseif (coin==2)
j = j-1; % move left
else
i = i+1; % move down
end
elseif (gwalled(i-1,j)==0) && (gwalled(i,j+1)==0) && (gwalled(i,j-1)==0)
% 0
% 0 0
coin = round( 1 + (3-1)*rand(1) ); % flip a 3-sided coin
if (coin==1)
j = j+1; % move right
elseif (coin==2)
j = j-1; % move left
else
i = i-1; % move up
end
elseif (gwalled(i-1,j)==0) && (gwalled(i+1,j)==0) && (gwalled(i,j-1)==0)
% 0
% 0 x
% 0
coin = round( 1 + (3-1)*rand(1) ); % flip a 3-sided coin
if (coin==1)
j = j-1; % move left
elseif (coin==2)
i = i+1; % move down
else
i = i-1; % move up
end
elseif (gwalled(i-1,j)==0) && (gwalled(i+1,j)==0) && (gwalled(i,j+1)==0)
% 0
% x 0
% 0
coin = round( 1 + (3-1)*rand(1) ); % flip a 3-sided coin
if (coin==1)
j = j+1; % move right
elseif (coin==2)
i = i+1; % move down
else
i = i-1; % move up
end
elseif (gwalled(i-1,j)==0) && (gwalled(i+1,j)==0)
% 0
% x
% 0
if (round(rand(1)))
i = i-1;
else
i = i+1;
end
elseif (gwalled(i,j-1)==0) && (gwalled(i,j+1)==0)
% 0 x 0
if (round(rand(1)))
j = j+1;
else
j = j-1;
end
elseif (gwalled(i,j-1)==0) && (gwalled(i+1,j)==0)
% 0 x
% 0
if (round(rand(1)))
j = j-1;
else
i = i+1;
end
elseif (gwalled(i,j+1)==0) && (gwalled(i+1,j)==0)
% x 0
% 0
if (round(rand(1)))
j = j+1;
else
i = i+1;
end
elseif (gwalled(i,j+1)==0) && (gwalled(i-1,j)==0)
% 0
% x 0
if (round(rand(1)))
i = i-1;
else
j = j+1;
end
elseif (gwalled(i,j-1)==0) && (gwalled(i-1,j)==0)
% 0
% 0 x
if (round(rand(1)))
j = j-1;
else
i = i-1;
end
elseif (gwalled(i,j+1)==0)
j=j+1;
elseif (gwalled(i,j-1)==0)
j=j-1;
elseif (gwalled(i+1,j)==0)
i=i+1;
elseif (gwalled(i-1,j)==0)
i=i-1;
else
%'ATTENTION: THERE ARE NO MORE PLACES TO GO'
%'I GET TO START OVER'
% leave the while loop
numoftries=numoftries+1;
break
end % end of all the "if/elseif" statements
% to watch growth, take out the ";" and uncomment the "pause"
% 'other head'
gwalled(i,j)=counter;
% pause
% clc
%decrement counter
counter = counter-1;
end % end of the second while loop
% if you've reached this point, the second head ran out
% of options. Check to see if the matrix is full
% initialize "full" to true
full = 1;
for x = 1:numrows+2
for y = 1:numcolumns+2
if gwalled(x,y) == 0
%matrix is not full
full = 0;
end
end
end
if full
numofsuccesses = numofsuccesses+1;
times(numofsuccesses) = toc;
tries(numofsuccesses) = numoftries;
suc(numofsuccesses,:,:)= gwalled;
gwalled % remove ";" to display successful output
% surf(gwalled(2:numrows+1,2:numcolumns+1))
pause
clc
tic % reset the stopwatch
end
end % end the main "for" loop
