Blue Theme Orange Theme Green Theme Red Theme
 
World Class ASP.NET Hosting – Click Here for 3 Months Free/NO Setup Fee!
Home | Forums | Videos | Photos | Downloads | Blogs | Interviews | Jobs | Beginners | Training
 | Consulting  
Submit an Article Submit a Blog 
 Login Close
User Id:
Password:
 
Forgot Password
Forgot Username
Why Register
 Jump to
Skip Navigation Links
TechnologyExpand Technology
WebsiteExpand Website
 Resources  
Close
 Our Network  
Close
Search :       Advanced Search »
Home » GDI+ & Graphics » Using Genetic Algorithms to come up with Sudoku Puzzles

Using Genetic Algorithms to come up with Sudoku Puzzles

Sudoku is a new type of puzzle from Japan that will keep you entertained for a time and may even get you hooked. This article demonstrates how to generate a fully populated Sudoku grid using genetic algorithms.

Author Rank:
Total page views :  71639
Total downloads :  2354
   Print Read/Post comments Post a comment  Similar Articles  
   Email to a friend  Bookmark  Author's other articles  
Download Files:
Sudoku.ZIP
 
Become a Sponsor

Figure 1 - Best Sudoku Genome from Generation 900

Well there is a new craze here in New York City... Sudoku.  You see it in the bookstores, the subways, and on the newstands.   The closest analogy  I can come up with to describe Sudoku is the Rubicks Cube , but easier.  The way Sudoku works is you are given a grid like the one shown in figure 2 containing numbers.   The object of Sudoku is to fill the grid with all the numbers in such a way that each row, column, and 3x3 bold square has a unique numbers 1-9.   There exists only one solution to the puzzle, so when you finish the puzzle you can check it against an answer key.  If you are interested in Sudoku, you can go to the website http://www.sudoku.com/ and check it out.

Figure 2 - Sample Sudoku puzzle

Having gotten a little hooked on these brain-spinning puzzles myself,  I decided to write a genetic algorithm to create possible Sudoku solutions.  It took a while, but I finally came up with a fitness function, mutation, and crossover function that would help produce a solution as shown in figure 3.  Note that it took many, many generations to arrive at a unique solution for the gene population, but eventually it does happen. (A fitness of -->1 indicates that we finally found a Sudoku Square).

Figure 3 - Sudoku Solution after 36,700 generations of genes

Design

The Design was taken from the Genetic Algorithm Mastermind article and adapted to produce a Sudoku Genomes.  The SudokuGenome contains a 9x9 rectangular integer array.  The Genome can do basic GA functions such as Mutate, Crossover, Calculate Fitness, and Initialize.  The Population class contains the gene pool and can manipulate the genes in the pool to produce the next generation.  If you want to understand more about Genetic Algorithms, please read my article on the subject on C# Corner, Implementing a Genetic Algorithms in C# and .NET. 

Figure 4 - UML Design Reverse Engineered using WithClass

Fitness Function

As always, coming up with the proper fitness function for the genetic algorithm is the greatest challenge.  The way we determined the fitness function was using three hashtables that act as histograms.  The fitness algorithm first goes through each column of the Sudoku Genome and uses the number contained in the cell as a hash key.  A value is added to the ColumnMap with the hash key in each cell.  After an  entire column is traversed, the algorithm looks at the count of the ColumnMap .  If every key in the column is unique, then the ColumnMap contains a total of 9 values.  If the column contains a few duplicates, the total count in the ColumnMap will always be less than 9.  The count can then be used as a representative fitness of uniqueness for a particular column.  By adding this number for all columns, we can come up with a fitness for uniqueness of columns.  We can then perform the same exact technique for determining row uniqueness.  The RowMap is populated with keys from each cell in a row of the Sudoku grid.  If the row is entirely unique, then the RowMap will contain 9 entries.   The same technique is also used for each 3x3 cell grouping (shown in figure 1).  The SquareMap is populated with cell values as keys for this hashtable.  Listing 1 demonstrates the entire fitness function operating  on our Sudoku Gene's Multidimensional Array.

Listing 1 - Fitness function for the Sudoku Grid

