--- /dev/null
+\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}
+
