Échec et SQL

Est-il possible de calculer tous les déplacements de toutes les pièces du jeu d’échecs par de simples requêtes SQL ? Assurément oui, voici la démonstration….

0 – Voici notre modèle de données :


CREATE TABLE T_CASE_CAS
(COL_NUM   SMALLINT,
 RNG_NUM   SMALLINT);
 
INSERT INTO T_CASE_CAS
VALUES (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8),  
       (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8),  
       (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8),    
       (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8),    
       (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8),    
       (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8),  
       (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7), (7, 8),  
       (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8);

1 – déplacement du fou dans le jeu d’échec

Pour le fou qui se déplace en diagonal, le déplacement relatif dans la colonne entre la case départ et la case d’arrivée doit être égal au déplacement relatif entre la colonne de départ et la colonne d’arrivée. Bien entendu il est interdit de rester sur place !
En effectuant un produit cartésien de toutes les cases entres elles nous avons le potentiel global de cases de départ et d’arriver. Il ne suffit plus que de filtrer !


WITH T AS
(
SELECT 'F' AS PIECE, D.RNG_NUM AS RNG_DEP, D.COL_NUM AS COL_DEP,
       A.RNG_NUM AS RNG_ARV, A.COL_NUM AS COL_ARV
FROM   dbo.T_CASE_CAS AS D
-- produit cartésien -->
       CROSS JOIN dbo.T_CASE_CAS AS A  
-- filtrage sur déplacement -->
WHERE  ABS(D.RNG_NUM - A.RNG_NUM) = ABS(D.COL_NUM - A.COL_NUM)
-- interdiction de rester sur place -->
  AND  D.RNG_NUM <> A.RNG_NUM  
  AND  D.COL_NUM <> A.COL_NUM
)
SELECT PIECE, CHAR(COL_DEP + 64) + CAST(RNG_DEP AS CHAR(1)) AS DEPART,
              CHAR(COL_ARV + 64) + CAST(RNG_ARV AS CHAR(1)) AS ARRIVE
FROM  T  
ORDER BY 1, 2, 3;

Au total 560 mouvements différents.

2 – déplacement de la tour dans le jeu d’échec

La tour se déplace de manière orthogonale. Cela revient à dire que seule la colonne ou la rangée bouge. On utilise au final la même technique que pour le fou : produit cartésien, interdiction de rester sur place et filtrage sur la condition précitée.


WITH T AS
(
SELECT 'T' AS PIECE, D.RNG_NUM AS RNG_DEP, D.COL_NUM AS COL_DEP,
       A.RNG_NUM AS RNG_ARV, A.COL_NUM AS COL_ARV
FROM   dbo.T_CASE_CAS AS D
-- produit cartésien -->
       CROSS JOIN dbo.T_CASE_CAS AS A
-- filtrage sur déplacement -->
WHERE  (   ABS(D.RNG_NUM - A.RNG_NUM) = 0
        OR ABS(D.COL_NUM - A.COL_NUM) = 0 )
-- interdiction de rester sur place -->
  AND  (   D.RNG_NUM <> A.RNG_NUM  
        OR D.COL_NUM <> A.COL_NUM)
)
SELECT PIECE, CHAR(COL_DEP + 64) + CAST(RNG_DEP AS CHAR(1)) AS DEPART,
              CHAR(COL_ARV + 64) + CAST(RNG_ARV AS CHAR(1)) AS ARRIVE        
FROM  T  
ORDER BY 1, 2, 3;

Soit au total 896 mouvements différents.

3 – déplacement de la reine

Le cas est trivial, puisqu’il consiste à combiner les deux clauses WHERE des deux requêtes précédentes :


WITH T AS
(
SELECT 'D' AS PIECE, D.RNG_NUM AS RNG_DEP, D.COL_NUM AS COL_DEP,
       A.RNG_NUM AS RNG_ARV, A.COL_NUM AS COL_ARV
FROM   dbo.T_CASE_CAS AS D
-- produit cartésien -->
       CROSS JOIN dbo.T_CASE_CAS AS A
-- filtrage sur déplacement -->
WHERE  (ABS(D.RNG_NUM - A.RNG_NUM) = ABS(D.COL_NUM - A.COL_NUM)
        OR ABS(D.RNG_NUM - A.RNG_NUM) = 0
        OR ABS(D.COL_NUM - A.COL_NUM) = 0)
-- interdiction de rester sur place -->
        AND  (   D.RNG_NUM <> A.RNG_NUM  
              OR D.COL_NUM <> A.COL_NUM))
SELECT PIECE, CHAR(COL_DEP + 64) + CAST(RNG_DEP AS CHAR(1)) AS DEPART,
              CHAR(COL_ARV + 64) + CAST(RNG_ARV AS CHAR(1)) AS ARRIVE              
