\documentclass[11pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{dsfont}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
%\usepackage{slashbox}
\usepackage{times}
\usepackage{multicol}
\usepackage{skak,chessboard}
\usepackage{textcomp}
\usepackage{pst-all}
\usepackage[a4paper]{geometry}

\geometry{hmargin=1cm, tmargin=1cm,bmargin=1.5cm}
\title{Département d'informatique, partiel de Mathématiques discrètes.\\  
Semestre 3, mars 2013, durée 30 min, J.-F. Couchot.}

\date{}

\begin{document}
\maketitle
\vspace{-5em}
\begin{tabular}{ll}
Nom:& ........................................\\
Prénom:& ........................................\\
\end{tabular}

Seuls les codes développés en TP sont autorisés.
Vos réponses seront données directement ci-dessous en python.


\section*{Échange de cavaliers au jeu d'échec}

Sur un échiquier 3x3, les deux cavaliers noirs sont placés sur les cases a1 et c1, les deux cavaliers blancs occupant les cases a3 et c3, comme représenté 
ci-dessous.
\begin{center}  
  \def\mylist{Na3,Nc3,na1,nc1}
  \setchessboard{
  maxfield=c3,
  setpieces=\mylist
}
\chessboard
\end{center}

L'objectif est de déterminer les mouvements qui autoriseront les
cavaliers blancs à prendre les places des cavaliers noirs, et vice versa.

Pour rappel, un cavalier se déplace en ``L'': par exemple le cavalier noir, 
en a1, peut se rendre soit en c2, soit en b3.
 
Comme il y a neuf cases sur le plateau, l'état du 
jeu est mémorisé à l'aide d'un 9-uplet  
$$
(x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8)
$$ 
où 
$x_0$ mémorise ce qu'il y a sur la case a1, 
$x_1$ mémorise ce qu'il y a sur la case a2, \ldots, 
$x_8$ mémorise ce qu'il y a sur la case c3. 
Un case $x_i$ est soit vide, soit avec un cavalier noir, soit avec un 
cavalier blanc. On mémorise ceci en affectant à $x_i$ 
soit la valeur 'v' (pour vide), 
soit la valeur 'n' (pour cavalier noir) ou  
soit la valeur 'b' (pour cavalier blanc). 



\begin{enumerate}
\item Donner le 9-uplet \verb+initial+ 
  qui représente l'état initial du jeu selon ce codage.
  Donner le 9-uplet \verb+final+ 
  qui représente l'état final du jeu selon ce codage.

\vspace{2cm}
\item Donner le code de la fonction \verb+nbre(u,c)+ qui reçoit en paramètres 
  un $n$-uplet \verb+u+ et un caractère \verb+c+ et qui retourne le nombre
  d'occurrences de ce caractère dans \verb+u+. Par exemple 
  \verb+nbre(initial,'b')+ vaut 2 et  \verb+nbre(initial,'v')+ vaut 5.
\vspace{3cm}
 
\item Si l'on construisait tous les plateaux de jeu 3x3 sans tenir compte 
  du nombre de cavaliers, combien en aurait-on? Justifier.
 \vspace{3cm}
\item Donner le code qui initialise la liste de plateaux, 
  nommée \verb+plateaux+, 
  avec tous les plateaux possibles, mais en tenant compte du fait qu'il 
  y a toujours deux cavaliers noirs et deux cavaliers blancs sur chaque 
  plateau.   
 \vspace{5cm}
\item Commenter le code suivant (à sa droite) 
  en détaillant la nature des paramètres, 
  ce qui est retourné, et pourquoi cette valeur?  
\begin{scriptsize}
\begin{verbatim}
def deplacement(co,ce):
      r=[[5,7],
         [6,8],
         [3,7],
         [2,8],
         [],
         [0,6],
         [1,5],
         [0,2],
         [1,3]]
      return ce in r[co]
\end{verbatim}
\end{scriptsize}
\item Donner le code de la fonction  \verb+deplacement_ok(p1,p2)+
  qui retourne vrai si l'on peut passer du plateau 
\verb+p1+ au plateau \verb+p2+.
\vspace{6cm}

\item Donner le code manquant 
  qui permet de résoudre le problème en utilisant 
  \verb+networkx+.

\end{enumerate}

\end{document}