/// <summary>
/// The Calculate Sudoku Fitness uses the uniqueness of columns, rows
/// and 3x3 squares in the grid to determine a fitness value
/// </summary>
/// <returns></returns>
private float CalculateSudokuFitness()
{
// set fitnesses for columns, rows, and squares initially to 0
float fitnessColumns = 0;
float fitnessRows = 0;
float fitnessSquares = 0;
// go through each column
for (int i = 0; i < 9; i++)
{
// Go through each cell in a column, add it to the ColumnMap according
// to the cell value
ColumnMap.Clear(); // clear the column map for each new column
for (int j = 0; j < 9; j++)
{
// check for uniqueness in row
if (ColumnMap[TheArray[i,j]] == null)
{
ColumnMap[TheArray[i,j]] = 0;
}
ColumnMap[TheArray[i,j]] = ((
int)ColumnMap[TheArray[i,j]]) + 1;
}
// accumulate the column fitness based on the number of entries in the ColumnMap
fitnessColumns += (float)(1.0f/ (10-ColumnMap.Count))/9.0f;
//fitnessColumns += (float)Math.Exp(ColumnMap.Count*10 - 90)/9;
}
// go through each row next
for (int i = 0; i < 9; i++)
{
// Go through each cell in a row, add it to the RowMap according
// to the cell value
RowMap.Clear(); // clear the row map for each new row
for (int j = 0; j < 9; j++)
{
// check for uniqueness in row
if (RowMap[TheArray[j,i]] == null)
{
RowMap[TheArray[j,i]] = 0;
}
RowMap[TheArray[j,i]] = ((
int)RowMap[TheArray[j,i]]) + 1;
}
// accumulate the row fitness based on the number of entries in the RowMap
fitnessRows += (float)(1.0f/ (10-RowMap.Count))/9.0f;
// fitnessRows += (float)Math.Exp(RowMap.Count*10 - 90)/9;
}
// go through next square
for (int l = 0; l < 3; l++)
{
for (int k = 0; k < 3; k++)
{
// Go through each cell in a 3 x 3 square, add it to the SquareMap according
// to the cell value
SquareMap.Clear(); // Clear the square map for each 3 x 3 square
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
// check for uniqueness in row
// check for uniqueness in row
if (SquareMap[TheArray[i + k*3,j + l*3]] == null)
{
SquareMap[TheArray[i+k*3,j+l*3]] = 0;
}
// accumulate the square fitness based on the number of entries in the SquareMap
SquareMap[TheArray[i + k*3,j + l*3]] = ((int)SquareMap[TheArray[i + k*3,j + l*3]]) + 1;
}
}
fitnessSquares += (
float)(1.0f/ (10-SquareMap.Count))/9.0f;
}
}
// The fitness of the entire Sudoku Grid is the product
// of the column fitness, row fitness and 3x3 square fitness
CurrentFitness = fitnessColumns * fitnessRows * fitnessSquares;
return CurrentFitness;
}

Conclusion

Sudoku is the latest fad for puzzle addicts and I suspect it's here to stay.  This article demonstrates how to generate a fully populated Sudoku puzzle using a genetic algorithm.  In our next article we will tackle solving actual Sudoku Puzzles with GA's like the one shown in figure 2.  In the meantime, you can wipe that puzzled  expression off your face, and delve into Sudoku in the land of C# and .NET.


Login to add your contents and source code to this article
 About the author
 
Mike Gold
Michael Gold is President of Microgold Software Inc., makers of the WithClass UML Tool. His company is a Microsoft VBA Partner and Borland Partner. Mike is a Microsoft MVP and founding member of C# Corner. He has a BSEE and MEng EE from Cornell University and has consulted for Chase Manhattan Bank, JP Morgan, Merrill Lynch, and Charles Schwab. Currently he is a senior developer at Finisar Corp. He has been involved in several .NET book projects, and is currently working on a book for using .NET with embedded systems. He can be reached at mike@c-sharpcorner.com
Looking for C# Consulting?
C# Consulting is founded in 2002 by the founders of C# Corner. Unlike a traditional consulting company, our consultants are well-known experts in .NET and many of them are MVPs, authors, and trainers. We specialize in Microsoft .NET development and utilize Agile Development and Extreme Programming practices to provide fast pace quick turnaround results. Our software development model is a mix of Agile Development, traditional SDLC, and Waterfall models.
Click here to learn more about C# Consulting.
 
