I now have uploaded the complete program regarding the topic Sudoku, which consists of the code parts of the previous posts, on GitHub you can find the source code, and here an installation file, with which the program can also be installed and run without Visual Studio.

## Monday, November 10, 2014

## Monday, November 3, 2014

### Generating Sudokus With C#

In this post I want to explain the creation of Sudokus of arbitrary difficulty with C#. It is very recommended to read the previous posts regarding these topics.

The class

First a random completely filled Sudoku is created, here the same principle as when solving a Sudoku by trying out is used.

Then in a loop always one random field is deleted and it is checked, whether the Sudoku is still uniquely solvable (for this the Sudoku is solved using brute force and the number of possibilites is counted) and at most as hard as the desired difficulty. If yes, we continue with the new Sudoku, otherwise with the old one. This is repeated as long as not the desired number of fields is deleted, afterwards the Sudoku is returned.

But of course it can be the case, that the fields are deleted very unforunately, and the future modification of the current Sudoku is hard. Therefor the number of tries to delete a field is counted, if the counter gets too high, we restart with the completely filled Sudoku.

But we also count this event, as it can also be the case, that the created Sudoku is especially unfortunate. If we have to restart too often, we create a new Sudoku.

And here the code:

The class

*SudokuCreator*is renponsible for generating Sudokus, the function*CreateRandomSudoku()*does this. It expects 2 parameters, the first describes the desired difficulty of the Sudoku, the second the number of fields to be deleted.First a random completely filled Sudoku is created, here the same principle as when solving a Sudoku by trying out is used.

Then in a loop always one random field is deleted and it is checked, whether the Sudoku is still uniquely solvable (for this the Sudoku is solved using brute force and the number of possibilites is counted) and at most as hard as the desired difficulty. If yes, we continue with the new Sudoku, otherwise with the old one. This is repeated as long as not the desired number of fields is deleted, afterwards the Sudoku is returned.

But of course it can be the case, that the fields are deleted very unforunately, and the future modification of the current Sudoku is hard. Therefor the number of tries to delete a field is counted, if the counter gets too high, we restart with the completely filled Sudoku.

But we also count this event, as it can also be the case, that the created Sudoku is especially unfortunate. If we have to restart too often, we create a new Sudoku.

And here the code:

public class SudokuCreator

{

bool Finished;

Random Rnd;

Sudoku Result;

public Sudoku CreateRandomSudoku(int Difficulty, int targetdels)

{

bool Start = true;

bool Done = false;

int Deleted = 0;

int Tolerance = 10;

// Various counters, we count the iterations we do in case the created instance somehow gets stuck, then we reset

int FieldDelCounter = 0;

int ResetCounter1 = 0;

int ResetCounter2 = 0;

Sudoku NewSudoku = null;

Sudoku Fallback = null;

int FallbackCounter = 0;

while (!Done)

{

if (ResetCounter1 > 40)

{

ResetCounter1 = 0;

Start = true;

}

if (ResetCounter2 > 40)

{

ResetCounter2 = 0;

Start = true;

}

if (Start)

{

// first, create a complete sudoku using brute force

NewSudoku = new Sudoku(new List<int>());

List<Sudoku.Field> ToDo = new List<Sudoku.Field>();

for (int i = 0; i < 9; i++)

{

for (int j = 0; j < 9; j++)

{

ToDo.Add(NewSudoku.Fields[i][j]);

}

}

Rnd = new Random();

Finished = false;

BruteForce(ToDo, 0, NewSudoku);

FallbackCounter = 0;

NewSudoku = Result.Copy();

Start = false;

Fallback = null;

}

Sudoku Cloned = NewSudoku.Copy();

int difficulty = Difficulty;

// take out one field and check if solutions still is unique and not harder than desired

if (DeleteField(Cloned, ref difficulty))

{

NewSudoku = Cloned;

Deleted++;

if (NewSudoku.Difficulty == Difficulty && Deleted >= targetdels)

{ // in this case we are done

NewSudoku.Difficulty = difficulty;

return NewSudoku;

}

else if (difficulty == Difficulty && Deleted < targetdels)

{ // matching difficulty found but more fields have to be deleted

Fallback = NewSudoku.Copy();

}

else if (Deleted >= targetdels + Tolerance) // enough fields deleted but not desired difficulty

{

if (FallbackCounter < 100 && Fallback != null) // first try fallback

{

NewSudoku = Fallback.Copy();

}

else

{

NewSudoku = Result.Copy();

ResetCounter1++;

FallbackCounter = 0;

}

Deleted = 0;

}

}

else

{

FieldDelCounter++;

if (FieldDelCounter > 100) // probably no more field can be deleted to get the desired difficulty

{

FieldDelCounter = 0;

NewSudoku = Result.Copy();

Deleted = 0;

ResetCounter2++;

}

continue;

}

}

return Result;

}

private bool DeleteField(Sudoku temp, ref int difficulty)

{

int i = Rnd.Next(0, 9); ;

int j = Rnd.Next(0, 9); ;

// select random not yet deleted field

while (!temp.Fields[i][j].Filled) {

i = Rnd.Next(0, 9);

j = Rnd.Next(0, 9);

}

temp.Fields[i][j].Value = 0;

temp.Fields[i][j].Filled = false;

SudokuSolver Test = new SudokuSolver();

int counter = 0;

int Difficulty = difficulty;

// check the desired characteristics

Sudoku Temp = Test.Solve(temp.Copy(), true, Difficulty);

if (Temp == null)

return false;

temp.Difficulty = Temp.Difficulty;

if (Temp.NrSolutions > 1 || Temp.Difficulty > Difficulty)

return false;

else

return true;

}

private void BruteForce(List<Sudoku.Field> ToDo, int pos, Sudoku Temp)

{ // the brute force implementation for creating complete sudokus

if (Finished)

return;

for (int i = 1; i <= 9; i++)

{

Sudoku Copied = Temp.Copy();

Copied.Fields[ToDo[pos].i][ToDo[pos].j].Filled = true;

Copied.Fields[ToDo[pos].i][ToDo[pos].j].Value = Rnd.Next(1, 10);

bool Valid = true;

foreach (Sudoku.Field f in Copied.GetGroup(ToDo[pos].i, ToDo[pos].j))

{

if (f.Filled && f.Value == Copied.Fields[ToDo[pos].i][ToDo[pos].j].Value)

{

Valid = false;

break;

}

}

if (Valid)

{

if (pos < ToDo.Count - 1)

BruteForce(ToDo, pos + 1, Copied);

else

{

Finished = true;

Result = Copied;

}

}

}

}

}

Subscribe to:
Posts (Atom)