Check Sudoku - Unity Tutorial - 5. Game rules

In the previous step we have implemented setting board cell values. In this one, we will add checking Sudoku rules, to prevent user from "clicking" illegal Sudoku board:

Implementation

At this stage, we need to create the game model. In order to do that, we create three classes:
  • BoardModel for storing the whole board model
  • CellModel for storing single cell model
  • CellSetModel for storing a set of cells (e.g. column, row, or 3x3 square)

Question 1:
Which element should store the board model?

Options:
  • Game manager (GameManager)
  • The board (BoardImage)
  • The work cell (WorkCellImage)
Decision:
Since we need to join the model with board images anyway, it's easiest if the board (BoardImage) creates the model upon creation and feeds all its cells into it. In order to simplify testing, we set the initial values for some of the board cells, getting a solvable Sudoku:

public class BoardImage : MonoBehaviour
{
    ...

    private BoardModel model;

    private void Awake()
    {
        ...

        model = new BoardModel(GetComponentsInChildren<CellImage>());

        // Set the initial board.
        //   9 2 |       | 7 5
        // 7     | 2   5 |     8
        // 4     | 8   9 |     1
        // ---------------------
        //   2 8 |       | 1 6
        //       |       |
        //   1 6 |       | 5 3
        // ---------------------
        // 1     | 5   6 |     2
        // 2     | 9   4 |     3
        //   4 3 |       | 8 9 
        model.SetCellValue(0, 1, 9);
        ...
        model.SetCellValue(8, 7, 9);
    }

    ...
}
Now, the hardest part. The board model (BoardModel) stores all given cells in a grid, creating a model for each one, and setting all the dependencies between cells, cell sets (columns, rows, 3x3 squares), neighboring cells etc. We also add a SetCellValue method used by the board to initialize the Sudoku:

public class BoardModel
{
    private const int NUM_COLS = 9;
    private const int NUM_ROWS = 9;
    private const int NUM_CELLS = NUM_COLS * NUM_COLS;

    private const int NUM_COLS_IN_GROUP = 3;
    private const int NUM_ROWS_IN_GROUP = 3;
    private const int NUM_CELLS_IN_GROUP = NUM_COLS_IN_GROUP * NUM_ROWS_IN_GROUP;
    private const int NUM_GROUP_COLS = NUM_COLS / NUM_COLS_IN_GROUP;
    private const int NUM_GROUP_ROWS = NUM_ROWS / NUM_ROWS_IN_GROUP;
    private const int NUM_GROUPS = NUM_GROUP_COLS * NUM_GROUP_ROWS;

    private CellModel[] cells = new CellModel[NUM_CELLS];
    private CellSetModel[] cols = new CellSetModel[NUM_COLS];
    private CellSetModel[] rows = new CellSetModel[NUM_ROWS];
    private CellSetModel[] groups = new CellSetModel[NUM_GROUPS];
    private CellImage[,] cellImageGrid = new CellImage[NUM_ROWS, NUM_COLS];

