The New Sudoku Players' Forum

[AbvAvg]

Hi. I am new to this great forum

I want to CREATE sudoku puzzles in PHP. Can someone please explain me the logic? I am not new to programming and am familiar with C, Java, Javascript, PHP, etc. I followed a particular logic but since this is PHP running under Apache, it kills the process in 30 seconds.

[Papy]

Il youy want to creta Sudoku problem the most easy methode is to compute latin square 9*9 or to get squares on public forum

When you have yours 81 cels grids you hide eandom celles and you try to solve the problem.

I say that it's easy not quick!
You can do that at the inverse:
You put for examples 30 cels on random places with random value and try to solve the grid
After every creator has personnal technics but we are still waiting someone to find where and why you have to put the clues logicaly
Good PHP I prefer PASCAL.
Papy

[AbvAvg]

Thanks Papy for your response. What is "latin square 9*9"?

I want to first generate a valid sudoku grid and than randomly erase squares to make a puzzle. Any help in this regard will be greatly appreciated. I have solving puzzles of various levels since quite some time now. But need to know how to create them.

OFF TOPIC:
As a social service, I am teaching web-development for free to physically challenged. We are on PHP now and I want to explain them the following concepts:

1. Loops (for() and while())
2. 2 dimensional arrays
3. Functions.
4. Improve their logical thinking.

I thought that if I take them thru the code of generating a sudoku puzzles thru PHP code it will take care of the first 3 points. I will make them solve a few puzzles to develop logical thinking and take care of the 4th.

[hobiwan]

To create a grid: You should know the valid candidates for every cell. A simple algorithm could then look like the following:

Take the cell with the least number of possible candidates
Take one of the candidates randomly, set it and check the grid
If the grid is invalid (a cell, thats not yet set, has no available candidates left), try another candidate
If it is valid, proceed with the next cell

When you start to erase cells you must check whether the puzzle still has only one valid solution, which means you need a brute force solver. Example source code is available here.

I take it that your students are beginners. Since both creating and brute force solving needs some sort of backtracking (recursion or some kind of stack) it could be a little too tough for them. If you only want to train loops and arrays you can stick to easier things. A few examples:

Convert a puzzle stored in an 2 dimensional array to a html table
Check the grid for values that occur more than once in a house and color them
Search for naked singles or pairs
Search for hidden singles...

[AbvAvg]

My students are surely newbies. They don't even know what is Sudoku and I will explain them the basics, then take them thru the logic of generating it manually and them program it.

The code that I have written works perfect if I enable only the X or Y or BLOCK. But even if only 2 are enabled, Apache kills it as taking too long

For those who understand PHP/C/C++/Java/Javascript this is the code that I thought about. This code creates a valid (solved) Sudoku grid.

To create a puzzle may be I will delete random numbers from the grid. But I am not too concerned about that currently.

Code: Select all

for ($x = 1; $x <=9; $x++)
{
    for ($y = 1; $y <= 9; $y++)
    {
        $done = 0;
        while ($done != 1) // This loop is for each num of maze
        {
            $the_num = rand(1,9);
            if (num_unique_x($the_num,$x)) // Function to check if its unique in X
            {
                if (num_unique_y($the_num,$y)) // Function to check if its unique in Y
                {
                    if (num_unique_block($the_num,$x,$y)) // Function to check if its unique in BLOCK
                    {
                        $sudoku_maze[$x][$y] = $the_num;
                        $done = 1;
                    }
                }
            }
        }
    }
}


@ hobiwan: Currently, I am not interested in knowing whether there is only one solution or more. I am more interested in generating a VALID Sudoku grid using PHP. My purpose is not to teach the concepts I mentioned

[m_b_metcalf]

For those who understand PHP/C/C++/Java/Javascript this is the code that I thought about. This code creates a valid (solved) Sudoku grid.

There are a number of ways of generating solution grids. One, that depends on having a backtracking solver available (you'll need this anyway at some point) is:

1) Fill three arrays of length 9 with the values 1 to 9 in random order.

2) Place into an empty grid 9 values, using one array as the row index, the second as the column index, the third as the value.

