pds_lauro_gama_sudoku.tex.bak

\documentclass[
	% -- opções da classe memoir --
	12pt,				% tamanho da fonte
	openright,			% capítulos começam em pág ímpar (insere página vazia caso preciso)
	oneside,			% para impressão em verso e anverso. Oposto a twoside
	a4paper,			% tamanho do papel.
	% -- opções da classe abntex2 --
	chapter=TITLE,		% títulos de capítulos convetidos em letras maiúsculas 
	%section=TITLE,		% títulos de seções convertidos em letras maiúsculas
	%subsection=TITLE,	% títulos de subseções convertidos em letras maiúsculas
	%subsubsection=TITLE,% títulos de subsubseções convertidos em letras maiúsculas
	% -- opções do pacote babel --
	english,			% idioma adicional para hifenização
	french,				% idioma adicional para hifenização
	spanish,			% idioma adicional para hifenização
	brazil,				% o último idioma é o principal do documento
	article,			% documento divido por sections
	]{uea-abntex2}

%\evensidemargin 0.5 cm

% ---
% PACOTES
% ---

% ---
% Pacotes fundamentais 
% ---
\usepackage{lmodern}			% Usa a fonte Latin Modern
\usepackage[T1]{fontenc}		% Selecao de codigos de fonte.
\usepackage[utf8]{inputenc} 	% Codificacao do documento (conversão automática dos acentos)
\usepackage{indentfirst}		% Indenta o primeiro parágrafo de cada seção.
\usepackage{color}				% Controle das cores
\usepackage{graphicx}			% Inclusão de gráficos
\usepackage{microtype} 			% para melhorias de justificação
\usepackage{array}
\usepackage{cite}
\usepackage{longtable}
\usepackage{calc}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{ifthen}
\usepackage{lscape}
\usepackage[table]{xcolor}
\usepackage{listings}
\def\inputGnumericTable{}
% ---
% cores
% ---
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=Matlab,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=left,
  numbersep=5pt,% how far the line-numbers are from the code 
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,
  tabsize=4
}

% ---
% Pacotes adicionais, usados apenas no âmbito do Modelo Canônico do abnteX2
% ---
\usepackage{lipsum}				% para geração de dummy text
% ---

% ---
% Pacotes de citações
% ---
\usepackage[brazilian,hyperpageref]{backref}	 % Paginas com as citações na bibl
\usepackage[num]{abntex2cite}	% Citações padrão ABNT
\usepackage{tocloft}
\usepackage{parskip}

% --- 
% CONFIGURAÇÕES DE PACOTES
% ---

% ---
% Configurações do pacote backref
% Usado sem a opção hyperpageref de backref
\renewcommand{\backrefpagesname}{Citado na(s) página(s):~}
% Texto padrão antes do número das páginas
\renewcommand{\backref}{}
% Define os textos da citação
\renewcommand*{\backrefalt}[4]{
	\ifcase #1 %
		Nenhuma citação no texto.%
	\or
		Citado na página #2.%
	\else
		Citado #1 vezes nas páginas #2.%
	\fi}%
% ---

% ---
% Informações de dados para CAPA e FOLHA DE ROSTO
% ---
\titulo{RESOLUÇÃO DE SUDOKU}
\autor{LAURO MANOEL LIMA DA GAMA}
\local{Manaus}
\data{2014}
\instituicao{%
  UNIVERSIDADE DO ESTADO DO AMAZONAS
  \par
  ESCOLA SUPERIOR DE TECNOLOGIA}
\orientador[Professor:]{Victor Enrique Vermehren Valenzuela}
% O preambulo deve conter o tipo do trabalho, o objetivo, 
% o nome da instituição e a área de concentração 
\preambulo{Implementação e analise de um programa solucionador de jogos matemáticos do tipo sudoku utilizando Matlab.}
% ---

% ---
% Configurações de aparência do PDF final

% alterando o aspecto da cor azul
\definecolor{blue}{RGB}{41,5,195}

