Informed Search Algorithms to Solve Sudoku Samurai

• Download English article - 597 KB
• Download Persian article - 984 KB
• Download source - 27.22 KB

Introduction

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.

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

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:

1. Every 3 × 3 square must be unique from one to nine without repeating.
2. The inner square of the value of a row is not unique.
3. Should be built in each square of a column value is not unique.

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

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.

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

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

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

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

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

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

The following output four of the first instance is zero and shows the correct answer.

Reference

• Solving Sudoku using Informed Search Algorithms