View original (French)

Writing a Sudoku Program

wada -  
 le7amdon -
Hello
I have some programming knowledge, and I would like to write a small program to solve SUDOKU!
1) What simple programming language for PC can I use?
2) Is it possible to obtain the appropriate compiler for free? (COBOL or another??)
3) Is there anyone who has already created this type of program?
THANK YOU all for reading me
If someone could provide me with a little help, I would be very grateful!!
See you soon

17 réponses

Réponse 1 / 17
TAMZA
 
Hello, I am a student at FST Tunis, and I have already programmed the solution to SODUKU problems in C.
I tell you, as a future engineer, that design is more important in this kind of problem.
Here is what the design of this program might look like:
1- Sweep each 3*3 submatrix (or array) in search of a null element.
2- Associate a structure with each empty cell found, containing an array 'V' of size 9 of probabilities initialized to 0.
3- Sweep the two rows and columns (of the 9*9 SODUKU) corresponding to the found null element: if they do not contain a certain digit 'a', the cell of the same rank in 'V' receives 1.
4- Iterate this process until a vector (or array 'V') is found that contains only one element equal to 1; thus, the corresponding cell of this array 'V' receives the value of the rank containing this 1.
5- Iterate these 4 steps as many times as necessary depending on the complexity of the SODUKU (my program performs between 3 and 7 iterations).

In the end, I apologize for not going into structural details, I am honored to respond to you, please contact me, and thank you.
10
fleez
 
Hi Tamza,
I have to do a computer project on programming a Sudoku in EXCEL/VBA or JavaScript.
Have you ever done something like this and could you help me?
Thank you very much in advance.
0
imen
 
Désolé, je ne peux pas aider avec ça.
0
samanthaoups Posted messages 13 Status Membre
 
Good evening Hamza
I am expected to create a program in C that solves a Sudoku
That is to say, I need to create a grid and solve it
If possible, I would appreciate your help and guidance on how to proceed because honestly, I don't know where to start :s
Thank you in advance Tamza
0
le7amdon > samanthaoups Posted messages 13 Status Membre
 
Hello
Just create functions or procedures that perform the specified functions, each action required at each step announced by Hamza should be presented as a function or procedure that achieves the goal. But here, it's important to consider the number and types of parameters that may exist each time in the functions.
Good job :)
0
rody
 
Hello RAMKA, it's Rodys. I'm a computer science student at IST GABON and I have a project that the teacher asked us to research on the web, and apparently you know about it.
Here, could you send me the C program for solving a Sudoku grid? I'll make an effort to understand it (with comments, if possible). Please send it to my email.

Thank you again.
0
Réponse 2 / 17
kilian Posted messages 8675 Registration date   Status Modérateur Last intervention   1 526
 
At this address, there is an implementation in C and another in Python.
It was done by Rusty Russell (the main designer of the Linux Firewall)
http://ozlabs.org/~rusty/index.cgi/tech/2005-06-20.html

Good luck, it looks complex...
3
lami20j Posted messages 21506 Registration date   Status Modérateur, Contributeur sécurité Last intervention   3 570
 
Salut Kilian,
<ital>
It seems complex...</ital> you're right.

Take a look at what a Perl code for Sudoku says (version 4 and 3 lines of code).

http://www.ecclestoad.co.uk/blog/2005/05/25/sudoku_solver_in_four_lines.html
0
kilian Posted messages 8675 Registration date   Status Modérateur Last intervention   1 526
 
Even worse :-)
0
Moi > kilian Posted messages 8675 Registration date   Status Modérateur Last intervention  
 
Personally, I recommend HTML/JavaScript, it's simple and doesn't require a compiler.
I spent a few hours doing it.
0
Réponse 3 / 17
kilian Posted messages 8675 Registration date   Status Modérateur Last intervention   1 526
 
A graphical interface in Delphi seems like a good choice to me...
3
Réponse 4 / 17
Jack
 
Good evening everyone.

So I've created a small website, and to attract visitors I would like to include a Sudoku game. How can I do that?

Thank you in advance for your replies.
3
Réponse 5 / 17
arth Posted messages 84 Registration date   Status Contributeur Last intervention   1 293
 
Hello

So for the language, I would say you can do it in any of them, but since I'm an advocate of C and Java, I can only recommend those two. For C you have the DevC++ compiler which is free ( http://www.bloodshed.net ), and for Java you have the Eclipse compiler, also free ( http://www.eclipse.org ).

I also recommend the site http://www.cppfrance.com , which has C++ sources on Sudoku solving. I think you can get inspired by it to create your program and even improve the algorithm

Good night
2
Réponse 6 / 17
TLa Posted messages 57 Status Membre 12
 
Hello,

I coded an HTML/JavaScript page to help me solve Sudoku:
http://www.larmoire.info/jeux/sudoku/ (very CPU-intensive at startup)

The C++ version: http://www.larmoire.info/jeux/sudoku/sudoku.cpp
compiled with djgpp (a gcc for Windows) or gcc under Linux
the interface is command-line based

then a layer on top of the excellent site https://www.hugedomains.com/domain_profile.cfm?d=koalog&e=com
which has the downside of displaying incorrectly placed numbers compared to the solution and not those which break the rules,
http://www.larmoire.info/jeux/sudoku/koalog.tcl
2
kilian Posted messages 8675 Registration date   Status Modérateur Last intervention   1 526
 
I coded an HTML / JavaScript page to help me solve sudoku:
http://www.larmoire.info/jeux/sudoku/ (very CPU-intensive at startup)

