PDA

View Full Version : Need programming project help - sudoku combinations lister?



JAD
02-19-2009, 03:56 AM
Well I have this project for C++ and I have to make a program that will list all possible combinations for a 4x4 sudoku square. Here's how it works if you don't already know,

-16 numbers form a 4 by 4 square. All numbers have a value of 1-16, and are all different.

-all rows and columns must sum 34.

-all diagonals must sum 34.

-the four 2 by 2 quadrants (mini squares) must sum 34.

Example:

1 4 14 15
13 16 2 3
8 5 11 10
12 9 7 6


So the program has to store all of the combinations and all that crap in a multi dimensional array. Then, it has to print out the first 5 and last 5 combinations to make sure it works.

I am having a lot of trouble figuring out how to do this. If anybody has already made a program like this, could make a program like this for me (that'd be great!), or could at least explain a way of going about this to me it would be very appreciated.

Thanks a lot!

Boreas
02-19-2009, 04:22 AM
Brute force the top 3x3, and fill in the rest in accordance with the 34 thing. Skip to the next combo as soon as it becomes impossible (including the top left 2x2). If you fill out the whole thing and all 34s check out, save it to the answer array. The answer array can be a 3d int array, where its an array of 4x4 2d int array, Array[example][0][0]:=1 Array[example][3][3]:=6. Or it can be an array of 0..15 1d int array, Array[example][0]:=1, Array[example][15]:=6. Or it could be an array tpas, where each tpa is 16 long and contains the xy location of each number. I would suggest the first way, because you can easily check for the 34s with for loops, for x:=0 to 3 do sum:=sum+tmpArray[x][0].

JAD
02-19-2009, 05:52 AM
Brute force the top 3x3, and fill in the rest in accordance with the 34 thing. Skip to the next combo as soon as it becomes impossible (including the top left 2x2). If you fill out the whole thing and all 34s check out, save it to the answer array. The answer array can be a 3d int array, where its an array of 4x4 2d int array, Array[example][0][0]:=1 Array[example][3][3]:=6. Or it can be an array of 0..15 1d int array, Array[example][0]:=1, Array[example][15]:=6. Or it could be an array tpas, where each tpa is 16 long and contains the xy location of each number. I would suggest the first way, because you can easily check for the 34s with for loops, for x:=0 to 3 do sum:=sum+tmpArray[x][0].

I guess the problem is I don't understand how to "brute force" it. How do I know where to put which numbers where? Your answer would have been very helpful if it was for someone who knew what they were doing lol.

Thanks Boreas.


And if anybody has a program/can write a program to help me out it would still be awesome. Thanks.

Boreas
02-19-2009, 06:33 AM
Basically stacked for loops with some checks.
Start with
123
456
78[]
then cycle the last one 1-16 skipping what is already there. Then increase the 8 once, and cycle the last one again. Increase 9 that was the 8 again, and cycle 16. Once the 8-9-... has cycled completely, change the 7 and start again. Rinse and repeat.


You will need something like:
if IsAlreadyInSquare(i) then continue;
Also something to check if all 34s are true. Go to the next combination if false.

JAD
02-19-2009, 06:46 AM
Basically stacked for loops with some checks.
Start with
123
456
78[]
then cycle the last one 1-16 skipping what is already there. Then increase the 8 once, and cycle the last one again. Increase 9 that was the 8 again, and cycle 16. Once the 8-9-... has cycled completely, change the 7 and start again. Rinse and repeat.


You will need something like:
if IsAlreadyInSquare(i) then continue;
Also something to check if all 34s are true. Go to the next combination if false.

Ugh... I'm sorry Boreas, I feel like an idiot :(

I'm still not understanding. Can you give me some detailed psuedo code or something? I'm just not following your explanation, but I understand code. Thanks again for the help; sorry I'm not getting it.

Boreas
02-19-2009, 10:07 PM
Something like this
for TmpArray[0]:= 1 to 16 do
begin
if AlreadyInSquar(TmpArray[0]) then continue;
for TmpArray[1]:=1 to 16 do
begin
if AlreadyInSquare(TmpArray[1]) then continue;
//you get the idea
for TmpArray[8]:= 1 to 16 do
begin
if AlreadyInSquare(TmpArray[8]) then continue;
if AllSums34 then //this function returns false and exits
//as soon as one of them isnt 34
AddTmpArrayToAnswerArray;
//a lot of ends
AllSums34 transposes the 0-8 int array into a 2d 0-3 by 0-3 int array (where its a 3x3 in the top left of a 4x4). Then it fills in the right column and bottom row with the only numbers that will fit, and then when the number that will fit can't be used because it is already being used, it will return false and exit. Then it can check the 4 quadrants. You could also check the top left quadrant after TmpArray[4].

JAD
02-20-2009, 01:50 AM
Thanks a lot Boreas! That was all I needed to get started... It makes more sense now.

I wrote just about the whole program now, but when I go to run it, nothing happens; I just wait for it to print a square. I was wondering if you could take a look at my code?



#include <iostream>

using namespace std;

int answersArray[3456][4][4], currentAnswer=0;

//Prototype
void fillArray(int smSquare[]);
void printIt(int num);

int main()
{
int smSquare[9];
for(int i=0; i < 3456; i++)
{
fillArray(smSquare);
printIt(i);
}
cout << "\nPress enter key to continue...";
cin.get();
return 0;
}

void printIt(int num)
{
for(int i=0; i < 4; i++)
{
for(int j=0; j < 4; j++)
cout << answersArray[num][j][i] << " ";
cout << "\n";
}
}

bool inSquare(int val, int smSquare[], int currentSpot)
{
for(int i=0; i < currentSpot; i++)
if(smSquare[i] == val) return true;
return false;
}

/************************************************** **************\
checkAndConvert changes the array to 2d, fills in the rest of the
square, returns true and puts the new array into the answers array
if everything checks out (everything sums 34)
/************************************************** **************\ */
bool checkAndConvert(int smSquare[])
{
int total;
//Converts small 3x3 square into big 4x4 square (multi dimensional)
int bgSquare[4][4];
bgSquare[0][0] = smSquare[0];
bgSquare[1][0] = smSquare[1];
bgSquare[2][0] = smSquare[2];
bgSquare[0][1] = smSquare[4];
bgSquare[1][1] = smSquare[5];
bgSquare[2][1] = smSquare[6];
bgSquare[0][2] = smSquare[7];
bgSquare[1][2] = smSquare[8];
bgSquare[2][2] = smSquare[9];
//End conversion

//Fill empty spots
/* complete rows */
bgSquare[3][0] = 34 - smSquare[0] - smSquare[1] - smSquare[2];
bgSquare[3][1] = 34 - smSquare[3] - smSquare[4] - smSquare[5];
bgSquare[3][2] = 34 - smSquare[6] - smSquare[7] - smSquare[8];
/*complete columns */
bgSquare[0][3] = 34 - smSquare[0] - smSquare[3] - smSquare[6];
bgSquare[1][3] = 34 - smSquare[1] - smSquare[4] - smSquare[7];
bgSquare[2][3] = 34 - smSquare[2] - smSquare[5] - smSquare[8];
/*fill last spot*/
bgSquare[3][3] = 34 - bgSquare[0][3] - bgSquare[1][3] - bgSquare[2][3];
//End Fill empty spots

//Check 34's
/* rows */
for(int i=0; i < 4; i++)
{
total = 0;
for(int j=0; j < 4; j++)
total += bgSquare[i][j];
if(total != 34) return false;
}
/* columns */
for(int i=0; i < 4; i++)
{
total = 0;
for(int j=0; j < 4; j++)
total += bgSquare[j][i];
if(total != 34) return false;
}
//End check 34's

//Save to answers Array
for(int i=0; i < 4; i++)
for(int j=0; j < 4; j++)
answersArray[currentAnswer][j][i] = bgSquare[j][i];
currentAnswer += 1;
//End save to answers Array
return true;
}

void fillArray(int smSquare[])
{
for(smSquare[0]=1; smSquare[0] < 17; smSquare[0]++)
{
//if(inSquare(smSquare[0], smSquare, 0)) continue;
for(smSquare[1]=1; smSquare[1] < 17; smSquare[1]++)
{
if(inSquare(smSquare[1], smSquare, 1)) continue;
for(smSquare[2]=1; smSquare[2] < 17; smSquare[2]++)
{
if(inSquare(smSquare[2], smSquare, 2)) continue;
for(smSquare[2]=1; smSquare[2] < 17; smSquare[2]++)
{
if(inSquare(smSquare[3], smSquare, 3)) continue;
for(smSquare[3]=1; smSquare[3] < 17; smSquare[3]++)
{
if(inSquare(smSquare[4], smSquare, 4)) continue;
for(smSquare[4]=1; smSquare[4] < 17; smSquare[4]++)
{
if(inSquare(smSquare[5], smSquare, 5)) continue;
for(smSquare[5]=1; smSquare[5] < 17; smSquare[5]++)
{
if(inSquare(smSquare[6], smSquare, 6)) continue;
for(smSquare[6]=1; smSquare[6] < 17; smSquare[6]++)
{
if(inSquare(smSquare[7], smSquare, 7)) continue;
for(smSquare[7]=1; smSquare[7] < 17; smSquare[7]++)
{
if(inSquare(smSquare[8], smSquare, 8)) continue;
for(smSquare[8]=1; smSquare[8] < 17; smSquare[2]++)
{
if(inSquare(smSquare[8],smSquare,0)) continue;
if(checkAndConvert(smSquare))
return;
}
}
}
}
}
}
}
}
}
}
}


If you don't have the time to look at this I totally understand. But if you could find the logic error then that would be great because I can't seem to.

Thanks again.

BTW, I know that I don't search for diagonals and quadrants yet. I just wanted to see if it would work just finding rows and columns before I wrote that, but it didn't.

Boreas
02-20-2009, 04:17 AM
Sorry I don't know C++ (didn't realize what forum this was until half way into my first post :p), but it seems like you're on the right track.

