sudoku_yue(I)

function output = sudoku_yue(I)
% Function: sudoku_yue
%           used for solving 9x9 sudoku puzzle
%
% Input: I = 9x9 sudoku puzzle
%        for example: 
%          I = [0 0 0 3 0 1 7 0 0 ; 
%               1 0 0 0 4 0 0 2 0 ;
%               0 6 0 0 0 0 0 5 0 ;
%               9 0 0 4 0 5 0 0 0 ;
%               0 0 6 0 0 0 1 0 0 ;
%               0 0 0 2 0 6 0 8 9 ;
%               0 7 0 0 0 0 4 9 0 ;
%               0 8 0 0 5 0 0 0 2 ;
%               0 0 9 0 0 7 0 0 0 ;]
% Output: output = 9x9 solution 
%         for example:   
%           output = [2,9,5,3,6,1,7,4,8;
%                     1,3,7,5,4,8,9,2,6;
%                     8,6,4,7,9,2,3,5,1;
%                     9,1,8,4,3,5,2,6,7;
%                     5,2,6,8,7,9,1,3,4;
%                     7,4,3,2,1,6,5,8,9;
%                     6,7,2,1,8,3,4,9,5;
%                     3,8,1,9,5,4,6,7,2;
%                     4,5,9,6,2,7,8,1,3;]
% Usage: output = sudoku_yue(I);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% All copyrights reserved
% By Yue Wu
% 10/05/2009
% ECE Dept, Tufts Univ.
% MA, Medford 02155
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% 1. initially solve the puzzle via initial logical exclusion
simple = solve_sudoku_init(I);

%% 2. further guessing
test = simple ==0;
if sum(test(:))~=0 % if all grids have been filled in, then we've done
    % otherwise we do following processing
    % 1) get numbers along each row, col and boc
    bocmap = [1 1 1 2 2 2 3 3 3];
    for i = 1:9
        ori_row{i} = setdiff(unique(simple(i,:)),0);
        ori_col{i} = setdiff(unique(simple(:,i)),0);
    end

    list = [1 4 7];
    for x = 1:3
        for y = 1:3
            i = list(x);
            j = list(y);
            ori_boc{x,y} = setdiff(unique(simple(i:i+2,j:j+2)),0);
        end
    end

    % 2) find all possible number for each grid in sudoku
    candi = sudoku_grid_candidates(simple);
    
    % 3) get a desired list of unfilled grid indices
    tmp_veri = zeros(9); % tmp_veri used to store the grid that have been already filled in
    % stat.row calculates how many grid along one grid's row have been filled
    % stat.col calculates how many grid along one grid's col have been
    % stat.boc calculates how many grid along one grid's row have been filled
    % stat_sum calculates the sum of above three 
    stat_sum = zeros(9);
    for i = 1:9
        for j = 1:9
            if ~isempty(candi{i,j})
                if numel(candi{i,j})>1
                    stat(i,j).row = numel(ori_row{i});
                    stat(i,j).col = numel(ori_col{j});
                    z = sub2ind([3,3],bocmap(i),bocmap(j));
                    stat(i,j).boc = numel(ori_boc{z});
                    stat_sum(i,j) = stat(i,j).row+stat(i,j).col+stat(i,j).boc;
                else
                    tmp_veri(i,j) = candi{i,j};
                end
            end
        end
    end
    
    % based on the number of pieces of information for each grid
    % we generate a desired list of unfilled grids' indices
    [list,nums] = scan_sq(stat_sum,candi);
    
    % 4) recursive algorithm
    veri = cell(size(list)); % initialize guessing matrix veri for each step
    veri{1} = tmp_veri; % assign initial solution to veri{1}
    done = 0; 
    ind = 1; % index for step #, i.e. veri{ind}
    element_ind = 1; % index for numbers in one grid
    try_num = zeros(size(list)); % initialize try_num to zero
    % try_num is used to control whether we've tried all possible number in
    % a grid

    while ~done
        cell_ind = list(ind);% current grid index
        c_cell = candi{cell_ind};% possible numbers
        c_element = c_cell(element_ind); % get one elment
        veri{ind}(cell_ind) = c_element;% try to fill in this element
        try_num(ind) = try_num(ind)+1; %try_num + 1 
        T = sudoku_comflick(veri{ind},cell_ind);%T is to stand for whether the matrix has any conflict
        if T == 0 % if no conflict
            if ind == numel(list) % whether we've done all steps, if yes
                done = 1; % we've done
            else % otherwise
                ind = ind+1; % point to next grid
                element_ind = 1; % assign index for numbers in the next grid to 1
                veri{ind} = veri{ind-1}; % initially assign next step veri 
            end
        else % if comflict happens
            %does the algorithm try all possible numbers in the cell?
            if try_num(ind) == nums(ind)% yes we tried all
                % then we should go back and find the last grid in previous
                % steps that have not been fully tried
                clear tmp_try tmp_nums test
                tmp_try = try_num(1:ind-1); % get the try_number of previous grids
                tmp_nums = nums(1:ind-1); % get the the number of each previous grid
                test = tmp_try ~= tmp_nums; 
                tmp_ind = find(test == 1); % find where are the grids we didn't tried its all numbers
                ind = tmp_ind(end); % find the index of last grid satifies this condition
                try_num(ind+1:end) = 0; % reassign try_num of grids after the above grid to zero 
                veri{ind}(list(ind:end)) = 0; % revise previous assigned grids to zero
                element_ind = try_num(ind)+1; % move element_ind to the next possible number in the grid
            else % no, still some number could be tried
                element_ind = element_ind+1;
            end
        end
    end
    %% 3. Output
    output = veri{end};
else
    output = simple;
end