% informações do PDF
\makeatletter
\hypersetup{
     	%pagebackref=true,
		pdftitle={\@title}, 
		pdfauthor={\@author},
    	pdfsubject={\imprimirpreambulo},
	    pdfcreator={LaTeX with abnTeX2},
		pdfkeywords={matlab}{sudoku}{recursividade}, 
		colorlinks=false,       		% false: boxed links; true: colored links
   		linkcolor=black,          	% color of internal links
    	citecolor=blue,        		% color of links to bibliography
    	filecolor=magenta,      		% color of file links
		urlcolor=blue,
		bookmarksdepth=4
}
\makeatother
% --- 

% --- 
% Espaçamentos entre linhas e parágrafos 
% --- 

% O tamanho do parágrafo é dado por:
\setlength{\parindent}{1.3cm}

% Controle do espaçamento entre um parágrafo e outro:
\setlength{\parskip}{0.2cm}  % tente também \onelineskip

% ---
% compila o indice
% ---
\makeindex
% ---

% ----
% Início do documento
% ----
\begin{document}

% Retira espaço extra obsoleto entre as frases.
\frenchspacing 

% ----------------------------------------------------------
% ELEMENTOS PRÉ-TEXTUAIS
% ----------------------------------------------------------
% \pretextual

% ---
% Capa
% ---
\imprimircapa
% ---

% ---
% Folha de rosto
% ---
\imprimirfolhaderosto
% ---

% ---
% NOTA DA ABNT NBR 15287:2011, p. 4:
%  ``Se exigido pela entidade, apresentar os dados curriculares do autor em
%     folha ou página distinta após a folha de rosto.''
% ---

% ---
% inserir lista de ilustrações
% ---
%***********3 linhas comentadas pois não é obrigatória a Lista de Figuras
%\pdfbookmark[0]{\listfigurename}{lof}
%\listoffigures*
%\cleardoublepage
% ---

% ---
% inserir lista de tabelas
% ---
%***********3 linhas comentadas pois não é obrigatória a Lista de Tabelas
%\pdfbookmark[0]{\listtablename}{lot}
%\listoftables*
%\cleardoublepage
% ---

% ---
% inserir lista de abreviaturas e siglas
% ---
\begin{siglas}
  \item[EST] Escola Superior de Tecnologia
  \item[UEA] Universidade do Estado do Amazonas 
\end{siglas}
 ---

% ---
% inserir lista de símbolos
% ---
%\begin{simbolos}
%  \item[$ \Gamma $] Letra grega Gama
%  \item[$ \Lambda $] Lambda
%  \item[$ \zeta $] Letra grega minúscula zeta
%  \item[$ \in $] Pertence
%\end{simbolos}
% ---
% ---
% inserir o sumario
% ---
%\pdfbookmark[0]{\contentsname}{toc}
\renewcommand{\contentsname}{\vspace*{3.4cm}SUMÁRIO}
\tableofcontents*
%\cleardoublepage
% ---

% ----------------------------------------------------------
% ELEMENTOS TEXTUAIS
% ----------------------------------------------------------

% ----------------------------------------------------------
% Introdução
% ----------------------------------------------------------
\textual
\pagestyle{simple}

\newpage

\chapter*{\vspace*{3.4cm}INTRODUÇÃO}
\addcontentsline{toc}{section}{INTRODUÇÃO}
O jogo sudoku é um dos mais populares passatempos matemáticos de todos os tempos. O seu objetivo é o preenchimento com números de uma matriz de 9x9 elementos de forma que cada linha, coluna e submatriz de 3x3 elementos contenha todos os dígitos entre 1 e 9.

O jogo tem origens na frança em meados de 1895 e sua forma atual foi introduzida no japão pela editora Nikoli em abril de 1984 com o nome \emph{Suji wa dokushin ni kagiru}. O nome foi posteriormente abreviado para sudoku por Maki Kaji.\cite{Pegg}

A resolução desse jogo pode ser feita por um computador através de recursividade, onde o programa irá sugerir um numero para uma posição vazia do sudoku e verifica se essa escolha é valida. Caso seja valida o programa continuará, caso não seja ele irá tentar outro numero até encontrar um que seja valido para aquela posição. Dessa forma o programa irá preencher todas as posições até que o jogo esteja completo ou seja deduzido que não há soluções validas e o jogo foi formulado de forma incorreta.\cite{Weeks}


% ----------------------------------------------------------
% Capitulo de textual  
% ----------------------------------------------------------
\newpage
%\chapter*{\vspace*{3.4cm}PROJETO DE PESQUISA}

