Contents

% SUDOKU_GENERATE   Will generate random sudoku table.
%   [ A, rating, solution ] = SUDOKU_GENERATE( d, desiredRating )
%   [ A, rating, solution ] = SUDOKU_GENERATE( d, desiredRating, verbose )
%
% Syntax:  [ A, rating, solution ] = SUDOKU_GENERATE( d, desiredRating, verbose )
%
% Inputs:
%    d - Size of block edge in the sudoku table. Must be larger than 2 and
%    integer number.
%    desiredRating - Rating which will generator try to approach. Must be
%    non-negative integer number. Resulting rating can be relatively far
%    from desired rating, it is up to user to run the generator again if
%    not satisfied with it, as generation process it time demanding.
%    verbose - Boolean flag turning on progress console reporting. If true,
%    all steps of the generation will be reported. By default set to false.
%
% Outputs:
%    A - Generated sudoku table of dimensions (d*d)x(d*d) that has exactly
%    one solution with minimum number of clues for that solution.
%    rating - Rating of generated table.
%    solution - Filled table corresponding to A.
%
% Example 1:
%    [ A ] = sudoku_generate( 3, 500, true );
%
% Example 2:
%    desiredRating = 1000;
%    while true
%        [ A, rating ] = sudoku_generate( 3, desiredRating, false );
%        if desiredRating*0.9 < rating && rating < desiredRating*1.1
%            break;
%        end
%    end
%
% Other m-files required: generate_influence_indices.m, sudoku_solve.m
% Subfunctions: none
% MAT-files required: none
%
% See also: GENERATE_INFLUENCE_INDICES, SUDOKU_SOLVE

Sudoku generator

Function sudoku_generate generates sudoku table as close to desired rating as possible.

Head of function

First two arguments are mandatory while third serves only as progress tracking tool.

function [ A, rating, solution ] = sudoku_generate( d, desiredRating, verbose )

Check validity of inputs. Expect block size at least 2, non-negative desired rating and optional verbose flag.

if nargin < 1
    return;
end
if nargin < 2
    error('Expected at least two arguments!');
end
if nargin < 3
    verbose = false;
end
if d < 2
    error('Block size must be at least 2!');
end
if desiredRating < 0
    error('Desired rating must be non-negative!');
end

Initialize basic variables and constants.

r = d*d;                            % Edge size of the table.
t = r*r;                            % Total number of variables in the table.
timeoutRating = t*t*5;              % Rating at which is solver interrupted.
optionRange = max(ceil(81/r),2);    % Number of options in main loop.
stage2 = false;                     % Flag turning on solution count search.
C = generate_influence_indices(d);  % Influence index cache.
A = zeros(r);                       % Matrix for solution with no assignments.
domains = ones(r,r,r);              % Domains for all variables with no restriction.
domainSizes = ones(r,r)*r;          % Matrix representing full domains.

Main loop generating random table with one solution and vaguely close to desired rating. This loop first finds 10 feasible assignments that lead to at least one solution, and then picks one that leads to solution with rating closest to desired. This assignment is applied and loop repeats.

In each iteration is tested whether number of solutions can be found, if yes, solution count is tested in all iterations to follow to converge as fast as possible to single solution.

n = 1;
options = cell(optionRange,5);
while n <= t

    % Try to count solutions, and turn on their consideration in case it is
    % possible to count them already.
    if ~stage2
        [ ~, ~, rating, solutionCount ] = sudoku_solve( A, C, timeoutRating/4 );
        if rating > 0
            stage2 = true;
            if verbose
                fprintf('Entering stage 2!\n');
            end
        end
    end

    % Try to generate optionRange number of options. In case there is not
    % enough of those or tested options terminate on range check, whole
    % procedure is terminated and started over.
    try
        k = optionRange;
        while k > 0
            if ~stage2
                solutionCount = 1;
                [row, col, value, rating, domain] = generateAssignment();
            else
                [row, col, value, rating, domain, solutionCount] = generateAssignment();
            end

            if rating > 0
                % In case we have a solution, we store it in list of
                % options and progress to the next one. Stored values are
                % coordinates of the assignment, resulting rating, modified
                % domain, distance from desired rating and number of
                % solutions itself.
                options{k, 1} = row;
                options{k, 2} = col;
                options{k, 3} = value;
                options{k, 4} = rating;
                options{k, 5} = domain;
                options{k, 6} = abs(desiredRating-rating)*solutionCount;
                options{k, 7} = solutionCount;
                k = k - 1;
            else
                domains(row, col, value) = 0;
                domainSizes(row, col) = domainSizes(row, col)-1;
            end
        end
    catch ME
        % If dead end is encountered by generate function, exception is
        % thrown and it should result in restart of the search process.
        % Different one should never by thrown, but just in case it has
        % been it will be rethrown to ensure this function will terminate.
        if (~strcmp(ME.identifier,'Generator:deadEnd'))
            rethrow(ME);
        end

        % Perform restart of first stage.
        if(verbose)
            fprintf('Restarting - dead end!\n');
        end;
        n = 1;
        A = zeros(r);
        domains = ones(r,r,r);
        domainSizes = ones(r,r)*r;
        stage2 = false;
        continue;
    end

    % Sort out best option for this iteration and retrieve it.
	options = sortrows(options, 6);
    row = options{1,1};
    col = options{1,2};
    value = options{1,3};
    rating = options{1,4};
    domain = options{1,5};
    solutionCount = options{1, 7};

    % Perform assignment of selected option to the solution and its support
    % structures.
    A(row, col) = value;
    rel = C(:, row, col);
    ser = domains(:, :, value);
    pos = rel(logical(ser(rel)));
    posG = pos+(value-1)*t;
    domains(row, col, domain) = 0;
    domainSizes(row, col) = -1;
    domainSizes(pos) = domainSizes(pos) - 1;
    domains(posG) = 0;

    if(verbose)
        fprintf('Processed %d ( rating %.2f ) %d\n',n, rating, ...
            stage2*solutionCount);
    end;

    % Progress counter to next assignment and check whether current table
    % has one solution. In case it does so, there is no point in further
    % iterations, as any accepted value would be part of this solution.
    n = n+1;
    if stage2 && solutionCount == 1
        break;
    end
