Generating New Sudoku Puzzles

You can see the live version here Light Beta Sudoku
I searched a lot for algorithms and methods to create new Sudoku Puzzles for my site (Sudoku.lightbeta.com), and the most Algorithms that I as interested is was GA (Genetic Algorithms), so I started playing with it. My results were not so impressive but will do the job needed.

The idea of GA is simply  Generate a several random solution

1. Calculate each solution fitness  (or how much percentage of the solution is correct)
2.  Generate New solution from mixing two good solutions (Reproduction)
3. Make very small changes randomly to this new solution (Mutation)
4. Do it again and again until you get a 100% correct solution

I need to have multiple new puzzles so whenever I complete I save it to a DB and start over.

Currently I’m creating new Sudoku’s every 3-5min, that’s slow but it will cover my Daily Sudoku site need.

I focusing on showing the fitness function because it’s the heart of the application.

Public Function CalculateFitness() As Single

        'max error are 81 so to norimilize devide on 81

        Dim CheckItems As New Hashtable

        Dim Errors As Integer = 0

        For Row = 0 To 8

            CheckItems.Clear()

            For Col = 0 To 8

                If Not CheckItems.ContainsKey(Me.Items(Row, Col)) Then CheckItems.Add(Me.Items(Row, Col), 0)

            Next

            Errors += (9 - CheckItems.Count)

        Next

        For Col = 0 To 8

            CheckItems.Clear()

            For row = 0 To 8

                If Not CheckItems.ContainsKey(Me.Items(row, Col)) Then CheckItems.Add(Me.Items(row, Col), 0)

            Next

            Errors += (9 - CheckItems.Count)

        Next

        For GroupX = 0 To 8 Step 3

            For GroupY = 0 To 8 Step 3

                CheckItems.Clear()

                For row = 0 To 2

                    For Col = 0 To 2

                        If Not CheckItems.ContainsKey(Me.Items(row, Col)) Then CheckItems.Add(Me.Items(row, Col), 0)

                    Next

                Next

                Errors += (9 - CheckItems.Count)

            Next

        Next

        LastFitness = 1 - (Errors / 81)

        Return LastFitness

    End Function

Simply I’m doing it in three phases; Checking the number of error in row, Columns and squares.

I’m assuming that for each group the numbers must be unique so that the group will contain the numbers from 1 to 9

So I’m adding them to a hash table with the number as the key, so if the number of items in the hash table is less that 9 it mean there was some duplicates that will give errors to the Sudoku solution.

If this function can be enhanced in performance it will be a huge update, so the solution will give more results with less time.