知性搜索算法解决数独武士（译文）

原文地址：https://www.codeproject.com/Articles/237372/Informed-search-algorithms-to-solve-Sudoku-Samurai

原文作者：hosein fereidooni

译文由本站 robot-v1.0 翻译

前言

Informed search algorithms to solve Sudoku Samurai

明智的搜索算法可解决Sudoku Samurai

• 下载英文文章-597 KB(Download English article - 597 KB)
• 下载波斯文-984 KB(Download Persian article - 984 KB)
• 下载源27.22 KB(Download source - 27.22 KB)

介绍(Introduction)

武士数独是一种在东亚流行的游戏.这种数独由五个内部数独组成.每个数独都互相覆盖.在本文中,我们使用已知的搜索算法来解决Sudoku.(Samurai Sudoku is a game popular in East Asia. This type of Sudoku consists of five internal Sudoku. Each Sudoku covers the other. In this article, we solve Sudoku using informed search algorithms.) 在另一篇论文中,完整描述了9 x 9 Sudoku解决方案.每个班级的数独解算器都会在主板上发布并回答.武士数独可以最终解决.面向对象程序和类的概念得到了很好的体现.(In another paper, a 9 x 9 Sudoku solution was fully described. The Sudoku solver to each class is posted and answered on the main board. Samurai Sudoku can be solved finally. The concept of object-oriented programs and classes are well represented.)

什么是武士数独(What is Samurai Sudoku)

武士数独包括五个主要部分.此Sudoku 21 * 21由主板组成.数独是四个侧面的数独,位于中心.数独被3 x 3的彼此覆盖.数独中间数独的四个部分由四个覆盖.数独的规则如下:(Samurai Sudoku consists of five main sections. This Sudoku 21 * 21 is composed of a main board. Sudoku is a Sudoku on four sides and is located in the center. Sudoku is a 3 x 3 of each other is covered. The four sections of the middle Sudoku Sudoku side is covered by four. The rules of Sudoku are as follows:)

• 每3×3平方必须从1到9唯一,且不能重复.(Every 3 × 3 square must be unique from one to nine without repeating.)
• 行值的内部平方不是唯一的.(The inner square of the value of a row is not unique.)
• 应该在每个方格中建立一个列的值不是唯一的.(Should be built in each square of a column value is not unique.) 在任何Sudoku中,内部行和列必须唯一,这一点很重要.而且并不是从第21行到第21列的末尾是唯一的.内部顺序对于解决Sudoku并不重要.(It is important that the internal row and column must be unique in any Sudoku. And not from beginning to end of row 21 and column is unique. The internal order is not important to solve Sudoku.)

解(Solution)

该算法首先建立21 * 21的范围.它由用户初始化.包含数字441的字符串作为输入发送到主类.有了这个输入,算法就开始工作.该作品分为五个主要部分.此选择是程序员,不会影响解决方案.然后,设备将发送类数独解算器.在该级别范围内,使用填充方法填充原始的9 x 9板.数独求解器和求解方法由主板调用完成.在该算法中,对于零数组的每个元素使用.(The algorithm first builds a range of 21 * 21. It is initialized by the user. A string that contains the number 441 is sent as input to the main class. Given this input, the algorithm begins its work. The piece takes five main parts. This choice is a programmer and does not affect the solution. The device then sends a Class Sudoku Solver. In this class range using the method of filling the original 9 x 9 board is filled. Sudoku Solver and solution method is called by the main board is complete. In this algorithm, for each element of an array of zero is used.) 最后,解决数独21 * 21的主板就位.通过此过程,将连续五次解决武士数独问题.(Finally, the main board to solve sudoku 21 * 21 and is in its place. With this process, five times in a row Samurai Sudoku will be resolved.)

分析代码(Analysis Code)

它由广告和展示两层组成.内部类的Sudoku实例化.它也可以与原始武士一起使用(It is composed of two layers of commercial and presentation. Sudoku for the internal class is instantiated. It will also work with the original samurai) Business 创建的类.第一堂课将解释…(class that is created. The first class will explain…)

武士商务舱(Samurai Business Class)

此类是21 * 21的二维数组,用作容纳使用武士数独的主板的容器.(This class is a two-dimensional array of 21 * 21 as a reservoir for holding the main board that uses the Samurai Sudoku.)

//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(RetSelectedSubSudoku)

此方法采用四个输入值并放置振铃.这将导致数组(This method takes four input values and puts the ring. This will result in an array of) string 值分开并作为输出返回.(values separated and returned as output.)

//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(InsertSolveSubSudoku)

此方法解决了将其原来位置建立的Sudoku重新放置在原始数组中的问题.此方法在输入字段中获取四个输入数字值,然后放置其位置.(This method solved the Sudoku built in their place back in the original array. This method takes four input numeric values in the input field and puts his place.)

//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(RetSamuraiSudokuBoard)

此方法需要(This method takes a) string 然后返回原始的武士(and returns to the original samurai.)

//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()类(Sudoku() class)

在将此类文件放在参考书中之前.(Prior to this class of paper is placed in the reference.)

表示层(Presentation Layer)

在这一层中,输入被接收并将被发送到类.获取输出后,将显示结果.(In this layer, the input is received and will be sent to the class. After getting the output, results will be displayed.)

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();

在此阶段之前,将定义处理和输入所需的变量和数组.已经完成了输入所需的步骤.接收原型和数组中所需类的数量以及初始输出.每次将数独解算器发送到内部选择和值时,都会重复第五阶段.答案可以溶解在其先前的位置.(Until this stage, variables and arrays needed for the processing and input are defined. The steps required for entry have been made. Prototyping and the amount of required classes in the array and initial output are received. The fifth stage is repeated every time a Sudoku Solver is sent to the internal selection and value. The answer can be dissolved in its previous location.)

//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;
}

最后,通过函数调用可以显示输出.(Finally, with the function call results in output to be displayed.)

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

以下第一个实例的输出4为零,并显示正确的答案.(The following output four of the first instance is zero and shows the correct answer.)

参考(Reference)

• 使用知情搜索算法求解数独(Solving Sudoku using Informed Search Algorithms)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。