    public BoardModel(CellImage[] cellImages)
    {
        Debug.AssertFormat(
            cellImages.Length == NUM_CELLS,
            "Invalid number of cell images. Expected {0}, but got {1}.",
            NUM_CELLS, cellImages.Length);

        // Create columns, rows and groups.
        for(int i = 0; i < NUM_COLS; ++i)
        {
            cols[i] = new CellSetModel(CellSetType.COLUMN);
        }
        for (int i = 0; i < NUM_ROWS; ++i)
        {
            rows[i] = new CellSetModel(CellSetType.ROW);
        }
        for (int i = 0; i < NUM_GROUPS; ++i)
        {
            groups[i] = new CellSetModel(CellSetType.GROUP);
        }

        // Iterate over the cells in their display order:
        //  0  1  2   9 10 11 ...
        //  3  4  5  12 ...
        //  6  7  8  ...
        //  ...
        for (int i = 0; i < cellImages.Length; ++i)
        {
            cells[i] = new CellModel();
            cellImages[i].SetModel(cells[i]);

            // Assign cell to the correct column, row, and group.
            // Group index for each cell :  0 0 0  0 0 0  0 0 0  1...
            // Cell within group         :  0 1 2  3 4 5  6 7 8  0...
            int cellGroup = i / NUM_CELLS_IN_GROUP;
            int cellWithinCellGroup = i % NUM_CELLS_IN_GROUP;

            // Row index for each cell   :  0 0 0  1 1 1  2 2 2  0...
            int cellGroupFirstCellRow =
                (cellGroup / NUM_GROUP_COLS) * NUM_ROWS_IN_GROUP;
            int cellRow =
                cellGroupFirstCellRow + cellWithinCellGroup / NUM_ROWS_IN_GROUP;

            // Column index for each cell:  0 1 2  0 1 2  0 1 2  3...
            int cellGroupFirstCellCol =
                (cellGroup % NUM_GROUP_COLS) * NUM_COLS_IN_GROUP;
            int cellCol =
                cellGroupFirstCellCol + cellWithinCellGroup % NUM_COLS_IN_GROUP;

            cellImageGrid[cellRow, cellCol] = cellImages[i];

            cols[cellCol].AddCell(cells[i]);
            cells[i].AddCellSet(cols[cellCol]);

            rows[cellRow].AddCell(cells[i]);
            cells[i].AddCellSet(rows[cellRow]);

            groups[cellGroup].AddCell(cells[i]);
            cells[i].AddCellSet(groups[cellGroup]);
        }

        // Set each cell image neighbors.
        for (int row = 0; row < NUM_ROWS; ++row)
        {
            for (int col = 0; col < NUM_COLS; ++col)
            {
                cellImageGrid[row, col].SetNeighbours(
                    cellImageGrid[(row + 1) % NUM_ROWS, col],
                    cellImageGrid[row, (col + 1) % NUM_COLS],
                    cellImageGrid[(row + NUM_ROWS - 1) % NUM_ROWS, col],
                    cellImageGrid[row, (col + NUM_COLS - 1) % NUM_COLS]);
            }
        }
    }

    public void SetCellValue(int row, int col, int value)
    {
        cellImageGrid[row, col].SetValue(value);
    }
}
Cell set (CellSetModel) must only store its type (COLUMN, ROW or GROUP) and all the cells in the set:

public enum CellSetType {
    CELL_SET_TYPE_UNSPECIFIED,
    COLUMN,
    ROW,
    GROUP
}

public class CellSetModel
{
    public CellSetType Type { get; private set; }

    private List<CellModel> cells = new List<CellModel>();

    public CellSetModel(CellSetType type)
    {
        Type = type;
    }

    public void AddCell(CellModel cell)
    {
        cells.Add(cell);
    }
}
Cell model (CellModel) must only store its value, and which sets it belongs to:

public class CellModel
{
    // Value in the cell. Value of 0 represents an empty cell.
    public int Value { get; private set; } = 0;

    private List<CellSetModel> cellSets = new List<CellSetModel>();

    public CellModel(){}

    public void AddCellSet(CellSetModel cellSet)
    {
        cellSets.Add(cellSet);
    }

    public void SetValue(int value)
    {
        Value = value;
    }
}
We'd like to block the possibility of setting cell value in the model, if the value already exists in some column, row, or 3x3 square.

Question 2:
How to check whether a value already exists in the given column, row, or 3x3 square?

Options:
  • Calculate it on-the-fly - i.e. CellModel stores only the value. Whenever there's a need to know the possible values, it calculates them by looking through all other cells in given column, row, or 3x3 square.
  • Memoize them, not to recalculate it every time - e.g. CellModel stores both the current value, and a set of all values existing in a given column, row, or 3x3 square.
Decision:
Since, in the computer science, "premature optimization is the root of all evil", we will calculate possible values on-the-fly.

In the cell set model (CellSetModel) we add AnyOtherCellHasValue method, which checks if any other cell contains the given value:

public class CellSetModel
{
    ...

    public bool AnyOtherCellHasValue(CellModel ignoredCell, int value)
    {
        foreach(CellModel cell in cells)
        {
            if (!cell.Equals(ignoredCell) && cell.Value.Equals(value))
            {
                return true;
            }
        }
        return false;
    }
}
In the cell model (CellModel) we add GetCellSetTypesHavingValue method, which returns the "cell set types" in which a given value already exists. When setting the value using SetValue we assert that given value does not exist in any other cell set:

