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 ;
}
Comment pour programmer un sudoku (cour védio)
