ecriture d'un programme pour SUDOKU Fermé

Question

Bonjour
j'ai quelques notions de programmation, et je voudrai ecrire un petit programme pour resoudre les SUDOKU!
1) quel langage simple sur PC puis-je utiliser?
2)est-il possible de se procurer gratuitement le compilateur adéquat? (cobol ou autre??)
3)y-a-t-il quelqu'un qui a deja fait ce type de programme?
MERCI à toutes et à tous de me lire
si quelqu'un pouvait m'apporter une petite aide, je lui en serai tres reconnaissant!!
à bientôt

TAMZA · Accepted Answer

Bonjour ,je suis un etudiant du FST de TUNIS, j ais deja programmer en C la solution des problemes SODUKU .
Je vous dits,en tant que future ingenieur, que la conception est plus importante dans ce genre de problemes.
Voici a quoi peut ressembler la conception de ce programme:
1- Balayer chaque sousmatrice (ou tableau) 3*3 a la recherche d un element nul
2-Associer a chaque case vide trouvee une structure contenant un tableau 'V' de taille 9 de probabilitees initialisee a 0
3-Balayer les deux ligne et colonne (du SODUKU 9*9)correspondants a l element nul trouvee : si elles ne contiennent pas un certain chiffre 'a' la case de meme rang de 'V' recoit 1
4-Iterer ce processus jusqu a la trouvaille d un vecteur(ou tableau 'V') ne contenant qu un seule element egale a 1,de ce fait la case correspondante a ce tableau 'V' recoit la valeur du rang contenant ce 1
5-Iterer ces 4 etapes tant de fois necessaires en fonction du complexitee du SODUKU (mon programme realise de 3 a 7 iterations)

En fin ,je m excuse pour ne pas entrer dans les details structurelles ,j ais l honneur de vous repondre ,contactez moi ,et merci.

arth · Answer

Bonjoir

alors le langage je dirais que tu peux le faire dans n'importe lequel, mais bon étant adepte du c et java, je ne saurais que te conseillais ceux-la. Pour le C tu as le compilateur Devc++ qui est gratuit ( http://www.bloodshed.net ), et pour java tu as le compilateur Eclipse, gratuit également ( http://www.ecipse.org ) .

Je te conseille aussi le site http://www.cppfrance.com , et sur lequel tu as des sources en c++ sur la résolution du sudoku. Tu peux je pense t'en inspirer pour réaliser ton programme, et voir meme améliorer l'algorithme

Bonne nuit

kilian · Answer

Sur cette adresse il ya un implémentation en C et une autre en Python.
C'est fait par Rusty Russel (le concepteur principal du Firewall de Linux)
http://ozlabs.org/~rusty/index.cgi/tech/2005-06-20.html

Bonne chance, ça a l'air complexe...

arth · Answer

Manque juste la chtite bibliothèque de départ, mais sinon ca semble intéressant.

WADA · Answer

Bonjour
merci pour votre reponse....mais j'ai mal posé mon problème et vous prie de m'en excuser!
Je vais donc reformuler mon problème en tachant d'être plus clair
1) pouvez vous me dire quel est à votre avis le langage le plus adapté à ces differentes contraintes:
- compilateur gratuit à telecharger
- pour PC windows XP
- Possibilite de faire paraitre une grille (pour mon SUDOKU)
d'y inscrire des chiffres, et de les recuperer dans mon programme
-possibilité de faire reapparaitre la grille complétée avec d'autres chiffres
-apprentissage aisé du langage et documentation gratuite
si possible en FRANçAIS!!

Peut-etre suis-je en train de trop en demander et je m'en excuse!!

Merci à vous tous de me lire!
à bientot

arth · Answer

Euh alors on te l'a un peu donné la réponse, les contraintes sont un peu bizarre, car tu peux aussi bien faire de l'affichage graphique en c, java, python ou autre. les compilateurs gratuits existent autant pour java, c , python,delphi,pascal . Je crois qu'après c'est à toi de choisir. Mais pour moi faire une interface est plus simple en java qu'en c en tout cas. Por les autres langages je ne sais pas. Pour les tutoriaux sur tous ces langages en francais je te conseile le site http://www.developpez.com

Voila

kilian · Answer

Une interface graphique en Delphi ça me semble un bon choix...