Wizzup?
02-20-2009, 01:43 PM
Thanks a lot Boreas! That was all I needed to get started... It makes more sense now.

I wrote just about the whole program now, but when I go to run it, nothing happens; I just wait for it to print a square. I was wondering if you could take a look at my code?



#include <iostream>

using namespace std;

int answersArray[3456][4][4], currentAnswer=0;

//Prototype
void fillArray(int smSquare[]);
void printIt(int num);

int main()
{
int smSquare[9];
for(int i=0; i < 3456; i++)
{
fillArray(smSquare);
printIt(i);
}
cout << "\nPress enter key to continue...";
cin.get();
return 0;
}

void printIt(int num)
{
for(int i=0; i < 4; i++)
{
for(int j=0; j < 4; j++)
cout << answersArray[num][j][i] << " ";
cout << "\n";
}
}

bool inSquare(int val, int smSquare[], int currentSpot)
{
for(int i=0; i < currentSpot; i++)
if(smSquare[i] == val) return true;
return false;
}

/************************************************** **************\
checkAndConvert changes the array to 2d, fills in the rest of the
square, returns true and puts the new array into the answers array
if everything checks out (everything sums 34)
/************************************************** **************\ */
bool checkAndConvert(int smSquare[])
{
int total;
//Converts small 3x3 square into big 4x4 square (multi dimensional)
int bgSquare[4][4];
bgSquare[0][0] = smSquare[0];
bgSquare[1][0] = smSquare[1];
bgSquare[2][0] = smSquare[2];
bgSquare[0][1] = smSquare[4];
bgSquare[1][1] = smSquare[5];
bgSquare[2][1] = smSquare[6];
bgSquare[0][2] = smSquare[7];
bgSquare[1][2] = smSquare[8];
bgSquare[2][2] = smSquare[9];
//End conversion

//Fill empty spots
/* complete rows */
bgSquare[3][0] = 34 - smSquare[0] - smSquare[1] - smSquare[2];
bgSquare[3][1] = 34 - smSquare[3] - smSquare[4] - smSquare[5];
bgSquare[3][2] = 34 - smSquare[6] - smSquare[7] - smSquare[8];
/*complete columns */
bgSquare[0][3] = 34 - smSquare[0] - smSquare[3] - smSquare[6];
bgSquare[1][3] = 34 - smSquare[1] - smSquare[4] - smSquare[7];
bgSquare[2][3] = 34 - smSquare[2] - smSquare[5] - smSquare[8];
/*fill last spot*/
bgSquare[3][3] = 34 - bgSquare[0][3] - bgSquare[1][3] - bgSquare[2][3];
//End Fill empty spots

//Check 34's
/* rows */
for(int i=0; i < 4; i++)
{
total = 0;
for(int j=0; j < 4; j++)
total += bgSquare[i][j];
if(total != 34) return false;
}
/* columns */
for(int i=0; i < 4; i++)
{
total = 0;
for(int j=0; j < 4; j++)
total += bgSquare[j][i];
if(total != 34) return false;
}
//End check 34's

//Save to answers Array
for(int i=0; i < 4; i++)
for(int j=0; j < 4; j++)
answersArray[currentAnswer][j][i] = bgSquare[j][i];
currentAnswer += 1;
//End save to answers Array
return true;
}

