I created a class that is able to generate a Sudoku board.
The following board generation steps are made:
Create a valid board with numbers on all squares, row by row
Basically I always generate the sequence 1 to 9 and I shift the elements on the cells. The shift amount depends on the row index.
Shuffle the board
Nothing extraordinary to explain here. Maybe just the fact that I also set the cells index here as well.
Empty the board until there is only 1 solution
Well, I am not totally sure if that is what my algorithm really does, but it seems to do a good job at least.
I start by picking the group with most visible cells (at the start they are all visible). Then, if I can solve that cell using sudoku solving methods (is this cell missing in the group/coulmn/row?) I make it invisible.
This ends when I am not able to find any other cell that I can hide.
public class SudokuGame
{
[DebuggerDisplay("{Value}")]
private class Cell
{
public int X { get; set; }
public int Y { get; set; }
public int Value { get; set; }
public bool IsVisible { get; set; }
private int Group
{
get { return Y/3 + X/3*3; }
}
public bool CanSolve(SudokuGame game)
{
var canSolve = game.GetColumnGroup(this)
.Where(c => c.X != X && c.Y != Y && c.Value == Value)
.All(c => c.IsVisible);
canSolve |= game.GetRowGroup(this)
.Where(c => c.X != X && c.Y != Y && c.Value == Value)
.All(c => c.IsVisible);
canSolve |= game.GetGroup(Group)
.Where(c => !c.IsVisible)
.Any(c =>
game.GetRow(c.X).Count(s => s.IsVisible) == 1 ||
game.GetColumn(c.Y).Count(s => s.IsVisible) == 1
);
return canSolve;
}
}
private Cell[][] _board = new Cell[9][];
public SudokuGame()
{
Contract.Assert(_board != null);
for (int i = 0; i < _board.GetLength(0); ++i)
{
CreateRow(i);
}
Shuffle();
EmptyUntilUniqueSolution();
}
private IEnumerable<Cell> GetColumnGroup(Cell cell)
{
var transpose = _board.Transpose();
for (int i = cell.Y / 3; i < cell.Y / 3 + 3; ++i)
{
foreach (var aux in transpose[i])
{
yield return aux;
}
}
}
private IEnumerable<Cell> GetRowGroup(Cell cell)
{
for (int i = cell.X/3; i < cell.X/3 + 3; ++i)
{
foreach (var aux in _board[i])
{
yield return aux;
}
}
}
private Cell[] GetColumn(int i)
{
return _board.Transpose()[i];
}
private Cell[] GetRow(int i)
{
return _board[i];
}
private Cell[] GetGroup(int i)
{
return _board.ViewAsNByM(3, 3).ToList()[i].SelectMany(c => c).ToArray();
}
private void Shuffle()
{
for (int i = 0; i < 10; ++i)
{
_board = _board.ViewAsNByM(3, 9)
.SelectMany(c => c.Shuffle())
.ToArray()
.Transpose()
.ViewAsNByM(3, 9)
.SelectMany(c => c.Shuffle())
.ToArray();
}
for (int i = 0; i < _board.GetLength(0); ++i)
{
for (int j = 0; j < _board[i].GetLength(0); ++j)
{
var cell = _board[i][j];
cell.X = i;
cell.Y = j;
}
}
}
private void CreateRow(int i)
{
const int groupSize = 3;
int warpCount = (i*groupSize)%_board.GetLength(0) + i/groupSize;
var oneToNine = Enumerable.Range(1, 9)
.WarpAround(warpCount)
.Select(v => new Cell
{
Value = v,
IsVisible = true
}).ToArray();
_board[i] = oneToNine;
}
private Cell PickGroupCell(Cell[][] cells)
{
foreach (var cell in cells.SelectMany(c => c).Where(c => c.IsVisible).Shuffle())
{
cell.IsVisible = false;
if (cell.CanSolve(this))
{
return cell;
}
cell.IsVisible = true;
}
return null;
}
private Cell GetVisibleCell()
{
var groups = _board.ViewAsNByM(3, 3).Select((g, idx) => new
{
Count = g.Sum(c => c.Count(s => s.IsVisible)),
Cell = PickGroupCell(g)
}).OrderByDescending(g => g.Count)
.ToList();
return groups.TakeWhile(g => g.Count == groups[0].Count)
.Select(g => g.Cell)
.Shuffle()
.FirstOrDefault();
}
private bool CanSolveBoard()
{
var unsolvedCells = _board.SelectMany(cells => cells).Where(c => !c.IsVisible);
return CanSolveBoard(unsolvedCells);
}
private bool CanSolveBoard(IEnumerable<Cell> unsolved)
{
var notSolved = unsolved.Where(cell => !cell.CanSolve(this)).ToList();
return notSolved.Count == 0 || unsolved.Count() != notSolved.Count;
}
private void EmptyUntilUniqueSolution()
{
var cell = GetVisibleCell();
if (cell == null)
{
return;
}
if (!CanSolveBoard())
{
cell.IsVisible = true;
return;
}
EmptyUntilUniqueSolution();
}
}
Utility methods used on the code, I do not require a review on those. But feel free to comment.
public static class CollectionUtils
{
public static IEnumerable<T[][]> ViewAsNByM<T>(this T[][] values, int m, int n)
{
var count = values.GetLength(0)*values[0].GetLength(0);
for (int i = 0; i < count/(n*m); ++i)
{
var matrix = new T[m][];
for (int j = 0; j < m; ++j)
{
matrix[j] = new T[n];
for (int k = 0; k < n; ++k)
{
int idxRow = j + (i/(values[0].GetLength(0)/n))*m;
int idxCol = (k + i*n)%values[0].GetLength(0);
matrix[j][k] = values[idxRow][idxCol];
}
}
yield return matrix;
}
}
public static T[][] Transpose<T>(this T[][] values)
{
var transposed = new T[values[0].GetLength(0)][];
for (int i = 0; i < values[0].GetLength(0); ++i)
{
transposed[i] = new T[values.GetLength(0)];
}
for (int i = 0; i < values.GetLength(0); i++)
{
for (int j = 0; j < values[0].GetLength(0); j++)
{
transposed[j][i] = values[i][j];
}
}
return transposed;
}
public static IEnumerable<T> WarpAround<T>(this IEnumerable<T> values, int n)
{
return values.Skip(n).Concat(values.Take(n));
}
private static readonly ThreadLocal<Random> Random =
new ThreadLocal<Random>(()=>new Random(42));
public static IList<T> Shuffle<T>(this IEnumerable<T> col)
{
var list = col as IList<T> ?? col.ToList();
var random = Random.Value;
for (int i = 0; i < list.Count; ++i)
{
//get a chance of staying in same place
list.Swap(i, random.Next(i, list.Count));
}
return list;
}
public static void Swap<T>(this IList<T> col, int idxSrc, int idxDest)
{
var aux = col[idxSrc];
col[idxSrc] = col[idxDest];
col[idxDest] = aux;
}
}
Any suggestions are appreciated.
