MARCIN.com
Marcin Jamro, PhD, DSc
How to solve Sudoku?
C# | .NET | Algorithms
Sudoku is a popular game that requires you to fill empty cells of the 9x9 board with numbers from 1 to 9. However, each row, each column, and each 3x3 box must contain only unique numbers. You can solve this puzzle with the backtracking algorithm.
Let's start with the following code:
bool Solve() { (int row, int col) = GetEmpty(); if (row < 0 && col < 0) { return true; } for (int i = 1; i <= 9; i++) { if (IsCorrect(row, col, i)) { board[row, col] = i; if (Solve()) { return true; } else { board[row, col] = 0; } } } return false; }
The GetEmpty
method searches for the first cell that is not already filled. Its code is as follows:
(int, int) GetEmpty() { for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { if (board[r, c] == 0) { return (r, c); } } } return (-1, -1); }
The IsCorrect
method ensures that after entering a provided number in a given cell (with specified row and column), the board still meets criteria of the Sudoku game. Its code is presented below:
bool IsCorrect(int row, int col, int num) { for (int i = 0; i < 9; i++) { if (board[row, i] == num) { return false; } if (board[i, col] == num) { return false; } } int rs = row - row % 3; int cs = col - col % 3; for (int r = rs; r < rs + 3; r++) { for (int c = cs; c < cs + 3; c++) { if (board[r, c] == num) { return false; } } } return true; }
You can check the Sudoku puzzle with the following code:
int[,] board = new int[,] { { 0, 5, 0, 4, 0, 1, 0, 0, 6 }, { 1, 0, 0, 9, 5, 0, 8, 0, 0 }, { 9, 0, 4, 0, 6, 0, 0, 0, 1 }, { 6, 2, 0, 0, 0, 5, 3, 0, 4 }, { 0, 9, 0, 0, 7, 0, 2, 0, 5 }, { 5, 0, 7, 0, 0, 0, 0, 8, 9 }, { 8, 0, 0, 5, 1, 9, 0, 0, 2 }, { 2, 3, 0, 0, 0, 6, 5, 0, 8 }, { 4, 1, 0, 2, 0, 8, 6, 0, 0 } }; if (Solve()) { for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) { Console.Write($"{board[r, c]} "); } Console.WriteLine(); } }
This entry can contain content, including parts of code, from one of my books, namely from the Second Edition of C# Data Structures and Algorithms, published by Packt Publishing in 2024. If you want to get a detailed description of this algorithm, as well as about many other algorithms, I encourage you to take a look at the mentioned book. You can buy it here.
The content, including any part of code, is presented without warranty, either express or implied. The author cannot be held liable for any damages caused or alleged to have been caused directly or indirectly by any content shown on this website.
Hello, I am Marcin
Reliable entrepreneur with 10+ years of companies operation, such as CEO at a few IT companies. I was an author of a few software & hardware products, still open to new ideas & cooperation.
Helpful expert with 10+ years of experience, together with PhD and DSc in Computer Science. I was an author of books and publications, as well as an expert in international projects.
Experienced developer with 10+ years of development and 100+ completed projects. I worked on various complex international projects, e.g. at Microsoft in USA and as CTO at a few companies. I have MCP, MCTS and MCPD certificates.
You can read more about me in my short bio. I am waiting for contact at [email protected], as well as at my Facebook and LinkedIn profiles.
Books
I am an author of a few books and numerous publications, also in high-quality international scientific journals.
If you want to learn data structures and algorithms in the context of C#, let's take a look at my newest book. It is the second edition of C# Data Structures and Algorithms. You can buy it here.
Projects
Do you like traveling? If so, discover an amazing world with local guides, right here and right now at: https://camaica.com
Travels
I love travels, learning new cultures and regions, meeting outstanding people, as well as taking pictures of beautiful places. Take a look at my travel diary.