3) Repeat step 2), but checking there is no clash with any of the previous 9 values.

4) Find any one of the multiple solutions to this pseudo-puzzle (ideally, the solver will search in random order, but to get going that's not necessary).

You have a grid.

HTH

Mike Metcalf

P.S. You could perhaps build this technique of an initial seed of fixed values into your existing code. You then keep these 16 to 18 values fixed, lessening the number of combinations dramatically.

[AbvAvg]

Thanks Mike. But the step 3 is what is creating problems in PHP. It has to be checked for uniqueness in 3 ways - X, Y and Block. Just doesn't work in PHP. It is a server side thing and use of resources is really important on server side.

[m_b_metcalf]

Thanks Mike. But the step 3 is what is creating problems in PHP. It has to be checked for uniqueness in 3 ways - X, Y and Block. Just doesn't work in PHP. It is a server side thing and use of resources is really important on server side.

I think there is a misunderstanding. You use step 3) only once. You then have a grid containing about 16 to 18 values (depending on any clashes), and then you either solve the grid (as in step 4), or use those values as fixed values in the algorithm you've displayed.

Regards,

Mike Metcalf

[Mike Barker]

Here's a very efficient (and compact) generator available from magictour. It may help in creation of your own.

char G[9999]="

suexg version 14, small randomized sudoku-generator in C,

generates about 24 sudokus per second with 1GHz
based on an exact cover solver, compiled with gcc3.2
Report bugs,improvement suggestions,feedback to sterten@aol.com
For some explanation of the solver see: http://magictour.free.fr/suexco.txt
This generator starts from an empty grid and adds clues completely at random
There are faster pseudo-random methods which generate upto 1000 sudokus
per second.
For a solver see: http://magictour.free.fr/suexk.exe
(C-sourcecode is attached to the executable )
Send sudokus with rating more than 100000 to sterten@aol.com
so they can be included in the list of hardest sudokus at
http://magictour.free.fr/top94

You can download a DOS/Windows executable of this program from
http://magictour.free.fr/suexg.exe

This software is public domain
";

#include <stdio.h>
#define MWC ((zr=36969*(zr&65535)+(zr>>16))^(wr=18000*(wr&65535)+(wr>>16)))

unsigned zr=362436069, wr=521288629;
int Rows[325],Cols[730],Row[325][10],Col[730][5],Ur[730],Uc[325],V[325],W[325];
int P[88],A[88],C[88],I[88],Two[888];
// char B[83]="0111155555135559999135999888133947778113946678333442678344422678442226678222666778";
char B[83]="0111222333111222333111222333444555666444555666444555666777888999777888999777888999";
char H[326][7];
int b,w,f,s1,m0,c1,c2,r1,l,i1,m1,m2,a,p,i,j,k,r,c,d,n=729,m=324,x,y,s;
int mi1,mi2,q7,part,nt,rate,nodes,seed,solutions,min,samples,sam1,clues;
char L[99]=".123456789";
FILE *file;

int solve();

