用于解决数独武士的信息搜索算法

hosein fereidooni

4.64/5 (8投票s)

2011年8月11日

CPOL

3分钟阅读

30908

1732

用于解决数独武士的信息搜索算法

引言

武士道数独是东亚流行的游戏。这种数独由五个内部数独组成。每个数独覆盖其他数独。在本文中，我们使用启发式搜索算法解决数独。

在另一篇论文中，详细描述了 9 x 9 的数独解决方案。数独求解器发布在每个类别中，并在主板上回答。最终可以解决武士道数独。面向对象程序和类的概念得到了很好的体现。

什么是武士道数独

武士道数独由五个主要部分组成。这种 21 * 21 的数独由一个主板组成。数独是位于四侧的数独，位于中心。数独是一个相互覆盖的 3 x 3。四个部分的中间数独被四个数独侧面覆盖。数独的规则如下

每个 3 × 3 的正方形必须从一到九且不重复。
行的内部正方形的值不唯一。
应该在每列的值中构建，该值不唯一。

重要的是，内部行和列在任何数独中都必须是唯一的。并且从第 21 行和列的开始到结束都不是唯一的。内部顺序对于解决数独并不重要。

解决方案

该算法首先构建一个 21 * 21 的范围。它由用户初始化。将包含数字 441 的字符串作为输入发送到主类。给定此输入，算法开始其工作。该部分由五个主要部分组成。这种选择是程序员决定的，不会影响解决方案。然后设备发送一个类数独求解器。在这个类范围内，使用填充原始 9 x 9 板的方法进行填充。数独求解器和解决方案方法由主板完成。在此算法中，对于数组的每个元素，使用零。

最后，主板解决 21 * 21 的数独，并在其位置。通过这个过程，武士道数独将连续解决五次。

代码分析

它由两个商业和演示层组成。数独是为内部类实例化的。它还将与创建的原始武士道Business类一起使用。第一个类将解释...

武士道业务类

此类是 21 * 21 的二维数组，用作保存使用武士道数独的主板的存储库。

//samurai board
        int[,] SamuraiBord = new int[21, 21];
//Constructor Method
//This method takes an array of all elements of the original value is zero. 
//set all samuraiboard element to zero
public SamuraiBusiness()
{
    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            SamuraiBord[i, j] = 0;
        }
    }
}
//Fill method
//This method takes a string array of input and The array
//to a scalar variable, the array will be the main board. 
//fill main board samurai by input string array
public void Fill(string[] lines)
{
    int k = 0;
    for (int i = 0; i <= 20; i++)
    {
        for (int j = 0; j <= 20; j++)
        {
            SamuraiBord[i, j] = int.Parse(lines[k]);
            k++;
        }
    }
}

RetSelectedSubSudoku

此方法接受四个输入值并将环放置。这将导致一个由string值组成的数组，这些值被分隔并作为输出返回。

//return sub sudoku
public string[] RetSelectedSubSudoku(int fromi, int toi, int fromj, int toj)
{
    int k = 0;

    string[] temp = new string[81];

    for (int i = fromi; i < toi; i++)
    {
        for (int j = fromj; j < toj; j++)
        {
            temp[k] =Convert.ToString(SamuraiBord[i, j]);
            k++;
        }
    }
    return temp;
}

InsertSolveSubSudoku

此方法将解决的数独构建在其原始数组中的位置。此方法接受四个输入数值，并在输入字段中放置它的位置。

//this method insert solves soduko in i,j place
public void InsertSolveSubSudoku(int fromi, int toi, 
       int fromj, int toj, string[] insertSolve)
{
    int k = 0;

    for (int i = fromi; i < toi; i++)
    {
        for (int j = fromj; j < toj; j++)
        {
            SamuraiBord[i,j] = Convert.ToInt32(insertSolve[k]);
            k++;
        }
    }
}

RetSamuraiSudokuBoard

此方法接受一个string并返回原始武士道。

