Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

NEWS:
sudoku solution

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
dimimal

Joined: 05 Nov 2010
Posts: 1
:

Items
PostPosted: Fri Nov 05, 2010 11:20 pm    Post subject: sudoku solution Reply with quote

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
View user's profile Send private message
narung

Joined: 24 Mar 2011
Posts: 7
:
Location: kln

Items
PostPosted: Sat Apr 23, 2011 7:13 pm    Post subject: Re Reply with quote

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
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 97
:
Location: Campbell, CA

Items
PostPosted: Mon Apr 25, 2011 1:20 am    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron
FREE FORUM HOSTING by AtFreeForum. Terms of Service - Privacy Policy
FASHION ACCESSORIES - BLING BLING - LADIES WATCHES - KOREAN CHILDREN CLOTHING - ONLINE BARGAIN STORE - FASHION JEWELLERIES