//------------------------------------------------------------
int main(int argc,char*argv[]){
if(argc<2){printf("\nusage:suexg random-seed [z] [with rating] \n\n");
printf(" generates z locally minimal sudokus [and rates them]\n");
printf(" use different numbers for seed to get different streams of sudokus\n");
printf(" default is : z=1e9 and without rating [if these are not specified]\n");
printf(" to redirect the sudokus to a file use e.g. : suexg 0 100 r >file\n");
printf("\n suexg i : printf more info\n suexg s : prints source-code\n");
exit(1);}
sscanf(argv[1],"%i",&seed);zr^=seed;wr+=seed;
samples=1000000000;if(argc>2)sscanf(argv[2],"%i",&samples);
rate=0;if(argc>3)rate=1;if(argc>4)rate=2;
if(argv[1][0]=='i'){printf("%s",G);exit(0);}
if(argv[1][0]=='s'){if((file=fopen(argv[0],"rb"))==NULL)
{printf("\ncan't find suexg.exe\n");exit(1);}
ip1:w=0;for(i=1;i<33;i++)w+=(fgetc(file)==45);if(w<32)goto ip1;
while(fgetc(file)!='_');
ip2:x=fgetc(file);if(x!=13)printf("%c",x);if(feof(file))exit(1);goto ip2;}

for(i=0;i<888;i++){j=1;while(j<=i)j+=j;Two[i]=j-1;}

r=0;for(x=1;x<=9;x++)for(y=1;y<=9;y++)for(s=1;s<=9;s++){
r++;Cols[r]=4;Col[r][1]=x*9-9+y;Col[r][2]=(B[x*9-9+y]-48)*9-9+s+81;
Col[r][3]=x*9-9+s+81*2;Col[r][4]=y*9-9+s+81*3;}
for(c=1;c<=m;c++)Rows[c]=0;
for(r=1;r<=n;r++)for(c=1;c<=Cols[r];c++){
a=Col[r][c];Rows[a]++;Row[a][Rows[a]]=r;}

c=0;for(x=1;x<=9;x++)for(y=1;y<=9;y++){c++;H[c][0]='r';H[c][1]=x+48;H[c][2]='c';H[c][3]=y+48;H[c][4]=0;}
c=81;for(b=1;b<=9;b++)for(s=1;s<=9;s++){c++;H[c][0]='b';H[c][1]=b+48;H[c][2]='s';H[c][3]=s+48;H[c][4]=0;}
c=81*2;for(x=1;x<=9;x++)for(s=1;s<=9;s++){c++;H[c][0]='r';H[c][1]=x+48;H[c][2]='s';H[c][3]=s+48;H[c][4]=0;}
c=81*3;for(y=1;y<=9;y++)for(s=1;s<=9;s++){c++;H[c][0]='c';H[c][1]=y+48;H[c][2]='s';H[c][3]=s+48;H[c][4]=0;}

sam1=0;
m0s:sam1++;if(sam1>samples)exit(0);

m0: for(i=1;i<=81;i++)A[i]=0;part=0;q7=0;
mr1:i1=(MWC>>8)&127;if(i1>80)goto mr1;i1++;if(A[i1])goto mr1;
mr3:s=(MWC>>9)&15;if(s>8)goto mr3;s++;
A[i1]=s;m2=solve();q7++;//if(q7>999)goto m0;
// add a random clue and solve it. No solution ==> remove it again.
// Not yet a unique solution ==> continue adding clues
if(m2<1)A[i1]=0;if(m2!=1)goto mr1;

//now we have a unique-solution sudoku. Now remove clues to make it minimal
part++;if(solve()!=1)goto m0;
for(i=1;i<=81;i++){mr4:x=(MWC>>8)&127;if(x>=i)goto mr4;x++;P[i]=P[x];P[x]=i;}
for(i1=1;i1<=81;i1++){s1=A[P[i1]];A[P[i1]]=0;if(solve()>1)A[P[i1]]=s1;}

if(rate){nt=0;mi1=9999;for(f=0;f<100;f++){solve();nt+=nodes;if(nodes<mi1)
{mi1=nodes;mi2=C[clues];}}
printf("rating:%6i , ",nt);if(rate>1)printf("hint:%s ",H[mi2]);}
for(i=1;i<=81;i++)printf("%c",L[A[i]]);printf("\n");
goto m0s;}

//-----------------------------------------------------------------------
int solve(){//returns 0 (no solution), 1 (unique sol.), 2 (more than one sol.)
for(i=0;i<=n;i++)Ur[i]=0;for(i=0;i<=m;i++)Uc[i]=0;
clues=0;for(i=1;i<=81;i++)
if(A[i]){clues++;r=i*9-9+A[i];
for(j=1;j<=Cols[r];j++){d=Col[r][j];if(Uc[d])return 0;Uc[d]++;
for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]++;}}}
for(c=1;c<=m;c++){V[c]=0;for(r=1;r<=Rows[c];r++)if(Ur[Row[c][r]]==0)V[c]++;}

