Any ideas on making my code a bit more clean and efficient? Any criticism is appreciated.
I don't like that I'm calling my lengthy DeepCopy
method so many times, but the BinaryFormatter
approach is much much slower. I haven't come up with a better approach than doing a deep copy of the entire SudokuBoard
due to all of the interwoven pointers, but I'm sure one exists.
Cell
public class Cell
{
public int value { get; private set; }
public bool isBlank { get; set; }
public List<int> possibilities { get; private set; }
public Section row { get; private set; }
public Section column { get; private set; }
public Section region { get; private set; }
public Cell(int v, bool b)
{
value = v;
isBlank = b;
if (!isBlank)
possibilities = new List<int>();
else
possibilities = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
}
public void SetSections(Section r, Section c, Section reg)
{
row = r;
column = c;
region = reg;
}
public void AssignCellValue()
{
// Only continue if cell isn't a preset value
if (isBlank)
{
// If answer found, block cell from use and modify peer region possibilities
if (possibilities.Distinct().Count() == 1)
{
value = possibilities.First(); // Set value to only possibility
possibilities.Clear();
isBlank = false;
row.RefactorPossibilities(); // In peer regions change each cell's possibilities
column.RefactorPossibilities(); // to reflect value change
region.RefactorPossibilities();
row.SingleOut();
column.SingleOut();
region.SingleOut();
}
}
}
public void ForceCellValue(int value)
{
if (isBlank)
{
possibilities.Clear();
possibilities.Add(value);
AssignCellValue();
}
}
}
Section
public enum SectionType { ROW, COLUMN, REGION }
public class Section
{
public List<Cell> items;
public SectionType type;
public Section(SectionType t)
{
type = t;
}
public void AssignCells(List<Cell> cells)
{
items = cells;
}
// Step through each cell, if a hardcoded cell is found then retrace
// the section and remove that possibility from each cell
public void RefactorPossibilities()
{
for (int i = 0; i < items.Count; i++)
{
if (!items[i].isBlank) // if cell has a set value
{
for (int j = 0; j < items.Count; j++) // retrace each cell in region and remove set value
if (items[j].isBlank) // from blank cells possibility list
{
if (items[j].possibilities.Count > 1)
{
items[j].possibilities.Remove(items[i].value);
}
if (items[j].possibilities.Distinct().Count() == 1) // if cell has only 1 possibility value left
{
if (!items.Any(x => x.value == items[j].possibilities.First()))
{
items[j].AssignCellValue(); // set cell to that value
}
}
}
}
}
}
// Search the section for possibility values occurring once, and if found set it to specified cell
public void SingleOut()
{
for (int i = 0; i < items.Count; i++)
{
int numSpecificPoss = items.OfType<Cell>()
.Where(x => x.isBlank)
.Where(x => x.possibilities.Contains(i + 1))
.Count();
if (numSpecificPoss == 1)
{
Cell SingledOut = items.OfType<Cell>()
.Where(x => x.isBlank)
.Where(x => x.possibilities.Contains(i + 1))
.Single();
//Console.WriteLine("Singled out");
SingledOut.ForceCellValue(i + 1);
}
}
}
public bool SectionVerified()
{
int allValues = items.OfType<Cell>()
.Where(x => x.value > 0)
.Select(x => x.value).ToArray()
.Count();
int distinctValues = items.OfType<Cell>()
.Where(x => x.value > 0)
.Select(x => x.value).ToArray()
.Distinct()
.Count();
if (allValues == distinctValues)
return true;
else
return false;
}
}
SudokuBoard
public class SudokuBoard
{
private Cell[,] board;
private List<Section> rows;
private List<Section> columns;
private List<Section> regions;
public static SudokuBoard DeepCopy(SudokuBoard copy)
{
SudokuBoard other = (SudokuBoard) copy.MemberwiseClone();
other.board = new Cell[9,9];
other.rows = new List<Section>();
other.columns = new List<Section>();
other.regions = new List<Section>();
for (int i = 0; i < 9; i++)
{
other.rows.Add(new Section(SectionType.ROW)); // initialize each Row
other.columns.Add(new Section(SectionType.COLUMN)); // initalize each Column
other.regions.Add(new Section(SectionType.REGION)); // initialize each Region
}
// Initalize each cell with it's preset value and whether or not it's a blank (modifiable) square
for (int i = 0; i < other.board.GetLength(0); i++)
{
for (int j = 0; j < other.board.GetLength(1); j++)
{
if ((copy.board[i, j].value > 0) && (copy.board[i, j].value <= 9)) // if coordinate is a preset cell, set it to value and isBlank false
other.board[i, j] = new Cell(copy.board[i, j].value, false);
else // else set it to zero and isBlank true
other.board[i, j] = new Cell(0, true);
}
}
// Assign each row and column it's group of cells
List<Cell> rowCells = new List<Cell>();
List<Cell> colCells = new List<Cell>();
for (int i = 0; i < other.board.GetLength(0); i++)
{
for (int j = 0; j < other.board.GetLength(1); j++)
{
rowCells.Add(other.board[i, j]); // load up all cells in row
colCells.Add(other.board[j, i]); // load up all cells in column
}
other.rows[i].AssignCells(rowCells); // set each rows cells
other.columns[i].AssignCells(colCells); // set each columns cells
rowCells = new List<Cell>(); // generate new List after each row as to not delete from memory
colCells = new List<Cell>(); // generate new List after each column as to not delete from memory
}
// Assign each region it's group of cells
List<Cell> regCells = new List<Cell>();
int reg = 0;
for (int i = 0; i < other.board.GetLength(0); i += 3)
{
for (int j = 0; j < other.board.GetLength(1); j += 3)
{
for (int k = i; k < i + 3; k++)
for (int l = j; l < j + 3; l++)
regCells.Add(other.board[k, l]); // load up all cells in region
other.regions[reg].AssignCells(regCells); // set each regions cells
++reg; // increment counter for List of regions
regCells = new List<Cell>(); // generate new List after each region as to not delete from memory
}
}
// Assign each cell their sections
int regNum = 0;
for (int i = 0; i < other.board.GetLength(0); i++)
{
for (int j = 0; j < other.board.GetLength(1); j++)
{
if ((j % 3 == 0) && (j != 0)) // step over one region horizontally every 3 cells
regNum++;
other.board[i, j].SetSections(other.rows[i], other.columns[j], other.regions[regNum]);
}
if (i < 2) // bring region back to 0
regNum = 0;
else if (i < 5) // bring region back to 3
regNum = 3;
else if (i < 8) // bring region back to 6
regNum = 6;
}
other.Refactor();
return other;
}
public SudokuBoard(int[,] presets)
{
if ((presets.GetLength(0) > 9) || (presets.GetLength(1) > 9))
throw new Exception("Error - Sudoku board size too large");
else
{
board = new Cell[9,9];
rows = new List<Section>();
columns = new List<Section>();
regions = new List<Section>();
// Initialize each section
for (int i = 0; i < 9; i++)
{
rows.Add(new Section(SectionType.ROW)); // initialize each Row
columns.Add(new Section(SectionType.COLUMN)); // initalize each Column
regions.Add(new Section(SectionType.REGION)); // initialize each Region
}
// Initalize each cell with it's preset value and whether or not it's a blank (modifiable) square
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if ((presets[i, j] > 0) && (presets[i, j] <= 9)) // if coordinate is a preset cell, set it to value and isBlank false
board[i, j] = new Cell(presets[i, j], false);
else // else set it to zero and isBlank true
board[i, j] = new Cell(0, true);
}
}
// Assign each row and column it's group of cells
List<Cell> rowCells = new List<Cell>();
List<Cell> colCells = new List<Cell>();
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
rowCells.Add(board[i, j]); // load up all cells in row
colCells.Add(board[j, i]); // load up all cells in column
}
rows[i].AssignCells(rowCells); // set each rows cells
columns[i].AssignCells(colCells); // set each columns cells
rowCells = new List<Cell>(); // generate new List after each row as to not delete from memory
colCells = new List<Cell>(); // generate new List after each column as to not delete from memory
}
// Assign each region it's group of cells
List<Cell> regCells = new List<Cell>();
int reg = 0;
for (int i = 0; i < board.GetLength(0); i += 3)
{
for (int j = 0; j < board.GetLength(1); j += 3)
{
for (int k = i; k < i + 3; k++)
for (int l = j; l < j + 3; l++)
regCells.Add(board[k, l]); // load up all cells in region
regions[reg].AssignCells(regCells); // set each regions cells
++reg; // increment counter for List of regions
regCells = new List<Cell>(); // generate new List after each region as to not delete from memory
}
}
// Assign each cell their sections
int regNum = 0;
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if ((j % 3 == 0) && (j != 0)) // step over one region horizontally every 3 cells
regNum++;
board[i, j].SetSections(rows[i], columns[j], regions[regNum]);
}
if (i < 2) // bring region back to 0
regNum = 0;
else if (i < 5) // bring region back to 3
regNum = 3;
else if (i < 8) // bring region back to 6
regNum = 6;
}
}
}
public List<Cell> GetPossibleGuesses()
{
var guesses = board.OfType<Cell>()
.Where(x => x.isBlank)
.ToList();
return guesses;
}
public Section GetSection(int position, SectionType type)
{
Section section = null;
if (type == SectionType.ROW)
section = rows[position];
else if (type == SectionType.COLUMN)
section = columns[position];
else if (type == SectionType.REGION)
section = regions[position];
return section;
}
public int GetNumberOfBlank()
{
return board.OfType<Cell>().Count(x => x.isBlank);
}
public bool Finished()
{
if( board.OfType<Cell>().All(x => (!x.isBlank) ))
return true;
else
return false;
}
public void Refactor()
{
for (int i = 0; i < 9; i++) // Initialize each cell's potential values
{
rows[i].RefactorPossibilities();
columns[i].RefactorPossibilities();
regions[i].RefactorPossibilities();
}
}
public void PrintEverything()
{
Console.WriteLine();
int row = 0;
for (int j = 0; j < 9; j++)
{
for(int z = 0; z < 3; z++)
{
for (int k = 0; k < 9; k++)
{
if ((k % 3 == 0) && ( k!= 0))
Console.Write(" █ ");
else if( k!= 0 )
Console.Write(" | ");
for (int l = row; l < row + 3; l++)
{
if (board[j, k].isBlank)
if (board[j, k].possibilities.Contains(l+1))
Console.Write(board[j, k].possibilities.Find(x => x == l+1));
else
Console.Write(" ");
else if (!board[j, k].isBlank)
{
Console.ForegroundColor = ConsoleColor.Green;
if (l == 4)
Console.Write(board[j, k].value);
else
Console.Write(" ");
Console.ForegroundColor = ConsoleColor.White;
}
else
Console.Write(" ");
}
}
if (row == 0)
row = 3;
else if (row == 3)
row = 6;
else if (row == 6)
row = 0;
Console.WriteLine();
}
if (((j+1) % 3 == 0) && j != 8)
Console.WriteLine("▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄");
else if( j != 8)
Console.WriteLine("----+-----+-----█-----+-----+-----█-----+-----+----");
}
}
public bool Solved()
{
int regionSum = 0;
int columnSum = 0;
int rowSum = 0;
bool legitimateSolution = true;
for (int i = 0; i < 9; i++)
{
regionSum = regions[i].items.Sum(x => x.value);
columnSum = columns[i].items.Sum(x => x.value);
rowSum = rows[i].items.Sum(x => x.value);
if ((regionSum != 45) || (columnSum != 45) || (rowSum != 45))
{
legitimateSolution = false;
break;
}
}
if (legitimateSolution)
return true;
else
return false;
}
public bool CurrentlyVerified()
{
for (int i = 0; i < 9; i++)
{
if (!rows[i].SectionVerified())
return false;
else if (!columns[i].SectionVerified())
return false;
else if (!regions[i].SectionVerified())
return false;
}
return true;
}
}
Solve
class Solve
{
SudokuBoard initialBoard;
SudokuBoard currentBoard;
List<Cell> blankCells;
Stopwatch sw;
int solutions;
public Solve(SudokuBoard initial)
{
initialBoard = initial;
solutions = 0;
sw = new Stopwatch();
sw.Start();
}
public void Restart()
{
currentBoard = SudokuBoard.DeepCopy(initialBoard);
blankCells = currentBoard.GetPossibleGuesses();
Start();
}
public void Start()
{
initialBoard.Refactor();
currentBoard = SudokuBoard.DeepCopy(initialBoard);
blankCells = currentBoard.GetPossibleGuesses();
Console.WriteLine("\n\tSolving....");
while (!currentBoard.Solved())
{
int numBlankCells = currentBoard.GetNumberOfBlank();
TrySolving();
// if TrySolving had no effect, brute force all solutions with RecursiveGuess
if (numBlankCells == currentBoard.GetNumberOfBlank())
RecursiveGuess(currentBoard, 0);
if (currentBoard.Finished() && !currentBoard.Solved())
Restart();
}
if (currentBoard.Finished() && currentBoard.Solved())
{
sw.Stop();
Console.Clear();
Console.WriteLine("\n\tElapsed: {0}", sw.Elapsed);
Console.WriteLine("\t{0} SOLUTION'S FOUND", solutions);
currentBoard.PrintEverything();
}
}
public bool TrySolving()
{
for (int i = 0; i < 9; i++)
{
currentBoard.GetSection(i, SectionType.ROW).SingleOut();
currentBoard.GetSection(i, SectionType.COLUMN).SingleOut();
currentBoard.GetSection(i, SectionType.REGION).SingleOut();
}
if (currentBoard.Solved())
return true;
else
return false;
}
public void RecursiveGuess(SudokuBoard previous, int previousGuess)
{
bool blocked = false;
bool fullyBlocked = false;
int currentGuess = 0;
SudokuBoard tempBoard = null;
double seconds = sw.Elapsed.TotalSeconds;
if (seconds % 5 < 0.001)
{
Console.WriteLine("\n\tElapsed: {0}", sw.Elapsed);
Console.WriteLine("\t{0} solutions", solutions);
}
if (previous.CurrentlyVerified())
{
if (!previous.Finished())
{
tempBoard = SudokuBoard.DeepCopy(previous);
blankCells = tempBoard.GetPossibleGuesses();
if (previousGuess != 0)
{
currentGuess = blankCells.First().possibilities.Find(x => x > previousGuess);
if (currentGuess == 0)
fullyBlocked = true;
}
else if (currentGuess < blankCells.First().possibilities.First())
{
currentGuess = blankCells.First().possibilities.First();
}
if (currentGuess != 0)
blankCells.First().ForceCellValue(currentGuess);
else
blocked = true;
if (tempBoard.Finished() && !tempBoard.Solved())
blocked = true;
if (!blocked)
RecursiveGuess(tempBoard, 0);
}
else if (previous.Solved())
{
fullyBlocked = true;
if (!previous.Equals(tempBoard))
currentBoard = SudokuBoard.DeepCopy(previous);
solutions++;
}
}
else
fullyBlocked = true;
if (!fullyBlocked)
RecursiveGuess(previous, currentGuess);
}
}
Main
class Program
{
static void Main(string[] args)
{
int[,] board = new int[9, 9];
board[0, 2] = 2;
board[0, 4] = 3;
board[0, 5] = 6;
board[0, 8] = 5;
board[1, 3] = 9;
board[2, 1] = 6;
board[2, 4] = 2;
board[2, 7] = 4;
board[3, 7] = 1;
board[4, 0] = 1;
board[4, 3] = 5;
board[4, 5] = 7;
board[4, 8] = 6;
board[5, 0] = 3;
board[6, 4] = 6;
board[6, 7] = 8;
board[7, 1] = 1;
board[7, 5] = 2;
board[8, 0] = 6;
board[8, 3] = 4;
board[8, 4] = 1;
board[8, 6] = 2;
SudokuBoard sudokuBoard = new SudokuBoard(board);
sudokuBoard.Refactor();
sudokuBoard.PrintEverything();
Solve solve = new Solve(sudokuBoard);
solve.Start();
}
}