heyawake-prolog/rendu/rendu.tex

\documentclass{article}

\usepackage[utf8x]{inputenc} % encodage utf-8
\usepackage[french]{babel} % en français
\usepackage[T1]{fontenc} % encodage T1 police
\usepackage[hidelinks]{hyperref} % lien dans table des matières
\usepackage[nameinlink, noabbrev]{cleveref} % lien pour les images
\usepackage{listings} % intégration code
\usepackage{xcolor} % couleur
\usepackage{enumitem} % listes personalisées
\usepackage{graphicx} % intégration images

% liste avec flèches
\newlist{listeFleche}{itemize}{4}
\setlist[listeFleche]{label=$\rightarrow$}
% couleurs
\definecolor{defaultPredicat}{RGB}{121, 94, 38}
\definecolor{definitionChar}{RGB}{175, 0, 219}
\definecolor{argsAndPredicat}{RGB}{0, 96, 181}
\definecolor{string}{RGB}{163, 99, 21}
\definecolor{comment}{RGB}{0, 128, 0}
\lstset{
    frame=single, % encadré
    breaklines=true, % lignes dans le cadre
    columns=fullflexible, % contenu bien présenté dans le cadre
    language=Prolog, % language
    tabsize=4, % nb d'espace par tabulation
    % chiffres
    numbers=left,
    numberstyle=\tiny,
    % affichage
    basicstyle=\ttfamily,
    keywordstyle=\color{defaultPredicat},
    identifierstyle=\color{argsAndPredicat},
    stringstyle=\color{string},
    commentstyle=\color{comment},
    literate=
        {:-}{{\textcolor{definitionChar}{:- }}}1
    % utf-8 fix source: https://en.wikibooks.org/wiki/LaTeX/Source_Code_Listings
        {á}{{\'a}}1 {é}{{\'e}}1 {í}{{\'i}}1 {ó}{{\'o}}1 {ú}{{\'u}}1
        {Á}{{\'A}}1 {É}{{\'E}}1 {Í}{{\'I}}1 {Ó}{{\'O}}1 {Ú}{{\'U}}1
        {à}{{\`a}}1 {è}{{\`e}}1 {ì}{{\`i}}1 {ò}{{\`o}}1 {ù}{{\`u}}1
        {À}{{\`A}}1 {È}{{\'E}}1 {Ì}{{\`I}}1 {Ò}{{\`O}}1 {Ù}{{\`U}}1
        {ä}{{\"a}}1 {ë}{{\"e}}1 {ï}{{\"i}}1 {ö}{{\"o}}1 {ü}{{\"u}}1
        {Ä}{{\"A}}1 {Ë}{{\"E}}1 {Ï}{{\"I}}1 {Ö}{{\"O}}1 {Ü}{{\"U}}1
        {â}{{\^a}}1 {ê}{{\^e}}1 {î}{{\^i}}1 {ô}{{\^o}}1 {û}{{\^u}}1
        {Â}{{\^A}}1 {Ê}{{\^E}}1 {Î}{{\^I}}1 {Ô}{{\^O}}1 {Û}{{\^U}}1
        {ã}{{\~a}}1 {ẽ}{{\~e}}1 {ĩ}{{\~i}}1 {õ}{{\~o}}1 {ũ}{{\~u}}1
        {Ã}{{\~A}}1 {Ẽ}{{\~E}}1 {Ĩ}{{\~I}}1 {Õ}{{\~O}}1 {Ũ}{{\~U}}1
        {œ}{{\oe}}1 {Œ}{{\OE}}1 {æ}{{\ae}}1 {Æ}{{\AE}}1 {ß}{{\ss}}1
        {ű}{{\H{u}}}1 {Ű}{{\H{U}}}1 {ő}{{\H{o}}}1 {Ő}{{\H{O}}}1
        {ç}{{\c c}}1 {Ç}{{\c C}}1 {ø}{{\o}}1 {å}{{\r a}}1 {Å}{{\r A}}1
        {€}{{\euro}}1 {£}{{\pounds}}1 {«}{{\guillemotleft}}1
        {»}{{\guillemotright}}1 {ñ}{{\~n}}1 {Ñ}{{\~N}}1 {¿}{{?`}}1 {¡}{{!`}}1,
    % espaces normaux sans underscore
    showspaces=false,
    showstringspaces=false,
    showtabs=false
}
\author{Kévin Martins Da Veiga [20009472] et Anri Kennel [20010664]}
\title{Projet Heyawake en Prolog}
\date{}

\begin{document}

    \maketitle
    \tableofcontents
    \newpage

    \section{Présentation du Projet}
    \subsection{Introduction et règles du jeu}
    L'Heyawake est un puzzle joué dans une grille rectangulaire séparée en plusieurs aires dont le but
    est de colorer des cases en noir et blanc en accord avec les règles :
    
    \begin{listeFleche}
        \item Certaines aires contiennent un chiffre qui montre combien il y a de cases noires dans l'aire
        \begin{listeFleche}
            \item Aire avec un 0 ne doit pas avoir de cases noires
            \item Aire avec un 1 contient une case noire, on répète ses étapes autant de fois qu'il le faut
        \end{listeFleche}
        \item Toutes les cases blanches doivent être connectées en un seul groupe, pas de groupes isolés, elles doivent toutes être reliées
        \item Deux cases noires ne peuvent être l'un à côté de l'autre horizontalement et verticalement (en diagonale, c'est possible)
        \begin{listeFleche}
            \item Ça veut dire que les cases noires doivent n'être qu'entourer de cases blanches
        \end{listeFleche}
        \item Une rangée de case blanche ne peut pas être alignée au-delà de 2 aires
    \end{listeFleche}

    \subsection{Réalisation}
    \begin{listeFleche}
        \item Mettre toutes les aires avec un 0 en blanc
        \item Mettre les aires avec 1 et que d'une case en noire
        \item Mettre des cases noires là où une rangée de cases blanches dans plus de 2 aires peut se faire
        \item Toujours mettre du blanc autour des cases noires
        \begin{listeFleche}
            \item En suivant cette étape, quand on met une case noire dans une aire avec un chiffre 1, colore tout le reste de l'aire en blanc
        \end{listeFleche}
        \item Toujours vérifié que les cases blanches ne sont pas piégées entre des cases noires
        \begin{listeFleche}
            \item Ça implique que dans ce schéma suivant avec B une case blanche, N une case noire et X une case vide :
            \begin{listeFleche}
                \item B X B $\rightarrow$ B B B
                \item N B N $\rightarrow$ N B N
                \item B N B $\rightarrow$ B N B
                \item Le X doit obligatoirement devenir blanc pour laisser une sortie à la case blanche qui se trouve entre les cases noires
            \end{listeFleche}
        \end{listeFleche}
    \end{listeFleche}

    Le programme se lance en appelant le prédicat \emph{\texttt{run}} avec comme argument une liste de listes des aires.

    \begin{lstlisting}
run([[0,0,1,1,2],  [2,0,2,2,-1], [3,0,5,1,-1],
     [0,2,0,4,-1], [1,2,1,3,0],  [3,2,5,2,0],
     [1,4,1,4,1],  [2,3,5,5,4],  [0,5,1,5,-1]]).
% [X1, Y1, X2, Y2, N] avec N le nombre de case noire dans l'aire
    \end{lstlisting}

    Cet appel correspond au puzzle ci-dessous
    \begin{figure}[ht]
        \centering
        \includegraphics[width=5cm, height=5cm]{default}
        \caption{Puzzle de difficulté facile d'Heyawake}
        \label{fig:defaultFig}
    \end{figure}


    \section{Résolution d'une grille avec des aires}
    \subsection{Ce que l'on a essayé}
    \begin{listeFleche}
        \item On vérifie les aires avec un 2 et de 4 cases puis on colorie la case 2 en noire et ses diagonales
        \begin{listeFleche}
            \item On colore les cases adjacentes aux noires en blanc, on le fait autant de fois que nécessaire
        \end{listeFleche}
        \item On regarde quelles cases doivent être colorées en noire pour éviter de faire des lignes de 4 cases blanches
        \item On connecte les cases blanches ensemble sans faire de lignes de plus de 3 cases dans des zones différentes

        \item Maintenant on essaie de rajouter des cases noires :
        \begin{listeFleche}
            \item On met une case noire pour éviter des groupes de 3 cases blanches
            \item On colorie les cases adjacentes à la nouvelle case noire en blanc
        \end{listeFleche}
        \item On fait en sorte que toutes les cases blanches soient connectées en rajoutant des cases blanches si possible
        \item On remplit les cases noires là où on peut les mettre, et on continue jusqu'à qu'il n'y est plus de cases sans couleurs.
    \end{listeFleche}

    \section{Le programme}
    \subsection{Le prédicat \emph{\texttt{aire}} en détail}
    Le prédicat \emph{\texttt{aire}} fonctionne comme l'image ci-contre. Il regarde chaque case de l'aire.
    Une fois arrivé à l'extrémité d'une aire, il descend d'une case s'il y une ligne en dessous puis il parcourt
    le chemin inverse avec le prédicat \emph{\texttt{airereverse}}.

    Par exemple, sur la \autoref{fig:defaultFig}, prenons l'aire en bas à droite :
    \begin{figure}[ht]
        \centering
        \includegraphics[width=5cm, height=5cm]{aireExplication}
        \caption{Explication fonctionnement \emph{\texttt{aire}}}
    \end{figure}

    \subsection{Liste des prédicats utilisés}
    \begin{listeFleche}
        \item \textbf{\texttt{aire(X1, Y1, X2, Y2, E, T)}} :
            Ce prédicat fait scanne l'aire renseignée et assigne une couleur via le prédicat \emph{\texttt{case}}.
        \item \textbf{\texttt{airereverse(X1, Y1, X2, Y2, 0, T)}} :
            Ce prédicat est appelée par le prédicat \emph{\texttt{aire}} et permet de vérifier tous les éléments
            d'une aire.
        \item \textbf{\texttt{case(X, Y, C)}} :
            Ce prédicat renvoie la couleur d'une case du puzzle.
        \item \textbf{\texttt{run([[X1, Y1, X2, Y2, E] | Q])}} :
            Ce prédicat lance la résolution du puzzle.
    \end{listeFleche}


    \section{Annexe : le code}
    \lstinputlisting{../resolveur.pl}

\end{document}