www.gusucode.com > rmidemos工具箱matlab源码程序 > rmidemos/sudoku_solver.m
function solution = sudoku_solver(problem) % SUDOKU_SOLVER - brute force solver example % % Usage: % sudoku_solver() % solves the default problem % sudoku_solver(NUMERIC_9x9_ARRAY) % use zeros for EMPTY cells % sudoku_solver(FILENAME) % FILENAME is an ASCII file with valid data % % See also: % Solving Sudoku using Simulink_Design_Verifier % http://www.mathworks.com/company/newsletters/articles/a-model-checking-example-solving-sudoku-using-simulink-design-verifier.html % Sudoku Solver at MATLAB Central % http://www.mathworks.com/matlabcentral/fileexchange/8083-matlab-sudoku-solver % Copyright 2013 The MathWorks, Inc. %% This code is a part of "RMI Linking in MATLAB" exercise. % Use with sudoku_requirements.docx %% Define problem to solve if nargin == 0 current = sudoku_default(); elseif ischar(problem) current = loadFromFile(problem); else current = problem; end if ~isValidPuzzle(current) disp(current) error('Not a valid array for Sudoku'); end %% Iterate until solved allUpdates = []; allFailures = []; while ~isDone(current) [current, update] = putDigit(current, allFailures); if update < 0 % We failed to find the next move for "current" puzzle. % This means the previous move was wrong, need to undo: if isempty(allUpdates) % Nothing to undo, which means we had to backtrack % everything and still could not put a digit. disp(getString(message('Slvnv:publish_all_vnv_demos:NoSolution'))); solution = []; return; else lastUpdate = allUpdates(end); end allFailures = [allFailures lastUpdate]; %#ok<AGROW> % Have to clear all "later" items allFailures(allFailures > lastUpdate) = []; % Provide feedback and undo: [row, col] = decodeMove(lastUpdate); current(row,col) = 0; allUpdates(end) = []; else allUpdates = [allUpdates update]; %#ok<AGROW> showCurrent(current); end end %% Return result solution = current; end %% Call this to print the current state of the puzzle after each move function showCurrent(current) str = ''; for i = 1:9 str = sprintf('%s\n\t', str); for j = 1:9 if current(i,j) > 0 str = sprintf('%s%d ', str, current(i,j)); else str = sprintf('%s ', str); end if mod(j,3) == 0 str = sprintf('%s ', str); end end if mod(i,3) == 0 str = sprintf('%s\n', str); end end fprintf(1, '%s\n', str); end %% Problem is solved if there are no more zeros in CURRENT table function result = isDone(current) result = ~any(any(current==0)); end %% Call this repeatedly untill solved function [current, update] = putDigit(current, failures) % locate an empty cell and fill with any digit that ... % is not yet present in same sub-square, and % is not yet present in same row, and % is not yet present in same column [row, col] = findEmpty(current); % will try to fill this cell allDigitsIn3x3 = getAllDigitsIn3x3(current, row, col); for digit = 1:9 if any(current(row,:)==digit) continue; end if any(current(:,col)==digit) continue; end if any(allDigitsIn3x3==digit) continue; end % This seems to be a suitable digit ... update = encodeMove(row, col, digit); if any(failures == update) % ... unless we tried this already continue; end % Accept this digit current(row, col) = digit; % our next move return; end % If we reached here, no suitable digit placement was found update = -1; end %% Utilities to store each move as a 3-digit number function encoded = encodeMove(row, col, digit) encoded = row * 100 + col * 10 + digit; end function [row, col, digit] = decodeMove(encoded) row = floor(encoded/100); col = floor((encoded-row*100)/10); digit = mod(encoded,10); end %% Scan 9x9 array to locate the nearest empty cell function [row, col] = findEmpty(current) for row = 1:9 myDigits = current(row,:); myZeros = find(myDigits == 0); if ~isempty(myZeros) col = myZeros(1); return; end end error('Failed to find zero in unfinished problem'); end %% For a given [ROW, COL] pair, return all known digits in a 3x3 sub-square function digits = getAllDigitsIn3x3(current, row, col) [firstR, lastR] = firstLast(row); [firstC, lastC] = firstLast(col); digits = []; for i = firstR:lastR for j = firstC:lastC digit = current(i,j); if digit > 0 digits = [digits digit]; %#ok<AGROW> end end end function [first, last] = firstLast(index) grp = floor((index-1)/3)+1; first = grp*3-2; last = grp*3; end end %% Allow to load from file function problem = loadFromFile(filename) if exist(filename, 'file') == 2 try problem = load(filename, '-ascii'); catch ex error('Failed to load data from "%s": %s', filename, ex.message); end else error('File "%s" not found.', filename); end end %% Check supplied Problem for validity function result = isValidPuzzle(data) result = false; if ~all(size(data) == [9 9]) fprintf(1, 'Invalid matrix size, should be 9x9\n'); else % Check each row for i = 1:9 if ~isValidSet(data(i,:)) fprintf(1, 'Row %d is invalid\n', i); return; end end % Check each column: for i = 1:9 if ~isValidSet(data(:,i)) fprintf(1, 'Column %d is invalid\n', i); return; end end % Check each sub-square: for i = [3 6 9] for j = [3 6 9] if ~isValidSet(getAllDigitsIn3x3(data, i, j)) fprintf(1, 'Sub-square at %d:%d is invalid\n', i,j); return; end end end result = true; end function myResult = isValidSet(array) nonEmpty = array(array > 0); uniqueDigits = unique(nonEmpty); if length(uniqueDigits) < length(nonEmpty) myResult = false; else myResult = true; end end end