Aide, résolution d'un taquin

Bonjour,
Dans le cadre d'un projet, je doit élaborer une grille de taquin résoluble, et pouvoir effectuer le déplacement des cases, et ensuite concevoir la partie graphique.
Pour la première partie c'est bon, mais je galère un peu sur le déplacement des cases.
Voici ce que j'ai déjà fait, en fait, on fait une grille de 3 par 3, mais on rajoute une colonne et une ligne, je pense qu'il faut la remplir de 1 pour éviter la confusion avec le déplacement de la case 0, je vous laisse regarder ;

#include <stdio.h>
#include "hasard.h"
#include "graphsimple.h"
#define  TAILLE 3 /* nombre de lignes et colonnes du taquin*/
#define NBMIN 0
#define NBMAX 8

#define VRAI 1
#define FAUX 0


      /*Sous prog*/
      
void remplir(int taquin[TAILLE+2][TAILLE+2]);
void afficher(int taquin[TAILLE+2][TAILLE+2]);
void deplacer(int taquin[TAILLE+2][TAILLE+2]);


     /*Prog principal*/

int main(void){

   int taquin[TAILLE+2][TAILLE+2];
   /*int dejatire[TAILLE*TAILLE];*/
  
   remplir(taquin);
   afficher(taquin);
   deplacer(taquin);
    
return 0;
}


     /*Corps sous prog*/

     /*Remplissage du taquin*/

void remplir(int taquin[TAILLE+2][TAILLE+2]){
   int i, j;
   int dejatire[TAILLE*TAILLE];
  
      for(i=0 ;i<=TAILLE*TAILLE-1;i++){
        dejatire[i]=FAUX;
      }
      for(i=1 ;i<=TAILLE;i++){
         for(j=1;j<=TAILLE;j++){
           do{
              taquin[i][j]=hasard(NBMIN, NBMAX);
           }
      
           while(dejatire[taquin[i][j]]==VRAI);
                dejatire[taquin[i][j]]=VRAI;
           }
        }
      }      


      /*Affichage taquin*/

void afficher(int taquin[TAILLE+2][TAILLE+2]){
  
   int i,j;
  
   for(i=1; i<=TAILLE; i++){
      for(j=1; j<=TAILLE; j++){
              
         printf("%d ", taquin[i][j]);
        
      }
      printf("\n");
   }
}
            
  
  
  /*Deplacement des cases du taquin*/

void deplacer(int taquin[TAILLE+2][TAILLE+2]){
   int i, j;
   int vide;
  
   printf("Selectionnez la case a deplacer :\n");
   scanf("%d %d", &i, &j);
      
      
   if(taquin[i][j]==0){
        
       printf("Selectionnez une case different de 0 \n");
       scanf("%d %d", &i, &j);
    
   }


Jusque là, ça marche, et après je bloque...
Merci et bonne journée :

Je n'ai pas de solution pour toi, mais j'ai lu un truc hier sur le jeu de taquin.  Celui qui l'a inventé avait promis une prime de 10.000$ à celui qui réussirait à résoudre le problème avec le jeu de 4X4 "initialisé" avec des chiffre, tous dans l'ordre, sauf, le 14 et le 15 inversés.  Personne n'a gagné, parce qu'il paraît que c'est la seule solution impossible...  Le testes-tu ?  Je ne sais pas si c'est également le cas avec un 3X3...