8
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

There is one thing I don't like about the SudokuGame... it's a god-class doing everything which means it's doing too much.

I suggest refactoring the code so that the SudokuGame receives a SudokuBoard or some kind of a ISudokuBoardFactory. Then put everything sudoku-board releated into a SudokuBoard class that expects from you the size of the board etc.

Additionally I'd implemeted a ISudokuSolver that can check whether a game can be won.

I think it would also be a good idea to create another class that can only generate boards.

Put it all together and you have nice modular sudoku game where you can test each unit separately and validate its functionality.

\$\endgroup\$
  • 1
    \$\begingroup\$ Don't you ever sleep ? ;-) \$\endgroup\$ – Heslacher Aug 23 '16 at 19:30
  • \$\begingroup\$ @Heslacher haha - I sometimes do but I also get up at half past five am ;-) \$\endgroup\$ – t3chb0t Aug 23 '16 at 19:34
  • \$\begingroup\$ @Heslacher I thought the same 😄 As well \$\endgroup\$ – Siobhan Aug 23 '16 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.