|
The
below program will solve Low, Medium and some of the difficult Sudoku puzzle. I
am still working on this to make this code to solve any types of Sudoku
puzzles. Experience it by testing your puzzle, Go through the code and leave
your comments to improve it.
Steps to Test/Execute the code:
1. Input
your puzzle in the “ProblemArray” property.
2. Input
“0” in the empty cell.
namespace Sudoku
{
public class SolveSudoku
{
static void Main(string[] args)
{ var
sudokuSolver = new SudokuSolver(ProblemArray);
sudokuSolver.Solve();
Console.ReadLine();
}
protected
static int[]
ProblemArray
{
get
{
////==
Low Grade
//return
new int[] {
// 0, 7, 1, 0, 9, 0, 8, 0,
0,
// 0, 0, 0, 3, 0, 6, 0, 0,
0,
// 4, 9, 0, 0, 0, 0, 7, 0,
5,
// 0, 1, 0, 9, 0, 0, 0, 0,
0,
// 9, 0, 2, 0, 0, 0, 6, 0,
3,
// 0, 0, 0, 0, 0, 8, 0, 2,
0,
// 8, 0, 5, 0, 0, 0, 0, 7,
6,
// 0, 0, 0, 6, 0, 7, 0, 0,
0,
// 0, 0, 7, 0, 4, 0, 3, 5, 0
// };
////==
Medium Grade
//return
new int[] {
// 0, 0, 0, 0, 4, 0, 0, 0,
0,
// 0, 4, 1, 0, 0, 0, 8, 5,
0,
// 5, 0, 0, 1, 8, 2, 0, 0,
6,
// 6, 8, 0, 0, 0, 7, 0, 4,
5,
// 0, 0, 0, 0, 0, 0, 0, 0,
0,
// 1, 5, 0, 4, 0, 0, 0, 6,
8,
// 4, 0, 0, 3, 6, 8, 0, 0,
2,
// 0, 1, 2, 0, 0, 0, 6, 9,
0,
// 0, 0, 0, 0, 9, 0, 0, 0, 0,
// };
//==
Difficult Grade
return
new int[] {
0, 1, 8,
0, 2, 0, 0, 0, 0,
0, 6, 5,
1, 4, 0, 8, 0, 2,
0, 0, 0,
0, 0, 6, 5, 0, 1,
0, 0, 3,
0, 7, 0, 9, 1, 6,
0, 0, 0,
0, 0, 0, 0, 0, 0,
1, 5, 2,
0, 6, 0, 3, 0, 0,
7, 0, 6,
4, 0, 0, 0, 0, 0,
3, 0, 1,
0, 5, 9, 2, 7, 0,
0, 0, 0,
0, 8, 0, 6, 9, 0
};
}
}
}
}
namespace Sudoku
{
using
System;
using
System.Collections.Generic;
using
System.Linq;
using
System.Text;
public class SudokuSolver
: SudokuSource
{
public
SudokuSolver(int[] ProblemArray)
{
FillSudokuGrid(ProblemArray);
Console.WriteLine("====== Source Sudoku ======");
WriteSudokuGrid();
}
public void Solve()
{
int
previousValue;
int
currentValue;
Func<int> SumOfSudokuValue = () => SourceArray.Sum(t
=> t.Sum());
do
{
previousValue =
SumOfSudokuValue();
SolveArray();
currentValue =
SumOfSudokuValue();
}
while
(previousValue != currentValue);
Console.WriteLine("====== Solved Sudoku ======");
WriteSudokuGrid();
}
private
void SolveArray()
{
var
list = new List<int>();
for
(var row = 0; row < SourceArray.Length;
row++)
{
for
(var column = 0; column <
SourceArray.Length; column++)
{
var
currentValue = SourceArray[row][column];
if
(currentValue > 0)
continue;
list.Clear();
for
(var i = 1; i <= 9; i++)
{
if (CheckCurrentFullRow(row, column, i))
{
if (CheckCurrentFullColumn(row, column, i))
{
if (CheckCurrentFullSquare(row, column, i))
list.Add(i);
}
}
}
if
(list.Count() == 1)
{
SourceArray[row][column] = list[0];
}
else
if (list.Count() > 1)
{
var posValue = CheckNeighbourValue(row, column, list);
if (posValue > 0) SourceArray[row][column] = posValue;
}
}
}
}
//Check Row
contains the Assigning Value
private
bool CheckCurrentFullRow(int Row, int Column, int AssignValue)
{
for
(var i = 0; i <= 8; i++)
{
if
(SourceArray[Row][i] == AssignValue && Column != i)
return
false;
}
return true;
}
//Check
Column contains the Assigning value.
private
bool CheckCurrentFullColumn(int Row, int Column, int AssignValue)
{
for
(var i = 0; i <= 8; i++)
{
if
(SourceArray[i][Column] == AssignValue && i != Row)
return
false;
}
return
true;
}
//Check
Square Contains the Assigning Value.
private
bool CheckCurrentFullSquare(int Row, int Column, int AssignValue)
{
var
rowStart = (Row / 3) + 1;
var
rowIndexEnd = (rowStart * 3) - 1;
if
(rowIndexEnd == 0) rowIndexEnd = 3;
var
rowIndexStart = rowIndexEnd - 2;
var
columnStart = (Column / 3) + 1;
var
columnIndexEnd = (columnStart * 3) - 1;
if
(columnIndexEnd == 0) columnIndexEnd = 3;
var
columnIndexStart = columnIndexEnd - 2;
for
(var curRow = rowIndexStart; curRow <=
rowIndexEnd; curRow++)
{
for
(var curColumn = columnIndexStart; curColumn
<= columnIndexEnd; curColumn++)
{
if
(SourceArray[curRow][curColumn] == AssignValue && curColumn != Column
&& curRow != Row)
return false;
}
}
return
true;
}
private
int CheckNeighbourValue(int CurrentRow, int CurrentColumn,
List<int>
PossibleIntList)
{
var
rowStart = (CurrentRow / 3) + 1;
var
rowIndexEnd = (rowStart * 3) - 1;
if
(rowIndexEnd == 0) rowIndexEnd = 3;
var
rowIndexStart = rowIndexEnd - 2;
var
columnStart = (CurrentColumn / 3) + 1;
var
columnIndexEnd = (columnStart * 3) - 1;
if
(columnIndexEnd == 0) columnIndexEnd = 3;
var
columnIndexStart = columnIndexEnd - 2;
var
applicableRows = new List<int>();
var
currentSquareRows = new List<int>();
for
(var curRow = rowIndexStart; curRow <=
rowIndexEnd; curRow++)
{
currentSquareRows.Add(curRow);
if
(CurrentRow != curRow)
{
applicableRows.Add(curRow);
}
}
var
applicableColumns = new List<int>();
var
currentSquareColumns = new List<int>();
for
(var curColumn = columnIndexStart; curColumn
<= columnIndexEnd; curColumn++)
{
currentSquareColumns.Add(curColumn);
if
(CurrentColumn != curColumn)
{
applicableColumns.Add(curColumn);
}
}
var
resultArray = new List<int>();
for
(int i = 0; i < PossibleIntList.Count();
i++)
{
var
assignValue = PossibleIntList[i];
var
newIntArray = NewArray;
//Copy
all values from exisiting array
for
(var curRow = rowIndexStart; curRow <=
rowIndexEnd; curRow++)
{
for
(var curColumn = columnIndexStart; curColumn
<= columnIndexEnd; curColumn++)
{
if (curRow == CurrentRow && curColumn == CurrentColumn)
continue;
newIntArray[curRow][curColumn] = SourceArray[curRow][curColumn];
}
}
foreach
(var applicableColumn in
applicableColumns)
{
for
(int row = 0; row <= 8; row++)
{
if (SourceArray[row][applicableColumn] == assignValue &&
!currentSquareRows.Contains(row))
{
if (newIntArray[CurrentRow][applicableColumn] == 0)
newIntArray[CurrentRow][applicableColumn] = assignValue;
foreach (var
applicableRow in applicableRows)
{
if (newIntArray[applicableRow][applicableColumn] ==
0)
newIntArray[applicableRow][applicableColumn] = assignValue;
}
break;
}
}
}
foreach
(var applicableRow in
applicableRows)
{
for
(int column = 0; column <= 8; column++)
{
if (SourceArray[applicableRow][column] == assignValue &&
!currentSquareColumns.Contains(column))
{
if (newIntArray[applicableRow][CurrentColumn] == 0)
newIntArray[applicableRow][CurrentColumn] = assignValue;
foreach (var
applicableColumn in applicableColumns)
{
if (newIntArray[applicableRow][applicableColumn] ==
0)
newIntArray[applicableRow][applicableColumn] = assignValue;
}
break;
}
}
}
//Check
all square having values.
var
allHavingValues = true;
newIntArray[CurrentRow][CurrentColumn]
= -1;
for
(var curRow = rowIndexStart; curRow <=
rowIndexEnd; curRow++)
{
for
(var curColumn = columnIndexStart; curColumn
<= columnIndexEnd; curColumn++)
{
if (newIntArray[curRow][curColumn] == 0)
{
allHavingValues = false;
}
}
}
if
(allHavingValues)
{
resultArray.Add(assignValue);
}
}
var
possibleValue = 0;
if
(resultArray.Count() == 1)
possibleValue = resultArray[0];
return
possibleValue;
}
private
void WriteSudokuGrid()
{
var
objString = new StringBuilder();
foreach
(var t in
SourceArray)
{
for
(var j = 0; j < SourceArray.Length; j++)
{
objString.Append(t[j] + " ");
}
objString.Append("\n");
}
Console.WriteLine(objString.ToString());
}
}
public abstract class SudokuSource
{
protected
int[][] SourceArray { get;
set; }
protected
void FillSudokuGrid(int[]
ProblemArray)
{
SourceArray = new int[9][];//Row Declaration.
for
(var i = 0; i < SourceArray.Length; i++)
{
SourceArray[i] = new int[9];//Column Declaration
}
Func<int, int, int> FindCurrentCell = (Row, Column) => (Row *
9) + Column;
//Push
the values into the array.
for
(var i = 0; i < SourceArray.Length; i++)
{
for
(var j = 0; j < SourceArray.Length; j++)
{
SourceArray[i][j] =
ProblemArray[FindCurrentCell(i, j)];
}
}
}
protected
int[][] NewArray
{
get
{
var
newArrray = new int[9][];
for
(var i = 0; i < newArrray.Length; i++)
{
newArrray[i] = new int[9];
}
foreach
(var t in newArrray)
{
for
(var j = 0; j < newArrray.Length; j++)
{
t[j] = 0;
}
}
return
newArrray;
}
}
}
}
Program Output: 
|