attila · Answer

Bonjour moi je dois creer une solveuse de sudoku en language C mais le pb c'est que je ne sais pas par ou commencer, Vous n'avez pas un algorithme a me passer?Merci!

random · Answer

j'ai écrit un solver de sudoku
je me suis servi de vba avec interface excel
pour les algos voir wikipedia
le plus simple à programmer est assez facile on construit un array de 9x9 dans lequel on met "123456789"
on ajoute les contraintes ainsi si un 1 est donné en(1,1) on remplace le "123456789" par "1"
on propage les contraintes en lignes en colonnes et en carré pour toutes les cellules(?,1) différentesde (1,1) on ôte de "123456789" "1" et pour toutes les cellules (1,?) on fait de même, on continue avec les cellules de (1,1) à (3;3)
on reprend la grille depuis le début tant qu'elle évolue
ensuite on prend en compte les contraintes implicites un chiffre
par colonne par ligne par carré et leurs combinaisons
ce modèle doit itérer tant qu'on fait évoluer la grille
à ce moment soit la grille est complète (toutes les grilles faciles
sont résolues avec moins de chiffres entrés que le problème n'en donne)
sinon le plus payant est de procèder par essai erreur à partiir des
doublets restants

Jack · Answer

Bonsoir à tous.Alors moi j'ai fait un petit site, et pour attirer les visiteurs je voudrais y inclure le jeu du Sudoku. Comment faire ?Merci d'avance pour vos réponses.

TLa · Answer

Salut,

J'ai codé une page html / javascript pour m'aider à resoudre les sudoku :
http://www.larmoire.info/jeux/sudoku/ (très gourmand en cpu au démarrage)

la version en C++ : http://www.larmoire.info/jeux/sudoku/sudoku.cpp
compilé avec djgpp (un gcc pour windows) ou gcc sous linux
l'interface est en ligne de commande

puis une surcouche à l'excellent site https://www.hugedomains.com/domain_profile.cfm?d=koalog&e=com
qui a le défaut d'afficher les chiffres mal placés par rapport à la solution et non pas ceux qui enfraignent les regles,
http://www.larmoire.info/jeux/sudoku/koalog.tcl

shryke2a · Answer

ba en fait je voudrais savoir où apprendre la programmation mais quand je dis apprendre c'est pas un tuto c'est un truc aprés lequel je pourrais me débrouilller tout seul!

Brice · Answer

Bonjour,

http://phpsudo.free.fr

Sudoku Open source en php et javascript.  Grilles 4*4, 6*6, 8*8, 9*9, 10*10, 12*12, 14*14 et 16*16 chiffres et lettres ! Solution unique, grilles illimitées et 3 niveaux de difficultés... A suivre...

Je le trouve pas mal

henrin · Answer

Ci-joint le code du solveur (hors IHM) :

henrin · Answer

voici le source :

/*====================================================================================== SUDOKU ==

Global:

kuMain main grid

Basic operations:

gridClear
gridCopy
cellDisplay part of gridDisplay
gridDisplay show a grid
gridGet read and check the displayed grid

Grid computing:

gridCheck checks if a grid is valid
gridPossible preliminary computatiion for solving
gridExtract partial solve
gridFill partial solve
gridSolve recursive solve the input grid

Other functions:

msg

Functions not included in this listing:

fileI/O
user interface
================================================================================================*/

#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdarg.h>

#define STD 2
#define ERR 1
#define FATAL 0

#define SINGLE 1
#define SHOW 2
#define SEARCH 4

#define N 3 /* SUDOKU dimension */
#define N2 (N * N)
#define N4 (N2*N2)

#define SOLMAX 10 /* maximum number of solutions */

/* sudoku grid definition */
typedef char KU[N2][N2][N2+1] ; /* if KU[row][col][0] > 0 it is the defined value */
/* else KU[row][col][val]= 1 if val is a possible value */
KU kuMain ;

int gridCheck(KU ku) ;

/*----------------------------------------------------------------------------------------------*/
void msg(int mask, char *fmt,...) /* show std, error or fatal message */
/*----------------------------------------------------------------------------------------------*/
{
char s[1024] = "" ; /* buffer for building the error message */
int s1 = 0 ; /* character or message count */
va_list ap ;

if (mask == ERR)
{
Beep() ;
s1 = sprintf(s, "%s", "** ERREUR ** ") ;
}

va_start(ap, fmt) ; /* build the error message */
vsprintf(s + s1, fmt, ap) ;
va_end(ap) ;

/* display message */

switch (mask)
{
case STD :
case ERR :
break ;
case FATAL :
/* display fatal message */
exit(1) ;
}
}

/*===================================================================== BASIC OPERATION & I/O ==*/

/*----------------------------------------------------------------------------------------------*/
void gridClear(KU ku) /* clear only the visible part */
/*----------------------------------------------------------------------------------------------*/
{
int r, c ;
for (r = 0 ; r < N2 ; r++)
for (c = 0 ; c < N2 ; c++)
ku[r][c][0] = 0 ;
}

/*----------------------------------------------------------------------------------------------*/
void gridCopy(KU kuSrc, KU kuDest) /* copy grid kuSrc to kuDest */
/*----------------------------------------------------------------------------------------------*/
{
int r, c ;
for (r = 0 ; r < N2 ; r++)
for (c = 0 ; c < N2 ; c++)
kuDest[r][c][0] = kuSrc[r][c][0] ;
}

/*----------------------------------------------------------------------------------------------*/
void cellDisplay(int r, int c, int v, int bold)
/*----------------------------------------------------------------------------------------------*/
{
char s[2] = " " ;
int color ;
s[0] = v + '0' ;
if (s[0] == '0') s[0] = '\0' ;

/* display text s in the cell at column c and row r */
/* text attribute: bold */
}

/*----------------------------------------------------------------------------------------------*/
void gridDisplay(KU ku) /* display grid on UIR */
/*------------------------------------------------------------------------------------------------
This function displays the source grid (kuMain) with bold characters.
If the solution (ku) is defined (not null), it is displayed with normal characters.
------------------------------------------------------------------------------------------------*/
{
int r, c, v ;
for (r = 0 ; r < N2 ; r++)
for (c = 0 ; c < N2 ; c++)
{
char k = kuMain[r][c][0] ; /* source grid */
int bold = 1 ;
cellDisplay(r, c, k, 1) ;
if (ku && k == 0) /* filled data */
{
k = ku[r][c][0] ;
bold = 0 ;
}
cellDisplay(r, c, k, bold) ;
}
}

/*----------------------------------------------------------------------------------------------*/
int gridGet(KU ku) /* get grid from UIR - result = same as gridCheck() */
/*----------------------------------------------------------------------------------------------*/
{
int e, r, c ;

gridClear(ku) ;
for (r = 0 ; r < N2 ; r++)
for (c = 0 ; c < N2 ; c++)
{
char s[16] ;
int ic ;

/* get the text of the cell at column c and row r */
switch (strlen(s))
{
case 0 :
ic = 0 ;
break ;
case 1 :
ic = s[0] - '0' ;
if (ic >= 1 && ic <= N2) break ;
default :
msg(ERR, "Cellule non valide") ;
return -1 ;
}
ku[r][c][0] = ic ;
}

e = gridCheck(ku) ;
if (e < 0)
msg(ERR, "Grille non valide") ;
return e ;
}

/*============================================================================ GRID COMPUTING ==*/

/*----------------------------------------------------------------------------------------------*/
int gridCheck(KU ku) /* check if a grid is valid */
/*------------------------------------------------------------------------------------------------
This function returns the number of defined cells, and -1 if the grid is not valid.
------------------------------------------------------------------------------------------------*/
{
int b, r, c, rf, cf, v ;
int count[N2 + 1] ; /* index = 1..N2 */
int defined = 0 ;

for (r = 0 ; r < N2 ; r++) /* check values */
for (c = 0 ; c < N2 ; c++)
{
v = ku[r][c][0] ;
if (v < 0 || v > N2)
return -1 ;
if (v > 0)
defined++ ;
}

for (r = 0 ; r < N2 ; r++) /* process rows */
{
for (v = 1 ; v <= N2 ; v++) count[v] = 0 ; /* reset counts */
for (c = 0 ; c < N2 ; c++) /* count defined */
if (v = ku[r][c][0]) count[v]++ ;
for (v = 1 ; v <= N2 ; v++) /* check counts */
if (count[v] > 1)
return -1 ;
}

for (c = 0 ; c < N2 ; c++) /* process columns */
{
for (v = 1 ; v <= N2 ; v++) count[v] = 0 ; /* reset counts */
for (r = 0 ; r < N2 ; r++) /* count defined */
if (v = ku[r][c][0]) count[v]++ ;
for (v = 1 ; v <= N2 ; v++) /* check counts */
if (count[v] > 1)
return -1 ;
}

for (b = 0 ; b < N2 ; b++) /* process blocks */
{
int r1 = N * (b / N) ;
int c1 = (N * b) % N2 ;
for (v = 1 ; v <= N2 ; v++) count[v] = 0 ; /* reset counts */
for (c = c1 ; c < c1 + N ; c++) /* count defined */
for (r = r1 ; r < r1 + N ; r++)
if (v = ku[r][c][0]) count[v]++ ;
for (v = 1 ; v <= N2 ; v++) /* check counts */
if (count[v] > 1)
return -1 ;
}

return defined ; /* grid is valid */
}

/*----------------------------------------------------------------------------------------------*/
int gridPossible(KU ku) /* set and count the possible values */
/*----------------------------------------------------------------------------------------------*/
{
int r, c, v ;
int possible = 0 ; /* counter */

for (r = 0 ; r < N2 ; r++)
for (c = 0 ; c < N2 ; c++)
{
int r1, c1, r2, c2 ;

if (ku[r][c][0]) /* case defined cell */
{
for (v = 1 ; v <= N2 ; v++) /* none are possible */
ku[r][c][v] = 0 ;
continue ;
}

for (v = 1 ; v <= N2 ; v++) /* at first: all are possible */
ku[r][c][v] = 1 ;
for (c1 = 0 ; c1 < N2 ; c1++) /* process row */
{
if (v = ku[r][c1][0])
ku[r][c][v] = 0 ;
}
for (r1 = 0 ; r1 < N2 ; r1++) /* process column */
{
if (v = ku[r1][c][0])
ku[r][c][v] = 0 ;
}
c1 = N * (c / N) ; /* process block */
c2 = c1 + N ;
for ( ; c1 < c2 ; c1++)
{
r1 = N * (r / N) ;
r2 = r1 + N ;
for ( ; r1 < r2 ; r1++)
{
if (v = ku[r1][c1][0])
ku[r][c][v] = 0 ;
}
}
for (v = 1 ; v <= N2 ; v++) /* count the number of possibles */
if (ku[r][c][v]) possible++ ;
}

return possible ;
}

/*----------------------------------------------------------------------------------------------*/
int gridExtract(KU ku) /* extract single possible values */
/*------------------------------------------------------------------------------------------------
Result is the number of found values, or -1 if error
------------------------------------------------------------------------------------------------*/
{
int r, c, v ;
for (r = 0 ; r < N2 ; r++)
for (c = 0 ; c < N2 ; c++)
{
int found = 0 ;
if (ku[r][c][0]) continue ; /* skip defined cells */

for (v = 1 ; v <= N2 ; v++)
{
if (ku[r][c][v])
{
if (found) break ; /* break if > 1 possible */
found = v ;
}
}
if (v <= N2) continue ; /* and skip cell */
if (found == 0)
return -1 ;

ku[r][c][0] = found ;
return 1 ;
}
return 0 ;
}

/*----------------------------------------------------------------------------------------------*/
int gridFill(KU ku) /* insert values */
/*----------------------------------------------------------------------------------------------*/
{
int b, r, c, rf, cf, v ;

for (r = 0 ; r < N2 ; r++) /* process rows */
for (v = 1 ; v <= N2 ; v++) /* search for v */
{
int found = 0 ;
for (c = 0 ; c < N2 ; c++) /* skip if defined */
if (ku[r][c][0] == v)
{
found = 1 ;
break ;
}
if (found) continue ;
for (c = 0 ; c < N2 ; c++) /* count number of possibles */
{
if (ku[r][c][0] == 0 && ku[r][c][v])
{
if (++found > 1) break ;
cf = c ;
}
}
if (found == 1) /* if only one: set value */
{
ku[r][cf][0] = v ;
return 1 ;
}
}

for (c = 0 ; c < N2 ; c++) /* process columns */
for (v = 1 ; v <= N2 ; v++) /* search for v */
{
int found = 0 ;
for (r = 0 ; r < N2 ; r++) /* skip if defined */
if (ku[r][c][0] == v)
{
found = 1 ;
break ;
}
if (found) continue ;
for (r = 0 ; r < N2 ; r++) /* count number of possibles */
{
if (ku[r][c][0] == 0 && ku[r][c][v])
{
if (++found > 1) break ;
rf = r ;
}
}
if (found == 1) /* if only one: set value */
{
ku[rf][c][0] = v ;
return 1 ;
}
}

for (b = 0 ; b < N2 ; b++) /* process blocks */
{
int r1 = N * (b / N) ;
int c1 = (N * b) % N2 ;
for (v = 1 ; v <= N2 ; v++) /* search for v */
{
int found = 0 ;
for (c = c1 ; c < c1 + N ; c++) /* skip if defined */
{
for (r = r1 ; r < r1 + N ; r++)
if (ku[r][c][0] == v)
{
found = 1 ;
break ;
}
if (found) break ;
}
if (found) continue ;
for (c = c1 ; c < c1 + N ; c++) /* count number of possibles */
{
for (r = r1 ; r < r1 + N ; r++)
{
if (ku[r][c][0] == 0 && ku[r][c][v])
{
if (++found > 1) break ;
rf = r ;
cf = c ;
}
}
if (found > 1) break ;
}
if (found == 1) /* if only one: set value */
{
ku[rf][cf][0] = v ;
return 1 ;
}
}
}

return 0 ;
}

/*----------------------------------------------------------------------------------------------*/
int gridSolve(KU ku, int level, int stat) /* solver */
/*------------------------------------------------------------------------------------------------
ku : grid input/output
level : depth of the recursive solver input
stat : search mode - bit fields: SEARCH, SHOW input
result : number of solutions found
------------------------------------------------------------------------------------------------*/
{
static solutionNb ;
int r, c, v ;
int e, found ;

if (level == 0) /* first call */
solutionNb = 0 ;

for (;;) /* direct solver */
{
e = gridCheck(ku) ; /* number of cells defined */
if (e < 0) return 0 ; /* invalid grid */
if (e == N4) /* solution found */
{
solutionNb++ ;
if (solutionNb > SOLMAX) stat = 0 ;

if ((stat & SHOW) && solutionNb > 1)
{
char l[64] ;
sprintf(l, "Voir solution n°% d ?", solutionNb) ;
if (ConfirmPopup(l) == 0) stat = 0 ;
}

if (stat & SHOW) gridDisplay(ku) ;
return solutionNb ;
}

gridPossible(ku) ;
found = gridExtract(ku) ;
if (found < 0) /* case error */
return 0 ;
if (found == 0)
found = gridFill(ku) ;
if (stat & SINGLE)
{
if (found)
{
found = 0 ; /* search last defined */
for (r = 0 ; r < N2 ; r++)
{
for (c = 0 ; c < N2 ; c++)
if (found = ku[r][c][ku[r][c][0]]) break ;
if (found) break ;
}
msg(STD, "Ligne %d, colonne %d : %d", r + 1, c + 1, ku[r][c][0]) ;
}
else
msg(STD, "pas de solution simple") ;
return 0 ;
}
if (found == 0)
break ;
}

found = 0 ; /* hytothesis trial */
for (r = 0 ; r < N2 ; r++) /* search undefined cell */
{
for (c = 0 ; c < N2 ; c++)
if (found = (ku[r][c][0] == 0)) break ;
if (found) break ;
}

for (v = 1 ; v <= N2 ; v++) /* try loop on the possible values */
{
if (ku[r][c][v])
{
KU kuTry ;
ku[r][c][0] = v ;
gridCopy(ku, kuTry) ;
gridSolve(kuTry, level + 1, stat) ;
if ((stat & SEARCH) == 0) return solutionNb ;
}
}

return solutionNb ;
}

fati · Answer

je vous demande de m'aider à ecrire un programme pour resoudre une grille de sudoku en python 
et merci

dave · Answer

j'ai capté un jeu gratuit de sudoku en 3D vraiment pas mal : http://sudoku-3d.com ça devrait t'aider je pense :-)

Ecriture d'un programme pour SUDOKU

17 réponses