2016 年 11 月

# 測試回合 - 使用組合演化解出數獨

[圖 1] 非簡單數獨問題

[圖 2 獨使用組合的發展

## 示範程式

[圖 3 示範程式結構

``````using System;
using System.Collections.Generic;
namespace SudokuEvo
{
class SudokuEvoProgram
{
static Random rnd = new Random(0);
static void Main(string[] args)
{
Console.WriteLine("Begin solving Sudoku");
Console.WriteLine("The problem is: ");
int[][] problem = new int[9][];
problem[0] = new int[] { 0, 0, 6, 2, 0, 0, 0, 8, 0 };
problem[1] = new int[] { 0, 0, 8, 9, 7, 0, 0, 0, 0 };
problem[2] = new int[] { 0, 0, 4, 8, 1, 0, 5, 0, 0 };
problem[3] = new int[] { 0, 0, 0, 0, 6, 0, 0, 0, 2 };
problem[4] = new int[] { 0, 7, 0, 0, 0, 0, 0, 3, 0 };
problem[5] = new int[] { 6, 0, 0, 0, 5, 0, 0, 0, 0 };
problem[6] = new int[] { 0, 0, 2, 0, 4, 7, 1, 0, 0 };
problem[7] = new int[] { 0, 0, 3, 0, 2, 8, 4, 0, 0 };
problem[8] = new int[] { 0, 5, 0, 0, 0, 1, 2, 0, 0 };
DisplayMatrix(problem);
int numOrganisms = 200;
int maxEpochs = 5000;
int maxRestarts = 20;
int[][] soln = Solve(problem, numOrganisms,
maxEpochs, maxRestarts);
Console.WriteLine("Best solution found: ");
DisplayMatrix(soln);
int err = Error(soln);
if (err == 0)
Console.WriteLine("Success \n");
else
Console.WriteLine("Did not find optimal solution \n");
Console.WriteLine("End Sudoku demo");
} // Main()
public static int[][] Solve(int[][] problem,
int numOrganisms, int maxEpochs, int maxRestarts) { . . }
public static void DisplayMatrix(int[][] matrix) { . . }
public static int[][] SolveEvo(int[][] problem,
int numOrganisms, int maxEpochs) { . . }
public static int[][] RandomMatrix(int[][] problem) { . . }
public static int[] Corner(int block) { . . }
public static int Block(int r, int c) { . . }
public static int[][] NeighborMatrix(int[][] problem,
int[][] matrix)
public static int[][] MergeMatrices(int[][] m1,
int[][] m2) { . . }
public static int Error(int[][] matrix) { . . }
public static int[][] DuplicateMatrix(int[][] matrix) { . . }
public static int[][] CreateMatrix(int n) { . . }
} // Program
public class Organism
{
public int type;  // 0 = worker, 1 = explorer
public int[][] matrix;
public int error;
public int age;
public Organism(int type, int[][] m, int error, int age)
{
this.type = type;
this.matrix = SudokuEvoProgram.DuplicateMatrix(m);
this.error = error;
this.age = age;
}
}
} // ns
``````

``````int[][] problem = new int[9][];
problem[0] = new int[] { 0, 0, 6, 2, 0, 0, 0, 8, 0 };
...
problem[8] = new int[] { 0, 5, 0, 0, 0, 1, 2, 0, 0 };
DisplayMatrix(problem);
``````

``````int numOrganisms = 200;
int maxEpochs = 5000;
int maxRestarts = 20;
int[][] soln = Solve(problem, numOrganisms, maxEpochs, maxRestarts);
Console.WriteLine("Best solution found: ");
DisplayMatrix(soln);
``````

``````int err = Error(soln);
if (err == 0)
Console.WriteLine("Success");
else
Console.WriteLine("Did not find optimal solution");
``````

## 矩陣初始化和錯誤

[圖 4 顯示 RandomMatrix 方法的定義。

[圖 4 RandomMatrix 方法定義

``````public static int[][] RandomMatrix(int[][] problem)
{
int[][] result = DuplicateMatrix(problem);
for (int block = 0; block < 9; ++block) {
// Create a List with values 1-9
// Shuffle the values in List
// Walk through each cell in current block
// If a cell is occupied, remove that value from List
// Walk through each cell in current block
// If cell is empty, add value from List
}
return result;
}
``````

``````public static int Error(int[][] matrix)
{
int err = 0;
for (int i = 0; i < 9; ++i) {  // Each row
// Determine missing values in row
// Add 1 to err for each missing value
}
for (int j = 0; j < 9; ++j) {  // each column
// Determine missing values in column
// Add 1 to err for each missing value
}
return err;
}
``````

## 產生一個芳鄰矩陣

3 x 3 子格線恆定性，因為芳鄰方案必須限制本身成為子方格的排列。更具體而言，將決定芳鄰矩陣中，演算法選取區塊，隨機]，然後在區塊中 （未儲存格包含從問題定義為固定的值），選取兩個儲存格和交換兩個儲存格的值。

``````public static int[][] NeighborMatrix(int[][] problem, int[][] matrix)
{
int[][] result = DuplicateMatrix(matrix);
int block = rnd.Next(0, 9);  // pick a random block
// Determine which cells have values that can be swapped
// Pick two of those cells: (r1,c1) and (r2,c2)
int tmp = result[r1][c1];
result[r1][c1] = result[r2][c2];
result[r2][c2] = tmp;
return result;
}
``````

## 合併兩個矩陣

MergeMatrices 方法接受兩個 9 x 9 的矩陣，從兩個生物物件。方法會掃描透過區塊 0 到 8。每個區塊，會產生介於 0.0 到 1.0 之間的隨機值。如果隨機值低於 0.50 (亦即，大約一半的時間)，然後交換兩個區塊中的值。程式碼是︰

``````public static int[][] MergeMatrices(int[][] m1, int[][] m2)
{
int[][] result = DuplicateMatrix(m1);
for (int block = 0; block < 9; ++block) {
double pr = rnd.NextDouble();
if (pr < 0.50) {
// Replace values in block of m1 with those in m2
}
}
return result;
}
``````

## SolveEvo 方法

[圖 5 主要 SolveEvo 方法中實作的演算法

``````public static int[][] SolveEvo(int[][] problem,
int numOrganisms, int maxEpochs)
{
int numWorker = (int)(numOrganisms * 0.90);
int numExplorer = numOrganisms - numWorker;
Organism[] hive = new Organism[numOrganisms];
// Initialize each Organism
int epoch = 0;
while (epoch < maxEpochs) {
for (int i = 0; i < numOrganisms; ++i) {
// Process each Organism
}
// Merge best worker with best explorer, increment epoch
}
return bestMatrix;
}
``````

``````generate a neighbor matrix
if neighbor is better (or Organism makes mistake)
update matrix with neighbor
reset age to 0
else
don't update matrix
increment age
end-if
``````

``````determine index of best worker Organism
determine index of best explorer Organism
create new Organism using best worker and best explorer
determine index of worst worker Organism
replace worst worker with new child Organism
``````

## 總結

Dr。James McCaffrey 適用於在美國華盛頓州 Redmond 的 Microsoft Research 他曾在數個 Microsoft 產品，包括 Internet Explorer 和 Bing。Dr。可以連線到 McCaffrey jammc@microsoft.com