end

This function will generate feasible assignment of random value to random variable determined by row, col, and value. Returned rating is such that current table would have if returned assignment was made. Returned domain is just convenience value.

If sixth return parameter, solutionCount, is defined, generated assignment is done along with solution count, otherwise solver is called to find only first solution (feasibility check).

    function [row, col, value, rating, domain, solutionCount] = generateAssignment()
        % Pick random variable that has non-empty domain.
        av = find(domainSizes>0);
        [row, col] = ind2sub([r,r], av(randi([1, numel(av)])));

        if isempty(row) || isempty(col)
            throw(MException('Generator:deadEnd','There are no more feasible assignments!'));
        end

        % Pick random value from domain of picked variable.
        domain = find(domains(row, col, :));
        value = domain(randi([1, numel(domain)]));

        % Test feasibility of this assignment.
        A(row, col) = value;
        if nargout == 6
            [ ~, ~, rating, solutionCount ] = sudoku_solve( A, C, timeoutRating );
        else
            [ ~, ~, rating ] = sudoku_solve( A, C, timeoutRating );
        end
        A(row, col) = 0;
    end

In this stage is current table reduced to as few clues as possible while maintaining its property of one solution.

baseRating = rating;
while true
    % Each iteration can make the evaluation only more difficult, so once
    % desired rating is exceeded, there is no point in continuing, as the
    % distance would get only bigger.
    if baseRating > desiredRating*1.1
        if(verbose)
            fprintf('Desired rating exceeded! (%.2f)\n', baseRating);
        end
        break;
    end

    % Call function that removes an assignment, if it is possible. If false
    % is returned, it means nothig could be returned, so we terminate at
    % whichever current rating is.
    if ~removeAssignment()
        break;
    end
end

% Call solve once again in final table to get solution table.
[ solution, ~, rating ] = sudoku_solve( A, C );

This function will try to find an assignment that can be removed from the table without changing its solution. All assignments are iterated, removed, number of solutions tested and if it passes, found assignment is removed permanently and true flag returned.

    function [ removed ] = removeAssignment()
        % Collect all assignments in the table and permute them randomly to
        % ensure non-deterministic behaviour.
        assigned = find(A);
        assignedCount = numel(assigned);
        assigned = assigned(randperm(assignedCount));
        if(verbose)
            fprintf('Assigned values %d\n',numel(assigned));
        end

        % Try to remove each assignment.
        removed = false;
        for ind = assigned(:)'
            value = A(ind);
            A(ind) = 0;

            [ ~, ~, rating, solutionCount ] = sudoku_solve( A, C, timeoutRating );
            dist = abs(desiredRating - baseRating);

            if rating < 0
                if(verbose)
                    fprintf('(%d) Rating overflow %.2f, keeeping.\n', ...
                        assignedCount, rating);
                end
            elseif solutionCount ~= 1
                if(verbose)
                    fprintf('(%d) Increased solution count %d, keeeping.\n', ...
                        assignedCount, solutionCount);
                end
            elseif abs(desiredRating - rating) > dist*1.5
                if(verbose)
                    fprintf('(%d) Rating change unfavourable %.2f, keeping.\n', ...
                        assignedCount, rating);
                end
            else
                if(verbose)
                    fprintf('(%d) Removed, rating %.2f.\n', ...
                        assignedCount, rating);
                end
                removed = true;
                baseRating = rating;
                break;
            end
            A(ind) = value;
        end
    end
end