public class CellModel
{
    ...

    public List<CellSetType> GetCellSetTypesHavingValue(int value)
    {
        List<CellSetType> result = new List<CellSetType>();
        foreach(CellSetModel cellSet in cellSets)
        {
            if (cellSet.AnyOtherCellHasValue(this, value))
            {
                result.Add(cellSet.Type);
            }
        }
        return result;
    }

    public void SetValue(int value)
    {
        Debug.AssertFormat(
            value == 0 || GetCellSetTypesHavingValue(value).Count == 0,
            "Invalid value being set: {0}", value);
        ...
    }
}
Instead of storing the value, the cell (CellImage) stores its model, whether it is selected, and the information about its neighbours (next cell in column or row, previous cell in column or row):

public class CellImage : MonoBehaviour
{
    public bool Selected { get; private set; } = false;
    ...

    private CellModel model;
    private CellImage nextInCol, nextInRow;
    private CellImage prevInCol, prevInRow;

    // Start is called before the first frame update
    void Start()
    {
    
    }

    ...

    public void Select()
    {
        Selected = true;
        ...
    }

    public void Unselect()
    {
        Selected = false;
        ...
    }

    public void OnClick()
    {
        ...
    }

    public void SetModel(CellModel model)
    {
        this.model = model;
    }

    public void SetNeighbours(CellImage nextInCol, CellImage nextInRow, CellImage prevInCol, CellImage prevInRow)
    {
        this.nextInCol = nextInCol;
        this.nextInRow = nextInRow;
        this.prevInCol = prevInCol;
        this.prevInRow = prevInRow;
    }


    public int GetValue()
    {
        return model.Value;
    }

    public void SetValue(int value)
    {
        model.SetValue(value);
        ...
    }
}
The cells now use the model to store values, but we can still select invalid values...:


...getting the following console error logs, whenever it happens:
Invalid value being set: 1
 #0 GetStacktrace(int)
 ...

Invalid value being set: 2
 #0 GetStacktrace(int)
 ...
