Even though it's the first time I'm writing something this "big", it feels like I know C# quite well (it is very similar to Java after all). It's been nice to learn LINQ also and I am very impressed by the features (which is just like Steams in Java 8), and perhaps I have overused it here (if it's possible to do that).
Class summary
- SudokuFactory: Contains static methods to create some Sudoku variations
- SudokuBoard: Contains collection of
SudokuRuleand ofSudokuTile - SudokuRule: Whether it's a box, a line, a row, or something entirely different doesn't matter. Contains a collection of
SudokuTilethat must be unique. - SudokuTile: Each tile in the puzzle. Can be "blocked" (like a hole in the puzzle), remembers it's
possibleValues, and also contains a value (0 is used for tiles without a value) - SudokuProgress: Used to know what the progress of a solving step was.
- Program: Main starting point. Contains tests for seven different Sudokus. All have been verified to be solved correctly.
Since this is the first time I'm using C# and LINQ, please tell me anything. All suggestions welcome. Except for the fact that the method box should be called Box. I'd be especially interested in cases where I could simplify some of the LINQ usage (trust me, there is a lot). I hope you are able to follow all the LINQ queries. I have tried to put some short comments where needed to explain what is happening. If you want an explanation for some part, post a comment and I will explain.
As usual, I have a tendency to make the challenge into something super-flexible with support for a whole lot of more or less unnecessary things. Some of the possible puzzles that this code can solve is:
- A hard classic 9x9 Sudoku with 3x3 boxes that requires more advanced techniques (or in my case, more or less "brute force" by trial and error)
- Nonomino
- HyperSudoku
- Samurai Sudoku
- A classic Sudoku of any size with any number of boxes and size of boxes (only completely tested on 9x9 with 3x3 boxes and 4x4 with 2x2 boxes but any sizes should be possible)
These images are puzzles that are tested and solved in the below code:
One known issue with the implementation is if you would input an empty puzzle, then it would work for years to find all the possible combinations for it.
SudokuProgress
public enum SudokuProgress { FAILED, NO_PROGRESS, PROGRESS }
SudokuTile
public class SudokuTile
{
internal static SudokuProgress CombineSolvedState(SudokuProgress a, SudokuProgress b)
{
if (a == SudokuProgress.FAILED)
return a;
if (a == SudokuProgress.NO_PROGRESS)
return b;
if (a == SudokuProgress.PROGRESS)
return b == SudokuProgress.FAILED ? b : a;
throw new InvalidOperationException("Invalid value for a");
}
public const int CLEARED = 0;
private int _maxValue;
private int _value;
private int _x;
private int _y;
private ISet<int> possibleValues;
private bool _blocked;
public SudokuTile(int x, int y, int maxValue)
{
_x = x;
_y = y;
_blocked = false;
_maxValue = maxValue;
possibleValues = new HashSet<int>();
_value = 0;
}
public int Value
{
get { return _value; }
set
{
if (value > _maxValue)
throw new ArgumentOutOfRangeException("SudokuTile Value cannot be greater than " + _maxValue.ToString() + ". Was " + value);
if (value < CLEARED)
throw new ArgumentOutOfRangeException("SudokuTile Value cannot be zero or smaller. Was " + value);
_value = value;
}
}
public bool HasValue
{
get { return Value != CLEARED; }
}
public string ToStringSimple()
{
return Value.ToString();
}
public override string ToString()
{
return String.Format("Value {0} at pos {1}, {2}. ", Value, _x, _y, possibleValues.Count);
}
internal void ResetPossibles()
{
possibleValues.Clear();
foreach (int i in Enumerable.Range(1, _maxValue))
{
if (!HasValue || Value == i)
possibleValues.Add(i);
}
}
public void Block()
{
_blocked = true;
}
internal void Fix(int value, string reason)
{
Console.WriteLine("Fixing {0} on pos {1}, {2}: {3}", value, _x, _y, reason);
Value = value;
ResetPossibles();
}
internal SudokuProgress RemovePossibles(IEnumerable<int> existingNumbers)
{
if (_blocked)
return SudokuProgress.NO_PROGRESS;
// Takes the current possible values and removes the ones existing in `existingNumbers`
possibleValues = new HashSet<int>(possibleValues.Where(x => !existingNumbers.Contains(x)));
SudokuProgress result = SudokuProgress.NO_PROGRESS;
if (possibleValues.Count == 1)
{
Fix(possibleValues.First(), "Only one possibility");
result = SudokuProgress.PROGRESS;
}
if (possibleValues.Count == 0)
return SudokuProgress.FAILED;
return result;
}
public bool IsValuePossible(int i)
{
return possibleValues.Contains(i);
}
public int X { get { return _x; } }
public int Y { get { return _y; } }
public bool IsBlocked { get { return _blocked; } } // A blocked field can not contain a value -- used for creating 'holes' in the map
public int PossibleCount
{
get {
return IsBlocked ? 1 : possibleValues.Count;
}
}
}
SudokuRule
public class SudokuRule : IEnumerable<SudokuTile>
{
internal SudokuRule(IEnumerable<SudokuTile> tiles, string description)
{
_tiles = new HashSet<SudokuTile>(tiles);
_description = description;
}
private ISet<SudokuTile> _tiles;
private string _description;
public bool CheckValid()
{
var filtered = _tiles.Where(tile => tile.HasValue);
var groupedByValue = filtered.GroupBy(tile => tile.Value);
return groupedByValue.All(group => group.Count() == 1);
}
public bool CheckComplete()
{
return _tiles.All(tile => tile.HasValue) && CheckValid();
}
internal SudokuProgress RemovePossibles()
{
// Tiles that has a number already
IEnumerable<SudokuTile> withNumber = _tiles.Where(tile => tile.HasValue);
// Tiles without a number
IEnumerable<SudokuTile> withoutNumber = _tiles.Where(tile => !tile.HasValue);
// The existing numbers in this rule
IEnumerable<int> existingNumbers = new HashSet<int>(withNumber.Select(tile => tile.Value).Distinct().ToList());
SudokuProgress result = SudokuProgress.NO_PROGRESS;
foreach (SudokuTile tile in withoutNumber)
result = SudokuTile.CombineSolvedState(result, tile.RemovePossibles(existingNumbers));
return result;
}
internal SudokuProgress CheckForOnlyOnePossibility()
{
// Check if there is only one number within this rule that can have a specific value
IList<int> existingNumbers = _tiles.Select(tile => tile.Value).Distinct().ToList();
SudokuProgress result = SudokuProgress.NO_PROGRESS;
foreach (int value in Enumerable.Range(1, _tiles.Count))
{
if (existingNumbers.Contains(value)) // this rule already has the value, skip checking for it
continue;
var possibles = _tiles.Where(tile => !tile.HasValue && tile.IsValuePossible(value)).ToList();
if (possibles.Count == 0)
return SudokuProgress.FAILED;
if (possibles.Count == 1)
{
possibles.First().Fix(value, "Only possible in rule " + ToString());
result = SudokuProgress.PROGRESS;
}
}
return result;
}
internal SudokuProgress Solve()
{
// If both are null, return null (indicating no change). If one is null, return the other. Else return result1 && result2
SudokuProgress result1 = RemovePossibles();
SudokuProgress result2 = CheckForOnlyOnePossibility();
return SudokuTile.CombineSolvedState(result1, result2);
}
public override string ToString()
{
return _description;
}
public IEnumerator<SudokuTile> GetEnumerator()
{
return _tiles.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public string Description { get { return _description; } }
}
SudokuBoard:
public class SudokuBoard
{
public SudokuBoard(SudokuBoard copy)
{
_maxValue = copy._maxValue;
tiles = new SudokuTile[copy.Width, copy.Height];
CreateTiles();
// Copy the tile values
foreach (var pos in SudokuFactory.box(Width, Height))
{
tiles[pos.Item1, pos.Item2] = new SudokuTile(pos.Item1, pos.Item2, _maxValue);
tiles[pos.Item1, pos.Item2].Value = copy.tiles[pos.Item1, pos.Item2].Value;
}
// Copy the rules
foreach (SudokuRule rule in copy.rules)
{
var ruleTiles = new HashSet<SudokuTile>();
foreach (SudokuTile tile in rule)
{
ruleTiles.Add(tiles[tile.X, tile.Y]);
}
rules.Add(new SudokuRule(ruleTiles, rule.Description));
}
}
public SudokuBoard(int width, int height, int maxValue)
{
_maxValue = maxValue;
tiles = new SudokuTile[width, height];
CreateTiles();
if (_maxValue == width || _maxValue == height) // If maxValue is not width or height, then adding line rules would be stupid
SetupLineRules();
}
public SudokuBoard(int width, int height) : this(width, height, Math.Max(width, height)) {}
private int _maxValue;
private void CreateTiles()
{
foreach (var pos in SudokuFactory.box(tiles.GetLength(0), tiles.GetLength(1)))
{
tiles[pos.Item1, pos.Item2] = new SudokuTile(pos.Item1, pos.Item2, _maxValue);
}
}
private void SetupLineRules()
{
// Create rules for rows and columns
for (int x = 0; x < Width; x++)
{
IEnumerable<SudokuTile> row = GetCol(x);
rules.Add(new SudokuRule(row, "Row " + x.ToString()));
}
for (int y = 0; y < Height; y++)
{
IEnumerable<SudokuTile> col = GetRow(y);
rules.Add(new SudokuRule(col, "Col " + y.ToString()));
}
}
internal IEnumerable<SudokuTile> TileBox(int startX, int startY, int sizeX, int sizeY)
{
return from pos in SudokuFactory.box(sizeX, sizeY) select tiles[startX + pos.Item1, startY + pos.Item2];
}
private IEnumerable<SudokuTile> GetRow(int row)
{
for (int i = 0; i < tiles.GetLength(0); i++)
{
yield return tiles[i, row];
}
}
private IEnumerable<SudokuTile> GetCol(int col)
{
for (int i = 0; i < tiles.GetLength(1); i++)
{
yield return tiles[col, i];
}
}
private ISet<SudokuRule> rules = new HashSet<SudokuRule>();
private SudokuTile[,] tiles;
public int Width
{
get { return tiles.GetLength(0); }
}
public int Height {
get { return tiles.GetLength(1); }
}
public void CreateRule(string description, params SudokuTile[] tiles)
{
rules.Add(new SudokuRule(tiles, description));
}
public void CreateRule(string description, IEnumerable<SudokuTile> tiles)
{
rules.Add(new SudokuRule(tiles, description));
}
public bool CheckValid()
{
return rules.All(rule => rule.CheckValid());
}
public IEnumerable<SudokuBoard> Solve()
{
ResetSolutions();
SudokuProgress simplify = SudokuProgress.PROGRESS;
while (simplify == SudokuProgress.PROGRESS) simplify = Simplify();
if (simplify == SudokuProgress.FAILED)
yield break;
// Find one of the values with the least number of alternatives, but that still has at least 2 alternatives
var query = from rule in rules
from tile in rule
where tile.PossibleCount > 1
orderby tile.PossibleCount ascending
select tile;
SudokuTile chosen = query.FirstOrDefault();
if (chosen == null)
{
// The board has been completed, we're done!
yield return this;
yield break;
}
Console.WriteLine("SudokuTile: " + chosen.ToString());
foreach (var value in Enumerable.Range(1, _maxValue))
{
// Iterate through all the valid possibles on the chosen square and pick a number for it
if (!chosen.IsValuePossible(value))
continue;
var copy = new SudokuBoard(this);
copy.Tile(chosen.X, chosen.Y).Fix(value, "Trial and error");
foreach (var innerSolution in copy.Solve())
yield return innerSolution;
}
yield break;
}
public void Output()
{
for (int y = 0; y < tiles.GetLength(1); y++)
{
for (int x = 0; x < tiles.GetLength(0); x++)
{
Console.Write(tiles[x, y].ToStringSimple());
}
Console.WriteLine();
}
}
public SudokuTile Tile(int x, int y)
{
return tiles[x, y];
}
private int _rowAddIndex;
public void AddRow(string s)
{
// Method for initializing a board from string
for (int i = 0; i < s.Length; i++)
{
var tile = tiles[i, _rowAddIndex];
if (s[i] == '/')
{
tile.Block();
continue;
}
int value = s[i] == '.' ? 0 : (int)Char.GetNumericValue(s[i]);
tile.Value = value;
}
_rowAddIndex++;
}
internal void ResetSolutions()
{
foreach (SudokuTile tile in tiles)
tile.ResetPossibles();
}
internal SudokuProgress Simplify()
{
SudokuProgress result = SudokuProgress.NO_PROGRESS;
bool valid = CheckValid();
if (!valid)
return SudokuProgress.FAILED;
foreach (SudokuRule rule in rules)
result = SudokuTile.CombineSolvedState(result, rule.Solve());
return result;
}
internal void AddBoxesCount(int boxesX, int boxesY)
{
int sizeX = Width / boxesX;
int sizeY = Height / boxesY;
var boxes = SudokuFactory.box(sizeX, sizeY);
foreach (var pos in boxes)
{
IEnumerable<SudokuTile> boxTiles = TileBox(pos.Item1 * sizeX, pos.Item2 * sizeY, sizeX, sizeY);
CreateRule("Box at (" + pos.Item1.ToString() + ", " + pos.Item2.ToString() + ")", boxTiles);
}
}
internal void OutputRules()
{
foreach (var rule in rules)
{
Console.WriteLine(String.Join(",", rule) + " - " + rule.ToString());
}
}
}
SudokuFactory:
public class SudokuFactory
{
private const int DefaultSize = 9;
private const int SamuraiAreas = 7;
private const int BoxSize = 3;
private const int HyperMargin = 1;
public static IEnumerable<Tuple<int, int>> box(int sizeX, int sizeY)
{
foreach (int x in Enumerable.Range(0, sizeX))
{
foreach (int y in Enumerable.Range(0, sizeY))
{
yield return new Tuple<int, int>(x, y);
}
}
}
public static SudokuBoard Samurai()
{
SudokuBoard board = new SudokuBoard(SamuraiAreas*BoxSize, SamuraiAreas*BoxSize, DefaultSize);
// Removed the empty areas where there are no tiles
var queriesForBlocked = new List<IEnumerable<SudokuTile>>();
queriesForBlocked.Add(from pos in box(BoxSize, BoxSize*2) select board.Tile(pos.Item1 + DefaultSize, pos.Item2 ));
queriesForBlocked.Add(from pos in box(BoxSize, BoxSize*2) select board.Tile(pos.Item1 + DefaultSize, pos.Item2 + DefaultSize * 2 - BoxSize));
queriesForBlocked.Add(from pos in box(BoxSize*2, BoxSize) select board.Tile(pos.Item1 , pos.Item2 + DefaultSize));
queriesForBlocked.Add(from pos in box(BoxSize*2, BoxSize) select board.Tile(pos.Item1 + DefaultSize * 2 - BoxSize, pos.Item2 + DefaultSize));
foreach (var query in queriesForBlocked)
{
foreach (var tile in query) tile.Block();
}
// Select the tiles in the 3 x 3 area (area.X, area.Y) and create rules for them
foreach (var area in box(SamuraiAreas, SamuraiAreas))
{
var tilesInArea = from pos in box(BoxSize, BoxSize) select board.Tile(area.Item1 * BoxSize + pos.Item1, area.Item2 * BoxSize + pos.Item2);
if (tilesInArea.First().IsBlocked)
continue;
board.CreateRule("Area " + area.Item1.ToString() + ", " + area.Item2.ToString(), tilesInArea);
}
// Select all rows and create columns for them
var cols = from pos in box(board.Width, 1) select new { X = pos.Item1, Y = pos.Item2 };
var rows = from pos in box(1, board.Height) select new { X = pos.Item1, Y = pos.Item2 };
foreach (var posSet in Enumerable.Range(0, board.Width))
{
board.CreateRule("Column Upper " + posSet, from pos in box(1, DefaultSize) select board.Tile(posSet, pos.Item2));
board.CreateRule("Column Lower " + posSet, from pos in box(1, DefaultSize) select board.Tile(posSet, pos.Item2 + DefaultSize + BoxSize));
board.CreateRule("Row Left " + posSet, from pos in box(DefaultSize, 1) select board.Tile(pos.Item1, posSet));
board.CreateRule("Row Right " + posSet, from pos in box(DefaultSize, 1) select board.Tile(pos.Item1 + DefaultSize + BoxSize, posSet));
if (posSet >= BoxSize*2 && posSet < BoxSize*2 + DefaultSize)
{
// Create rules for the middle sudoku
board.CreateRule("Column Middle " + posSet, from pos in box(1, 9) select board.Tile(posSet, pos.Item2 + BoxSize*2));
board.CreateRule("Row Middle " + posSet, from pos in box(9, 1) select board.Tile(pos.Item1 + BoxSize*2, posSet));
}
}
return board;
}
public static SudokuBoard SizeAndBoxes(int width, int height, int boxCountX, int boxCountY)
{
SudokuBoard board = new SudokuBoard(width, height);
board.AddBoxesCount(boxCountX, boxCountY);
return board;
}
public static SudokuBoard ClassicWith3x3Boxes()
{
return SizeAndBoxes(DefaultSize, DefaultSize, DefaultSize / BoxSize, DefaultSize / BoxSize);
}
public static SudokuBoard ClassicWith3x3BoxesAndHyperRegions()
{
SudokuBoard board = ClassicWith3x3Boxes();
const int HyperSecond = HyperMargin + BoxSize + HyperMargin;
// Create the four extra hyper regions
board.CreateRule("HyperA", from pos in box(3, 3) select board.Tile(pos.Item1 + HyperMargin, pos.Item2 + HyperMargin));
board.CreateRule("HyperB", from pos in box(3, 3) select board.Tile(pos.Item1 + HyperSecond, pos.Item2 + HyperMargin));
board.CreateRule("HyperC", from pos in box(3, 3) select board.Tile(pos.Item1 + HyperMargin, pos.Item2 + HyperSecond));
board.CreateRule("HyperD", from pos in box(3, 3) select board.Tile(pos.Item1 + HyperSecond, pos.Item2 + HyperSecond));
return board;
}
public static SudokuBoard ClassicWithSpecialBoxes(string[] areas)
{
int sizeX = areas[0].Length;
int sizeY = areas.Length;
SudokuBoard board = new SudokuBoard(sizeX, sizeY);
var joinedString = String.Join("", areas);
var grouped = joinedString.Distinct();
// Loop through all the unique characters
foreach (var ch in grouped)
{
// Select the rule tiles based on the index of the character
var ruleTiles = from i in Enumerable.Range(0, joinedString.Length)
where joinedString[i] == ch // filter out any non-matching characters
select board.Tile(i % sizeX, i / sizeY);
board.CreateRule("Area " + ch.ToString(), ruleTiles);
}
return board;
}
}
Program:
static class Program
{
[STAThread]
static void Main()
{
SolveFail();
SolveClassic();
SolveSmall();
SolveExtraZones();
SolveHyper();
SolveSamurai();
SolveIncompleteClassic();
}
private static void SolveFail()
{
SudokuBoard board = SudokuFactory.SizeAndBoxes(4, 4, 2, 2);
board.AddRow("0003");
board.AddRow("0204"); // the 2 must be a 1 on this row to be solvable
board.AddRow("1000");
board.AddRow("4000");
CompleteSolve(board);
}
private static void SolveExtraZones()
{
// http://en.wikipedia.org/wiki/File:Oceans_Hypersudoku18_Puzzle.svg
SudokuBoard board = SudokuFactory.ClassicWith3x3BoxesAndHyperRegions();
board.AddRow(".......1.");
board.AddRow("..2....34");
board.AddRow("....51...");
board.AddRow(".....65..");
board.AddRow(".7.3...8.");
board.AddRow("..3......");
board.AddRow("....8....");
board.AddRow("58....9..");
board.AddRow("69.......");
CompleteSolve(board);
}
private static void SolveSmall()
{
SudokuBoard board = SudokuFactory.SizeAndBoxes(4, 4, 2, 2);
board.AddRow("0003");
board.AddRow("0004");
board.AddRow("1000");
board.AddRow("4000");
CompleteSolve(board);
}
private static void SolveHyper()
{
// http://en.wikipedia.org/wiki/File:A_nonomino_sudoku.svg
string[] areas = new string[]{
"111233333",
"111222333",
"144442223",
"114555522",
"444456666",
"775555688",
"977766668",
"999777888",
"999997888"
};
SudokuBoard board = SudokuFactory.ClassicWithSpecialBoxes(areas);
board.AddRow("3.......4");
board.AddRow("..2.6.1..");
board.AddRow(".1.9.8.2.");
board.AddRow("..5...6..");
board.AddRow(".2.....1.");
board.AddRow("..9...8..");
board.AddRow(".8.3.4.6.");
board.AddRow("..4.1.9..");
board.AddRow("5.......7");
CompleteSolve(board);
}
private static void SolveSamurai()
{
// http://www.freesamuraisudoku.com/1001HardSamuraiSudokus.aspx?puzzle=42
SudokuBoard board = SudokuFactory.Samurai();
board.AddRow("6..8..9..///.....38..");
board.AddRow("...79....///89..2.3..");
board.AddRow("..2..64.5///...1...7.");
board.AddRow(".57.1.2..///..5....3.");
board.AddRow(".....731.///.1.3..2..");
board.AddRow("...3...9.///.7..429.5");
board.AddRow("4..5..1...5....5.....");
board.AddRow("8.1...7...8.2..768...");
board.AddRow(".......8.23...4...6..");
board.AddRow("//////.12.4..9.//////");
board.AddRow("//////......82.//////");
board.AddRow("//////.6.....1.//////");
board.AddRow(".4...1....76...36..9.");
board.AddRow("2.....9..8..5.34...81");
board.AddRow(".5.873......9.8..23..");
board.AddRow("...2....9///.25.4....");
board.AddRow("..3.64...///31.8.....");
board.AddRow("..75.8.12///...6.14..");
board.AddRow(".......2.///.31...9..");
board.AddRow("..17.....///..7......");
board.AddRow(".7.6...84///8...7..5.");
CompleteSolve(board);
}
private static void SolveClassic()
{
var board = SudokuFactory.ClassicWith3x3Boxes();
board.AddRow("...84...9");
board.AddRow("..1.....5");
board.AddRow("8...2146.");
board.AddRow("7.8....9.");
board.AddRow(".........");
board.AddRow(".5....3.1");
board.AddRow(".2491...7");
board.AddRow("9.....5..");
board.AddRow("3...84...");
CompleteSolve(board);
}
private static void SolveIncompleteClassic()
{
var board = SudokuFactory.ClassicWith3x3Boxes();
board.AddRow("...84...9");
board.AddRow("..1.....5");
board.AddRow("8...2.46."); // Removed a "1" on this line
board.AddRow("7.8....9.");
board.AddRow(".........");
board.AddRow(".5....3.1");
board.AddRow(".2491...7");
board.AddRow("9.....5..");
board.AddRow("3...84...");
CompleteSolve(board);
}
private static void CompleteSolve(SudokuBoard board)
{
Console.WriteLine("Rules:");
board.OutputRules();
Console.WriteLine("Board:");
board.Output();
var solutions = board.Solve().ToList();
Console.WriteLine("Base Board Progress:");
board.Output();
Console.WriteLine("--");
Console.WriteLine("--");
Console.WriteLine("All " + solutions.Count + " solutions:");
var i = 1;
foreach (var solution in solutions)
{
Console.WriteLine("----------------");
Console.WriteLine("Solution " + i++.ToString() + " / " + solutions.Count + ":");
solution.Output();
}
}
}
