COMPULSORY UPGRADE!!! Request an upgrade NOW! 32+ Pre-installed Modifications! 3 Server Locations to choose from: USA, UK and JAPAN.
11th December 2012 - setBB: All servers are upgraded to run using SSD drive. Click Here to report problems!
| View previous topic :: View next topic |
| Author |
Message |
| dimimal
| | Joined: 05 Nov 2010 | | Posts: 1 | | : | |
Items |
|
 Posted: Fri Nov 05, 2010 11:20 pm Post subject: sudoku solution |
 |
|
hello to everyone ,
I am beginer in programmming c++ and i have to do a project concerning generation sudoku solutions with genetic algorithm. firstly i have done a draft of two functions : one to the initialization and second to the fitness. do you have any ideas to construct the fitness function?
| Code: |
#include <stdio>
#include <stdlib>
#include <time>
#include <string>
void sudoku(int***genes,int size,int size1,int size2)
{
for(int k=0; k<size; k++)
{
for(int i=0; i<size1; i++)
{
for(int j=0; j<size2; j++)
{
genes[k][i][j]=(rand()%9)+1;
}
}
}
}
void print(int ***genes,int a,int b,int c)
{
for(int i=0;i<a;i++)
{
for(int j=0;j<b;j++)
{
for(int k=0;k<c;k++)
printf(" %d ",genes[i][j][k]);
printf("\n");
}
printf("=================================\n");
}
}
int fitness(int ***genes,int a,int b, int c)
{
double genome[100];
double count1=0;
double count2=0;
double sum=0;
for(int k=0; k<a; k++)
{
for(int i=0; i<b; i++)
{
for(int j=0; j<c; j++)
{
if((genes[k][i][0]==genes[k][i+1][0])&&(genes[k][0][j]==genes[k][0][j+1]))
{
count1++;
}
}
}
}
for(k=0; k<a; k++)
{
for(i=0; i<3; i++)
{
for(j=0; j<3; j++)
{
if((genes[k][i][0]==genes[k][i+1][0]) && (genes[k][0][j]==genes[k][0][j+1]))
{
count2++;
}
}
}
}
}
int main()
{
srand(time(NULL));
int ***genes=new int**[100];
for(int i=0;i<100;i++)
{
genes[i]=new int*[9];
for(int j=0;j<9;j++)
genes[i][j]=new int[9];
}
sudoku(genes,100,9,9);
print(genes,100,9,9);
return(0);
}
|
this is not the final solution but is a draft to explain my thought.
count the error and i want to store it to array so that i know how many chromosome (sudoku) is proper to generate a child.
have you any ideas improving the code? |
|
| Back to top |
|
 |
| narung
| | Joined: 24 Mar 2011 | | Posts: 7 | | : | | Location: kln |
Items |
|
| Posted: Sat Apr 23, 2011 7:13 pm Post subject: Re |
|
|
The most common way to annotate grids is by writing in tiny numbers - usually referred to as "pencilmarks" - which really mean "this number is still possible for this cell." You may be able to narrow down a cell to only contain "5 and 8" but not know which one.
If you write a tiny 58 in the cell, then later on you may make another placement which allows you to cross off one of your pencilmarks. So, if you crossed out the 5, you know that the cell can now only contain an 8, so you can erase both pencilmarks and write in the large 8.
This example is computer generated, and shows all of the possible pencilmarks that could be added. You don't need to add in all of the pencilmarks - good players find it slows them down too much for the easiest puzzles, but need to use them for trickier puzzles. |
|
| Back to top |
|
|
| PIsaacson
| | Joined: 17 Jan 2006 | | Posts: 97 | | : | | Location: Campbell, CA |
Items |
|
| Posted: Mon Apr 25, 2011 1:20 am Post subject: |
|
|
dimimal,
If your fitness function is supposed to check whether or not the generated sudoku puzzle is valid, then you need to do something like the following:
| Code: |
// Set of 9 cell indexes for each of the 27 sectors - 9 rows, 9 columns and 9 boxes
// row = index / 9;
// col = index % 9;
// box = (row / 3) * 3 + (col / 3);
// offset within the box = (row % 3) * 3 + (col % 3)
const unsigned char sectors[27][9] =
{{ 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},
{ 0, 9,18,27,36,45,54,63,72},
{ 1,10,19,28,37,46,55,64,73},
{ 2,11,20,29,38,47,56,65,74},
{ 3,12,21,30,39,48,57,66,75},
{ 4,13,22,31,40,49,58,67,76},
{ 5,14,23,32,41,50,59,68,77},
{ 6,15,24,33,42,51,60,69,78},
{ 7,16,25,34,43,52,61,70,79},
{ 8,17,26,35,44,53,62,71,80},
{ 0, 1, 2, 9,10,11,18,19,20},
{ 3, 4, 5,12,13,14,21,22,23},
{ 6, 7, 8,15,16,17,24,25,26},
{27,28,29,36,37,38,45,46,47},
{30,31,32,39,40,41,48,49,50},
{33,34,35,42,43,44,51,52,53},
{54,55,56,63,64,65,72,73,74},
{57,58,59,66,67,68,75,76,77},
{60,61,62,69,70,71,78,79,80}};
bool valid_grid ()
{
// Check to see if the grid is a valid puzzle - all sectors completely covered with digits 1-9 (as bit offsets)
for (int s = 0; s < 27; s++)
{
int found = 0;
// Traverse all 9 cells within sector s
for (int n = 0; n < 9; n++)
{
int nx = sectors[s][n];
int rx = nx / 9;
int cx = nx % 9;
// Assumes cell[x][y] contains the values 1-9 or 0 if unassigned.
int shift = cell[rx][cx];
found |= shift ? 1 << (shift - 1) : 0;
}
// Ensure that we found all 9 values for this sector (bits 0-8 set)
if (found != 0x1ff)
return false;
}
return true;
} |
This algorithm is faster than one that checks all 81 cells and stores each sector result for a final test against the 27 accumulated results. That's because this one will exit as soon as it discovers an illegal sector, which is what usually happens during puzzle generation. The 81 algorithm is faster if you assume that the grid is probably correct, but need to check anyway.
One large problem is that your algorithm for generating a filled sudoku grid does not take into account that once you place a digit, it is now excluded from all peer cells (those that share the same row/col/box). It is highly unlikely that you will ever generate a valid puzzle this way. Plus, you really need to use a better random number generator than the builtin C runtime rand function. Google RNG and steal something better - like Mersenne Twister or Boost Fibonacci.
One neat algorithm (Ahola B159) takes into account the fact that you can fill boxes 1/5/9 without worrying about any conflicts. Do this by using your brand-spanking new and improved RNG to shuffle the digits 1-9, then assign them to box 1. Repeat for box 5 and repeat for box 9. You now stand a much better chance of creating a valid sudoku grid than by just randomly filling cells and hoping for the best. Filling in the remaining empty cells is usually done by using DLX or some other fast solver to generate a solution grid (there will always be multiple solutions at this point, so just pick one). Unless you have a mal-coded DLX, you will always wind up with a valid grid this way. An alternative approach and one that is much faster, but with a much lower success rate, is to use a naked/hidden solver with a single level of guessing to complete the grid, and then check to see if it's valid (using your new and improved validation function).
I've probably missed the whole point of using fractals or genetics, but I would suspect that the best place to apply such would be at the guessing stage of the latter approach for filling a grid. Perhaps a heuristics guided chaotic function at the guessing stage would emulate mutations and natural selection???
Cheers,
Paul |
|
| Back to top |
|
|
| |
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
