win2000 , visual studio 2005, console application

(sorry my poor english)
I dont know very well how start explain whats my problem..

Im making a sudoku game (not unic solution, just random =P)
the problem is the loop where it suppose to verify the sudoku rules and make the corrections necessary, are working 'fine'(?), but it doesnt finish mostly times ( wich means it works perfectly some times =/ )

Another weird thing, is that it are working just like i want to( i figure that cause i debugged this loop one million times, step by step, and didnt find any wrong stuff), so you think, LOGICAL error, yeah i agree, but if the problem is logical, why it works some times, and more weird:
if i comment the loop in parts( there are 3 parts, the blocks( the nine main blocks in sudoku grid), the horizontals lines, and the verticals lines), if i comment 2 of them( letting just one), it will works perfectly, generating a sudoku just with one of its rules...(and if i let 2 rules, it works more times( not making the loop forever)
i cant find the logical problem..

so let me explain my algorithm:
- sort 81 random numbers ( 0-9) and put them in a vector (int positions_fix)
- verify and correct errors loop:
while verification is not donne:
verification donne(this is a bool)

in block rules
block1 2 3 4 5 6 7 8 9(each block have its own loop)
if it find a error, it will fix it(changing the number by a right one, and verifing all again.
when it finishes, there are no errors in the block rules

verify horizontals
(verify all lines) if it find a error, it will fix it(changing the number by a right one, and verifing all again,and marking verification donne as false(cause the block rules are no more safe))
when it finishes, horizontals are free of error

verify verticals( the same as the horizontals)
end of loop
-show numbers

As you see, its very simple, and i SUPPOSE it should work IF IMPLEMENTED RIGHT...right? Cause it should verify until no more errors are find...wich happens some times...

i dont have a clue about what to do, i tried so many things that my brain got burned

So, yeah the code...this loop is kinda long, so if you think theres a problem on my algorythm, gimmie a help...if theres no way to find out whats the problem, im attaching a cpp file with the loop stuff , im also posting here parts of the loop ,
here is:

(obs: +10 are for fixed numbers(the start numbers on a sudoku game, but now all numbers are being fixed for test, so all 81 numbers are fixed (10-19)

here is where are all the numbers to be sorted and corrected

``````int positions_fix;//81 positions(fix numbers(+10))
//		0  1  2		3  4  5		6  7  8
//		9  10 11	12 13 14	15 16 17
//		18 19 20	21 22 23	24 25 26

//		27 28 29	30 31 32	33 34 35
//		36 37 38	39 40 41	42 43 44
//		45 46 47	48 49 50	51 52 53

//		54 55 56	57 58 59	60 61 62
//		63 64 65	66 67 68	69 70 71
//		72 73 74	75 76 77	78 79 80``````

how is the loop for the blocks rules:

``````//the loop
//block1  0  1  2
//        9  10 11
//        18 19 20
for(int x=0, aux_x=0; x<=20; x++){

for(int y=0, aux_y=0; y<=20; y++){

if(positions_fix[x]!=NULL){

if(positions_fix[x]>10&&positions_fix[y]>10&&x!=y){//both>10				//1

while(positions_fix[x]==positions_fix[y]&&x!=y){

positions_fix[x]=((rand()%9)+1)+10;
y=0;
aux_y=0;

}//F while
}//F if both >10

}//F if != NULL

aux_y++;
if(aux_y==3){y=y+6; aux_y=0;}//new line in the block(+1 cause for ++, so +7)

}//F for y

aux_x++;
if(aux_x==3){x=x+6; aux_x=0;}//each ciclo de 0 à 2

}//F for x``````

the horizontals loop

``````//horizontals

int linha=0;//what line are
int flinha=8;//where the line ends
int end_y_at=8;
int start_y_from=0;
int aux_y=0;

for(int start_x_from=0, aux_x=0; start_x_from<=80; start_x_from++){
for(NULL; aux_y<=end_y_at; start_y_from++){

if(positions_fix[start_x_from]!=NULL){

if(positions_fix[start_x_from]>10&&positions_fix[start_y_from]>10&&start_x_from!=start_y_from){//both>10			//1

while(positions_fix[start_x_from]==positions_fix[start_y_from]&&start_x_from!=start_y_from){

positions_fix[start_x_from]=((rand()%9)+1)+10;
start_y_from=linha;
aux_y=linha;
verification_donne=false;//numbers changed, verific blocks again

}//F while

}//F if both >10

}//F if != NULL

aux_y++;

}//F for y

aux_x++;
if(aux_x==9){

start_y_from=linha;
end_y_at=end_y_at+9;
linha=linha+9;
aux_y=aux_y+9;
flinha=flinha+9;
aux_x=0;
}//F if aux_x==9&&
else {
start_y_from=linha;
aux_y=linha;
end_y_at=flinha;
}

}//F for aux_x``````
``````//verticals

for( int x=0, y=72; x<=8,y<=80; x++, y++){//x= start line at/ y= end line at

for( int z=x; z<=y; z=z+9){

for( int w=x; w<=y; w=w+9){

if(positions_fix[z]!=NULL){

if(positions_fix[z]>10&&positions_fix[w]>10&&z!=w){//both>10		//1

while(positions_fix[z]==positions_fix[w]&&z!=w){

positions_fix[z]=((rand()%9)+1)+10;
w=x;
verification_donne=false;

}//F while [z]==[y]

}//F if both>10
}//F if == NULL

}//F for x

}//F for z

}//F for x``````

remembering, each of these works alone, just 2 of these works a little(with means sometimes it finishes ok, and sometimes never finish), and all of these almost doesnt work..

another important thing, is that when it DOESNT finish, it keep doing the entire loop( it keeps doing all verification rules, it dont get stucked in a specific point(never))

also, if i let less numbers in the grid(not 81, like 20 numbers) it finishes ok...

I think the problem that you are running into is the fact that it is VERY unlikely to just randomly select digits to fill into the grid and have a grid that meets all of the criteria.

There are improvements you can make to your algorithm to make better …

## All 3 Replies

I think the problem that you are running into is the fact that it is VERY unlikely to just randomly select digits to fill into the grid and have a grid that meets all of the criteria.

There are improvements you can make to your algorithm to make better choices, but the problem you are trying to solve is hard in and of itself.

As an example of the type of inefficiency of your current algorithm, I present the filling of your random positions table:

``````for(int x=0; x<81; x++){//20 random positions 0-80 (no repetition) in a vector(fix numbers)
fix_nros_random_positions[x]=(rand()%81);
for(int y=0; y<81; y++){
while(fix_nros_random_positions[x]==fix_nros_random_positions[y]&& x!=y){//if is the same position, will be the same result
fix_nros_random_positions[x]=(rand()%81);
y=0;//position changed, so verific all again
}//F while
}//F for y
}//F for x``````

The algorithm generates a random location, and then searches the entire list to make sure that there are no duplicates, even locations that haven't been filled yet.

The desired functionality -- as I understand it -- is to generate a random ordered list of grid cell indexes where each cell is listed once. This is similar to software representation of a deck of cards, where you 'shuffle' the cards to get a random ordering. Most of the shuffle algorithms I've seen, fill the 'deck' with an ordered list of the cards and then proceed to randomly swap 2 cards. Using a similar algorithm here:

``````// fill the random positions
for (int x = 0; x < 81; x++) {
fix_nros_random_positions[x] = x;
}

// perform 1000 exchanges
// the 1000 was chosen arbitrarily, feel free to change it, but it should be at least 2x or 3x your array size
for (int ri = 0; x < 1000; x++) {
int cp1 = rand()%81;
int cp2 = rand()%81;
int tmp = fix_nros_random_positions[cp1];
fix_nros_random_positions[cp1] = fix_nros_random_positions[cp2];
fix_nros_random_positions[cp2] = tmp;
}``````

Having said that, I'm not sure what purpose the above array was supposed to serve.

You should be able to apply a similar logic to the digits in the grid.
You can start with either the boxes, the rows or the columns, but each of those WILL contain the digits 0-9, always. There will never be any duplicates.

The approach I would likely follow would be to fill each of the rows with the digits 0-9 and then 'shuffle' the digits in the row. In fact, now that I think about it, you might even be able to 'progressively' verify the grid. The random mix for the first row is always good as it has nothing to conflict with. The second row must not have any digits in the same column as previous rows, nor any conflicts in the 'block' areas. Once you have a 'valid' second row, you should be able to generate a third row that does not violate any of the constraints. This would allow you to 'progress' through the grid without having to go back and re-visit previous rows.

I think the principle could also be applied to progressively validating each of the column values in the row as well. If a digit doesn't work in its current location, exchange it for one later in the row.

See what you can do with that idea towards solving your problem.

That 'deck shuffler algorythm' is awsome, i never got either close in thinking about that, i'll try it, and use it progressively as you mentioned

it will take looong.. i will change all logical questions that i was triing to solve in my mind for new ones, gotta clean my brain very well first @.@

tanx for the help

So about my code, once i though that the problem could be that what im triing to do is so hard and unlikely to happen that even the processor can take like years to finish it.. o.o (very stupid way of thinking) very impossible to be true.. but i figured out that when it do works, it happens in less than a second, every times it worked, it never took more than a second to finish, so doesnt make any sense...
with that i started to think theres some condition in my grid that when achieved make the loop impossible to finish, but after debugging step by step, with all variables being watched, i never saw anything like that happening -__-, very frustrating...

I've been playing with the algorithm I proposed and I've come to the conclusion that you can't 'progressively' validate. At least not without some provision to 'go back and try again'.

I've been having my suggestion get stuck when it painted itself into a corner. (For example on one run, a valid block of 9 needed the lower right corner be 4 to be successful, but the value 4 was previously used in that column. ) In order to complete, it would necessarily have to revisit at least previous columns, if not previous rows as well.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.