void fillArray(int smSquare[])
{
for(smSquare[0]=1; smSquare[0] < 17; smSquare[0]++)
{
//if(inSquare(smSquare[0], smSquare, 0)) continue;
for(smSquare[1]=1; smSquare[1] < 17; smSquare[1]++)
{
if(inSquare(smSquare[1], smSquare, 1)) continue;
for(smSquare[2]=1; smSquare[2] < 17; smSquare[2]++)
{
if(inSquare(smSquare[2], smSquare, 2)) continue;
for(smSquare[2]=1; smSquare[2] < 17; smSquare[2]++)
{
if(inSquare(smSquare[3], smSquare, 3)) continue;
for(smSquare[3]=1; smSquare[3] < 17; smSquare[3]++)
{
if(inSquare(smSquare[4], smSquare, 4)) continue;
for(smSquare[4]=1; smSquare[4] < 17; smSquare[4]++)
{
if(inSquare(smSquare[5], smSquare, 5)) continue;
for(smSquare[5]=1; smSquare[5] < 17; smSquare[5]++)
{
if(inSquare(smSquare[6], smSquare, 6)) continue;
for(smSquare[6]=1; smSquare[6] < 17; smSquare[6]++)
{
if(inSquare(smSquare[7], smSquare, 7)) continue;
for(smSquare[7]=1; smSquare[7] < 17; smSquare[7]++)
{
if(inSquare(smSquare[8], smSquare, 8)) continue;
for(smSquare[8]=1; smSquare[8] < 17; smSquare[2]++)
{
if(inSquare(smSquare[8],smSquare,0)) continue;
if(checkAndConvert(smSquare))
return;
}
}
}
}
}
}
}
}
}
}
}


