This article talks about the coding written to solve the Sudoku problem. The program tries to solve the problem as a normal human does. If it still doesn't solve, then it uses the brute force method as a last attempt. There might be cases where the program cannot solve the puzzle which is a scope for developing this program better.

## Introduction

Sudoku is an interesting puzzle suitable for all ages and available easily. I always wanted to write a program to solve Sudoku puzzle once I got interested in it. I did a brief check to find out any Sudoku solvers on the internet but they are all based on brute force method mostly. I wanted to write the code in the way I try to solve the problem manually. I have tried two times in the past but have only been partially successful. Then with the third attempt, I managed to complete to a reasonable state. To begin with, this program hence doesn’t do any guessing work. If it cannot solve the puzzle, then I try to use the brute force method to solve using possible values which are obtained.

## Background

You need to have some understanding of the basics to solve Sudoku. The solution solves the puzzle mostly when one can solve the code without any guessing. For unsolved puzzle, you can use the log to find out possible values, which can be given as an input to try further. I have attached the full working version of the application (EXE) and the source code for further development.

## Using the Code

After porting the solution to a different computer, I had an issue with forms rendering due to DPI issue. Hence, I had to use the below code to solve it. Without these lines, Winform looks blur in different machines.

static class Program
{
[STAThread]
static void Main()
{
if (Environment.OSVersion.Version.Major >= 6)
SetProcessDPIAware();
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new SudokuCSharp.Form1());
}
[System.Runtime.InteropServices.DllImport("user32.dll")]
private static extern bool SetProcessDPIAware();
}

Now to the coding part, my solving pattern is as follows:

To hold the problem statement, I created a structure as this:

private struct mStruct
{
public bool isLocked;
public int curValue;
public bool isSource;
public string posValue;
public int quarter;
public string rem;
}

Then I created an array out of this to hold the problem statement. The fields of the `mstruct`

are explained here:

`isLocked`

: boolean type - to know the value cannot be altered. This can be part of an initial problem or a correct value found after iterations. So there is no option to change once it is fixed. `curvalue`

: integer - the current value on the cell `isSource`

: boolean type - if `true`

, then it is from the problem statement. If `false`

, then it is the value to be found. To differentiate a cell value is from problem statement or a found value. `posvalue`

: `string`

- contains all the possible values a cell can hold in comma separated fashion. `quarter`

: integer - I have split the entire 9x9 cells into 9 quarters. This value tells in which quarter the cell falls into. `rem`

: this is a `string`

to hold any remarks.

I created a 9x9 array with the above `struct`

and hold the problem statement in it. I call this array as `playArray`

as I am going to play with it to find the answers.

I also did an easy to identify a cell from the textbox control name. All the `textbox`

controls are named as this: '`txtq<quarter>r<row no>c<col no>`

'. For example, in the text box name '`txtq2r0c7`

' - `txt`

to define it is a text box, next 2 letters '`q2`

' tells in which quarter it is - here is second quarter. Next 4 letters '`r0c7`

' tell the row and col position - 0^{th} `row`

and 7^{th} `col`

. In this way, I am able to identify from where the value is coming and also easy to assign the values back to the `textbox`

. Refer to the below image for `textbox`

namings and `quarter`

naming.

The reason for dividing the area into quarters is to solve the 3x3 cells in a quarter. As you know, the simple Sudoku rule: No. 1 - 9 to be there non repetitive in a row and col and quarter.

### Loading Problem Statement

It is a bit hard to enter the cells with values from the problem as we need to use the tab to move between the `textbox`

es. Instead, I thought of an easy way to do it - by entering 0 in the cells where there is no value.

For example, the problem statement: `000500809180400060000070010500000070649000000020010000090032000010005600700000480`

is loaded as below. The values are entered row wise and all the `0`

s are assumed as blank on the grid. This helps to load the problem faster.

### Solving the Puzzle

The puzzle is tried iteratively till the solution is found. The key function is:

SolveHorizontalVerticalOrQuadrant("q");
SolveHorizontalVerticalOrQuadrant("r");
SolveHorizontalVerticalOrQuadrant("c");

First solve by quarter, then row wise and then column wise. Note the function name is the same except for the parameter '`q`

','`r`

,'`c`

' to distinguish whether we are solving for quarter, row or col wise. The logic remains the same except based on the parameter that is sent, the array is picked up accordingly and worked upon.

Once I know the list of values in an array, I identify cells that don't have values (cells that need to be solved). Then assign all the possible values to those cells using. To begin with, it can hold all values from 1 to 9. Then I iterate the remaining cells which have values and remove those values from the possible values for that cell.

