Forums des Zéros

21 mai 2021 à 19:25:33

Et en plus ton exemple est solvable en mode taquin «classique»

22 mai 2021 à 3:41:36

Je n'ai pas étudié ton code, mais ce que dit White Crow me laisse croire que tu places les jetons à leur place au début et tu les mélanges ensuite.
Puis tu essaies de jouer?
Certains les place de façon aléatoire au début, mais il arrive que des combinaisons soient impossibles à résoudre.

Le Tout est souvent plus grand que la somme de ses parties.

22 mai 2021 à 10:29:44

PierrotLeFou a écrit:

Je n'ai pas étudié ton code, mais ce que dit White Crow me laisse croire que tu places les jetons à leur place au début et tu les mélanges ensuite.

Oui, c'est cela.

PierrotLeFou a écrit:

Certains les place de façon aléatoire au début, mais il arrive que des combinaisons soient impossibles à résoudre.

Oui, sur la totalité des position possible, il y en a la moitié de résolvable et la moitié de non résolvable. Mais je n'ai pas regardé l'algo qui permet de dire si une combinaison est résolvable ou pas. J'ai pas trop voulu me cassé la tête.

drx

22 mai 2021 à 10:38:08

Joli.

En fait ça me fait un peu flipper de voir comme les choses peuvent être plus simples quand on s'appuie sur les OS et à quel point je n'y connais que dalle en lib system.

ça me fait penser à la fois où je me suis laissé tenté par Unity et que j'ai fait en 5 heures ce que je ne ferai jamais avec ma lib mitonnée à feux doux depuis 10 ans. Mais le C# n'est manifestement pas mon truc...

En tout cas, c'est un très bel exemple qui me donne tort lorsque j'affirme (souvent) que le C n'est pas forcément le meilleur moyen lorsqu'on veut surtout arriver à ses fins.

Bravo.

Bonhomme !! | Jeu de plateforme : Prototype.

22 mai 2021 à 11:13:08

rouloude a écrit:

PierrotLeFou a écrit:

Certains les place de façon aléatoire au début, mais il arrive que des combinaisons soient impossibles à résoudre.

Oui, sur la totalité des position possible, il y en a la moitié de résolvable et la moitié de non résolvable. Mais je n'ai pas regardé l'algo qui permet de dire si une combinaison est résolvable ou pas. J'ai pas trop voulu me cassé la tête.

L'algo pour vérifier qu'une position est résoluble n'est pas hyper compliqué et se généralise bien à tous les puzzles N×N.
Ce qui peut être intéressant dans ce genre d'exercice est de construire un solveur.

fun facts:

Le plus grand nombre de mouvement requis pour résoudre un taquin solvable est 80. Il existe 17 positions (normalisées) qui nécessitent exactement 80 mouvements. Il faut en moyenne 52,6 mouvements pour gagner.
Il existe un algorithme en 12 étapes «adapté aux humains» pour résoudre les taquins.
Il y a 3520 positions qui sont également des carrés magiques ^_^

22 mai 2021 à 13:44:52

drx a écrit:

En tout cas, c'est un très bel exemple qui me donne tort lorsque j'affirme (souvent) que le C n'est pas forcément le meilleur moyen lorsqu'on veut surtout arriver à ses fins.

La programmation en utilisant directement l'API Win32 n'est plus très utilisée de nos jours, et bien évidement ça ne fonctionne que sous Windows.

Mais ça fonctionne sous toutes les versions de Windows depuis Windows 95 (à condition de ne pas utiliser de fonctions de API trop récentes).

22 mai 2021 à 14:14:31

@rouloude:
En regardant ta fonction Init(), je me rend compte que tu échanges toujours la case vide avec une autre case.
J'en ai fait un copier-coller et j'ai fait de petits tests. C'est assez bien mélangé.
Il arrive que la case vide ne soit pas à la place attendue à la fin (3,3)
Forcément tu pourrais résoudre le jeu. Tu n'aurais qu'à faire les opérations dans l'ordre inverse.
Je n'ai pas dit que ce serait la solution optimale, mais une solution possible.
Il faudrait que je regarde du côté des solveurs.
j'ai déjà gribouillé de petites fonctions pour décaler une ligne/colonne au complet (ou moins).

Le Tout est souvent plus grand que la somme de ses parties.

22 mai 2021 à 14:21:51

PierrotLeFou a écrit:

@rouloude:
En regardant ta fonction Init(), je me rend compte que tu échanges toujours la case vide avec une autre case.

C'est cela, je mélange comme on mélangerait un vrai Taquin en bois ou en plastique.