i=clues;m0=0;m1=0;solutions=0;nodes=0;
m2:i++;I[i]=0;min=n+1;if(i>81 || m0)goto m4;
if(m1){C[i]=m1;goto m3;}
w=0;for(c=1;c<=m;c++)if(!Uc[c]) { if(V[c]<2){C[i]=c;goto m3;}
if(V[c]<=min){w++;W[w]=c;};
if(V[c]<min){w=1;W[w]=c;min=V[c];} }
mr:c2=MWC&Two[w];if(c2>=w)goto mr;C[i]=W[c2+1];
m3:c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
r=Row[c][I[i]];if(Ur[r])goto m3;m0=0;m1=0;
nodes++;//if(nodes>9999 && part==0)return 0;
for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]++;}
for(j=1;j<=Cols[r];j++){c1=Col[r][j];
for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]++;if(Ur[r1]==1)
for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]--;
if(Uc[c2]+V[c2]<1)m0=c2;if(Uc[c2]==0 && V[c2]<2)m1=c2;}}}
if(i==81)solutions++;if(solutions>1)goto m9;goto m2;
m4:i--;c=C[i];r=Row[c][I[i]];if(i==clues)goto m9;
for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]--;
for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]--;
if(Ur[r1]==0)for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]++;}}}
if(i>clues)goto m3;
m9:return solutions;}

[AbvAvg]

I think I haven't understood what you have explained. Please re-phrase.

[Jean-Christophe]

The code that I have written works perfect if I enable only the X or Y or BLOCK. But even if only 2 are enabled, Apache kills it as taking too long

For those who understand PHP/C/C++/Java/Javascript this is the code that I thought about. This code creates a valid (solved) Sudoku grid.

To create a puzzle may be I will delete random numbers from the grid. But I am not too concerned about that currently.

Code: Select all

for ($x = 1; $x <=9; $x++)
{
    for ($y = 1; $y <= 9; $y++)
    {
        $done = 0;
        while ($done != 1) // This loop is for each num of maze
        {
            $the_num = rand(1,9);
            if (num_unique_x($the_num,$x)) // Function to check if its unique in X
            {
                if (num_unique_y($the_num,$y)) // Function to check if its unique in Y
                {
                    if (num_unique_block($the_num,$x,$y)) // Function to check if its unique in BLOCK
                    {
                        $sudoku_maze[$x][$y] = $the_num;
                        $done = 1;
                    }
                }
            }
        }
    }
}


Your code lacks backtracking and will loop infinitly in the while ($done != 1) loop whenever it hits some contradiction. That is, when no more candidate is available for some cell, because all digits are already assigned to another cell either in the same row or column or block. It's very likely to hit such a contradiction soon or later. Indeed, I'm surprised you could get some puzzle with that code

PS: See also the Sudoku Programmers Forum

[AbvAvg]

I don't know what's backtracking, but I am sure this isn't an endless loop.

The while() loop goes on only till it finds a right numbers which is unique in X, Y and BLOCK. The same while loop is done 9 x 9 = 81 times.

But admittedly, I am here to learn the logic to generate a valid Sudoku grid and will try this (and any other) logic in an offline application using Visual Basic.

Thanks for your input and the link.

[Jean-Christophe]

I'm sure it will loop infinitly at some point in most cases. For example consider this situation:

Code: Select all

+-------+-------+-------+
| 1 4 . | . . . | . . . |
| 2 5 . | . . . | . . . |
| 3 6 . | . . . | . . . |
+-------+-------+-------+
| 4 1 . | . . . | . . . |
| 5 2 . | . . . | . . . |
| 6 3 . | . . . | . . . |
+-------+-------+-------+
| 7 ? . | . . . | . . . |
| 8 ? . | . . . | . . . |
| 9 ? . | . . . | . . . |
+-------+-------+-------+

There is no candidate left for r789c2 (with ?).
The while ($done != 1) will loop infinitly at r7c2.
So you need to detect this conflict and backtrack, undo previous instanciation(s) and try some other digit.

[AbvAvg]

You are right Jean. The logic is flawed and probably it must be getting into endless loop.

I am glad I came to the forum

I will look around for some other example to teach those PHP concepts.

Thanks so much.