Ubuntu-fr

maloq

sudoku solver

bonjour,

Aujourdhui, à mon cours de droit du travail, je séchais lamentablement sur le petit jeu Sudoku (petit jeu japonais de logique assez rigolo). Celui que j'avais devant les yeux était particulièrement velu, et au bout de 3h d'énervement, je décide, non pas d'abandonner, mais de me lancer dans un algo de résolution de ce satané b**** de m**** de jeu.

Ainsi, après 3h d'Xemacs, je suis enfin venu a bout de n'importe quel Sudoku du monde... gnarf!!!! on me la fait pas à moi.

Je me demandais juste: comment faire pour partager ce petit logiciel avec ceux que ce jeu éxaspère aussi? (si ca interesse quelqu'un...)

thom

Re : sudoku solver

Ben tu peux le mettre entre les balises code ici ou sur une page du wiki...

---

-> Ubuntu on a Sony Vaio VNG-FS115B
-> Wificonfig is a little script aimed to ease the switching between networks, for people who have 2 network cards : a wired one and a wireless one.

maloq

Re : sudoku solver

ca roule (faut compiler avec pkg-config gtk+-2.0 gthread-2.0)

#include <stdio.h>
#include <stdlib.h>
#include <gtk/gtk.h>
#include <string.h>

typedef struct _data * pdata;
typedef struct _data
{
  gboolean fin;

  char table[9][9];

  GtkWidget *cases[9][9];
  guint timeout_id;

}Data;


gboolean resoudre(GtkWidget *bouton, GtkWidget *cases[9][9]);
gint popup_message(gchar *message);
gpointer brute_force(gpointer data_);
gboolean fonction_timeout(gpointer data_);
char *itos(char n);
gboolean table_possible(gchar table[9][9],gint ligne, gint colonne);
gboolean recur(gchar table[9][9], gpointer visible);
gboolean charger_fichier(char *nom,GtkWidget *cases[9][9]);

int main (int argc, char **argv)
{
  GtkWidget *fenetre_principale;
  GtkWidget *table;
  GtkWidget *cases[9][9];
  GtkWidget *v_box;
  GtkWidget *bouton_exec;

  gint l,c;

  if (!g_thread_supported ()) g_thread_init (NULL);
  gtk_init(&argc,&argv);

  //la fenetre principale
  fenetre_principale=gtk_window_new(GTK_WINDOW_TOPLEVEL);
  gtk_window_set_title(GTK_WINDOW(fenetre_principale),"EasySudoku");
  gtk_window_set_resizable(GTK_WINDOW(fenetre_principale),FALSE);
  gtk_window_set_position(GTK_WINDOW(fenetre_principale),GTK_WIN_POS_MOUSE);

  //la tabble et les entries
  table=gtk_table_new(9,9,TRUE);
  for(l=0;l!=9;l++)
    for(c=0;c!=9;c++)
      {
	cases[l][c]=gtk_entry_new();
	gtk_widget_set_usize(cases[l][c],20,20);
	gtk_entry_set_max_length(GTK_ENTRY(cases[l][c]),1);
	gtk_table_attach_defaults(GTK_TABLE(table),cases[l][c],l,l+1,c,c+1);
      }

  //le bouton execute
  bouton_exec=gtk_button_new_with_label(" Resoudre! ");

  //la boite verticale
  v_box=gtk_vbox_new(FALSE,3);
  
  //  on remplie la boite
  gtk_box_pack_start(GTK_BOX(v_box),table,TRUE,FALSE,3);
  gtk_box_pack_start(GTK_BOX(v_box),bouton_exec,FALSE,FALSE,3);
  gtk_container_add(GTK_CONTAINER(fenetre_principale),v_box);

  //connection aux signaux
  gtk_signal_connect(GTK_OBJECT(fenetre_principale),"delete_event",GTK_SIGNAL_FUNC(gtk_main_quit),NULL);
  gtk_signal_connect(GTK_OBJECT(fenetre_principale),"destroy_event",GTK_SIGNAL_FUNC(gtk_main_quit),NULL);
  gtk_signal_connect(GTK_OBJECT(bouton_exec),"clicked",GTK_SIGNAL_FUNC(resoudre),cases);


  if(argc==2)
    charger_fichier(argv[1],cases);

  gtk_widget_show_all(fenetre_principale);
  gtk_main();

  return 0;
}



gboolean charger_fichier(char *nom,GtkWidget *cases[9][9])
{
  FILE *fp;
  char tab[81];
  gint l,c,i;
  char texte[2];
  texte[1]='\0';

  if((fp=fopen(nom,"rb"))==NULL)
    {
      g_warning("Impossible d'ouvrir le fichier en lecture\n");
      return FALSE;
    }

  fread(tab,1,81,fp);

  for(i=0,l=0;l!=9;l++)
    for(c=0;c!=9;c++)
      {
	texte[0]=tab[i];
	gtk_entry_set_text(GTK_ENTRY(cases[c][l]),texte);
	i++;
      }

  fclose(fp);
  return TRUE;
}

  

char *itos(char n)
{
  char *retour;
  
  switch (n)
    {
    case 0: retour=""; break;
    case 1: retour="1"; break;
    case 2: retour="2"; break;
    case 3: retour="3"; break;
    case 4: retour="4"; break;
    case 5: retour="5"; break;
    case 6: retour="6"; break;
    case 7: retour="7"; break;
    case 8: retour="8"; break;
    case 9: retour="9"; break;
    default: retour=""; break;
    }

  return retour;
}

gint popup_message(char *message)
{
  GtkWidget *dialog = gtk_message_dialog_new (NULL,
					      GTK_DIALOG_DESTROY_WITH_PARENT,
					      GTK_MESSAGE_INFO,
					      GTK_BUTTONS_CLOSE,
					      "%s",
					      message);
  gtk_dialog_run (GTK_DIALOG (dialog));
  gtk_widget_destroy (dialog);
  
  return 0;
}

gboolean resoudre(GtkWidget *bouton, GtkWidget *cases[9][9])
{
  gint l,c;
  gboolean error=FALSE;
  pdata data = (pdata)g_malloc(sizeof(Data));

  data->fin=FALSE;
  
  for(l=0;l!=9;l++)
    {
      for(c=0;c!=9;c++)
	{
	  data->cases[l][c]=cases[l][c];
	  data->table[l][c]=(char)atoi(gtk_entry_get_text(GTK_ENTRY(cases[l][c])));
	  if(data->table[l][c]<0 || data->table[l][c]>9)
	    {
	      error=TRUE;
	      break;
	    }
	}
      if(error==TRUE) break;
    }
  if(error==TRUE) 
    popup_message("Les champs doivent contenir un chiffre entre 1 et 9, ou etre laisses vides");
  else
    g_thread_create(brute_force,data,FALSE,NULL);

  data->timeout_id=gtk_timeout_add(200,fonction_timeout,data);
    
  return FALSE;
}

gboolean fonction_timeout(gpointer data_)
{
  pdata data=(pdata)data_;
  int l,c;
  char *texte;

  for(l=0;l!=9;l++)
    for(c=0;c!=9;c++)
      {
	texte=itos(data->table[l][c]);
	gtk_entry_set_text(GTK_ENTRY(data->cases[l][c]),texte);
      }

  if(data->fin==TRUE)
    {
      popup_message("ok!");
      return FALSE;
    }
  
  return TRUE;
}



gboolean table_possible(gchar table[9][9],gint ligne, gint colonne)
{
  gint l,c,l2,c2;
  gchar base=table[ligne][colonne];

  table[ligne][colonne]=0;

  //on verifie la grande ligne
  for(l=0;l!=9;l++)
    if(table[l][colonne]==base) return FALSE;

  //la colonne
  for(c=0;c!=9;c++)
    if(table[ligne][c]==base) return FALSE;

  //et enfin la minicase (on se place en haut a droite de la minicase)
  l=ligne-ligne%3;
  c=colonne-colonne%3;
  
  for(l2=l;l2!=l+3;l2++)  
    for(c2=c;c2!=c+3;c2++)
      if(table[l2][c2]==base) return FALSE;

  table[ligne][colonne]=base;

  return TRUE;
}


gboolean recur(gchar table[9][9], gpointer visible)
{
  gchar table_prim[9][9];
  gchar *pt=(gchar *)table;
  gint l,c,cpt;

  memcpy(table_prim,table,81);  //duplique la table
  memcpy(visible,table,81);     //on la recopie pour l'affichage

  //premiere case vide
  for(cpt=0;cpt!=81;cpt++)
    if(pt[cpt]==0) break;

  //tout est rempli on retourne succes (TRUE)
  if(cpt==81) return TRUE;

  //quelle case vide?
  c=cpt%9;
  l=(cpt-c)/9;
  
  //on lui met des valeurs
  for(cpt=1;cpt!=10;cpt++)
    {
      table_prim[l][c]=cpt;
      if(table_possible(table_prim,l,c)==TRUE)
	if(recur(table_prim,visible)==TRUE)
	  return TRUE;
    }

  return FALSE;
}

    

gpointer brute_force(gpointer data_)
{
  pdata data=(pdata)data_;
  gchar table[9][9];

  memcpy(table,data->table,81);
  recur(table,data->table);
  data->fin=TRUE;
  
  return NULL;
}

Dernière modification par maloq (Le 16/12/2005, à 21:38)

HoPHP

Re : sudoku solver

Salut,

tout d'abord bravo pour ton script que je n'ai pas essayé (oui, honte sur moi...). Cela a certainement dû être très intéressant à faire.

Je savais qu'il existait déjà des scripts pas mal et j'ai retrouvé celui auquel je pensais, il faut que tu le testes:

Ksudoku ! (L'installation par paquets pose quelques problèmes... mais tu as l'air de maîtriser la compilation ...)

Il permet plusieurs choses:

* Création selon plusieurs paramètres

* Sudoku en 3 dimensions

* Résolution
* Introduction de Sudokus personnalisés (pour les résoudre)
etc...

Bref. Tout ça pour dire que ce que tu as fait, c'est très bien, tu t'es sûrement défoulé (ceci n'a pas de connotation négative!) à faire ton script, mais en fait, ça existe déjà, en "mieux". Bref, dommage...

@+, HoPHP

P.S. J'ai peur de ne pas me faire comprendre: c'est cool ce que tu as fait, mais ça existe malheureusement déjà.

---

Merci de ne pas jeter d'arguments aux trolls qui se trouvent dans la fosse.
HoPHP est mort, vive OdyX

maloq

Re : sudoku solver

:-)

nop, t'inquiète, pour moi, l'interet était juste intellectuel, le fait que ca existe deja, meme en mieux, ne m'interesse pas, juste le fait que je suis capable de le faire... je voulais juste en faire profiter.
Cela dit, si ca existe en mieux autre part, tant mieux pour tout le monde, mon mesage ne sert alors a rien :-D

PS: si il y a d'autres codeurs fous fans de defis algorithmiques... je suis preneur

HoPHP

Re : sudoku solver

Défi (juste le temps que je t'en trouve un autre...): Coder la fonction "Plus petit dénominateur commun" en deux lignes de code.

Sinon, les projets dans lesquels tu pourrais te lancer pour le bien de l'humanité (je te laisse le soin des recherches...).

GNU/Hurd
Encodeur Ogg Vorbis en arithmétique entière
kernel GNU/Linux

Bref, le choix est vaste

---

Merci de ne pas jeter d'arguments aux trolls qui se trouvent dans la fosse.
HoPHP est mort, vive OdyX

m+rh-e

Re : sudoku solver

Défi (juste le temps que je t'en trouve un autre...): Coder la fonction "Plus petit dénominateur commun" en deux lignes de code.

Pour du c++, le travail est également déja fait
http://www.boost.org/libs/math/doc/comm … ml#gcd_obj

Dernière modification par m+rh-e (Le 19/12/2005, à 19:52)

Eric P.

Re : sudoku solver

Au sujet de l'installation de KSudoku, je conseille la méthode suivante:
- télécharger ksudoku-0.3-1.i386.rpm sur http://sourceforge.net/projects/ksudoku/
- sudo alien -d ksudoku-0.3-1.i386.rpm
- sudo dpkg -i ksudoku_0.3-2_i386.deb