We want the work cell to cross out some of the possibilities for a selected cell. According to our idea, the values which exist in the column will be crossed out with blue colour (#1E88E5), existing in the row with red colour (#D81B60), existing in the 3x3 square with the yellow colour (#FFC107).


We download a free cross icon from pixabay.com, which we paint into different colours using GIMP:


In the possibility (PossibilityRect) we add three images (StrikethroughColImage, StrikethroughRowImage, StrikethroughGroupImage) placed so that a few of them can be displayed at the same time (if e.g. given value exists both in the column, and in the row):


In the possibility (PossibilityRect) we also add Enabled and Selected properties as well as methods for activating the strikethrough images:

public class PossibilityRect : MonoBehaviour
{
    public bool Enabled { get; private set; } = true;
    public bool Selected { get; private set; } = false;
    public GameObject strikethroughColImage;
    public GameObject strikethroughRowImage;
    public GameObject strikethroughGroupImage;

    ...

    // Start is called before the first frame update
    void Start()
    {
        ...
        Disable();
    }

    ...

    public void Select()
    {
        Selected = true;
        ...
    }

    public void Unselect()
    {
        Selected = false;
        ...
    }

    public void OnClick()
    {
        if (Enabled)
        {
            ...
        }
    }

    public void Enable()
    {
        valueText.alpha = 1;
        Enabled = true;
    }

    public void Disable()
    {
        valueText.alpha = 0.5f;
        Enabled = false;
    }

    public void ClearStrikethrough()
    {
        strikethroughColImage.SetActive(false);
        strikethroughRowImage.SetActive(false);
        strikethroughGroupImage.SetActive(false);
    }

    public void DisplayStrikethroughForType(CellSetType cellSetType)
    {
        Disable();
        switch (cellSetType)
        {
            case CellSetType.COLUMN:
                strikethroughColImage.SetActive(true);
                break;
            case CellSetType.ROW:
                strikethroughRowImage.SetActive(true);
                break;
            case CellSetType.GROUP:
                strikethroughGroupImage.SetActive(true);
                break;
        }
    }
}
Question 3:
Who should activate/deactivate possibilities and strikethrough images?

Options:
  • The work cell (WorkCellImage) - it already remembers the selected cell. It doesn't have access to the columns in all the cells to determine which possibilities should be crossed out.
  • Possibility (PossibilityRect) - also does not have access to all the cells.
  • Selected cell (CellImage) - it has access (through its model) to all other cells in the same column, row, and 3x3 square
Decision:
The activation/deactivation of possibilities and their strikethrough images will be done by the currently selected cell.

In the cell (CellImage) we add methods for activating and deactivating a single possibility, which are meant to only be invoked when the cell is selected:

public class CellImage : MonoBehaviour
{
    ...

    public void DisablePossibility(PossibilityRect possibility)
    {
        Debug.Assert(Selected, "Only selected cell can disable possibility.");
        if (possibility.Value == model.Value)
        {
            possibility.Unselect();
        }
        else
        {
            possibility.ClearStrikethrough();
        }
        possibility.Disable();
    }

    public void EnablePossibility(PossibilityRect possibility)
    {
        Debug.Assert(Selected, "Only selected cell can enable possibility.");
        possibility.Enable();
        if (possibility.Value == model.Value)
        {
            possibility.Select();
        }
        else
        {
            foreach (CellSetType cellSetType in model.GetCellSetTypesHavingValue(possibility.Value))
            {
                possibility.DisplayStrikethroughForType(cellSetType);
            }
        }
    }
}
Finally in the work cell (WorkCellImage) we update the SelectCell and SelectPossibility methods so that:
  • Selecting a selected cell "unselects" it
  • When a cell is selected, possibilities are activated
  • When a cell is unselected, possibilities are deactivated
  • Selecting a selected possibility "unselects" it
public class WorkCellImage : MonoBehaviour
{
    ...

    public void SelectCell(CellImage cell)
    {

        Debug.Assert(cell != null, "Cell cannot be null.");
        if (selectedCell != null)
        {
            foreach (PossibilityRect possibility in GetComponentsInChildren<PossibilityRect>())
            {
                selectedCell.DisablePossibility(possibility);
            }
            selectedPossibility = null;
            selectedCell.Unselect();
        }
        // Selecting "already selected" cell should unselect it.
        if (selectedCell == cell)
        {
            selectedCell = null;
        }
        else
        {
            selectedCell = cell;
            selectedCell.Select();
            foreach (PossibilityRect possibility in GetComponentsInChildren<PossibilityRect>())
            {
                if (possibility.Value == selectedCell.GetValue())
                {
                    selectedPossibility = possibility;
                }
                selectedCell.EnablePossibility(possibility);
            }
        }
    }

    public void SelectPossibility(PossibilityRect possibility)
    {
        Debug.Assert(selectedCell != null, "Selected cell cannot be null.");
        Debug.Assert(possibility != null, "Possibility cannot be null.");
        if (selectedPossibility != null)
        {
            selectedPossibility.Unselect();
        }
        // Selecting "already selected" possibility should unselect it.
        if (selectedPossibility == possibility)
        {
            selectedPossibility = null;
            selectedCell.SetValue(0);
        }
        else
        {
            selectedPossibility = possibility;
            selectedPossibility.Select();
            selectedCell.SetValue(selectedPossibility.Value);
        }
    }
}
We get a functional app, which strikes out impossible values, and prevents user from "clicking" illegal Sudoku board:


At the end, we would like to improve the experience for keyboard users. We would like:
  • arrows to move the selected cell
  • the "space" key to unselect a cell
  • digits to select the possible value
  • the "zero" digit to unselect a possible value
In order to do that, we add arrow and "space" keys handling to the cell (CellImage):

public class CellImage : MonoBehaviour
{
    ...
    
    // Update is called once per frame
    void Update()
    {
        if (Selected) {
            if (Input.GetKeyDown(KeyCode.DownArrow))
            {
                SelectCellInTheNextFrame(nextInCol);
            }
            if (Input.GetKeyDown(KeyCode.RightArrow))
            {
                SelectCellInTheNextFrame(nextInRow);
            }
            if (Input.GetKeyDown(KeyCode.UpArrow))
            {
                SelectCellInTheNextFrame(prevInCol);
            }
            if (Input.GetKeyDown(KeyCode.LeftArrow))
            {
                SelectCellInTheNextFrame(prevInRow);
            }
            if (Input.GetKeyDown(KeyCode.Space))
            {
                SelectCellInTheNextFrame(this);
            }
        }
    }

    private async void SelectCellInTheNextFrame(CellImage cell)
    {
        await Task.Yield();
        WorkCellImage.Instance.SelectCell(cell);
    }
    
    ...
}
We add digit keys handling to the possible value (PossibilityRect):

public class PossibilityRect : MonoBehaviour
{
    ...

    private KeyCode GetKeyCode()
    {
        switch (Value)
        {
            case 1: return KeyCode.Alpha1;
            case 2: return KeyCode.Alpha2;
            case 3: return KeyCode.Alpha3;
            case 4: return KeyCode.Alpha4;
            case 5: return KeyCode.Alpha5;
            case 6: return KeyCode.Alpha6;
            case 7: return KeyCode.Alpha7;
            case 8: return KeyCode.Alpha8;
            case 9: return KeyCode.Alpha9;
            default: return KeyCode.None;
        }
    }

    // Update is called once per frame
    void Update()
    {
        // Select this possibility if its value is pressed
        if ((Enabled && Input.GetKeyDown(GetKeyCode())) ||
            // ...or unselect it if it's currently selected and '0' is pressed.
            (Selected && Input.GetKeyDown(KeyCode.Alpha0)))
        {
            WorkCellImage.Instance.SelectPossibility(this);
        }
    }
    
    ...
}
That's how we get the app from the introduction.

GitHub

Commits related to this step are here:

Next steps

The app shows possible values for a cell only after it is selected. In the next step we will add hints about the cells which only have one valid possibility (and what it is).

Polish | English
Previous
Next

Comments

Post a Comment

Popular posts from this blog

The Beginnings

  Motivation As a programmer, and at the same time puzzle lover ( GMiL ,  WSPC ), mortgage owner, real-estate owner, home budget planner, etc. I simplify my life with the use of a computer in many different ways: Implement solvers for some puzzles - to check my own solutions of course ;-) Create spreadsheets calculating my mortgage rates - in Swiss franks of course ;-) Create an app to analyze publicly available Polish land and mortgage registers from  Elektroniczne Księgi Wieczyste  - for my own use Every six months analyze my family's home budget - to figure out when I'll finally be  financially independent ... I realized that I'm surely not the only person with such problems / questions, so I decided to create a set of tools for solving them, thus simplifying everyday life. What will be here? To increase my motivation, and maybe motivate other people for sharing their tools, I plan to describe the process of creating all the tools in this blog. To maximize my...
