function sudoku(cmd)
%SUDOKU Graphical User Interface for playing Sudoku-Puzzles.
%
% Game Rules:
% Fill in the grid so that every row, every column, and every 3x3 box
% contains the digits 1 through 9.
%
% Game Board:
% The sudoku interface lets the user solve sudoku puzzles graphically.
% The puzzles are either generated by the built-in puzzle generator
% (three difficult levels can be chosen), randomly taken from the built-
% in database of 160 really difficult puzzles, entered manually by the
% user or loaded from three standard ascii sudoku files 'Simple Sudoku'
% (.ss), 'Sudoku Puzzle' (.sdk) or 'Sudoku Puzzle Collection' (.sdm).
% The game board can be saved to Simple Sudoku and Sudoku Puzzle files.
% The current board can also be exported to various image-files, such as
% jpg, png, bmp, eps or tiff. The board can be printed and also copied to
% clipboard to be pasted as an image in for example a MS Word document.
%
% Game Controls:
% The sudoku game can be played using either mouse or keyboard (or both).
% Move around marker using arrow keys and add a number using number keys.
% Delete, backspace or 0 (zero) will remove number from board. With mouse
% you move around marker using left-click and reach a context-menu with
% number choices using right-click.
% Illegal characters can not be entered.
%
% Game Solver:
% The sudoku game has two built-in puzzle solvers, one quick and one
% 'human-like'. The quick one is based on Dancing Links (DLX),a technique
% suggested by Donald Knuth to efficiently implement his Algorithm X.
% Algorithm X is a recursive, nondeterministic, depth-first, brute-force
% algorithm that finds all solutions to the exact cover problem.
% The human solver finds Naked Singles, Hidden Singles, Naked Pairs and
% Locked Candidates 1 and 2. If this is not enough it takes a guess and
% tries to solve it recursively.
% The dlx-solver is used for solving and generating puzzles while the
% human puzzle is used to generate a log of solution steps.
% The game allows for automatic solving of the whole puzzle or just one
% single square. To help the user one can show all possible candidates
% for unfilled squares as well as showing all mistakes in a different
% color as well as making it impossible to make an illegal mark.
%
% Extra Features:
% The sudoku game has Undo and Redo functionality that can be reached
% from the Edit-menu, Context-menu or by the shortcuts Ctrl-Z (Undo) and
% Ctrl-R (Redo).
% Every time one restarts a game a timer is started. Current time can be
% shown using Ctrl-T or enable/disabled from the Help menu.
% A coloring help of possible candidates can be added to the matrix from
% the colored numbers in the toolbar.
%
% Example:
% sudoku % Start Main Sudoku Interface
% sudoku('uitest') % Solve all 160 boards in database (test set)
% Developed by Per-Anders Ekstrm, 2003-2007 Facilia AB.
if ~nargin
feval(mfilename,'init')
return;
end
if ~(ischar(cmd)||isscalar(cmd))
return;
end
switch cmd
%------------------------------------------------------------------
case 'init'
% MAIN FIGURE
scrsz = get(0,'ScreenSize');
hFigure = figure( ...
'Name','Sudoku', ...
'Menubar','none',...
'NumberTitle','off', ...
'KeyPressFcn',sprintf('%s(double(get(gcbf,''Currentcharacter'')))',mfilename), ...
'Units','pixels', ...
'Tag','Sudoku', ...
'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');
fMenu = uimenu(hFigure,'Label','&File');
nGMenu = uimenu(fMenu,'Label','New Game');
uimenu(nGMenu,'Label','Easy','Callback',sprintf('%s(''Easy'')',mfilename))
uimenu(nGMenu,'Label','Normal','Callback',sprintf('%s(''Normal'')',mfilename))
uimenu(nGMenu,'Label','Hard','Callback',sprintf('%s(''Hard'')',mfilename))
uimenu(nGMenu,'Label','From Database','Separator','on','Callback',sprintf('%s(''Database'')',mfilename))
uimenu(fMenu,'Label','Input Game','Callback',sprintf('%s(''InputGame'')',mfilename))
uimenu(fMenu,'Label','Restart Game','Callback',sprintf('%s(''Restart'')',mfilename))
uimenu(fMenu,'Label','Open ...','Accelerator','O','Separator','on','Callback',sprintf('%s(''Open'')',mfilename))
uimenu(fMenu,'Label','Save As ...','Accelerator','A','Callback',sprintf('%s(''SaveAs'')',mfilename))
uimenu(fMenu,'Label','Print Preview...','Separator','on','Callback','printpreview(gcf)')
uimenu(fMenu,'Label','Print...','Accelerator','P','Callback','printdlg(gcf)')
uimenu(fMenu,'Label','Exit','Separator','on','Accelerator','Q','Callback','closereq;')
% Create the edit menu
eMenu = uimenu(hFigure,'Label','&Edit');
uimenu(eMenu,'Label','Undo','Accelerator','Z','Callback',sprintf('%s(''Undo'')',mfilename),'Tag','Undo','Enable','off')
uimenu(eMenu,'Label','Redo','Accelerator','R','Callback',sprintf('%s(''Redo'')',mfilename),'Tag','Redo','Enable','off')
uimenu(eMenu,'Label','Copy','Accelerator','C','Callback','print(gcf,''-dmeta'')','Separator','on')
% Create the solver menu
sMenu = uimenu(hFigure,'Label','&Solver','Tag','Solver');
uimenu(sMenu,'Label','Solve Game','Callback',sprintf('%s(''Solve'')',mfilename))
uimenu(sMenu,'Label','Solve Current Position','Callback',sprintf('%s(''SolveCurrentPosition'')',mfilename))
uimenu(sMenu,'Label','Show Solver Log','Callback',sprintf('%s(''ShowSolverLog'')',mfilename))
uimenu(sMenu,'Label','Show Candidates','Separator','on','Callback',sprintf('%s(''ShowCandidates'')',mfilename),'Tag','ShowCandidates')
uimenu(sMenu,'Label','Show Mistakes','Callback',sprintf('%s(''ShowMistakes'')',mfilename),'Tag','ShowMistakes')
uimenu(sMenu,'Label','Block Invalid Moves','Callback',sprintf('%s(''BlockInvalidMoves'')',mfilename),'Tag','BlockInvalidMoves')
% Create the help menu
hMenu = uimenu(hFigure,'Label','&Help');
uimenu(hMenu,'Label','Help','Accelerator','H','Callback',sprintf('helpwin %s',mfilename))
uimenu(hMenu,'Label','Show Timer','Accelerator','T','Callback',sprintf('%s(''ShowTimer'')',mfilename),'Separator','on','Tag','ShowTimer')
uimenu(hMenu,'Label','About','Callback',sprintf('%s(''About'')',mfilename),'Separator','on')
% Create the uicontextmenu for the axis
cmenu = uicontextmenu;
uimenu(cmenu,'Label','Make 1','Callback',sprintf('%s(49)',mfilename))
uimenu(cmenu,'Label','Make 2','Callback',sprintf('%s(50)',mfilename))
uimenu(cmenu,'Label','Make 3','Callback',sprintf('%s(51)',mfilename))
uimenu(cmenu,'Label','Make 4','Callback',sprintf('%s(52)',mfilename))
uimenu(cmenu,'Label','Make 5','Callback',sprintf('%s(53)',mfilename))
uimenu(cmenu,'Label','Make 6','Callback',sprintf('%s(54)',mfilename))
uimenu(cmenu,'Label','Make 7','Callback',sprintf('%s(55)',mfilename))
uimenu(cmenu,'Label','Make 8','Callback',sprintf('%s(56)',mfilename))
uimenu(cmenu,'Label','Make 9','Callback',sprintf('%s(57)',mfilename))
uimenu(cmenu,'Label','Delete','Callback',sprintf('%s(48)',mfilename))
uimenu(cmenu,'Label','Undo','Separator','on','Callback',sprintf('%s(''Undo'')',mfilename),'Tag','Undo','Enable','off')
uimenu(cmenu,'Label','Redo','Callback',sprintf('%s(''Redo'')',mfilename),'Tag','Redo','Enable','off')
% Create the Toolbar
tb = uitoolbar(hFigure);
iconpath = sprintf('%s%stoolbox%smatlab%sicons%s',matlabroot,filesep,filesep,filesep,filesep);
tmp = load([iconpath 'newdoc.mat']);
uipushtool(tb,'CData',tmp.cdata,'TooltipString','New Game','ClickedCallback',sprintf('%s(''Database'')',mfilename));
tmp = load([iconpath 'opendoc.mat']);
uipushtool(tb,'CData',tmp.cdata,'TooltipString','Open file','ClickedCallback',sprintf('%s(''Open'')',mfilename));
tmp = load([iconpath 'savedoc.mat']);
uipushtool(tb,'CData',tmp.cdata,'TooltipString','Save','ClickedCallback',sprintf('%s(''SaveAs'')',mfilename));
tmp = NaN*zeros(16);
tmp([39;40;41;42;43;56;57;58;59;73;74;75;88;90;91;103;107;119;134;150;166;182;199;203;204;216;217;218]) = 0;
uipushtool(tb,'CData',repmat(tmp,[1 1 3]),'TooltipString','Undo','ClickedCallback',sprintf('%s(''Undo'')',mfilename),'Separator','on','Tag','Undo','Enable','off');
tmp = NaN*zeros(16);
tmp([40;41;42;55;59;60;70;86;102;118;135;151;155;168;170;171;185;186;187;200;201;202;203;215;216;217;218;219]) = 0;
uipushtool(tb,'CData',repmat(tmp,[1 1 3]),'TooltipString','Redo','ClickedCallback',sprintf('%s(''Redo'')',mfilename),'Tag','Redo','Enable','off');
uitoggletool(tb,'CData',getToggleCData([1 0 0.8],1),'TooltipString','1','Separator','on','Tag','[1 0 0.8]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename))
uitoggletool(tb,'CData',getToggleCData([0.8 1 0],2),'TooltipString','2','Tag','[0.8 1 0]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename));
uitoggletool(tb,'CData',getToggleCData([0 0.8 1],3),'TooltipString','3','Tag','[0 0.8 1]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename));
uitoggletool(tb,'CData',getToggleCData([0.5 1 0.5],4),'TooltipString','4','Tag','[0.5 1 0.5]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename));
uitoggletool(tb,'CData',getToggleCData([0.5 0.5 1],5),'TooltipString','5','Tag','[0.5 0.5 1]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename));
uitoggletool(tb,'CData',getToggleCData([1 0.5 0.5],6),'TooltipString','6','Tag','[1 0.5 0.5]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename));
uitoggletool(tb,'CData',getToggleCData([1 0.8 0.5],7),'TooltipString','7','Tag','[1 0.8 0.5]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename));
uitoggletool(tb,'CData',getToggleCData([0.5 1 0.8],8),'TooltipString','8','Tag','[0.5 1 0.8]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename));
uitoggletool(tb,'CData',getToggleCData([0.8 0.5 1],9),'TooltipString','9','Tag','[0.8 0.5 1]','ClickedCallback',sprintf('%s(''Toggle'')',mfilename));
% MATRIX AXES
axes( ...
'Parent',hFigure, ...
'Units','normalized', ...
'Clipping','off', ...
'XTick',[],...
'YTick',[],...
'Tag','SudokuAxes',...
'ButtonDownFcn',sprintf('%s(''ButtonDown'');',mfilename), ...
'UIContextMenu',cmenu, ...
'Position',[0.02 0.02 0.96 0.96]);
axis('square')
axis([0 9 0 9])
hold on
% GRID
arrayfun(@(x)plot([x x],[0 9],'k','linewidth',2),[9/3 18/3])
arrayfun(@(y)plot([0 9],[y y],'k','linewidth',2),[9/3 18/3])
arrayfun(@(x)plot([x x],[0 9],'k'),linspace(1,8,8))
arrayfun(@(y)plot([0 9],[y y],'k'),linspace(1,8,8))
plot([0 9],[0 0],'k','linewidth',2)
plot([0 9],[9 9],'k','linewidth',3)
plot([0 0],[0 9],'k','linewidth',3)
plot([9 9],[0 9],'k','linewidth',2)
% TEXT FIELDS
arrayfun(@(x)text( ...
'Position',[mod(x-1,9) 9-ceil(x/9)]+.5, ...
'String',num2str(x), ...
'FontUnits','normalized', ...
'FontSize',0.07, ...
'Tag',num2str(x), ...
'ButtonDownFcn',sprintf('%s(''ButtonDown'');',mfilename), ...
'UIContextMenu',cmenu, ...
'HorizontalAlignment','center'), ...
1:81)
ud.ShowCandidates = 0;
ud.ShowMistakes = 0;
ud.BlockInvalidMoves = 0;
set(gca,'UserData',ud)
% Start a board from database
feval(mfilename,'Database')
%------------------------------------------------------------------
case {127 8} % delete (48 means 0 => remove number)
feval(mfilename,48)
%------------------------------------------------------------------
case {48 49 50 51 52 53 54 55 56 57} % a number between 0-9
ud = get(gca,'UserData');
if ud.board(ud.histpos,ud.currpos)~=cmd-48 && ...
ismember(ud.currpos,find(ud.board(1,:)==0)) && ...
(~ud.BlockInvalidMoves||ud.solution(ud.currpos)==cmd-48)
board = ud.board(ud.histpos,:);
board(ud.currpos) = cmd-48;
ud.histpos = ud.histpos+1;
ud.board(ud.histpos,:) = board;
if size(ud.board,1)>ud.histpos
ud.board(ud.histpos+1:end,:) = [];
end
delete(findobj(gcf,'Tag','ColorHelp'))
set(findobj(gcbf,'Type','uitoggletool'),'State','off')
set(findobj(gcf,'Tag','Redo'),'Enable','off')
set(findobj(gcf,'Tag','Undo'),'Enable','on')
set(gca,'UserData',ud);
drawboard()
updateCandidates()
updateMistakes()
if isequal(board,ud.solution)&&isempty(ud.EndTime)
ud.EndTime = now;
set(gca,'UserData',ud);
I = getIcon();
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: %s\n'...
'Number of moves: %d'],...
datestr(ud.StartTime,13),...
datestr(ud.EndTime,13),...
datestr(ud.EndTime-ud.StartTime,13),...
ud.histpos),...
'Finished Sudoku-Puzzle','custom',I,map)
set(gca,'UserData',ud);
end
end
%------------------------------------------------------------------
case 'ButtonDown' % MouseClick
ud = get(gca,'UserData');
pos = get(gca,'CurrentPoint');
x = floor(pos(1,1))+1;
y = 9-floor(pos(1,2));
if ismember(x,1:9)&&ismember(y,1:9)
ud.currpos = x+9*(y-1);
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 28 % left
ud = get(gca,'UserData');
if ~ismember(ud.currpos,1:9:73)
ud.currpos = ud.currpos-1;
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 29 % right
ud = get(gca,'UserData');
if ~ismember(ud.currpos,9:9:81)
ud.currpos = ud.currpos+1;
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 30 % up
ud = get(gca,'UserData');
if ud.currpos>9
ud.currpos = ud.currpos-9;
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 31 % down
ud = get(gca,'UserData');
if ud.currpos<=81-9
ud.currpos = ud.currpos+9;
set(gca,'UserData',ud);
drawpos()
end
%------------------------------------------------------------------
case 'Undo'
ud = get(gca,'UserData');
if ud.histpos>1
ud.histpos = ud.histpos-1;
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
delete(findobj(gcf,'Tag','ColorHelp'))
set(findobj(gcbf,'Type','uitoggletool'),'State','off')
%------------------------------------------------------------------
case 'Redo'
ud = get(gca,'UserData');
if ud.histpos<size(ud.board,1)
ud.histpos = ud.histpos+1;
set(gca,'UserData',ud);
drawboard()
set(findobj(gcf,'Tag','Undo'),'Enable','on')
end
if size(ud.board,1)<=ud.histpos
set(findobj(gcf,'Tag','Redo'),'Enable','off')
end
delete(findobj(gcf,'Tag','ColorHelp'))
set(findobj(gcbf,'Type','uitoggletool'),'State','off')
%------------------------------------------------------------------
case {'Easy','Normal','Hard'}
ud = get(gca,'UserData');
[ud.board,ud.solution] = ...
generateBoard(strmatch(cmd,{'Easy','Normal','Hard'}));
set(gca,'UserData',ud)
feval(mfilename,'Restart')
%------------------------------------------------------------------
case 'Database'
ud = get(gca,'UserData');
ud.board = getFromDatabase('RandomBoard');
ud.solution = dlxsolver(ud.board,1);
set(gca,'UserData',ud)
feval(mfilename,'Restart')
%------------------------------------------------------------------
case 'Open'
ud = get(gca,'UserData');
[FileName,PathName,FilterIndex] = uigetfile( ...
{'*.ss','Simple Sudoku Files (*.ss)'; ...
'*.sdk','Sudoku Puzzle Files (*.sdk)'; ...
'*.sdm','Sudoku Puzzle Collection (*.sdm)'}, ...
'Pick a file');
switch FilterIndex
case 1 % ss
board = readSS(fullfile(PathName,FileName));
case 2 % sdk
board = readSDK(fullfile(PathName,FileName));
case 3 % sdk
board = readSDM(fullfile(PathName,FileName));
otherwise
board = zeros(1,81);
end
if isequal(true(1,81),ismember(board,0:9))
if FilterIndex
ud.board = board;
ud.solution = [];
ud.histpos = 1;
set(gca,'UserData',ud)
feval(mfilename,'Restart')
end
else
errordlg(sprintf('Couldn''t read a valid game from file "%s".',FileName))
end
%------------------------------------------------------------------
case 'Restart'
ud = get(gca,'UserData');
if isempty(ud.solution)
if ~isfield(ud,'histpos')
ud.histpos = 1;
end
[solution nsol]= dlxsolver(ud.board(ud.histpos,:),2);
if nsol==0
errordlg('Game has No Solution!');
return;
elseif nsol>1
errordlg('Game has Multiple Solutions!')
return;
end
ud.board = ud.board(ud.histpos,:);
ud.solution = solution;
end
ud.StartTime = now;
ud.EndTime = [];
ud.currpos = 1;
ud.histpos = 1;
set(gca,'UserData',ud)
drawboard()
drawpos()
updateCandidates()
updateMistakes()
set(findobj(gcf,'Tag','Solver'),'Enable','on')
set(findobj(gcf,'Tag','Undo'),'Enable','off')
set(findobj(gcf,'Tag','Redo'),'Enable','off')
delete(findobj(gcf,'Tag','ColorHelp'))
set(findobj(gcbf,'Type','uitoggletool'),'State','off')
%------------------------------------------------------------------
case 'SaveAs'
ud = get(gca,'UserData');
[FileName,PathName,FilterIndex] = uiputfile( ...
{'*.ss','Simple Sudoku Files (*.ss)'; ...
'*.sdk','Sudoku Puzzle Files (*.sdk)'; ...
'*.jpg','JPEG image (*.jpg)'; ...
'*.png','Portable Network Graphics (*.png)'; ...
'*.bmp','Windows bitmap (*.bmp)'; ...
'*.eps','EPS Level 1 (*.eps)'; ...
'*.tif','TIFF image (*.tif)'}, ...
'Save as');
switch FilterIndex
case 1 % ss
writeSS(fullfile(PathName,FileName),ud.board(ud.histpos,:));
case 2 % sdk
writeSDK(fullfile(PathName,FileName),ud.board(ud.histpos,:));
case{3 4 5 6 7}
delete(findobj(gca,'tag','currpos'))
saveas(gcf,fullfile(PathName,FileName))
drawpos()
end
%------------------------------------------------------------------
case 'Solve'
ud = get(gca,'UserData');
ind = find(ud.board(ud.histpos,:)~=ud.solution);
order = randperm(length(ind));
f = gcbf;
for i=1:length(ind)
ud.currpos = ind(order(i));
set(gca,'UserData',ud);
feval(mfilename,ud.solution(ind(order(i)))+48)
ud = get(gca,'UserData');
pause(.1)
if ~ishandle(f)
break
end
end
%------------------------------------------------------------------
case 'SolveCurrentPosition'
ud = get(gca,'UserData');
feval(mfilename,ud.solution(ud.currpos)+48)
%------------------------------------------------------------------
case 'InputGame'
ud = get(gca,'UserData');
ud.board = zeros(1,81);
ud.solution = [];
ud.histpos = 1;
ud.ShowCandidates = 0;
ud.ShowMistakes = 0;
ud.BlockInvalidMoves = 0;
set(gca,'UserData',ud);
drawboard()
updateCandidates()
updateMistakes()
set(findobj(gcf,'Tag','ShowCandidates'),'Checked','off')
set(findobj(gcf,'Tag','ShowMistakes'),'Checked','off')
set(findobj(gcf,'Tag','BlockInvalidMoves'),'Checked','off')
set(findobj(gcf,'Tag','Solver'),'Enable','off')
set(findobj(gcf,'Tag','Undo'),'Enable','off')
set(findobj(gcf,'Tag','Redo'),'Enable','off')
delete(findobj(gcf,'Tag','ColorHelp'))
set(findobj(gcbf,'Type','uitoggletool'),'State','off')
%------------------------------------------------------------------
case 'ShowCandidates'
ud = get(gca,'UserData');
menu = findobj(gcf,'Tag','ShowCandidates');
if strcmp('on',get(menu,'Checked'))
set(menu,'Checked','off')
ud.ShowCandidates = 0;
else
set(menu,'Checked','on')
ud.ShowCandidates = 1;
end
set(gca,'UserData',ud);
updateCandidates()
%------------------------------------------------------------------
case 'BlockInvalidMoves'
ud = get(gca,'UserData');
menu = findobj(gcf,'Tag','BlockInvalidMoves');
if strcmp('on',get(menu,'Checked'))
set(menu,'Checked','off')
ud.BlockInvalidMoves = 0;
else
set(menu,'Checked','on')
ud.BlockInvalidMoves = 1;
end
set(gca,'UserData',ud);
%------------------------------------------------------------------
case 'ShowMistakes'
ud = get(gca,'UserData');
menu = findobj(gcf,'Tag','ShowMistakes');
if strcmp('on',get(menu,'Checked'))
set(menu,'Checked','off')
ud.ShowMistakes = 0;
else
set(menu,'Checked','on')
ud.ShowMistakes = 1;
end
set(gca,'UserData',ud);
updateMistakes()
%------------------------------------------------------------------
case 'ShowTimer'
ud = get(gca,'UserData');
menu = findobj(gcf,'Tag','ShowTimer');
if strcmp('on',get(menu,'Checked'))
set(menu,'Checked','off')
ud.ShowTimer = 0;
set(gca,'UserData',ud);
delete(findobj(gcf,'Tag','Timer'))
else
set(menu,'Checked','on')
ud.ShowTimer = 1;
set(gca,'UserData',ud);
Timer = text(8.95,0,'',...
'FontUnits','normalized', ...
'FontSize',0.018, ...
'FontName','FixedWidth',...
'FontWeight','bold',...
'VerticalAlignment','bottom', ...
'HorizontalAlignment','right',...
'Tag','Timer');
while isfield(ud,'ShowTimer')&&ud.ShowTimer==1&&ishandle(Timer)
set(Timer,'String',datestr(now-ud.StartTime,13))
pause(1)
if ishandle(Timer)
ud = get(findobj('Tag','SudokuAxes'),'UserData');
end
end
end
%------------------------------------------------------------------
case 'Toggle'
delete(findobj(gcbf,'Tag','ColorHelp'))
State = get(gcbo,'State');
set(findobj(gcbf,'Type','uitoggletool'),'State','off')
if strcmp(State,'on')
set(gcbo,'State','on')
val = str2double(get(gcbo,'TooltipString'));
Color = str2num(get(gcbo,'Tag'));
width = .25;
ud = get(gca,'UserData');
% FILL
xx = [-width 0 width];
yy = [width 0 -width];
x = find(ud.board(ud.histpos,:)==0);
for i=1:length(x)
if ismember(val,getPossible(ud.board(ud.histpos,:),x(i)))
fill([0 width width 0 0]+mod(x(i)-1,9)+.38+xx(mod(val-1,3)+1),...
[0 0 width width 0]+9-ceil(x(i)/9)+.38+yy(ceil(val/3)),...
Color,...
'ButtonDownFcn',sprintf('%s(''ButtonDown'');',mfilename), ...
'Tag','ColorHelp')
end
end
else
end
%------------------------------------------------------------------
case 'ShowSolverLog'
% Shows the solver log
% --------------------
ud = get(gca,'UserData');
[solution LOGGER] = humansolver(ud.board(1,:));
xsize = 330;
ysize = 300;
scrsize = get(0,'screensize');
fig = figure('Name','MATLAB: Sudoku - Solution Log', ...
'Unit','Pixels','NumberTitle','off','Menubar','none',...
'Position',[0.5*(scrsize(3)-xsize) 0.5*(scrsize(4)-ysize) xsize ysize]);
uicontrol(fig,'Style','Listbox','Unit','Normalized',...
'Position',[0 0 1 1],'BackgroundColor',[1 1 1],...
'Max',3,'Min',1,'Callback','set(gco,''Value'',[])',...
'FontName','FixedWidth',...
'Value',[],'String', LOGGER);
%------------------------------------------------------------------
case 'uitest'
Database = getFromDatabase('Database');
lD = length(Database);
h = waitbar(0,sprintf('Solving %d hard boards from Database and check for unique solutions!',lD),'Name','Please wait...');
start = cputime;
for i=1:lD
board = str2num(regexprep(Database{i},'([0-9])','$1 '));
[solution nsol] = dlxsolver(board,2);
waitbar(i/lD)
if nsol~=1
waitbar(i/lD,h,'Fail!','Name')
set(h,'Name',sprintf('Elapsed time is %d seconds.',ceil(cputime-start)))
return
end
end
waitbar(1,h,'Pass!')
set(h,'Name',sprintf('Elapsed time is %d seconds.',ceil(cputime-start)))
p = findobj(h,'Type','patch');
set(p,'EdgeColor','k','FaceColor','g')
%close(h)
%------------------------------------------------------------------
case 'About'
I = getIcon();
map = [0 0 0;.5 .5 .6;1 1 1];
msgbox(sprintf([...
'Graphical User Interface for playing Sudoku-Puzzles.\n\n'...
'Developed by Per-Anders Ekstrm, 2003-2007 Facilia AB\n'...
'E-mail: peranders.ekstrom@facilia.se']),...
'About Sudoku','custom',I,map)
end
function CData = getToggleCData(color,number)
CData = zeros(16,16,3);
tmp = zeros(1,1,3);
tmp(1,1,:) = color;
CData(2:15,2:15,:) = repmat(tmp,[14 14 1]);
switch number
case 1
[ii jj]=ind2sub([16 16],[103;118;133;134;135;136;137;138;139;140;141]);
case 2
[ii jj]=ind2sub([16 16],[86;93;101;108;109;117;123;125;133;137;138;141;150;151;152;157]);
case 3
[ii jj]=ind2sub([16 16],[86;92;101;109;117;121;125;133;137;141;150;151;152;154;155;156]);
case 4
[ii jj]=ind2sub([16 16],[90;91;104;105;107;118;119;123;133;134;135;136;137;138;139;140;141;155]);
case 5
[ii jj]=ind2sub([16 16],[87;88;89;92;101;102;104;109;117;120;125;133;136;141;149;153;154;155;156]);
case 6
[ii jj]=ind2sub([16 16],[86;87;88;89;90;91;92;101;105;109;117;120;125;133;136;141;150;153;154;155;156]);
case 7
[ii jj]=ind2sub([16 16],[101;117;123;124;125;133;136;137;138;149;150;151;165]);
case 8
[ii jj]=ind2sub([16 16],[86;87;88;90;91;92;101;105;109;117;121;125;133;137;141;150;151;152;154;155;156]);
case 9
[ii jj]=ind2sub([16 16],[86;87;88;89;92;101;106;109;117;122;125;133;137;141;150;151;152;153;154;155;156]);
end
for i=1:length(ii)
CData(ii(i),jj(i),:) = 0;
end
%--------------------------------------------------------------------------
function I = getIcon()
I = ones(16,16,3,'uint8')*255;
I(:,[1 6 11 16],:) = 0;
I([1 6 11 16],:,:) = 0;
I(2:5,2:5,[1 2]) = 0;
I(7:10,7:10,[2 3]) = 0;
I(12:15,12:15,[1 3]) = 0;
%--------------------------------------------------------------------------
function drawboard()
% Draw the numbers on the matrix
%--------------------------------------------------------------------------
ud = get(gca,'UserData');
board = ud.board(ud.histpos,:);
initboard = ud.board(1,:);
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'String',num2str(board(x))), ...
find(board))
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'String',''), ...
find(board==0))
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'Fontweight','Bold','Color',[.1 .1 .5]), ...
find(initboard))
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'Fontweight','Normal'), ...
find(initboard==0))
% -------------------------------------------------------------------------
function drawpos()
% Draw current position on matrix
%--------------------------------------------------------------------------
ud = get(gca,'UserData');
delete(findobj(gca,'tag','currpos'))
x = mod(ud.currpos-1,9);
y = 9-ceil(ud.currpos/9);
plot(x+[0 .995 .995 0 0]+0.005,y+[0 0 .995 .995 0],'r', ...
'LineWidth',2, ...
'Tag','currpos')
% -------------------------------------------------------------------------
function updateCandidates()
% Add/Remove Candidates in matrix
%--------------------------------------------------------------------------
delete(findobj(gca,'Tag','Tool'))
ud = get(gca,'UserData');
if ud.ShowCandidates
x = find(ud.board(ud.histpos,:)==0);
for i=1:length(x)
list = getPossible(ud.board(ud.histpos,:),x(i));
str = repmat(' ',3,3);
for j=1:length(list)
str(list(j)) = num2str(list(j));
end
% TEXT FIELDS
xx = [-.3 0 .3];
yy = [.3 0 -.3];
for j=1:length(list)
text( ...
'Position',[mod(x(i)-1,9)+.5+xx(mod(list(j)-1,3)+1), ...
9-ceil(x(i)/9)+.5+yy(ceil(list(j)/3))], ...
'String',num2str(list(j)), ...
'FontUnits','normalized', ...
'FontSize',0.018, ...
'FontWeight','bold',...
'Tag','Tool', ...
'ButtonDownFcn',sprintf('%s(''ButtonDown'');',mfilename), ...
'VerticalAlignment','middle', ...
'HorizontalAlignment','center')
end
end
end
% -------------------------------------------------------------------------
function updateMistakes()
% Add/Remove Mistakes in matrix
%--------------------------------------------------------------------------
ud = get(gca,'UserData');
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'Color',[0 0 0]), ...
find(ud.board(1,:)==0))
if ud.ShowMistakes
arrayfun(@(x)set(findobj(gca,'tag',num2str(x)), ...
'Color',[1 0 0]), ...
find(ud.board(ud.histpos,:)~=ud.solution))
end
% -------------------------------------------------------------------------
function possible = getPossible(board,ind)
% Returns the possible values in board for the element in position ind
%--------------------------------------------------------------------------
y = ceil(ind/9);
x = mod(ind-1,9)+1;
xstart = (ceil(x./3)-1)*3+1;
ystart = (ceil(y./3)-1)*3+1;
square = board([xstart+(ystart-1)*9:xstart+(ystart-1)*9+2 ...
xstart+ystart*9:xstart+ystart*9+2 ...
xstart+(ystart+1)*9:xstart+(ystart+1)*9+2]);
column = board(x:9:81);
row = board(y+(y-1)*8:y+8+(y-1)*8);
possible = setdiff(1:9,[square(:);column(:);row(:)]);
% -------------------------------------------------------------------------
function board = readSS(filename)
% Returns a board read from a Simple Sudoku (.ss) file
%--------------------------------------------------------------------------
ss = textread(filename,'%s');
ss([4,8]) = [];
board = [];
for i=1:9
ss{i} = strrep(ss{i},'|','');
ss{i} = strrep(ss{i},'.','0');
ss{i} = regexprep(ss{i},'([0-9])','$1 ');
board = [board str2num(ss{i})];
end
% -------------------------------------------------------------------------
function writeSS(filename,board)
% Writes board to a Simple Sudoku (.ss) file
%--------------------------------------------------------------------------
fid = fopen(filename,'wt');
for i=1:9
str = num2str((board(1+(i-1)*9:1+(i-1)*9+8)));
str([8 17]) = '|';
str = strrep(str,'0','.');
str = strrep(str,' ','');
fprintf(fid,'%s\n',str);
if ismember(i,[3 6])
fprintf(fid,'-----------\n');
end
end
fclose(fid);
% -------------------------------------------------------------------------
function board = readSDK(filename)
% Returns a board read from a Sudoku Puzzle (.sdk) file
%--------------------------------------------------------------------------
sdk = textread(filename,'%s');
board = [];
for i=1:length(sdk)
if isempty(strfind(sdk{i},'#'))
sdk{i} = strrep(sdk{i},'.','0');
sdk{i} = regexprep(sdk{i},'([0-9])','$1 ');
board = [board str2num(sdk{i})];
end
end
% -------------------------------------------------------------------------
function writeSDK(filename,board)
% Write board to a Sudoku Puzzle (.ss) file
%--------------------------------------------------------------------------
fid = fopen(filename,'wt');
for i=1:9
str = num2str((board(1+(i-1)*9:1+(i-1)*9+8)));
str = strrep(str,'0','.');
str = strrep(str,' ','');
fprintf(fid,'%s\n',str);
end
fclose(fid);
% -------------------------------------------------------------------------
function board = readSDM(filename)
% Returns a board read from a Sudoku Puzzle Collection (.sdm) file
%--------------------------------------------------------------------------
sdm = textread(filename,'%s');
board = str2num(regexprep(sdm{ceil(rand*length(sdm))},'([0-9])','$1 '));
% -------------------------------------------------------------------------
function bool = isSolvable(board)
% Check if board is solvable
%--------------------------------------------------------------------------
bool = true;
ind = [1,4,7];
for i=1:9
xstart = ind(mod(i-1,3)+1);
ystart = ind(ceil((i)/3));
index = [xstart+(ystart-1)*9:xstart+(ystart-1)*9+2, ...
xstart+ystart*9:xstart+ystart*9+2, ...
xstart+(ystart+1)*9:xstart+(ystart+1)*9+2];% for each square
if ~isempty(find(histc(board(index),1:9)>1))
bool=false;
return;
end
index = i+(i-1)*8:i+8+(i-1)*8;% for each row
if ~isempty(find(histc(board(index),1:9)>1))
bool=false;
return;
end
index = i:9:81;% for each column
if ~isempty(find(histc(board(index),1:9)>1))
bool=false;
return;
end
end
% -------------------------------------------------------------------------
function [board,solution] = generateBoard(level)
% Generate a new game
%--------------------------------------------------------------------------
% Fill game Matrix with a random solution, only interested in one
% solution
board = zeros(1,81);
board(1:9) = randperm(9);
[board,solution] = deal(dlxsolver(board));
% Remove numbers according to the difficulty level of the game
number = 2*(level*10);
% Now when we randomly remove hints, we want to make sure that
% there is only a single solution, therefore look for two solutions
stillin = 1:81;
while number && ~isempty(stillin)
tmpboard = board;
trypos = stillin(ceil(rand*length(stillin)));
tmpboard(trypos) = 0;
[dummy,nsol] = dlxsolver(tmpboard,2);
if nsol==1
board = tmpboard;
number = number-1;
end
stillin(stillin==trypos) = [];
end
% -------------------------------------------------------------------------
function [solution log] = humansolver(board)
% Solve the game as an human might do it...
% -------------------------------------------------------------------------
global BOXINDICES ROWINDICES COLINDICES INDBOX INDROW INDCOL LOGGER
if ~isSolvable(board)
solution = [];
return;
end
% Assign Global Variables
INDROW = ceil((1:81)/9);
INDCOL = mod((1:81)-1,9)+1;
INDBOX = zeros(1,81);
[BOXINDICES,ROWINDICES,COLINDICES] = deal(zeros(9));
ind = [1,4,7];
for i=1:9
xstart = ind(mod(i-1,3)+1);
ystart = ind(ceil((i)/3));
box = [xstart+(ystart-1)*9:xstart+(ystart-1)*9+2,...
xstart+ystart*9:xstart+ystart*9+2,...
xstart+(ystart+1)*9:xstart+(ystart+1)*9+2];
INDBOX(box) = i;
BOXINDICES(:,i) = box;
ROWINDICES(:,i) = i+(i-1)*8:i+8+(i-1)*8;
COLINDICES(:,i) = INDCOL(i):9:81;
end
LOGGER = {' '};
LOGGER(end+1) = {' Log of solution sequence for ''Human'' solver'};
LOGGER(end+1) = {' -------------------------------------------'};
for i=1:9
LOGGER{end+1} = [' ' strrep(strrep(num2str(board((i-1)*9+1:i*9)),'0','.'),' ','')];
end
state = ones(9,81);
ind = find(board);
for i=1:length(ind)
[board,state] = assignAndExclude(board,state,ind(i),board(ind(i)));
end
solution = solveRecursive(board,state,[]);
log = LOGGER;
% -------------------------------------------------------------------------
function solution = solveRecursive(board,state,solution)
% Solve the board, recursively if necesseary
%--------------------------------------------------------------------------
global LOGGER
oldboard = [];
while ~isequal(board,oldboard)
oldboard = board;
[board,state] = nakedSingles(board,state);
[board,state] = hiddenSingles(board,state);
end
emptyind = find(board==0);
if isempty(emptyind)
solution(end+1,:) = board;
LOGGER{end+1} = ' ';
LOGGER{end+1} = ' Solution Found!';
return;
else
newstate = nakedPairs(board,state);
if ~isequal(newstate,state)
solution = solveRecursive(board,newstate,solution);
return
end
newstate = lockedCandidates(board,state);
if ~isequal(newstate,state)
solution = solveRecursive(board,newstate,solution);
return
end
% We need to take a guess to solve this!
siz = sum(state);
[minval pos] = min(siz(emptyind));
if minval==0
return;
end
bestind = emptyind(pos);
candidates = find(state(:,bestind))';
for candidate = candidates(randperm(length(candidates)))
if isempty(solution)
LOGGER{end+1} = ' ';
LOGGER{end+1} = sprintf(' Need to take a guess, try %d at (%d,%d)',candidate,mod(bestind-1,9)+1,ceil(bestind/9));
[board,staterec] = assignAndExclude(board,state,bestind,candidate);
for i=1:9
LOGGER{end+1} = [' ' strrep(strrep(num2str(board((i-1)*9+1:i*9)),'0','.'),' ','')];
end
solution = solveRecursive(board,staterec,solution);
if isempty(solution)
LOGGER{end+1} = ' ';
LOGGER{end+1} = ' The guess was wrong...';
end
else
return;
end
end
end
% -------------------------------------------------------------------------
function [board,state] = assignAndExclude(board,state,ind,val)
% If a value is known in a certain position, clear all others that
% cannot be in the state matrix
%--------------------------------------------------------------------------
global BOXINDICES ROWINDICES COLINDICES INDBOX INDROW INDCOL
state(val,BOXINDICES(:,INDBOX(ind))) = 0; % the square
state(val,COLINDICES(:,INDCOL(ind))) = 0; % the column
state(val,ROWINDICES(:,INDROW(ind))) = 0; % the row
state(:,ind) = 0; % the element
state(val,ind) = 1; % put it back
board(ind) = val; % new known value
% -------------------------------------------------------------------------
function [board,state] = nakedSingles(board,state)
% Any cells which have only one candidate can safely be assigned that value
% -------------------------------------------------------------------------
global LOGGER
emptyind = find(board==0);
for i=1:length(emptyind)
if sum(state(:,emptyind(i)))==1
val = find(state(:,emptyind(i)));
[board,state] = assignAndExclude(board,state,emptyind(i),val);
LOGGER{end+1} = ' ';
LOGGER{end+1} = sprintf(' Naked Single: %d (%d,%d)',val,ceil(emptyind(i)/9),mod(emptyind(i)-1,9)+1);
for i=1:9
LOGGER{end+1} = [' ' strrep(strrep(num2str(board((i-1)*9+1:i*9)),'0','.'),' ','')];
end
end
end
% -------------------------------------------------------------------------
function [board,state] = hiddenSingles(board,state)
% Very frequently, there is only one candidate for a given row, column or
% box, but it is hidden among other candidates.
% -------------------------------------------------------------------------
global BOXINDICES ROWINDICES COLINDICES
for i=1:9
[board,state] = hiddenSinglesHelper(board,state,BOXINDICES(:,i));
[board,state] = hiddenSinglesHelper(board,state,ROWINDICES(:,i));
[board,state] = hiddenSinglesHelper(board,state,COLINDICES(:,i));
end
function [board,state] = hiddenSinglesHelper(board,state,indices)
global LOGGER
emptyind = find(board(indices)==0);
for k=1:length(emptyind)
val = find(sum(state(:,indices(emptyind)),2)-2*state(:,indices(emptyind(k)))<0);
if ~isempty(val)&&length(val)==1
[board,state] = assignAndExclude(board,state,indices(emptyind(k)),val);
tmp = indices(emptyind(k));
LOGGER{end+1} = ' ';
for i=1:length(tmp)
LOGGER{end+1} = sprintf(' Hidden Single: %d (%d,%d)',val,ceil(tmp/9),mod(tmp-1,9)+1);
end
for i=1:9
LOGGER{end+1} = [' ' strrep(strrep(num2str(board((i-1)*9+1:i*9)),'0','.'),' ','')];
end
end
end
% -------------------------------------------------------------------------
function state = nakedPairs(board,state)
% If two cells in a group contain an identical pair of candidates and only
% those two candidates, then no other cells in that group could be those
% values.
% These 2 candidates can be excluded from other cells in the group.
% -------------------------------------------------------------------------
global BOXINDICES ROWINDICES COLINDICES
for i=1:9
state = nakedPairsHelper(board,state,BOXINDICES(:,i));
state = nakedPairsHelper(board,state,ROWINDICES(:,i));
state = nakedPairsHelper(board,state,COLINDICES(:,i));
end
function state = nakedPairsHelper(board,state,indices)
global LOGGER
emptyind = find(board(indices)==0);
if emptyind>2
statesum = sum(state(:,indices(emptyind)),1);
if histc(statesum,2)>1
val = find(statesum==2);
for i=1:length(val)-1
for j=i+1:length(val)
if isequal(state(:,indices(emptyind(val(i)))),state(:,indices(emptyind(val(j)))))
pair = find(state(:,indices(emptyind(val(i)))));
emptyindtmp = emptyind;
emptyindtmp([val(i),val(j)]) = [];
if find(state(pair,indices(emptyindtmp)))
state(pair,indices(emptyindtmp)) = 0;
tmpind = indices(emptyindtmp);
LOGGER{end+1} = ' ';
for ii=1:length(tmpind)
LOGGER{end+1} = sprintf(' Naked Pair: %d %d can''t be at (%d,%d)',pair(1),pair(2),ceil(tmpind(ii)/9),mod(tmpind(ii)-1,9)+1);
end
end
end
end
end
end
end
% -------------------------------------------------------------------------
function state = lockedCandidates(board,state)
% Locked Candidates 1
% Sometimes a candidate within a box is restricted to one row or column.
% Since one of these cells must contain that specific candidate, the
% candidate can safely be excluded from the remaining cells in that row or
% column outside of the box.
%
% Locked Candidates 2
% Sometimes a candidate within a row or column is restricted to one box.
% Since one of these cells must contain that specific candidate, the
% candidate can safely be excluded from the remaining cells in the box.
% -------------------------------------------------------------------------
global BOXINDICES ROWINDICES COLINDICES INDBOX INDROW INDCOL LOGGER
empty = find(board==0);
% Locked Candidates 1
steprow = [1,1,-1;2,-1,-2];
stepcol = [3,-3,-3;6,3,-6];
for i=1:9
indices = BOXINDICES(:,i);
emptyind = find(board(indices)==0);
found = board(indices(board(indices)~=0));
unfound = setdiff(1:9,found);
for j=unfound
places = find(state(j,indices(emptyind)));
if length(unique(INDROW(indices(emptyind(places)))))==1
RI = ROWINDICES(:,INDROW(indices(emptyind(places(1)))));
BI1 = BOXINDICES(:,i+steprow(1,mod(i-1,3)+1));
BI2 = BOXINDICES(:,i+steprow(2,mod(i-1,3)+1));
BI = [BI1(:);BI2(:)];
IRIBI = intersect(empty,intersect(RI,BI(:)));
IRBIPOS = find(state(j,IRIBI)==1);
if ~isempty(IRBIPOS)
state(j,IRIBI(IRBIPOS)) = 0;
tmpind = IRIBI(IRBIPOS);
LOGGER{end+1} = ' ';
for ii=1:length(tmpind)
LOGGER{end+1} = sprintf(' Locked Candidate 1 (row): %d can''t be at (%d,%d)',j,ceil(tmpind(ii)/9),mod(tmpind(ii)-1,9)+1);
end
end
elseif length(unique(INDCOL(indices(emptyind(places)))))==1
CI = COLINDICES(:,INDCOL(indices(emptyind(places(1)))));
BI1 = BOXINDICES(:,i+stepcol(1,ceil((i)/3)));
BI2 = BOXINDICES(:,i+stepcol(2,ceil((i)/3)));
BI = [BI1(:);BI2(:)];
ICIBI = intersect(empty,intersect(CI,BI(:)));
ICIBIPOS = find(state(j,ICIBI)==1);
if ~isempty(ICIBIPOS)
state(j,ICIBI(ICIBIPOS)) = 0;
tmpind = ICIBI(ICIBIPOS);
LOGGER{end+1} = ' ';
for ii=1:length(tmpind)
LOGGER{end+1} = sprintf(' Locked Candidate 1 (column): %d can''t be at (%d,%d)',j,ceil(tmpind(ii)/9),mod(tmpind(ii)-1,9)+1);
end
end
end
end
end
% Locked Candidates 2
for i=1:9
indices = COLINDICES(:,i);
emptyind = find(board(indices)==0);
found = board(indices(board(indices)~=0));
unfound = setdiff(1:9,found);
for j=unfound
places = find(state(j,indices(emptyind)));
if length(unique(INDBOX(indices(emptyind(places)))))==1
BI = BOXINDICES(:,INDBOX(indices(emptyind(places(1)))));
DBICI = intersect(empty,setdiff(BI(:),indices));
DBICIPOS = find(state(j,DBICI)==1);
if ~isempty(DBICIPOS)
state(j,DBICI(DBICIPOS)) = 0;
tmpind = DBICI(DBICIPOS);
LOGGER{end+1} = ' ';
for ii=1:length(tmpind)
LOGGER{end+1} = sprintf(' Locked Candidate 2 (column): %d can''t be at (%d,%d)',j,ceil(tmpind(ii)/9),mod(tmpind(ii)-1,9)+1);
end
end
end
end
indices = ROWINDICES(:,i);
emptyind = find(board(indices)==0);
found = board(indices(board(indices)~=0));
unfound = setdiff(1:9,found);
for j=unfound
places = find(state(j,indices(emptyind)));
if length(unique(INDBOX(indices(emptyind(places)))))==1
BI = BOXINDICES(:,INDBOX(indices(emptyind(places(1)))));
DBIRI = intersect(empty,setdiff(BI(:),indices));
DBIRIPOS = find(state(j,DBIRI)==1);
if ~isempty(DBIRIPOS)
state(j,DBIRI(DBIRIPOS)) = 0;
tmpind = DBIRI(DBIRIPOS);
LOGGER{end+1} = ' ';
for ii=1:length(tmpind)
LOGGER{end+1} = sprintf(' Locked Candidate 2 (row): %d can''t be at (%d,%d)',j,ceil(tmpind(ii)/9),mod(tmpind(ii)-1,9)+1);
end
end
end
end
end
% -------------------------------------------------------------------------
function varargout = dlxsolver(board,nsol)
% we have a binary n*m matrix whose rows are indexed with r and columns with c.
% At step i a row and column is chosen from that matrix and an entry
% into the sudoku-matrix A()() is computed from them.
%
% A(1..9)(1..9) contains the sudoku-grid. A(x)(y)=0 iff the cell (x,y) is empty
% Rows(c) is the number of rows matching column c in the binary exactcover-matrix
% Row(c)(i) , i=1..Rows(c) is the index of the i-th row which matches column c
% Cols(r) is the number of columns matching row r in the binary exactcover-matrix
% Col(r)(i) , i=1..Cols(c) is the index of the i-th column which matches row r
% Ur(r) is zero, iff row r has not yet been marked forbidden
% Uc(c) is zero, iff column c has not yet been marked forbidden
% Ci(i) is the column chosen at step i
% Ri(i) is the row chosen at step i
%
% Based on c-code by Guenter Stertenbrink
% http://magictour.free.fr/suexco.txt
% -------------------------------------------------------------------------
if nargin<2
nsol=1;
end
N=3;N2=N^2;N4=N2^2;m=4*N4;n=N2*N4;
Rows = zeros(m,1);
Row = zeros(m,N2);
Cols = zeros(n,1);
Col = zeros(n,4);
Ur = zeros(n,1);
Uc = zeros(m,1);
Ci = zeros(N4,1);
Ri = zeros(N4,1);
clues = sum(board~=0);
if clues==N4
if nargout
varargout{1}=board;
end
if nargout>1
varargout{2}=1;
end
if nargout>2
varargout{3}=0;
end
return
end
% generate the basic binary exact-cover-matrix,
% that is, not the matrix itself but the rows and columns
r=0;
for x=1:N2
for y=1:N2
for s=1:N2
r=r+1;
Cols(r)=4;
Col(r,1)=x*N2-N2+y;
Col(r,4)=(N*(floor((x-1)/N))+floor((y-1)/N))*N2+s+N4;
Col(r,3)=x*N2-N2+s+N4*2;
Col(r,2)=y*N2-N2+s+N4*3;
end
end
end
for r=1:n
for c=1:Cols(r)
x=Col(r,c);
Rows(x)=Rows(x)+1;
Row(x,Rows(x))=r;
end
end
% do the initial markings required by the given clues
for i=1:N4
if board(i)
r=(mod(i-1,9)+1)*N4-N4+(ceil(i/9))*N2-N2+board(i);
for j=1:Cols(r)
c1=Col(r,j);
Uc(c1)=Uc(c1)+1;
for k=1:Rows(c1)
r1=Row(c1,k);
Ur(r1)=Ur(r1)+1;
end
end
end
end
V = zeros(n,1);
for c=1:m
V(c)=0;
for r=1:Rows(c)
if Ur(Row(c,r))==0
V(c)=V(c)+1;
end
end
end
%/* walk through the searchtree now */
% backtrack through all subsets of the rows
i=clues;
m0=0;m1=0;
guesses=0;
solutions=0;
state=2;
while(1)
switch state
case 2
% next level. Compute the next entry
i=i+1;
Ri(i)=0;
% find the column c=Ci(i) with fewest matching rows,
% if empty column is found, then backtrack
mini=n+1;
if i>N4||m0
state=4;continue;
end
if m1
Ci(i)=m1;
state=3;continue;
end
for c=1:m
if Uc(c)==0
if V(c)<mini
mini=V(c);
Ci(i)=c;
if mini<2
guesses=guesses-1;break
end
end
end
end
guesses=guesses+1;
state=3;
case 3
% walk through all unmarked rows r matching column c=Ci(i)
while(1)
c=Ci(i);
Ri(i)=Ri(i)+1;
if Ri(i)>Rows(c)
state=4;break
end
r=Row(c,Ri(i));
if ~Ur(r)
break
end
end
if state==4
continue
end
m0=0;m1=0;
if ~solutions
x=floor((r-1)/N4)+1;
y=floor(mod(r-1,N4)/N2)+1;
s=floor(mod(r-1,N2))+1;
board(x+9*(y-1))=s;
end
% delete all columns which match row r and all rows which match
% any of these columns
for j=1:Cols(r)
c1=Col(r,j);
Uc(c1)=Uc(c1)+1;
end
for j=1:Cols(r)
c1=Col(r,j);
for k=1:Rows(c1)
r1=Row(c1,k);
Ur(r1)=Ur(r1)+1;
if Ur(r1)==1
for l=1:Cols(r1)
c2=Col(r1,l);
V(c2)=V(c2)-1;
if Uc(c2)+V(c2)<1
m0=c2;
end
if Uc(c2)==0 && V(c2)<2
m1=c2;
end
end
end
end
end
% entry was made, matrix was updated, goto the next level
if i==N4
solutions=solutions+1;
if solutions==nsol
i=clues+1;
state=4;continue
end
end
state=2;
case 4
% Backtrack. Goto previous level, take back the last move
% restore the data as they were before that move and make the
% next available move at that level
i=i-1;
if i~=clues
c=Ci(i);
r=Row(c,Ri(i));
for j=1:Cols(r)
c1=Col(r,j);
Uc(c1)=Uc(c1)-1;
for k=1:Rows(c1)
r1=Row(c1,k);
Ur(r1)=Ur(r1)-1;
if Ur(r1)==0
for l=1:Cols(r1)
c2=Col(r1,l);
V(c2)=V(c2)+1;
end
end
end
end
if~solutions
x=floor((r-1)/N4)+1;
y=floor(mod(r-1,N4)/N2)+1;
board(x+9*(y-1))=0;
end
if i>clues
state=3;continue
end
else
if nargout
varargout{1}=board;
end
if nargout>1
varargout{2}=solutions;
end
if nargout>2
varargout{3}=guesses;
end
return
end
end
end
% -------------------------------------------------------------------------
function out = getFromDatabase(choice)
% Returns random board from database or the full database
%--------------------------------------------------------------------------
Database = { ...
'016400000200009000400000062070230100100000003003087040960000005000800007000006820'
'049008605003007000000000030000400800060815020001009000010000000000600400804500390'
'760500000000060008000000403200400800080000030005001007809000000600010000000003041'
'000605000003020800045090270500000001062000540400000007098060450006040700000203000'
'409000705000010000006207800200000009003704200800000004002801500000060000905000406'
'000010030040070501002008006680000003000302000300000045200500800801040020090020000'
'080070030260050018000000400000602000390010086000709000004000800810040052050090070'
'000093006000800900020006100000080053006000200370050000002500040001009000700130000'
'096500780007001000000000100604009070010802060080400203008000000000900300041008920'
'000000000140070000005106900021005080400000007080700620009304500000020018000000000'
'000600000047100000890040013001004020200090008030800500450070036000006840000005000'
'003070900000901000200308007072000510400000002015000840900104005000503000006020300'
'907002800300004057100070000009003000000020000000600200000010008570300004002700905'
'600000450080002000009070100000003940000040000012800000001080700000200030097000006'
'600000008000000100001307000004900280003102900092005300000203400005000000100000006'
'100000008050000070702000406900801007060000090010020050003080600080000040070503080'
'004705900000801000600040005430000082008000400920000063200030001000502000007608200'
'080306040100020008000050000300000006067080950800000002000070000600010003070904080'
'000000600004500097002800010070003001000050000200900080020006300130004700009000000'
'000000009000020003046900050310200090000105000080009017030008420900030000100000000'
'006300200708000000100050080400005030070010020090400008050040009000000506004006300'
'290700000004020010003004000050070060900203007020090030000500400010080600000006071'
'000000000500010004030605210090020081007000400260030050026803070900050008000000000'
'000000060005007009079080310130600000000000000000004078083050790900400600020000000'
'000509000007000305000008170001900006020030010600004500084200000509000400000703000'
'309000000000030050041600000400700003080020040100004009000008120030050000000000906'
'000604002000039050008000400900003041003000500670100009002000100080490000700306000'
'000000007040800095005031000400003020006010800030200009000420700190006040600000000'
'500904008001000070000007090007000400906805702003000600080100000060000900700406005'
'003600507000930000080007000058000000106000908000000340000400090000058000507009200'
'005000600004306900800209005040010080000000000002605700000000000006507300010000040'
'060000010790010032008000400000849000040607050000153000009000700670030091050000060'
'008009061010500009700030400090300008005000200800005030004020006300004070920800100'
'800000209000100007005002000060050004004080700300090020000900600200005000607000003'
'090008370000000000300605012000010006031060820200040000940201008000000000017400060'
'100260009070000050000008200003070004900846003800030600004600300080000040700081002'
'007006000004000006060109080006270000080000030000038900010802090500000800000300100'
'002000900090070030004000700028107650000050000007304100060000080001438200000000000'
'060000800000040500500200047008009060070105090030800100840006003002070000003000010'
'008000100070040030600507004007080600040602050006050300700205003020070080009000200'
'000009360010020000004000002003102006050070040100406900900000500000060030028700000'
'003004000602300000050600807508000009000070000700000201407008020000005904000700600'
'050901060700050003006000900800020004070403020400060005001000700600010008030504010'
'000300007806012000004005200000030050508000406040070000003800600000940301100003000'
'200070004006000800090308050003109600800000005001507300040803090002000400600040007'
'005000700020503080800090005030050070008704100070030040100040009040902010009000600'
'600801003080402010000090000890000052004000900510000037000010000030904020700603008'
'500003007001070000000805160208000500010090040005000709026709300000010900800200001'
'006908200030050080800000004400501003050000040200804007300000005060080010005107600'
'080063001400500030000004800060000902500000006207000080004600000090005003300720010'
'000002900050900800008001037060130208000804000803056090610400300004008070007600000'
'003000200014000390080000040030807050009040700007206800300000004000529000090070010'
'300104008008090100040000070200708004060000010700903005020000090001080400400309001'
'100703009002010600000406000380000064650000023720000058000508000008070200900602001'
'008102050020050800003000000070380500000209000009015060000000200005090010040508700'
'200010009000904000007805600045000920300000008079000140008109300000503000900040006'
'300000004020805090007090600060050010008704300070080020001020500080109040700000001'
'570904023800000004003000100300060005000401000100070002002000900700000001680502047'
'802000000300600500000050070080590040009000600060071090070020000001008007000000803'
'006020079000000001005630000003470000020009705000005400900008104600090000087000000'
'070000060040507090009108300000802000010000020002903500200030004400206009005000600'
'010050080500603007006000500070060090600204001020030040002000400700106003080020060'
'060040050100000008008703600002107900800000002009502100001304200900000003030070090'
'080003900060400015300010600700000050002070800040000009001020503450006090006100070'
'010502080408000501090000030600050003000907000500010009050000040104000208030408070'
'130607092700201003000030000320000061005000300910000057000010000500403008270508036'
'800204007009030800070000090700106002060000070900402006090000050004060700300809004'
'800203005040050010003000800200506001060000030900708006006000100090020040100304007'
'090000020003908700500702009370040061006000900140070083900605008005107600010000050'
'730080016800609003000000000050407090200000004010502070000000000500104002370020045'
'000600000810400900040010030001300500030060020002007600070030090005009068000005000'
'032000590000000000007569300008706400004803700020000080080194060060070010000000000'
'020901040900702003000050000240000089009000400380000067000080000400207006050103070'
'000000000034105720016000450040080010009070200070000060700802006068090540000000000'
'059060340000000000100703006608000902700080001030000080000000000400207003007809100'
'406905803100030006093000750050000080800000002000894000620000037000000000001709600'
'009806300000040000400507009903000602010000080508000901700104006000060000001908200'
'700104008009000600030020010800701005002000100300402009020040090007000300100203006'
'006700084040005600000090000000030005930000021100050000000070000002400010780009300'
'008000090000095600010070300003000009046020710700000400002080030005940000060000200'
'091050800500704006000100000020000900100060003006000050000007000600803004009040270'
'007000500020000090034105670006408100000050000005703200063209410010000020002000300'
'060040030300000008001307500005080700700651002006070300003709100200000003050030090'
'120000006000090070000045100900506000006010500000207001007450000080020000400000089'
'200040608005060000000009010080700900300000002009004080070300000000050700803020005'
'400020003050801070007090500060000010501000307030000090005040100090608050200010006'
'200805009004000800060010020400203008005000100700901003090020060003000700600504001'
'040900100000008060690000002009003004050020070200100600700000089020800000004002050'
'042001000800000009000630000009007100650000082001200400000064000200000003000100560'
'080401090900050001001296400705000906069000320802000107007945800400010009090602010'
'005003020700050300010004805201000000070030010000000709809200640002060008060800100'
'010607050700000001004000800300010007000502000900070004006000100200000009070405060'
'600500002019080000070000040040100870000070000057003020020000050000090180800006004'
'020008000907030100050200930005300004070060010200009500042003070008050301000800020'
'560030900200090501000700000005008006070000080400900700000003000902040003006010054'
'003708600000020000200509007107000508020000090904000206600802001000040000008601700'
'780000021900501003003000400030904010000000000090807060001000900800209005560000042'
'300005006400270000008009000590300000700060009000004017000800600000012008800700004'
'600050001090301040007000200030104050100000002080705010001000600070906020500030008'
'830000000000400010100053200060200400007080100008009060006810004090005000000000021'
'000000700090500080007009600010090024020070060580060010004200900060008050005000000'
'000000602000003040000480390014800000500030001000002730087041000090300000601000000'
'300000009206030704070904080000040000000308000060109020050000090608000502012000670'
'100207006000906000004010200810000073005020400430000025001070800000802000500103004'
'500208006003010200010000080600904001020000040400701002080000030001050900900603007'
'005040790000007006800010002000800010901000203020001000400050007200300000069070500'
'012000004700600900905003080050430100000805000008016050090300805001007003500000640'
'600003507000020080003900006009700001010000030200006400100004200090080000302500008'
'070000030081903500006070000000100003800020009400006000000060400004508160020000080'
'060010502020008000400500008094002006000000000800300970600001007000600040509040080'
'020507030900203008000010000860401023007000800530809046000090000400605009090102050'
'000700000690040000042005000100200500020000090004009006008900100460050720070002030'
'040301080200000003005020100700106005004000200600402009009010700500000008030908020'
'061000200050901006000000080005060000040208060000030700020000000900604030008000470'
'004803200000705000300020008480000061007000500690000032200090007000407000008602300'
'310000057450687031000030000700204006003000500200803009000020000620548073580000062'
'000073000000245000072100300360000900005000800004000053009006120000421000000350000'
'001080500000109000400205001037000650500000002049000170900507006000402000005060900'
'300800710001027004080000002800004090030010070070900003200000040500460300047002005'
'008020000017503000450001600030005140800000009041700060004600035000304290000090400'
'036708000150400000807050000360000002008000100400000079000070905000005048000609310'
'200103009009000800070080040100020006007604200600090001060030050004000600900207004'
'500904001090307060001050900200000006900786005060102070100000002029000640000000000'
'830701056690050027000000000200080004010405030400010009000000000520070068380206095'
'000000008020106000001080530700000400040307090005000001053010600000609070900000000'
'000300000000060210016904080001000350020000060038000900050801420087030000000006000'
'090000010200608007007000500010070040000905000050020030001000300600209004040000050'
'800030005000204000007809100091000650500000003032000890004907500000502000900060007'
'300040009009000100050906030005704900400000002003501700040803020006000300500060008'
'600903004009600100030000000200490060004050300070032005000000010007009600300805002'
'807001500030980000400300002058100006060000050900003280500006001000059040002800605'
'090080020000947000000203000027406980100000005006105700005000800410000039800000004'
'000005000009610040300070002000400310004000500085007000800020009070098400000100000'
'000000000007020800863000152600809004030000010004000200090308020040507090006000400'
'006040002040001000800006000000105970002000500073804000000300004000500010900070200'
'001090700300507004050462030000308000043000510000601000010935020200106005008070300'
'005006300000410900700000065030092001060103080800640030270000003009038000003900400'
'000720100100805003000000040400010006070000020500090004050000000600104007004063000'
'000105000400000001302000508040000070600010004900000002000050000050708060007634800'
'005200800070030090900400002000000609050010040809000000200003004010040060008001900'
'005080000070309000900000304480600000000050000000007031604000002000802070000030500'
'008000100100267003020080070060509010009000300030402060080040050500826001003000800'
'230000060600009708000605010003700690000000000097004800020106000804200006010000029'
'920035100050000000008690000804500020000000000010004908000029700000000060005460092'
'003000000090040020005701006004010600010408090008020700800209000050080010000000400'
'005302004000000500020600008100005000030981060000200009400006010008000000300508400'
'600807001010326070000104000146000859030000010759000243000409000060513020300208005'
'001050200050107080200309005013000920900000004024000650100804002070205010002060500'
'070080000100420900008301070017000500850000031009000280090604800003018005000030060'
'270040081500800007000000300000308090700050002060204000006000900300005004940030015'
'040310002203006000060809000802000540600000007059000206000608020000100605100092030'
'000000370009750001080103000040300100000080000007006050000208090800014700092000000'
'530004600100070900002000074000030001060807040700060000250000100009010006004700052'
'003060700000800020500207004071040600800609007002080490100508006020006000008070900'
'010070600000000090030006500006150040300080002070093100002900080060000000008020010'
'020000080600080003000704000007106400010090070004203900000305000800060001060000090'
'000007090940000002002800076000070600500010008004060000710005800300000054050900000'
'000709000750000039009302500405090302000000000201060904003801700620000013000607000'
'500084000010500004060000800900030000080706090000020001002000060700009080000240003'
'009080005517000000000061700190030500003008604000000000060070049402003060070006050'};
switch choice
case 'Database'
out = Database;
case 'RandomBoard'
out = str2num(regexprep(Database{ceil(rand*length(Database))},'([0-9])','$1 '));
end