private readonly string possSolution = @"123456789";

Code where all possible values a cell can hold is determined as below:

for (int j = 0; j < noOfElementsInRowOrCol; j++)
{
if (lStruct[j].curValue > 0)
{
lPossSolution = lPossSolution.Replace(lStruct[j].curValue.ToString(),
"");
}
else
{
row = Int32.Parse(lStruct[j].rem.Substring(1, 1));
col = Int32.Parse(lStruct[j].rem.Substring(3, 1));
zeroCells[k] = row * 10 + col;
k += 1;
}
}

There are two ways to determine the correct value for an empty cell:

If there is only one possible value based on rest of the cells or if there is one unique value in the possible values (If a cells possible values are like this: 1,2,3,2,3 based on the rest of the cells, it clearly tells it can hold either 1 or 2 or 3, Since, 1s occurrence is only once, it clearly shows that is the value it can hold). This is achieved by this function below:

private void GetUniqueValue(string lStr)
{
Array.Clear(lIntArray, 0, lIntArray.Length);
Array.Clear(ldoubleIntArray, 0, ldoubleIntArray.Length);
Array.Clear(ltripleIntArray, 0, ltripleIntArray.Length);
int i = 0;
int j = 0;
int k = 0;
Dictionary<char, int> dict = new Dictionary<char, int>();
try
{
foreach (char ch in lStr)
{
if (dict.ContainsKey(ch))
dict[ch] = dict[ch] + 1;
else
dict.Add(ch, 1);
}
foreach (KeyValuePair<char, int> m in dict)
{
if (m.Value == 1)
{
if (m.Key.ToString() != ":")
{
lIntArray[i] = Int32.Parse(m.Key.ToString());
i++;
}
}
else if (m.Value == 2)
{
if (m.Key.ToString() != ":")
{
ldoubleIntArray[j] = Int32.Parse(m.Key.ToString());
j++;
}
}
else if (m.Value == 3)
{
if (m.Key.ToString() != ":")
{
ltripleIntArray[k] = Int32.Parse(m.Key.ToString());
k++;
}
}
}
}
catch (Exception e)
{
HasChanged = false;
throw e;
}
}

The possible values on the empty cells are updated using the below two methods:

UpdatePossValues(lvalue.ToString(), row.ToString(), col, false);
UpdatePossValues(lvalue.ToString(), col.ToString(), row, true);
UpdatePossValuesInQuarter(lvalue.ToString(), playArray[row, col].quarter);

The possible values after every iteration are printed on the rich `textbox`

as this. Please see the `if`

condition - `isSource`

field is used to pick the possible values on the cells to be solved.

private void PrintPossSolution()
{
for (int i = 0; i < noOfElementsInRowOrCol; i++)
{
for (int j = 0; j < noOfElementsInRowOrCol; j++)
{
if (!playArray[i, j].isSource)
{
richTextBox1.AppendText("R" + i.ToString() + "C" +
j.ToString() + ": " + playArray[i, j].posValue + Environment.NewLine);
}
}
}
}

I have also added some more methods to solve using additional techniques if the usual way of solving doesn't give the complete answer.

SolvePossibleValuesRow2();
SolvePossibleValuesCol2();

For example, let’s assume in Q3, both the cells `r4c0`

and `r4c1`

has possible values which are 2,3, then, this gives a clue that both 2 and 3 can be there only in r4 and not in any other row in that quarter. With this clue, these 2 nos’, can be removed from r3 and r5 in that quarter. This will solve other empty cells by reducing the possible values. The same thing has been extended for `column`

as well. These are called naked pairs.

The solution can be further extended for 3 cells in a quarter both row and col wise which is a scope for further development.

A fully solved puzzle is shown here. The no. 45 against each row and cols shows the count of the row and col. This is used to check whether the program has solved the solution or not.

The log shows the iteration taken to solve. Also, for every cell to be solved, it shows possible values. Here in this case as it is solved, each cell has only one value. In cases where the program could not solve, it shows the possible values - for e.g., R0C1: 5,6,7 which means R0C1 can have either 5 or 6 or 7.

## Points of Interest

The naming convention of the textboxes was one of the good ways to get and assign the values back to the textbox. For more understanding on the naked pairs, please refer to the links below:

## History

- 8
^{th} June, 2020: Version 1.0 - Normal methods to solve - 29
^{th} June, 2020: Version 1.0 (no change) - Implemented Hidden naked pairs in possible solutions - 20
^{th} February, 2021: Version 1.1 - Implemented Brute Force method

I am currently working as programmer in a software company. I focus mostly on Microsoft Products and currently in dot net framework 3.5.