\vspace{24pt}

\section{DESENVOLVIMENTO}
\hspace*{0.8cm}
O programa desenvolvido em Matlab utiliza os princípios de recursividade para preencher os espaços vazios de uma matriz 9x9. Ao detectar que a matriz não possui espaços vazios o sudoku é considerado resolvido.

O programa completo está descrito abaixo:
\begin{lstlisting}
function S = sudoku(M,S)
if ~exist('S','var')
    S = zeros([size(M),0]);
end
firstId = find(M(:)==0, 1 );
if isempty(firstId)  
    S(:,:,size(S,3)+1) = M;  
else 
    [i,j] = ind2sub([9,9],firstId);
    for k=1:9
        ii = (ceil(i/3)-1)*3+1;
        jj = (ceil(j/3)-1)*3+1;
        mm = M(ii:ii+2,jj:jj+2);
        if sum(M(i,:)==k)==0 && sum(M(:,j)==k)==0 && sum(mm(:)==k)==0
            M(i,j) = k;
            S = sudoku(M,S);
        end
    end
end
\end{lstlisting}

A primeira linha do programa é a definição da função sudoku. Essa função recebe dois parâmetros M e S.
O parâmetro M é a matriz 9x9 que representa o sudoku não resolvido e o parâmetro S é o resultado da função, portanto a função recebe ela mesma como parâmetro.
\begin{lstlisting}
function S = sudoku(M,S)
\end{lstlisting}

Ao ser iniciada, a função sudoku verifica se a variável S existe. Em caso negativo essa é a primeira vez que a função está sendo executada em um laço recursivo e a variável S deve ser inicializada como uma matriz nula do mesmo tamanho da matriz M.
\begin{lstlisting}
if ~exist('S','var')
    S = zeros([size(M),0]);
end
\end{lstlisting}

Na linha 5 a função sudoku usa o comando \emph{find}\cite{Mathworks} para encontrar o índice da primeira célula da matriz M com valor igual a zero. 
\begin{lstlisting}
firstId = find(M(:)==0, 1 );
\end{lstlisting}

Caso não haja elementos iguais a zero o sudoku está completamente preenchido e a solucao do jogo foi encontrada e o resultado é salvo na matriz S.
\begin{lstlisting}
if isempty(firstId)  
    S(:,:,size(S,3)+1) = M;
\end{lstlisting}

Caso haja elementos com valor zero a função irá tentar encontrar todos os valores que podem ser inseridos nessa célula.
Esse processo começa utilizando o comando \emph{ind2sub}\cite{Mathworks} para encontrar as coordenadas de linha e coluna da célula \emph{M(i,j)}.
\begin{lstlisting}
[i,j] = ind2sub([9,9],firstId);
\end{lstlisting}

Para isso é necessário criar um laço para testar os possíveis números para essa célula.
\begin{lstlisting}
for k=1:9
    ii = (ceil(i/3)-1)*3+1;
    jj = (ceil(j/3)-1)*3+1;
    mm = M(ii:ii+2,jj:jj+2);
    ...
end
\end{lstlisting}
No código acima  a variável \emph{mm} recebe os índices da submatriz 3x3 em que a célula \emph{M(i,j)} está localizada. A partir desses índices é verificado se o valor \emph{k} atende os requisitos do sudoku.
Caso atenda então a célula \emph{M(i,j)} é preenchida com o valor \emph{k} e a função sudoku é chamada recursivamente de modo que esse processo se repetirá até que seja encontrada uma solução para o jogo.
\begin{lstlisting}
if sum(M(i,:)==k)==0 && sum(M(:,j)==k)==0 && sum(mm(:)==k)==0
            M(i,j) = k;
            S = sudoku(M,S);
    end
\end{lstlisting}

% ----------------------------------------------------------
% Referências bibliográficas
% ----------------------------------------------------------
% Uncomment the following two lines if you want to have a bibliography. Please do not forget to add an entry to your bibliography and reference it by using the \cite{} command
\newpage
\vspace*{2.3cm}
%\section{REFERÊNCIAS}
\renewcommand{\bibname}{REFERÊNCIAS}
\bibliography{references}
\end{document}