FROM  T  
ORDER BY 1, 2, 3;

Soit au total : 1456 mouvements différents.

4 – déplacement du cavalier

Là encore le cas est simple, soit un déplacement de deux cases sur un axe et 3 sur l’autre ou l’inverse. Notez qu’il n’est pas nécessaire de filtrer sur le « sur place ».


WITH T AS
(
SELECT 'C' AS PIECE, D.RNG_NUM AS RNG_DEP, D.COL_NUM AS COL_DEP,
       A.RNG_NUM AS RNG_ARV, A.COL_NUM AS COL_ARV
FROM   dbo.T_CASE_CAS AS D
-- produit cartésien -->
       CROSS JOIN dbo.T_CASE_CAS AS A
-- filtrage sur déplacement -->
WHERE  (    ABS(D.RNG_NUM - A.RNG_NUM) = 2
        AND ABS(D.COL_NUM - A.COL_NUM) = 3 )
  OR   (    ABS(D.RNG_NUM - A.RNG_NUM) = 3
        AND ABS(D.COL_NUM - A.COL_NUM) = 2 )
)
SELECT PIECE, CHAR(COL_DEP + 64) + CAST(RNG_DEP AS CHAR(1)) AS DEPART,
              CHAR(COL_ARV + 64) + CAST(RNG_ARV AS CHAR(1)) AS ARRIVE
FROM  T  
ORDER BY 1, 2, 3;

Au total : 240 mouvements différents

5 – déplacement du roi

Un cas à nouveau simple : on test si il y a au plus déplacement relatif d’une case dans un axe et on évite le sur place.


WITH T AS
(
SELECT 'R' AS PIECE, D.RNG_NUM AS RNG_DEP, D.COL_NUM AS COL_DEP,
       A.RNG_NUM AS RNG_ARV, A.COL_NUM AS COL_ARV
FROM   dbo.T_CASE_CAS AS D
-- produit cartésien -->
       CROSS JOIN dbo.T_CASE_CAS AS A
-- filtrage sur déplacement -->
WHERE  ABS(D.RNG_NUM - A.RNG_NUM) <= 1
  AND  ABS(D.COL_NUM - A.COL_NUM) <= 1
-- interdiction de rester sur place -->
  AND  (   D.RNG_NUM <> A.RNG_NUM  
        OR D.COL_NUM <> A.COL_NUM)
)
SELECT PIECE, CHAR(COL_DEP + 64) + CAST(RNG_DEP AS CHAR(1)) AS DEPART,
              CHAR(COL_ARV + 64) + CAST(RNG_ARV AS CHAR(1)) AS ARRIVE
FROM  T  
ORDER BY 1, 2, 3;

Soit 420 mouvements différents.

6 – Déplacement des pions

De loin, c’est le plus compliqué et il faut considérer les pions noirs et les pions blancs qui se déplacent différemment. Il faut aussi considérer la prise faites en diagonale ainsi que le déplacement de deux cas depuis le point d’orgine et bien entendu la prise en passant lorsque le pion est au point d’origine…


WITH T AS
(
SELECT 'Pn' AS PIECE, D.RNG_NUM AS RNG_DEP, D.COL_NUM AS COL_DEP,
       A.RNG_NUM AS RNG_ARV, A.COL_NUM AS COL_ARV
FROM   dbo.T_CASE_CAS AS D
       CROSS JOIN dbo.T_CASE_CAS AS A
WHERE      ABS(D.COL_NUM - A.COL_NUM) <= 1
       AND D.RNG_NUM - A.RNG_NUM BETWEEN 1
                                 AND CASE  
                                        WHEN D.RNG_NUM = 7
                                           THEN 2
                                        ELSE 1
                                     END
       AND D.RNG_NUM <= 7
UNION  ALL
SELECT 'Pb' AS PIECE, D.RNG_NUM AS RNG_DEP, D.COL_NUM AS COL_DEP,
       A.RNG_NUM AS RNG_ARV, A.COL_NUM AS COL_ARV
FROM   dbo.T_CASE_CAS AS D
       CROSS JOIN dbo.T_CASE_CAS AS A
WHERE      ABS(D.COL_NUM - A.COL_NUM) <= 1
       AND A.RNG_NUM - D.RNG_NUM BETWEEN 1
                                 AND CASE  
                                        WHEN D.RNG_NUM = 2
                                           THEN 2
                                        ELSE 1
                                     END
       AND D.RNG_NUM >= 2       )                
SELECT PIECE, CHAR(COL_DEP + 64) + CAST(RNG_DEP AS CHAR(1)) AS DEPART,
              CHAR(COL_ARV + 64) + CAST(RNG_ARV AS CHAR(1)) AS ARRIVE        
