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