Anders Hesselboms teknikblogg

Evolutionary sudoku

2013-11-07

This is a successful attempt to use an evolutionary algorithm to generate a sudoku board. A complete board is created after usually less than a million iterations, sometimes after a couple of hundred generations.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
   class Program
   {
      static void Main(string[] args)
      {
         var s = new Sudoku();
         s.Display();
         Console.Write("Done. Press enter to quit.");
         Console.ReadLine();
      }
   }

   class Sudoku
   {
      int[,] field = new int[9,9];
      const int mutation_speed = 3;
      const int dead_end_limit = 60000;

      public Sudoku()
      {
         var r = new Random();
         //Create a list of possible characters on the game field.
         var l = new List<int>();
         for (var i = 1; i < 10; i++)
            for (var j = 1; j < 10; j++)
               l.Add(i);
         //Place them on the field randomly.
         for (var i = 0; i < 9; i++)
            for (var j = 0; j < 9; j++) {
               var index = r.Next(0, l.Count);
               var value = l[index]; l.RemoveAt(index);
               this.field[j, i] = value;
            }
         //Prepare for score counting. Low is better.
         int score = int.MaxValue, iterations = 0, generations = 0,
         iterations_since_last_climb = 0;
         //Define how a mutation works - a random element swap.
         Action<int[,]> mutate = a => {
            var speed = (score > 2 ? mutation_speed : 1);
            for (var i = 0; i < speed; i++) {
               int x1 = r.Next(0, 9), y1 = r.Next(0, 9),
                 x2 = r.Next(0, 9), y2 = r.Next(0, 9);
               var v = a[x1, y1]; a[x1, y1] = a[x2, y2]; a[x2, y2] = v;
            }
         };
         //Show progress.
         Action status = () => {
            Console.Title = string
               .Format("Score: {0:00} - Generations: {1:000} - " +
               "Iterations: {2:000000}" +
               " - Since last climb: {3:00000}",
               score, generations, iterations, iterations_since_last_climb);
         };
         //Let evolution work.
         do {
            iterations++;
            //If adaptation has stopped, the parent must mutate.
            if (iterations_since_last_climb >= dead_end_limit) {
               mutate(this.field);
               score = this.GetScore(this.field);
            }
            //Breed two new sudokos and modify them slightly.
            int[,] child1 = (int[,])this.field.Clone();
            int[,] child2 = (int[,])this.field.Clone();
            mutate(child1); mutate(child2);
            //Check new scores.
            var child1score = this.GetScore(child1);
            var child2score = this.GetScore(child2);
            //Keep the best one, if any.
            Action<int[,], int> keep = (a, s) => {
               this.field = (int[,])a.Clone(); score = s; generations++;
               iterations_since_last_climb = 0; };
            if (child1score < score)
               keep(child1, child1score);
            else if (child2score < score)
               keep(child2, child2score);
            else
               iterations_since_last_climb++;
            System.Threading.Thread.Yield();
            if ((iterations % 1000) == 0)
               status();
#if DEBUG
            this.Display();
            Console.CursorTop = 0;
#endif
         } while (score > 0);
         status();
      }

      private int GetScore(int[,] p)
      {
         //Define how fitness is determined. A better solution is wanted.
         Func<int[,], int, int, bool> checkrow = (arr, x, y) => {
            var val = arr[x, y]; var count = 0;
            for (var i = 0; i < 9; i++)
               if (arr[i, y] == val) count++;
            return (count == 1);
         };
         Func<int[,], int, int, bool> checkcol = (arr, x, y) => {
            var val = arr[x, y]; var count = 0;
            for (var i = 0; i < 9; i++)
               if (arr[x, i] == val) count++;
            return (count == 1);
         };
         Func<int[,], int, int, bool> checksection = (arr, x, y) => {
            var section_x = x; while (!((section_x % 3) == 0)) section_x--;
            var section_y = y; while (!((section_y % 3) == 0)) section_y--;
            var val = arr[x, y]; var count = 0;
            for (var row = section_x; row < section_x + 3; row++)
               for (var col = section_y; col < section_y + 3; col++)
                  if (arr[col, row] == val) count++;
            return (count == 1);
         };
         var score = 0;
         for (var i = 0; i < 9; i++)
            for (var j = 0; j < 9; j++) {
               if (!(checkrow(p, j, i))) score++;
               if (!(checkcol(p, j, i))) score++;
               if (!(checksection(p, j, i))) score++;
            }
         return score;
      }

      public void Display()
      {
         for (var y = 0; y < 9; y++) {
            for (var x = 0; x < 9; x++)
               Console.Write(field[x, y]);
            Console.WriteLine();
         }
      }

   }
}