Pretty…
0
TLa Posted messages 57 Status Membre 12
 
the koalog overlay has changed its address

http://www.larmoire.info/jeux/sudoku/koalog/
0
amina
 
Please, can you provide the source code of this program that you made? Thank you :)
0
Réponse 7 / 17
shryke2a
 
Well, actually, I would like to know where to learn programming, but when I say learn, I don't mean a tutorial; I mean something after which I could manage on my own!
2
Réponse 8 / 17
henrin
 
Here is the code of the solver (excluding the GUI):
2
Réponse 9 / 17
henrin
 


/*====================================================================================== 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", "** ERROR ** ") ;
}

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, "Invalid cell") ;
return -1 ;
}
ku[r][c][0] = ic ;
}

e = gridCheck(ku) ;
if (e < 0)
msg(ERR, "Invalid grid") ;
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
2
Réponse 10 / 17
dave
 
I found a really cool free 3D sudoku game: http://sudoku-3d.com I think it should help you :-)
2
Réponse 11 / 17
arth Posted messages 84 Registration date   Status Contributeur Last intervention   1 293
 
Just missing the little starting library, but otherwise it looks interesting.
1
kilian Posted messages 8675 Registration date   Status Modérateur Last intervention   1 526
 
Yep. However, the Python version works just fine...
0
Réponse 12 / 17
WADA
 
Hello
thank you for your response....but I poorly stated my problem and I apologize for that!
I will therefore restate my problem trying to be clearer
1) can you tell me what is, in your opinion, the most suitable language for these different constraints:
- free compiler to download
- for Windows XP PC
- Possibility to display a grid (for my SUDOKU)
to enter numbers in it, and retrieve them in my program
- possibility to display the completed grid with different numbers
- easy learning of the language and free documentation
if possible in FRENCH!!

Maybe I'm asking too much and I apologize!!

Thank you all for reading me!
see you soon
1
wada
 
Hello friends
Just to bump the message, as I haven't come across the right person yet
Thank you all for reading and maybe replying to me.
WADA
0
blackdiamant
 
Here you go, a FREE software from MICROSOFT in C 
http://www.microsoft.com/visualstudio/en-us/products/2010-editions/visual-csharp-express


after all, I'm not a gem in programming but I hope I helped you
0
Réponse 13 / 17
arth Posted messages 84 Registration date   Status Contributeur Last intervention   1 293
 
Uh, so they gave you the answer a bit, the constraints are a bit strange, because you can also do graphical display in C, Java, Python, or others. Free compilers exist for Java, C, Python, Delphi, Pascal as well. I think after that it’s up to you to choose. But for me, creating an interface is simpler in Java than in C anyway. For the other languages, I don't know. For tutorials on all these languages in French, I recommend the site http://www.developpez.com

There you go.
1
Réponse 14 / 17
attila
 
Hello, I need to create a Sudoku solver in C, but the problem is that I don't know where to start. Do you have an algorithm to share with me?

Thank you!
1
Réponse 15 / 17
random Posted messages 1612 Status Membre 155
 
I wrote a Sudoku solver
I used VBA with an Excel interface
For the algorithms, see Wikipedia
The simplest one to program is quite easy, you construct a 9x9 array in which you put "123456789"
You add the constraints, so if a 1 is given at (1,1), you replace "123456789" with "1"
You propagate the constraints across rows, columns, and squares for all cells (?,1) different from (1,1) by removing "1" from "123456789", and for all cells (1,?) you do the same, continuing with the cells from (1,1) to (3,3)
You revisit the grid from the beginning as long as it evolves
Then you take into account the implicit constraints: one number per column, per row, per square, and their combinations
This model must iterate as long as the grid is evolving
At this point, either the grid is complete (all easy grids are solved with fewer numbers entered than the problem provides)
Otherwise, the most fruitful approach is to proceed by trial and error starting from the remaining pairs

--
Isn't life beautiful?
1
pierrelgd Posted messages 1 Status Membre
 
Hi,
I'm working on a Sudoku solver program in Excel
and I can't find yours to compare
can you give me the exact location
or provide me with the link
Thanks
0
Réponse 16 / 17
Brice
 
Hello,

http://phpsudo.free.fr

Open source Sudoku in PHP and JavaScript. Grids of 4*4, 6*6, 8*8, 9*9, 10*10, 12*12, 14*14, and 16*16 with numbers and letters! Unique solution, unlimited grids, and 3 difficulty levels... Stay tuned...

I think it's pretty good.
1
loiso
 
Hello!
And in Python, what would that be? How to create the display function? I have already created my list of lists.
Thanks in advance.
0
henrin > loiso
 
I wrote one in C 2 or 3 years ago. The problem is the GUI.
In VB, it’s surely easier.

I picked it up in Python a year ago with much more pleasure
and improved performance:
- searching for simple solutions first,
- interactivity with the possibility of going back
- the ability to see all solutions

The advantage of Python, besides being free,
is that it is very easy to install and implement.
A great and free IDE is Wing101.
For documentation, ActivePython's (1 .chm file) is very handy.

For the GUI, Tkinter works well. We can manage to read everything.

Finally, for design, it's important to master:
- arrays, indices,
- indirection with indexes,
- recursion

Good luck
0
elsa > henrin
 
Hi Henri
you say you already made an algorithm to solve a sudoku in C.
I have to make an algorithm for futoshiki. I wanted to use the sudoku algorithm as a reference but I can't find one in C. Can you help me?
thank you very much
0
Réponse 17 / 17
fati
 
I'm asking you to help me write a program to solve a Sudoku grid in Python
and thank you.
0