FROM  T  
ORDER BY 1, 2, 3;

Soit au total 308 mouvements différents.

7 – statistiques diverses

Pour connaître le nombre de cases traversées lors du mouvement d’une pièce et entre les cases de départ et d’arrivée, il suffit de rajouter l’expression suivante au SELECT final :


, CASE  
     WHEN ABS(COL_DEP - COL_ARV) < ABS(RNG_DEP - RNG_ARV)  
        THEN ABS(RNG_DEP - RNG_ARV)  
     ELSE ABS(COL_DEP - COL_ARV)
  END - 1 AS CASES_TRAVERSEES

et si l’on veut connaître le nombre global de l’ensemble des cases traversée pour tous les mouvements, on peut rajouter l’expression suivante :


, SUM(CASE  
         WHEN ABS(COL_DEP - COL_ARV) < ABS(RNG_DEP - RNG_ARV)  
           THEN ABS(RNG_DEP - RNG_ARV)  
        ELSE ABS(COL_DEP - COL_ARV)
     END - 1) OVER() AS TOTAL_CASES_TRAVERSEES

Exemple, déplacement du fou dans le jeu d’échec :


WITH T AS
(
SELECT 'F' AS PIECE, D.RNG_NUM AS RNG_DEP, D.COL_NUM AS COL_DEP,
       A.RNG_NUM AS RNG_ARV, A.COL_NUM AS COL_ARV
FROM   dbo.T_CASE_CAS AS D
       CROSS JOIN dbo.T_CASE_CAS AS A
WHERE  ABS(D.RNG_NUM - A.RNG_NUM) = ABS(D.COL_NUM - A.COL_NUM)
  AND  D.RNG_NUM <> A.RNG_NUM  
  AND  D.COL_NUM <> A.COL_NUM
)
SELECT PIECE, CHAR(COL_DEP + 64) + CAST(RNG_DEP AS CHAR(1)) AS DEPART,
              CHAR(COL_ARV + 64) + CAST(RNG_ARV AS CHAR(1)) AS ARRIVE,
       CASE  
          WHEN ABS(COL_DEP - COL_ARV) < ABS(RNG_DEP - RNG_ARV)  
             THEN ABS(RNG_DEP - RNG_ARV)  
          ELSE ABS(COL_DEP - COL_ARV)
       END - 1 AS CASES_TRAVERSEES,
       SUM(CASE  
              WHEN ABS(COL_DEP - COL_ARV) < ABS(RNG_DEP - RNG_ARV)  
                 THEN ABS(RNG_DEP - RNG_ARV)  
              ELSE ABS(COL_DEP - COL_ARV)
           END - 1) OVER() AS TOTAL_CASES_TRAVERSEES  
FROM  T  
ORDER BY 1, 2, 3;

Bilan :


FOU   :   560 mouvements différents,   784 cases traversées
ROI   :   896 mouvements différents, 1 792 cases traversées
DAME  : 1 456 mouvements différents, 2 576 cases traversées
ROI   :   420 mouvements différents,     0 cases traversées
CAVAL :   240 mouvements différents,     0 cases traversées
PION  :   308 mouvements différents,    44 cases traversées  
------------------------------------------------------------
TOTAL : 3 880 mouvements différents, 5 196 cases traversées  
Ajoutons les roques, soit 4 mouvements, 5 cases traversées :  
        3 884 mouvements différents, 5 201 cases traversées

Table des mouvements :
Si codifié en smallint pour la pièce, la case départ et la case d’arrivée, cela fait : 6 octets par mouvements, soit : 23 304 octets. Pour PostGreSQL comme pour SQL Server cela ne représente que 3 pages de données d’une table !
Même sans index, la vérification d’un mouvement est instantanée !

Table des déplacements :
Si codifié en smallint pour la pièce, la case départ, la case d’arrivée et la case traversée, cela fait : 8 octets par déplacements, soit 41 608 octets.
Pour PostGreSQL comme pour SQL Server cela représente 6 pages de données d’une table, et avec un index, la vérification d’un mouvement n’a besoin de lire que 2 pages.
La vérification du déplacement est instantanné !


--------
Frédéric Brouard, SQLpro - ARCHITECTE DE DONNÉES, http://sqlpro.developpez.com/
Expert bases de données relationnelles et langage SQL. MVP Microsoft SQL Server
www.sqlspot.com : modélisation, conseil, audit, optimisation, tuning, formation
* * * * *  Enseignant CNAM PACA - ISEN Toulon - CESI Aix en Provence  * * * * *

MVP Microsoft SQL Server

Une réflexion au sujet de « Échec et SQL »

Laisser un commentaire