In this article, we're going
to look at Sudoku puzzle and algorithms used for solving it.
The Sudoku Puzzle
Simply put, Sudoku is a combinatorial
number placement puzzle with 9 x 9 cell grid partially filled in with numbers
from 1 to 9. The goal is to fill remaining, blank fields with the rest of
numbers so that each row and column will have only one number of each kind.
What's more, every 3 x 3 subsection of
the grid can't have any number duplicated as well. The level of difficulty
naturally rises with the number of blank fields in each board.
Problem Board
8 . . . . . . . .
. . 3 6 . . . . .
. 7 . . 9 . 2 . .
. 5 . . . 7 . . .
. . . . 4 5 7 . .
. . . 1 . . . 3 .
. . 1 . . . . 6 8
. . 8 5 . . . 1 .
. 9 . . . . 4 . . Solved Board
And, to spoil the solution quickly – the correctly solved puzzle
will give us the following result:
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
C# code
|
static void Main(string[] args) { var
sudoku = new char[,] { { '8', '.', '.', '.', '.', '.', '.', '.', '.' }, { '.', '.', '3', '6', '.', '.', '.', '.', '.' }, { '.', '7', '.', '.', '9', '.', '2', '.', '.' }, { '.', '5', '.', '.', '.', '7', '.', '.', '.' }, { '.', '.', '.', '.', '4', '5', '7', '.', '.' }, { '.', '.', '.', '1', '.', '.', '.', '3', '.' }, { '.', '.', '1', '.', '.', '.', '.', '6', '8' }, { '.', '.', '8', '5', '.', '.', '.', '1', '.' }, { '.', '9', '.', '.', '.', '.', '4', '.', '.' } };
solveSudoku(sudoku);
Console.ReadLine(); }
public static void
solveSudoku(char[,] sudokuBoard) { if
(sudokuBoard == null || sudokuBoard.Length == 0) return;
Problemsolver(sudokuBoard); } private static bool
Problemsolver(char[,] sudokuBoard) { for (int i =
0; i < sudokuBoard.GetLength(0); i++) { for (int j =
0; j < sudokuBoard.GetLength(1); j++) {
if
(sudokuBoard[i, j] == '.') { for (char c =
'1'; c <= '9'; c++) {
if (isValid(sudokuBoard, i, j, c))
{
sudokuBoard[i, j] = c;
if (Problemsolver(sudokuBoard)) return true;
else
sudokuBoard[i, j] = '.'; } } return false; } } } for (int i =
0; i < sudokuBoard.GetLength(0); i++) { for (int j =
0; j < sudokuBoard.GetLength(1); j++) {
Console.Write(sudokuBoard[i, j] + " "); }
Console.Write(Environment.NewLine); }
return true; } private static bool
isValid(char[,] board, int row, int
col, char c) { for (int i =
0; i < 9; i++) { //check
row if
(board[i, col] != '.' && board[i, col] == c) return false; //check column if
(board[row, i] != '.' && board[row, i] == c) return false; //check
3*3 block if
(board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] != '.'
&& board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] == c) return false; } return true; } |
Output
.png)