Introducing MaxV - one click. infinite control. Hyper-V Hosting from MaximumASP.
Finally – a virtual platform that delivers next-generation Windows Server 2008 Hyper-V virtualization technology from a managed hosting partner you can truly depend on. Visit www.maximumasp.com/max for a FREE 30 day trial. Hurry offer ends soon. Climb aboard the MaxV platform and take advantage of High Availability, Intelligent Monitoring, Recurrent Backups, and Scalability – with no hassle or hidden fees. As a managed hosting partner focused solely on Microsoft technologies since 2000, MaximumASP is uniquely qualified to provide the superior support that our business is built on. Unparalleled expertise with Microsoft technologies lead to working directly with Microsoft as first to offer IIS 7 and SQL 2008 betas in a hosted environment; partnering in the Go Live Program for Hyper-V; and product co-launches built on WS 2008 with Hyper-V technology.
Dynamic PDF
ceTE software specializes in components for dynamic PDF generation and manipulation. The DynamicPDF™ product line allows you to dynamically generate PDF documents, merge PDF documents and new content to existing PDF documents from within your applications.
Go.NET
Build custom interactive diagrams, network, workflow editors, flowcharts, or software design tools. Includes many predefined kinds of nodes, links, and basic shapes. Supports layers, scrolling, zooming, selection, drag-and-drop, clipboard, in-place editing, tooltips, grids, printing, overview window, palette. 100% implemented in C# as a managed .NET Control. Document/View/Tool architecture with many properties&events. Optional automatic layout.
Dundas Software
Dundas Chart for .NET is the most advanced .NET charting package available today.  With an extremely complete feature set, elegant architecture and easy implementation, Dundas Chart can quickly add advanced Charting functionality to enhance and transform ASP.NET and Windows Forms applications.  Whether you are implementing charting into internal projects, or building applications for clients, Dundas Chart offers advanced technology and advanced results to get the most out of data.
Clickatell's SMS Gateway
Clickatell's Developer Solutions allow you to SMS enable any website or application via a range of API's. Learn More about our API connections.
Free access to .NET Memory Management video
Everything you need to know about Garbage Collection, Temporary Objects, Fragmentation, Finalization and common causes of memory leaks in .NET. Watch the video here.
Microsoft Visual Studio 2010 Professional
Microsoft Visual Studio 2010 Professional will launch on April 12, but you can beat the rush and secure your copy today by pre-ordering at the affordable estimated retail price of $549 (US). Pre-order now.
Nevron Chart for .NET 2010.1 Now Available
The leading .NET charting control now features PDF, Flash and Silverlight export, visualization of large datasets and more. Deliver true charting functionality to your BI, Scorecard, Presentation or Scientific apps. Download evaluation now.
Developer-Ready ASP.NET 2.0 Web Hosting with 3 MONTHS FREE
Now supporting .NET 3.0 Framework with Windows Workflow Foundation, Windows Communication Foundation (WCF), Windows Presentation Foundation (WPF), windows CardSpace (WCS)! Providing more flexibility for Developers with Web Services Support and a User/Permission Manger. Also supporting MS SQL 2005/2000 with Real-Time Backups, FREE Automated Attach .MDF Tool, FREE SQL Restore and Shrink SQL DB Tools, and SQL
 
   Print Read/Post comments Post a comment  Similar Articles  
   Email to a friend  Bookmark  Author's other articles  
Download Files:
Sudoku.ZIP
 
 Post a Feedback, Comment, or Question about this article
Subject:  
Comment:  
Become a Sponsor
 Comments
givens by ana On January 26, 2008
how many given numbers did you use in your puzzle? and how did you ensure constraints are met regarding these gives (i.e.that teir position is not changed by crossover and mutation)? thanks
Reply | Email | Delete | Modify | 
Very Slow by Disco On September 18, 2009
This algorithm is very slow. I wrote one in C that took about 20ms to create a 9X9 sudoku solution. I was looking for a faster one, because I tried to make it create a 16X16 puzzle, but it took forever to do that.

All mine did was:

for each row
   for each col
      generate a list of valid possibilities for this cell
      if the list is empty, start again.
      else pick one at random, insert it into the cell.

It's a lot simpler that the algorithm in this article.
Reply | Email | Delete | Modify | 

 Hosted by MaximumASP  |  Found a broken link?  |  Contact Us  |  Terms & conditions  |  Privacy Policy  |  Site Map  |  Suggest an Idea  |  Media Kit
Current Version: 5.2009.6.2
 © 2010  contents copyright of their authors. Rest everything copyright Mindcracker. All rights reserved.