%% SOLVE_CLOCK     Solves a Final Fantasy XIII-2 clock puzzle
%  author: Nathaniel Johnston
%  license: GPL2
%
%  SOL = SOLVE_CLOCK(CLK) returns a single solution to a clock puzzle, or 0
%  if no solution exists (see URL for details)
%
%  SOL = SOLVE_CLOCK(CLK,1) returns all solutions to a clock puzzle, or 0
%  if no solution exists (see URL for details)
%
%  http://www.njohnston.ca/2012/02/counting-and-solving-final-fantasy-xiii-2s-clock-puzzles

%% Copyright (c) 2012 Nathaniel Johnston
% 
%  This program is free software; you can redistribute it and/or
%  modify it under the terms of the GNU General Public License
%  as published by the Free Software Foundation; either version 2
%  of the License, or (at your option) any later version.
%
%  This program is distributed in the hope that it will be useful,
%  but WITHOUT ANY WARRANTY; without even the implied warranty of
%  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%  GNU General Public License for more details.
%
%  You should have received a copy of the GNU General Public License
%  along with this program; if not, write to the Free Software
%  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
%  MA 02110-1301, USA.

%% Code starts here
function sol = solve_clock(clk,f_all)

    n = max(size(clk));
    tot_sol = [];
    if(n <= 1)
        sol = 0;
        return;
    elseif nargin < 2
        f_all = 0;
    end
    
    for j = 0:(n-1)
        sol = move(j,clk,j,n,1);
        if(max(size(sol)) > 1)
            if(f_all)
                tot_sol = [tot_sol;sol];
            else
                return;
            end
        end
        
        sol = move(j,clk,j,n,-1);
        if(max(size(sol)) > 1)
            if(f_all)
                tot_sol = [tot_sol;sol];
            else
                return;
            end
        end
    end
    if(f_all && max(size(tot_sol))>0)
        sol = tot_sol;
    end
end


function sol = move(j,clk,csol,n,dir)
    
    new = mod(j + dir*clk(j+1), n);
    tsol = [csol, new];
    
    if(max(csol == new) == 1)
        sol = 0;
    elseif(max(size(tsol)) == n)
        sol = tsol;
    else
        sol = move(new,clk,tsol,n,1);
        if(max(size(sol)) == 1)
            sol = move(new,clk,tsol,n,-1);
        end
    end
end