//return all samurai board
public string RetsamuraiSudokuBoard()
{
    int k = 0;

    string temp = string.Empty;

    for (int i = 0; i <= 20; i++)
    {
        for (int j = 0; j <= 20; j++)
        {
            temp +=  "  " + Convert.ToString(SamuraiBord[i, j]);
            k++;
        }
        temp += "\r\n";
    }
    return temp;
}

Sudoku() 类

在此类之前，将论文放在引用中。

表示层

在此层中，接收输入并将发送到该类。获取输出后，将显示结果。

SamuraiBusiness samurai = new SamuraiBusiness();
Sudoku sudoku = new Sudoku();
           
//9215
string InputText = "0000743680007452193685762381940008316452" + 
       "794831965270002697834157654819320006589241371983627450004" + 
       "931675823429578160001275386948376294519763824719562547136" + 
       "893125743968216198452734859168527430000007681534290000000" + 
       "000005148296370000000000009327648510000007682913452971685" + 
       "493721423658976312458371693957841265487932164858395174620" + 
       "009364715285148269730004726589136279435810005819237464761" + 
       "59238000819765234981632754000354182697253478619000627394851";

string[] InputTextArray = new string[441];

string[] Temp = new string[81];

//set temp array to zero
for (int i = 0; i < Temp.Length; i++)
{
    Temp[i] = string.Empty;
}

for (int i = 0; i < InputText.Length; i++)
{
    InputTextArray[i] = Convert.ToString(InputText[i]);
}

samurai.Fill(InputTextArray);

label2.Text = samurai.RetsamuraiSudokuBoard();

到目前为止，定义了处理和输入的变量和数组。已经完成了所需的条目步骤。在数组中定义原型和所需的类数量，并接收初始输出。第五阶段是每次将数独求解器发送到内部选择和值时都会重复。答案可以在其先前的位置被溶解。

//9,9 -1
sudoku.Fill(samurai.RetSelectedSubSudoku(0 , 9 , 0 , 9));
sudoku.SolvedSudoku();
Temp = sudoku.boardconverttostrarray();
samurai.InsertSolveSubSudoku(0 , 9 , 0 , 9 , Temp);

//set temp array to zero
for (int i = 0; i < Temp.Length; i++)
{
    Temp[i] = string.Empty;
}

//15,15 -2
sudoku.Fill(samurai.RetSelectedSubSudoku(6, 15 , 6 , 15));
sudoku.SolvedSudoku();
Temp = sudoku.boardconverttostrarray();
samurai.InsertSolveSubSudoku(6, 15, 6, 15, Temp);

//set temp array to zero
for (int i = 0; i < Temp.Length; i++)
{
    Temp[i] = string.Empty;
}

//12,21 -3
sudoku.Fill(samurai.RetSelectedSubSudoku(12, 21, 0, 9));
sudoku.SolvedSudoku();
Temp = sudoku.boardconverttostrarray();
samurai.InsertSolveSubSudoku(12, 21, 0, 9, Temp);

//set temp array to zero
for (int i = 0; i < Temp.Length; i++)
{
    Temp[i] = string.Empty;
}

//0,12 -4
sudoku.Fill(samurai.RetSelectedSubSudoku(0, 9 , 12 , 21));
sudoku.SolvedSudoku();
Temp = sudoku.boardconverttostrarray();
samurai.InsertSolveSubSudoku(0, 9, 12, 21, Temp);

//set temp array to zero
for (int i = 0; i < Temp.Length; i++)
{
    Temp[i] = string.Empty;
}

//12,21 -5
sudoku.Fill(samurai.RetSelectedSubSudoku(12 , 21 , 12 , 21));
sudoku.SolvedSudoku();
Temp = sudoku.boardconverttostrarray();
samurai.InsertSolveSubSudoku(12, 21, 12, 21, Temp);

//set temp array to zero
for (int i = 0; i < Temp.Length; i++)
{
    Temp[i] = string.Empty;
}

最后，通过函数调用，结果将作为输出显示。

// show output
label1.Text = samurai.RetsamuraiSudokuBoard();

以下输出的前四个实例为零，并显示正确的答案。

Sample Image - maximum width is 600 pixels

参考

使用启发式搜索算法解数独。