function npuzzle(cmd)
%NPUZZLE Graphical User Interface for playing the N-Puzzle.
%
% The Game:
% The N-puzzle is known in various versions, including the 8 puzzle, the
% 15 puzzle, and with various names. It is a sliding puzzle that consists
% of a grid of numbered squares with one square missing, and the labels
% on the squares jumbled up. If the grid is 33, the puzzle is called the
% 8-puzzle or 9-puzzle. If the grid is 44, the puzzle is called the
% 15-puzzle or 16-puzzle. The goal of the puzzle is to un-jumble the
% squares by only making moves which slide squares into the empty space,
% in turn revealing another empty space in the position of the moved
% piece. (From Wikipedia)
%
% Game Board:
% The N-Puzzle interface lets the user choose between several predefined
% sizes of boards, and also to choose any custom (valid) size N. A valid
% size of N is such that round(sqrt(N+1))^2-1 equals to N.
% All generated games are solvable. A game is generated by performing
% 1000 random moves of the empty space starting from the solution.
% User can also import any puzzle into the interface. Puzzle must be
% defined as an array or as a matrix with numbers spanning from 1 where
% the largest number is the empty space.
%
% Game Controls:
% The N-puzzle game can be played using either mouse or keyboard (or
% both). Move around marker using arrow keys and make a switch using
% space. With mouse you move around marker using left-click and make a
% switch using any other type of click (double-click, right-click,
% shift-click, etc.)
%
% Extra Game Features:
% The N-Puzzle game has Undo and Redo functionality that can be reached
% from the menu or by the shortcuts Ctrl-Z (Undo) and Ctrl-R (Redo).
% A simulation of the game so far can also be viewed using the control in
% the menu.
% The game now also has a built-in solver.
%
% Examples:
% npuzzle % Start Main N-Puzzle Interface
% npuzzle('fifteen') % Start new 15-Puzzle w/o Main Interface
% Developed by Per-Anders Ekstrm, 2003-2007 Facilia AB.
if ~nargin
npuzzle('init')
return;
end
if ~(ischar(cmd)||isscalar(cmd))
return;
end
switch cmd
%------------------------------------------------------------------
case 'init'
% MAIN FIGURE
scrsz = get(0,'ScreenSize');
hFigure = figure( ...
'Name','N-Puzzle', ...
'Menubar','none',...
'NumberTitle','off', ...
'KeyPressFcn','npuzzle(double(get(gcbf,''Currentcharacter'')))', ...
'Units','pixels', ...
'Tag','npuzzle', ...
'Position',[(scrsz(3)-510)/2 (scrsz(4)-500)/2 510 500], ...
'Color',[.95 .95 .95], ...
'Colormap',[1 1 1;.93 .97 .93;1 1 .6;.6 .8 1;.6 1 .6;1 .6 .6], ...
'Visible','on');
% MENU
FileMenu = uimenu(hFigure,'Label','File');
uimenu(FileMenu,'Label','New Game','Accelerator','N','Callback','npuzzle(''NewGame'')');
NewBoard = uimenu(FileMenu,'Label','New Board');
uimenu(NewBoard,'Label','3 (2x2)','Callback','npuzzle(''three'')');
uimenu(NewBoard,'Label','8 (3x3)','Callback','npuzzle(''eight'')');
uimenu(NewBoard,'Label','15 (4x4)','Callback','npuzzle(''fifteen'')');
uimenu(NewBoard,'Label','24 (5x5)','Callback','npuzzle(''twentyfour'')');
uimenu(NewBoard,'Label','35 (6x6)','Callback','npuzzle(''thirtyfive'')');
uimenu(NewBoard,'Label','48 (7x7)','Callback','npuzzle(''fourtyeight'')');
uimenu(NewBoard,'Label','Custom ...','Separator','on','Callback','npuzzle(''CustomBoard'')');
uimenu(FileMenu,'Label','Import Game ...','Callback','npuzzle(''ImportGame'')');
uimenu(FileMenu,'Label','Solve Game','Separator','on','Callback','npuzzle(''Solve'')');
uimenu(FileMenu,'Label','Exit','Accelerator','Q','Separator','on','Callback','delete(gcf)');
EditMenu = uimenu(hFigure,'Label','Edit');
uimenu(EditMenu,'Label','Undo','Accelerator','Z','Callback','npuzzle(''Undo'')','Tag','Undo');
uimenu(EditMenu,'Label','Redo','Accelerator','R','Callback','npuzzle(''Redo'')','Tag','Redo');
HelpMenu = uimenu(hFigure,'Label','Help');
uimenu(HelpMenu,'Label','Help','Accelerator','H','Callback','helpwin npuzzle');
uimenu(HelpMenu,'Label','Simulate History','Callback','npuzzle(''SimulateHistory'')','Separator','on');
uimenu(HelpMenu,'Label','About','Callback','npuzzle(''About'')','Separator','on');
% MATRIX AXES
axes( ...
'Parent',hFigure, ...
'Units','normalized', ...
'Clipping','on', ...
'Position',[0.02 0.02 0.96 0.96]);
axis('square')
% Start a new board with N=16
startgame(16)
%------------------------------------------------------------------
case 'Surface'
ud = get(gca,'UserData');
set(gcf,'Name',[num2str(ud.N-1) '-Puzzle'])
EdgeColor = [.6 .6 .6];
FaceColor = [1 1 1];
FontSize = .5/ud.n;
HoleColor = [.3 .3 .3];
delete(findobj(gca,'Tag','Surface'))
delete(findobj(gca,'Tag','Hole'))
arrayfun(@(x)delete(findobj(gca,'Tag',num2str(x))),1:1000)
% MATRIX SURFACE
CData = zeros(ud.n+1,ud.n+1);
surface( ...
zeros(size(CData)),CData, ...
'Parent',gca, ...
'ButtonDownFcn','npuzzle(''ButtonDown'');', ...
'EdgeColor',EdgeColor, ...
'FaceColor',FaceColor, ...
'LineWidth',1,...
'Tag','Surface')
axis off
hold on
% TEXT FIELDS
arrayfun(@(x)text( ...
'Position',[mod(x-1,ud.n)+1 ud.n+1-ceil(x/ud.n)]+.5, ...
'String','', ...
'FontUnits','normalized', ...
'FontSize',FontSize, ...
'Tag',num2str(x), ...
'ButtonDownFcn','npuzzle(''ButtonDown'');', ...
'HorizontalAlignment','center'), ...
1:ud.N)
% EMPTY FIELD
fill(1,1,HoleColor, ...
'ButtonDownFcn','npuzzle(''ButtonDown'');', ...
'Tag','Hole')
%------------------------------------------------------------------
case 'three'
startgame(4)
%------------------------------------------------------------------
case 'eight'
startgame(9)
%------------------------------------------------------------------
case 'fifteen'
startgame(16)
%------------------------------------------------------------------
case 'twentyfour'
startgame(25)
%------------------------------------------------------------------
case 'thirtyfive'
startgame(36)
%------------------------------------------------------------------
case 'fourtyeight'
startgame(49)
%------------------------------------------------------------------
case 'CustomBoard'
prompt = {'Input Size of Board (N):'};
name = 'Custom Board Size';
options.Resize = 'on';
answer = inputdlg(prompt,name,1,{'15'},options);
if ~isempty(answer)
N = str2double(answer{1})+1;
n = round(sqrt(N));
if n^2==N
startgame(N)
else
errordlg('Input Size (N) Not Accepted','Custom Board Size')
end
end
%------------------------------------------------------------------
case 'NewGame'
ud = get(gca,'UserData');
board = shuffleboard(1:ud.N,10000); % Shuffle the board
ud.board = board;
ud.boardhistory = ud.board;
ud.histpos = 1;
ud.starttime = clock;
ud.endtime = [];
set(gca,'UserData',ud);
set(findobj(gcf,'Tag','Undo'),'Enable','off')
set(findobj(gcf,'Tag','Redo'),'Enable','off')
drawboard()
drawpos()
%------------------------------------------------------------------
case 'ImportGame'
prompt = {'Input Game as a Vector or a Matrix:'};
name = 'Import Game';
options.Resize = 'on';
answer = inputdlg(prompt,name,1,{''},options);
if ~isempty(answer)&&~isempty(answer{1})
board = str2num(answer{1})';
board = board(:)';
N = length(board);
n = round(sqrt(N));
if ~isempty(board)&&n^2==N&&~ismember(0,ismember(1:N,board))
ud = get(gca,'UserData');
ud.board = board;
ud.N = N;
ud.n = n;
ud.currpos = 1;
ud.boardhistory = ud.board;
ud.histpos = 1;
ud.starttime = clock;
ud.endtime = [];
set(gca,'UserData',ud);
set(findobj(gcf,'Tag','Undo'),'Enable','off')
set(findobj(gcf,'Tag','Redo'),'Enable','off')
npuzzle('Surface')
drawboard()
drawpos()
else
errordlg('Input Game Not Accepted','Import Game')
end
end
%------------------------------------------------------------------
case 'SimulateHistory'
set(gcf,'Color',[.7 0 0],'Pointer','watch','CloseRequestFcn','','KeyPressFcn','')
ud = get(gca,'UserData');
for i=1:ud.histpos
hole = find(ud.boardhistory(i,:)==ud.N);
x = mod(hole-1,ud.n)+1;
y = ud.n+1-ceil(hole/ud.n);
delete(findobj(gca,'tag','currpos'))
plot(x+[0 .995 .995 0 0]+0.005,y+[0 0 .995 .995 0],'r', ...
'LineWidth',2, ...
'Tag','currpos')
pause(.2)
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'String',num2str(ud.boardhistory(i,x))), ...
1:ud.N)
set(findobj(gca,'tag','Hole'), ...
'XData',x+[0 .99 .99 0 0]+0.005,...
'YData',y+[0 0 .99 .99 0]+0.005)
pause(.3)
end
set(gcf,'Color',[.95 .95 .95],'Pointer','arrow','CloseRequestFcn','closereq','KeyPressFcn','npuzzle(double(get(gcbf,''Currentcharacter'')))')
drawpos()
%------------------------------------------------------------------
case 'Solve'
ud = get(gca,'UserData');
if sum(ud.board(:)'==1:ud.N)~=ud.N % if not solved
set(gcf,'Color',[.7 0 0],'Pointer','watch','CloseRequestFcn','','KeyPressFcn','')
pause(.2)
boardhistory = solve(ud.board);
ud.boardhistory = [ud.boardhistory(1:ud.histpos,:);boardhistory];
ud.board = 1:ud.N;
set(gca,'UserData',ud);
set(findobj(gcf,'Tag','Redo'),'Enable','off')
set(findobj(gcf,'Tag','Undo'),'Enable','on')
ud = get(gca,'UserData');
for i=ud.histpos:size(ud.boardhistory,1)
hole = find(ud.boardhistory(i,:)==ud.N);
x = mod(hole-1,ud.n)+1;
y = ud.n+1-ceil(hole/ud.n);
delete(findobj(gca,'tag','currpos'))
plot(x+[0 .995 .995 0 0]+0.005,y+[0 0 .995 .995 0],'r', ...
'LineWidth',2, ...
'Tag','currpos')
pause(.01)
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'String',num2str(ud.boardhistory(i,x))), ...
1:ud.N)
set(findobj(gca,'tag','Hole'), ...
'XData',x+[0 .99 .99 0 0]+0.005,...
'YData',y+[0 0 .99 .99 0]+0.005)
pause(.03)
end
ud.histpos = size(ud.boardhistory,1);
set(gca,'UserData',ud);
pause(.2)
set(gcf,'Color',[.95 .95 .95],'Pointer','arrow','CloseRequestFcn','closereq','KeyPressFcn','npuzzle(double(get(gcbf,''Currentcharacter'')))')
drawpos()
end
%------------------------------------------------------------------
case 'Undo'
ud = get(gca,'UserData');
if ud.histpos>1
ud.histpos = ud.histpos-1;
ud.board = ud.boardhistory(ud.histpos,:);
set(gca,'UserData',ud);
drawboard()
set(findobj(gcf,'Tag','Redo'),'Enable','on')
end
if ud.histpos<=1
set(findobj(gcf,'Tag','Undo'),'Enable','off')
end
%------------------------------------------------------------------
case 'Redo'
ud = get(gca,'UserData');
if ud.histpos<size(ud.boardhistory,1)
ud.histpos = ud.histpos+1;
ud.board = ud.boardhistory(ud.histpos,:);
set(gca,'UserData',ud);
drawboard()
set(findobj(gcf,'Tag','Undo'),'Enable','on')
end
if size(ud.boardhistory,1)<=ud.histpos
set(findobj(gcf,'Tag','Redo'),'Enable','off')
end
%------------------------------------------------------------------
case 'ButtonDown' % MouseClick
ud = get(gca,'UserData');
n = sqrt(ud.N);
pos = get(gca,'CurrentPoint');
ud.currpos = sub2ind([n n],floor(pos(1,1)),ud.n+1-floor(pos(1,2)));
set(gca,'UserData',ud);
drawpos()
% If not left-click, treat as space
if ~strcmpi('normal',get(gcf,'SelectionType'))
npuzzle(32)
end
%------------------------------------------------------------------
case 28 % left
ud = get(gca,'UserData');
if ud.currpos~=1
ud.currpos = ud.currpos-1;
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 29 % right
ud = get(gca,'UserData');
if ud.currpos~=ud.N
ud.currpos = ud.currpos+1;
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 30 % up
ud = get(gca,'UserData');
if ud.currpos>ud.n
ud.currpos = ud.currpos-ud.n;
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 31 % down
ud = get(gca,'UserData');
if ud.currpos<=ud.N-ud.n
ud.currpos = ud.currpos+ud.n;
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 32 % space
ud = get(gca,'UserData');
n = sqrt(ud.N);
hole = find(ud.board==ud.N);
bx = mod(hole-1,n)+1;
by = ud.n+1-ceil(hole/n);
cx = mod(ud.currpos-1,n)+1;
cy = ud.n+1-ceil(ud.currpos/n);
if (bx==cx&&abs(by-cy)==1)||(by==cy&&abs(bx-cx)==1)
ud.board(hole) = ud.board(ud.currpos);
ud.board(ud.currpos) = ud.N;
ud.histpos = ud.histpos+1;
ud.boardhistory(ud.histpos,:) = ud.board;
if size(ud.boardhistory,1)>ud.histpos
ud.boardhistory(ud.histpos+1:end,:) = [];
end
set(findobj(gcf,'Tag','Redo'),'Enable','off')
set(findobj(gcf,'Tag','Undo'),'Enable','on')
ud.currpos = hole;
set(gca,'UserData',ud);
drawboard()
drawpos()
if isempty(ud.endtime)
checksolution()
end
end
%------------------------------------------------------------------
case 'About'
ico = ones(13)*3; % create simple icon matrix
ico(:,1:4:13) = 1;
ico(1:4:13,:) = 1;
ico(10:12,10:12) = 2;
map = [0 0 0;.5 .5 .6;1 1 1];
msgbox(sprintf([...
'Graphical User Interface for playing the N-Puzzle.\n\n'...
'Developed by Per-Anders Ekstrm, 2003-2007 Facilia AB\n'...
'E-mail: peranders.ekstrom@facilia.se']),...
'About N-Puzzle','custom',ico,map)
end
end
%% FUNCTION: DRAWBOARD
function drawboard()
ud = get(gca,'UserData');
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'String',num2str(ud.board(x))), ...
1:ud.N)
hole = find(ud.board==ud.N);
x = mod(hole-1,ud.n)+1;
y = ud.n+1-ceil(hole/ud.n);
set(findobj(gca,'Tag','Hole'), ...
'XData',x+[0 .99 .99 0 0]+0.005,...
'YData',y+[0 0 .99 .99 0]+0.005)
end
%% FUNCTION: DRAWPOS
function drawpos()
ud = get(gca,'UserData');
delete(findobj(gca,'tag','currpos'))
x = mod(ud.currpos-1,ud.n)+1;
y = ud.n+1-ceil(ud.currpos/ud.n);
plot(x+[0 .995 .995 0 0]+0.005,y+[0 0 .995 .995 0],'r', ...
'LineWidth',2, ...
'Tag','currpos')
end
%% FUNCTION: SHUFFLEBOARD
function board = shuffleboard(board,times)
N = length(board);
n = sqrt(N);
hole = find(board==N);
for i=1:times
move = [1 -1 n -n];
x = mod(hole-1,n)+1;
y = ceil(hole/n);
switch x
case 1
move(2) = 1;
case n
move(1) = -1;
end
switch y
case 1
move(4) = n;
case n
move(3) = -n;
end
newhole = hole + move(ceil(rand*4));
board(hole) = board(newhole);
hole = newhole;
end
board(newhole) = N;
end
%% FUNCTION: CHECKSOLUTION
function checksolution()
ud = get(gca,'UserData');
if ~ismember(0,ud.board==1:ud.N)
ud.endtime = clock;
set(gca,'UserData',ud);
ico = ones(13)*3; % create simple icon matrix
ico(:,1:4:13) = 1;
ico(1:4:13,:) = 1;
ico(10:12,10:12) = 2;
map = [0 0 0;.5 .5 .6;1 1 1];
msgbox(sprintf([...
'CONGRATULATIONS!\n\n'...
'Start time: %s\n'...
'End time: %s\n\n'...
'Elapsed time: %d seconds\n'...
'Number of moves: %d'],...
datestr(ud.starttime,13),...
datestr(ud.endtime,13),...
round(etime(ud.endtime,ud.starttime)),...
ud.histpos),...
'Finished N-Puzzle','custom',ico,map)
end
end
%% FUNCTION: STARTGAME
function startgame(N)
ud = get(gca,'UserData');
ud.N = N;
ud.n = sqrt(N);
ud.currpos = 1;
set(gca,'UserData',ud);
npuzzle('Surface')
npuzzle('NewGame')
end
%% FUNCTION: SOLVE
function solution = solve(board)
board = board(:)';
solution = [];
N = length(board);
n = sqrt(N);
tilePos = @(tile,board)find(board==tile);
holePos = @(board)tilePos(N,board);
column = @(pos)mod(pos-1,n)+1;
row = @(pos)ceil(pos/n);
%% PHASE 1
% 1. Find the next tile you want to place in position in the top row.
% 2. If it is not the last tile of the row, it is fairly easy to place
% correctly, simply keep the following points in mind:
% 1. Never disturb any previously placed pieces.
% 2. To move the tile in a certain direction, move the other tiles
% around until the space is next to your tile on the side you want
% to move it to. Then you can move the tile.
% 3. If the last tile is not already in position, bring it to the position
% directly below its correct spot, with the space directly below that.
% Then move tiles in the following directions:
% Down, down, right, up, left, up, right, down, down, left, up.
% This should place the piece in position.
% Note it does temporarily disturb the previously placed tile.
for cr=1:n-2 % for all rows except last two rows
for cc=1:n-1 % for all columns except last column
currentTile = cc+(cr-1)*n;
% if tile not at correct position
if tilePos(currentTile,board)~=currentTile %
% if current tile is at bottom row, move it up one step
if row(tilePos(currentTile,board)) == n
% move hole to position above it
moveHoleToRowColumn(n-1,column(tilePos(currentTile,board)))
% pop the position up one step by moving hole down
moveHole('down')
end
% move hole to bottom or side of current tile
while row(holePos(board))<n && row(holePos(board))<row(tilePos(currentTile,board))
moveHole('down');
end
if tilePos(currentTile,board)==currentTile
continue
end
% if current tile is not at correct column
while column(tilePos(currentTile,board)) ~= cc
% move hole to bottom or under tile
while row(holePos(board))<n && row(holePos(board))<=row(tilePos(currentTile,board))
moveHole('down');
end
if tilePos(currentTile,board)==currentTile
continue
end
% move hole to left/right of current tile
if column(tilePos(currentTile,board)) <= cc
while column(holePos(board))<column(tilePos(currentTile,board))+1
moveHole('right');
end
while column(holePos(board))>column(tilePos(currentTile,board))+1
moveHole('left');
end
elseif column(tilePos(currentTile,board)) > cc
while column(holePos(board))>column(tilePos(currentTile,board))-1
moveHole('left');
end
while column(holePos(board))<column(tilePos(currentTile,board))-1
moveHole('right');
end
end
% move hole up to same row of current tile
if row(holePos(board)) > row(tilePos(currentTile,board))
while row(holePos(board)) > row(tilePos(currentTile,board))
moveHole('up');
end
end
if column(holePos(board)) > column(tilePos(currentTile,board))
moveHole('left');
else
moveHole('right');
end
end
% now tile is supposed to be at correct column
% if current tile is not at correct row
while row(tilePos(currentTile,board)) ~= cr
moveHoleToRowColumn(row(tilePos(currentTile,board))+1,column(tilePos(currentTile,board))+1)
moveHole('up','up','left','down')
end
end
end
currentTile = cr*n;
% if tile not at correct position
if tilePos(currentTile,board)~=currentTile
% if current tile is at bottom row
if row(tilePos(currentTile,board)) == n
% move hole to position above it
moveHoleToRowColumn(n-1,column(tilePos(currentTile,board)))
% pop the position up one step
moveHole('down')
end
% move hole to bottom or side of current tile
if row(holePos(board))~=n && row(holePos(board))<=row(tilePos(currentTile,board))
while row(holePos(board))<n && row(holePos(board))<row(tilePos(currentTile,board))
moveHole('down');
end
end
if tilePos(currentTile,board)==currentTile
continue
end
% if current tile is not at correct column
while column(tilePos(currentTile,board)) ~= n
% move hole to bottom or under tile
while row(holePos(board))<n && row(holePos(board))<=row(tilePos(currentTile,board))
moveHole('down');
end
if tilePos(currentTile,board)==currentTile
continue
end
% move hole to left/right of current tile
if column(tilePos(currentTile,board)) <= cc
while column(holePos(board))<column(tilePos(currentTile,board))+1
moveHole('right');
end
while column(holePos(board))>column(tilePos(currentTile,board))+1
moveHole('left');
end
elseif column(tilePos(currentTile,board)) > cc
while column(holePos(board))>column(tilePos(currentTile,board))-1
moveHole('left');
end
while column(holePos(board))<column(tilePos(currentTile,board))-1
moveHole('right');
end
end
% move hole up to same row of current tile
while row(holePos(board)) > row(tilePos(currentTile,board))
moveHole('up');
end
if column(holePos(board)) > column(tilePos(currentTile,board))
moveHole('left');
else
moveHole('right');
end
end
% move last tile to under its position
while row(tilePos(currentTile,board)) > cr+1
moveHoleToRowColumn(row(tilePos(currentTile,board))+1,n-1)
moveHole('up','up','right','down')
end
% move hole to underneath it
moveHoleToRowColumn(cr+2,n)
moveHole('up','up','left','down','right','down','left','up','up','right','down')
end
end
%% PHASE 2
% 1. Use the technique in phase 1 to solve each row in turn, until there
% are only two rows left.
% 2. Rotate the puzzle a quarter turn to the right. The left column of the
% two rows becomes the top row now.
% 3. Use the technique in phase 1 to solve each row in turn, until there
% are only two rows left. This means there is only a 2x2 square left to
% solve.
% 4. Move the pieces in the remaining 2x2 square around until one piece is
% positioned correctly, and the space is in the correct spot. The other
% two tiles should automatically be correctly positioned as well.
% 5. If there are two tiles that need to be swapped, then this cannot be
% done unless two other tiles are swapped as well. If there are two
% identical tiles somewhere in the puzzle, then you will have to swap
% them and solve the rest again.
% turn the board
for cc=1:n-2 % for all columns except last two columns
cr = n; % last row
currentTile = cc+(cr-1)*n;
% if tile not at correct position
if tilePos(currentTile,board)~=currentTile %
% if tile is not at last row, make it
if row(tilePos(currentTile,board)) ~= n
moveHoleToRowColumn(n,column(tilePos(currentTile,board)))
moveHole('up')
end
while column(tilePos(currentTile,board)) ~= cc
moveHoleToRowColumn(n-1,column(tilePos(currentTile,board)))
moveHole('left','down','right')
end
end
currentTile = cc+(cr-2)*n;
% if tile not at correct position
if tilePos(currentTile,board)~=currentTile
% move hole toright if it might disturb other pieces
if column(holePos(board))==cc
moveHole('right');
end
if tilePos(currentTile,board)==currentTile
continue
end
% tile is not at row n-1, make it
if row(tilePos(currentTile,board)) ~= n-1
moveHoleToRowColumn(n-1,column(tilePos(currentTile,board)))
moveHole('down')
end
% move last tile to under its position
while column(tilePos(currentTile,board)) ~= cc+1
moveHoleToRowColumn(n,column(tilePos(currentTile,board)))
moveHole('left','up','right')
end
% move hole to right side of it
moveHoleToRowColumn(n,cc+2);moveHole('up')
moveHole('left','left','down','right','up','right','down','left','left','up','right')
end
end
% Last 2x2 square
count = 0;
while holePos(board)~=n*n || tilePos((n-1)*n,board)~=(n-1)*n
if row(holePos(board))==n
if column(holePos(board))==n
moveHole('up')
else
moveHole('right')
end
else
if column(holePos(board))==n
moveHole('left')
else
moveHole('down')
end
end
count = count+1;
if count>10 % unsolvable
break
end
end
function swap(x,y)
xp = (board==x);
yp = (board==y);
board(xp) = y;
board(yp) = x;
end
function moveHole(varargin)
hp = find(board==N);
for ii=1:nargin
switch varargin{ii}
case 'left'
hp = hp-1;
case 'right'
hp = hp+1;
case 'up'
hp = hp-n;
case 'down'
hp = hp+n;
end
swap(N,board(hp))
solution = [solution;board];
end
end
function moveHoleToRowColumn(x,y)
while row(holePos(board)) < x
moveHole('down')
end
while row(holePos(board)) > x
moveHole('up')
end
while column(holePos(board)) < y
moveHole('right')
end
while column(holePos(board)) > y
moveHole('left')
end
end
end