If you don't have the time to look at this I totally understand. But if you could find the logic error then that would be great because I can't seem to.

Thanks again.

BTW, I know that I don't search for diagonals and quadrants yet. I just wanted to see if it would work just finding rows and columns before I wrote that, but it didn't.

Those nested if's...? :)

Try checking these pages out:
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku
http://en.wikipedia.org/wiki/Algorithmics_of_sudoku
http://en.wikipedia.org/wiki/Sudoku

Boreas
02-20-2009, 07:41 PM
I was wondering how long it would take you to be drawn to a thread with sudoku in the title as I was :p. However I think he might be looking for Magic Square (http://en.wikipedia.org/wiki/Magic_square).

JAD
02-21-2009, 12:00 AM
I was wondering how long it would take you to be drawn to a thread with sudoku in the title as I was :p. However I think he might be looking for Magic Square (http://en.wikipedia.org/wiki/Magic_square).

Yeah I realized that it was actually a magic square the other day :p

Thanks again for the help. I finally finished and submitted the assignment though, and I think I should get a pretty good grade on it.

Boreas
02-21-2009, 12:08 AM
Np. Sounds like a cool class.

JAD
02-21-2009, 12:18 AM
Np. Sounds like a cool class.

Yeah it's my second C++ programming class at the community college. It's pretty cool stuff.