Evil Science A whole load of stuff

25Feb/140

C# Brute Force Sudoku Algorithm

I've created in C# an algorithm that solves sudoku using the brute force method. This algorithm is contained in the class csSudokuBruteForce.cs that can be found on GitHub?here.

A little bit about it

The?csSudokuBruteForce class contains a class called csCell which represents a cell within a sudoku grid with properties representing the row, column, box that cell belongs to, the cell's value and whether it is solved; 81 of these cells are stored within a generic list called grid which represent sudoku.

The public method BruteForce is called to begin the brute algorithm, which returns a integer array representing the solved sudoku. Testing on Quad core PC shows that solutions can be found in under a second for any tried.

This algorithm doesn't test the validity of the provided sudoku before it starts the brute force algorithm, and may therefore crash out if what is given to it is incomplete, malformed, containing incorrect characters. It just assumes it'll get a string 81 characters in length that consists of only the numbers 1 to 9 and 0.

Using the code

This class is easy to use, and requires only a string of 81 characters?representing?the sudoku to be solved. ?Here's an example of it's use:


csSudokuBruteForce b = new csSudokuBruteForce();

<span style="line-height: 1.5em;">string puzzle = "003020600900305001001806400008102900700000008006708200002609500800203009005010300";</span>

//solve the sudoku and return the result as an integer array

int [] solution = ?b.BruteForce(puzzle);

If you're using this code in a C# Console Application and want to output the array containing the solution, here's how to do it using Linq:


Console.WriteLine (
solution.Select((val, ind) => val.ToString() + ((ind+1) % 9 == 0 ? "\n" : ""))
.Aggregate((total, current) => total + current)
);

What about Project Euler 96?

No. I'm not going to tell you how to to solve it.

Go on!

No.

Please?

I'll give you a hand, but no more.?Here's how to extract one puzzle at a time from Euler 96's text file of puzzles:


//load the entire sudoku.txt file
List<string> puzzles =?new StreamReader("sudoku.txt").sr.ReadToEnd().Split('\n').ToList();

string puzzle;

for (int ctr = 0; ctr <= 49; ctr++)</span>
{

puzzle = puzzles.Where((val, ind) => ind >= (ctr * 10) +1 &amp;amp;amp; ind < (ctr * 10) +10)
.Aggregate((total, current) => total + current);

}

It uses loads the text file into a generic list, and then uses Linq to extract the required data from that file. Use your brain and work out how to use it yourself.

You're welcome.

Filed under: C# Leave a comment
Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

No trackbacks yet.