Read more

Check Sudoku - Unity Tutorial - 3. App skeleton

Image
In the previous step we have  set up Unity and GitHub . In this one, we will create an app skeleton, with home page, settings panel, empty board: Implementation Since a lot has changed in Unity over the years (e.g. TextMeshPro is used instead of regular text) we start from completing a simple tutorial: Creative Core: UI Let's start with the home page. We want to have a Sudoku background, but without paying for any "stock" photos, therefore we print one page of problems from  WSPC 2021  and take the picture ourselves: The first challenge is making the home page look good in both portrait and landscape orientation. We achieve it by using AspectRatioFitter for the background as explained  here .  After reading  this  we add a title anchored to the upper left corner of the screen, and panel with buttons anchored to the lower right corner.  This gives us the following UI: We add some background music from pixabay.com . Following Creative Core UI : Ad...
Read more

Check Sudoku - Unity Tutorial - 4. Setting values

Image
In the previous step we have created app skeleton . In this one we will implement setting the values of board cells: Implementation In order to fill the board with 3x3 squares (we need 9 of those) and individual cells (we need 81) we create prefabs and use the  GridLayout  to display them. We create one  GroupRect  for each 3x3 group and one  CellImage  for each cell: We follow the same pattern with the work cell, where we display possible values. We create  PossibilityRect  to display possible cell value: After clicking the cell ( CellImage ), we want something (???) to highlight the selected cell with a frame, and we want the work cell ( WorkCellImage ) to display current cell value. After clicking another cell, something (???) should deselect the previous cell, highlight the new one, and display the new cell value in the work cell. Question 1: Which element should store the information about which cell is selected? Options: The game manager ( ...
Read more