Il me semble (je n'y ai pas trop regardé) que si tu inverse deux cases pleine cote à cote, il devient insolvable.

22 mai 2021 à 14:28:43

Si on regarde sur un jeu 2x2, ça semble évident:
AB
C
==
CB
A
Je ne vois pas comment faire tourner pour replacer dans le bon ordre.

Le Tout est souvent plus grand que la somme de ses parties.

22 mai 2021 à 23:09:40

J'ai fait un effort, j'ai mis des nombre à la place des lettres. Et la case vide en noir.

#include <windows.h>

#define GET_X_LPARAM(lp) ((int)(short)LOWORD(lp))
#define GET_Y_LPARAM(lp) ((int)(short)HIWORD(lp))
#define MoveTo(hdc,x,y) MoveToEx(hdc,x,y,NULL)

#define IDM_QUIT 100
#define IDM_NEW 101

#define NBC 4
#define LARG 64

int tab[NBC][NBC];

void exchange(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void Play(int y, int x)
{
    if(y>0 && tab[y-1][x]==0) exchange(&tab[y][x], &tab[y-1][x]);
    if(x>0 && tab[y][x-1]==0) exchange(&tab[y][x], &tab[y][x-1]);
    if(y<NBC-1 && tab[y+1][x]==0) exchange(&tab[y][x], &tab[y+1][x]);
    if(x<NBC-1 && tab[y][x+1]==0) exchange(&tab[y][x], &tab[y][x+1]);
}

void Init()
{
    int x = NBC-1;
    int y = NBC-1;

    for(int i=0; i<NBC*NBC; i++) *(tab[0]+i)=i+1;
    tab[NBC-1][NBC-1]=0;

    for(int i=0; i<10000; i++)
    {
        int rdv=rand()%4;
        if(rdv==0 && y>0)
        {
            exchange(&tab[y][x], &tab[y-1][x]);
            y--;
        }
        if(rdv==1 && x>0)
        {
            exchange(&tab[y][x], &tab[y][x-1]);
            x--;
        }
        if(rdv==2 && y<NBC-1)
        {
            exchange(&tab[y][x], &tab[y+1][x]);
            y++;
        }
        if(rdv==3 && x<NBC-1)
        {
            exchange(&tab[y][x], &tab[y][x+1]);
            x++;
        }
    }
}

LRESULT CALLBACK MainWndProc(HWND hwnd, UINT uMsg, WPARAM wParam, LPARAM lParam)
{
    switch (uMsg)
    {
    case WM_CREATE:
    {
        srand(GetTickCount());
        Init();
        return 0;
    }

    case WM_COMMAND :
        if(LOWORD(wParam) == IDM_QUIT) PostMessage(hwnd, WM_CLOSE,0,0);
        if(LOWORD(wParam) == IDM_NEW)
        {
            Init();
            InvalidateRect(hwnd, NULL, FALSE);
        }
        return 0;

    case WM_CLOSE :
        DestroyWindow(hwnd);
        return 0;

    case WM_LBUTTONUP:
    {
        int x = GET_X_LPARAM(lParam)/LARG;
        int y = GET_Y_LPARAM(lParam)/LARG;
        if(x<NBC && y<NBC) Play(y, x);
        InvalidateRect(hwnd, NULL, FALSE);
        return 0;
    }

    case WM_PAINT:
    {
        LOGFONT lf= {0};
        ZeroMemory(&lf, sizeof(LOGFONT));
        lstrcpy(lf.lfFaceName, "Arial");
        lf.lfHeight = LARG/2;
        lf.lfWeight = FW_BOLD;
        HFONT nbfont = CreateFontIndirect(&lf);

        HPEN hpen = CreatePen(PS_SOLID, 2, 0x00000000);
        RECT rect;
        GetClientRect(hwnd, &rect);

        PAINTSTRUCT ps;
        HDC hdc = BeginPaint(hwnd, &ps);
        HDC hdcDB = CreateCompatibleDC(hdc);
        HBITMAP bmDB = CreateCompatibleBitmap(hdc, rect.right, rect.bottom);
        SelectObject(hdcDB, bmDB);
        FillRect(hdcDB, &rect, GetStockObject(WHITE_BRUSH));

        SelectObject(hdcDB,hpen);
        for(int i=0; i<=NBC; i++)
        {
            MoveTo(hdcDB, 0, i*LARG);
            LineTo(hdcDB, NBC*LARG, i*LARG);
            MoveTo(hdcDB, i*LARG, 0);
            LineTo(hdcDB, i*LARG, NBC*LARG);
        }

        SelectObject(hdcDB, nbfont);
        for(int j=0; j<NBC; j++)
            for(int i=0; i<NBC; i++)
            {
                RECT caseRect= {i*LARG, j*LARG, i*LARG+LARG, j*LARG+LARG};
                char pion[3];
                int strsize = 1;
                wsprintf(pion, "%d", tab[j][i]);
                if(tab[j][i]>9) strsize = 2;
                DrawText(hdcDB, pion, strsize, &caseRect,
                                        DT_SINGLELINE | DT_CENTER | DT_VCENTER);
                if(tab[j][i]==0)
                {
                    SelectObject(hdcDB, GetStockObject(DKGRAY_BRUSH));
                    Rectangle(hdcDB, caseRect.left, caseRect.top,
                                               caseRect.right, caseRect.bottom);
                }
            }

        BitBlt(hdc, 0, 0, rect.right, rect.bottom, hdcDB, 0, 0, SRCCOPY);

        DeleteDC(hdcDB);
        DeleteObject(bmDB);
        EndPaint(hwnd, &ps);
        DeleteObject(nbfont);
        DeleteObject(hpen);
        return 0;
    }

    case WM_DESTROY :
        PostQuitMessage(0);
        return 0;

    default :
        return DefWindowProc(hwnd, uMsg, wParam, lParam);
    }
}

int WINAPI WinMain(HINSTANCE hinstance, HINSTANCE hPrevInstance,
                                                  LPSTR lpCmdLine, int nCmdShow)
{
    WNDCLASS wc = {0};
    wc.lpfnWndProc = MainWndProc;
    wc.hInstance = hinstance;
    wc.hCursor = LoadCursor(NULL, IDC_ARROW);
    wc.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
    wc.lpszClassName = "MaWinClass";
    RegisterClass(&wc);

    HMENU hSousMenu = CreateMenu();
    AppendMenu(hSousMenu, MF_STRING, IDM_NEW, "Nouvelle partie");
    AppendMenu(hSousMenu, MF_STRING, IDM_QUIT, "Quitter");
    HMENU hMenu  = CreateMenu();
    AppendMenu(hMenu, MF_POPUP, (UINT)hSousMenu, "Fichier");

    RECT winRect;
    SetRect(&winRect, 0, 0, LARG*NBC, LARG*NBC);
    AdjustWindowRect(&winRect, WS_CAPTION, TRUE);

    HWND hwnd = CreateWindow("MaWinClass", "Taquin",
                 WS_SYSMENU | WS_CAPTION | WS_MINIMIZEBOX,
                    CW_USEDEFAULT, CW_USEDEFAULT,
                       winRect.right-winRect.left, winRect.bottom-winRect.top,
                                                  NULL, hMenu, hinstance, NULL);

    ShowWindow(hwnd, nCmdShow);
    MSG msg;
    while(GetMessage(&msg, NULL, 0, 0)) DispatchMessage(&msg);
    return msg.wParam;
}

edit : modifications mineur du code.

-
Edité par rouloude 25 mai 2021 à 23:02:10

23 mai 2021 à 7:15:37

rouloude a écrit:

[...]

Il me semble (je n'y ai pas trop regardé) que si tu inverse deux cases pleine cote à cote, il devient insolvable.

En effet, la solvabilité dépend de la parité du «nombre d'inversions» ; informellement, une inversion c'est un nombre qui apparaît avant un nombre plus petit que lui en considérant le taquin linéaire (on lit ligne après ligne). Inverser deux pièces adjacente modifiera la parité. Si, pour le taquin, on numérote les lignes 0,1,2,3 alors pour qu'il soit solvable, il faut et il suffit que la parité du nombre d'inversions soit opposée à la parité de la ligne contenant le blanc (ou le noir lol).

23 mai 2021 à 18:13:19

Si vous n'avez pas la flemme pour résoudre le taquin, ce lien pourrait être intéressant:
http://www.mpechaud.fr/scripts/parcours/testtaquin.html

Le Tout est souvent plus grand que la somme de ses parties.

1 juin 2021 à 6:53:06

@rouloude:
Au lieu d'avoir une fonction exchange, on aurait pu le faire avec une macro.
L'appel aurait été évidemment différent:
au lieu de:
exchange(&a, &b)
on écrirait:
exchange(a, b)
avec la définition:
#define exchange(a,b) {char t=a; a=b; b=t;}

Le Tout est souvent plus grand que la somme de ses parties.

1 juin 2021 à 7:58:00

Ce n'est jamais une bonne idée de remplacer une fonction par une macro. Si tu veux un effet macro alors tu peux définir la fonction comme étant static inline.

1 juin 2021 à 11:43:05

PierrotLeFou a écrit:

@rouloude:
Au lieu d'avoir une fonction exchange, on aurait pu le faire avec une macro.

Ça n'a pas vraiment d’intérêt. Les macros ça peut être utile pour simplifier du code, mais pour remplacer des fonctions ? bof !

1 juin 2021 à 17:34:16

Dans le cas du taquin, ça n'a sans doute aucun intérêt.
Je fais actuelement des tests de performances sur différents algorithmes de tri où les échanges sont nombreux.
Dans les tris, on nous parle toujours du nombre de comparaisons, mais on néglige le nombre de déplacements.
Même si la différence n'est pas énorme entre une fonction et du code in-line, elle est non négligeable.

Le Tout est souvent plus grand que la somme de ses parties.

1 juin 2021 à 18:03:33

Fait le test avec une fonction static inline …

tu claques la définition dans un header que tu inclue là où tu en as besoin, et cela fait kl'effet d'une macro : les compilos modernes (gcc/clang) ne produisent pas de code d'appel de fonction et l'inline (sauf si tu demandes le contraire).

Tu as tous les avantages des fonctions (check des types, etc …) et des macros (inlining) sans le défaut des macros … que se passe-t-il si tu appelles la tienne ainsi :

exchange(a++,--b);