% A script to play Sudoku, a popular numbers game
%
% From websuoku.com:
%   "The rules of Sudoku are simple. Enter digits from 1 to 9 
%   into the blank spaces. Every row must contain one of each 
%   digit. So must every column, as must every 3x3 square."
%
% Implementation notes:
%  - Empty (undecided) cells are 0
%  - I'm calling the 3x3 squares "regions"
%
%
% The elimination strategies:
%  Strategy 1: 
%      If, within a region, the only possiblities are on the
%      same row or column, then we can eliminate this choice
%      from the other regions.
%
% Author: Greg Coombe
% Date: Nov 29, 2005
%
clear;

% Initialize the playing board
global B;

% load in the board from file
B = load('board.txt')

if ( size(B,1) ~= 9 | size(B,2) ~= 9 )
    error('Error loading 9x9 sudoku board file.');
end

filled_in = sum(sum( B ~= 0 ));
disp( ['There are ' num2str(filled_in) ' cells initially filled-in.'] );
 
% The data structure that we use to keep track of the valid values
% for this cell. For every cell on the board, there is a vector of
% 9 values (representing numerals 1-9). It is 1 if valid to write this
% number in this cell, 0 if it is not valid, and -1 if unassigned
global Valid;
Valid = ones(9,9,9);

% wipe out valid points where the inputs are
for i=1:9
    for j=1:9
        if ( B(i,j) ~= 0 )
            Valid(i,j,:) = zeros(1,9);
        end
    end
end


% A lookup table: This table tells us the locations of all of our 
% neighbors in our region, given our cell location. 
global RegionTable;
RegionTable = [1:3; 1:3; 1:3;
               4:6; 4:6; 4:6;
               7:9; 7:9; 7:9;];

% Start the main loop
old_filled_in = 0;
iter = 0;
halt_count = 0;
tic;
while( filled_in < 9*9 && halt_count < 10 && iter < 150 );
    % Strategy 1. Block out choices on rows or columns
    computeValid; 
    %strategy1;

    % Now check the board to see how many we can fill in
    computeValid; 
    fillBoard;
    
    % Now compute how many elements we have filled in 
    filled_in = sum(sum( B ~= 0 ));
    if ( old_filled_in == filled_in )
        halt_count = halt_count + 1;
    else
        halt_count = 0;
    end
    old_filled_in = filled_in;
    %disp( ['There are now ' num2str(filled_in) ' cells filled-in.'] );
    
     % Display some debugging information
    %valid_count = squeeze(sum(shiftdim(Valid,2)));
    %valid_count( B ~= 0 ) = 0;
    %valid_count

    iter = iter +1;
end

% Finally, display the resulting board
B

% How many choices are there per cell?
%sum(Valid,3)

% Failure!
if ( filled_in < 9*9 )
    disp(['Unable to find solution using direct methods after ' num2str(iter) ' iterations.']);
else
    disp(['Solution required ' num2str(iter) ' iterations.']);
end

toc;