Sudoku Solver

A sudoku solver! Made in +/- 4 hours, always fun these challenges 🙂

 

The code, made quite some time ago:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
using System.Diagnostics;

public class Solver : MonoBehaviour
{
    int[,] allNumbers = new int[9, 9];
    int[,,] allSquares = new int[9, 3, 3];
    List OtoN = new List();//One to Nine, all in a list
    List squaresToCheck = new List();//list of the squares, if one is full, remove from list
    List<int[,]> gambles = new List<int[,]>();//list of all the guessed numbers, will be deleted if the guess didn't work out
    int gambleDepth = 0;// if this is 1 we are gambling, if this turns to 2, we're stuck!
    bool gambling = false;
    public Text theText;//the sudoku textbox
    public Text dataText;//display of information after solving

    bool changes;//did we change anything this run? if yes, we don't need to start gambling
    bool solved;

    bool ran;

    Stopwatch timer = new Stopwatch();

    int timesPerSecond;
    //progression bars, not needed for only solving
    public Image surelyCorrectImage;
    public Image gambledImage;
    public InputField timesPerSecondInput;
    int emptySpaces = 81;

    void Start()
    {
        Reset();
    }

    void Reset()///reset all data for next run (,might as well restart scene in this case!)
    {
        OtoN.Clear();
        squaresToCheck.Clear();
        for (int i = 1; i < 10; i++) { OtoN.Add(i); squaresToCheck.Add(i - 1); } emptySpaces = 81; ReadFile(); SplitToSmallerSquares(); gambles.Clear(); gambleDepth = 0; gambling = false; solved = false; dataText.text = "runs through 'while': ? \nSeconds: ? \nMilliseconds: ?"; ran = false; timer.Reset(); } void Update() { if (Input.GetKeyDown(KeyCode.Keypad1) && !ran)//solve it! { ran = true; timer.Start(); StartCoroutine(Solve()); } if (Input.GetKeyDown(KeyCode.Keypad2) && ran) { Reset(); } } IEnumerator Solve()///the while loop which will keep running until it's solved. IEnumerator for showing progression, could be a normal method { int whileLoopRuns = 0; while (!solved)//while not solved, solve { if (squaresToCheck.Count == 0)//we're done! { solved = true; break; } whileLoopRuns++;//how many times did i run through? if (whileLoopRuns > 4999)
                break;
            changes = false;//to check if anything happened this run
            for (int i = 0; i < squaresToCheck.Count; i++) { MissingInSqr(squaresToCheck[i]);//check the squares we need to check } if (!changes)//nothing changed this run, it's time to gamble { gambleDepth++;// -- when gambled gambling = true;//from this point on we ahve to reset if things go wrong :( if (gambleDepth >= 2)//two times nothing in a row? we can't even gamble anymore! time to reset the gambles and try again
                {
                    foreach (int[,] gamble in gambles)
                    {
                        allNumbers[gamble[0, 0], gamble[0, 1]] = 0;//reset gambled numbers
                    }
                    squaresToCheck.Clear();//guess we gotta check everything again CANDO, make squaresToCheck permanently smaller if we didnt gamble
                    for (int i = 0; i < 9; i++) { squaresToCheck.Add(i); } SplitToSmallerSquares();//gotta update smaller boxes gambles.Clear();//clear list of gambled items } } RefreshText();//this one and the next lines until the end of the while loop bloat the speed process, but this way you can see the progression if (timesPerSecond == 0) { } else yield return new WaitForSeconds(1 / timesPerSecond); } timer.Stop(); dataText.text = "runs through 'while': " + whileLoopRuns + "\nSeconds: " + timer.ElapsedMilliseconds / (float)1000 + "\nMilliseconds: " + timer.ElapsedMilliseconds; if (whileLoopRuns > 4999)
            dataText.text = "This sudoku doesn't have a solution!";
        RefreshText();//lets show it!
        yield return null;
    }

    void ReadFile()///Read the file and put the numbers in my 9x9 matrix
    {
        string theBigOne = Resources.Load("sudoku").ToString();//load challenge text
        string noEnters = theBigOne.Replace('\n', ' ');//remove to enter
        string[] smallStrings = noEnters.Split(' ');//make small strings without spaces
        int currentStringy = 0;//the current "char" from smallStrings
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                allNumbers[j, i] = int.Parse(smallStrings[currentStringy]);//cramp them into my 2D array
                currentStringy++;//next number
            }
        }
        RefreshText();
    }

    void SplitToSmallerSquares()///make the 9x9 matrix into 9 3x3 matrixes
    {
        emptySpaces = 0;//for progression
        for (int i = 0; i < 9; i++)
        {
            int bonusX = (i % 3) * 3;// +3 or +6 for which column we select (0 = column 1, +3 = column 2)
            int bonusY = (i / 3) * 3;// +3 or +6 for which row we select (0 = row 1, +3 = row 2)
            for (int y = 0; y < 3; y++)
            {
                for (int x = 0; x < 3; x++)
                {
                    allSquares[i, x, y] = allNumbers[x + bonusX, y + bonusY];//put numbers from 9x9 into i's 3x3
                    if (allNumbers[x + bonusX, y + bonusY] == 0)
                        emptySpaces++;
                }
            }
        }
    }

    void MissingInSqr(int sqr)///checks what numbers are missing in a a square & what positions are empty, at the end calls "CheckSqrAndPlace"
    {
        List missing = new List(OtoN);//what numbers i have to check the empty positions for
        List<int[,]> positionsEmpty = new List<int[,]>();//positions that are empty and have to be checked
        for (int y = 0; y < 3; y++)
        {
            for (int x = 0; x < 3; x++)
            {
                if (allSquares[sqr, x, y] != 0)
                {
                    missing.Remove(allSquares[sqr, x, y]);//checking square is not 0, we already have this number!
                }
                else
                {
                    int[,] current = new int[1, 3] { { sqr, x, y } };//this is an empty spot!
                    positionsEmpty.Add(current);
                }
            }
        }
        List<int[,]> worldPositionsEmpty = new List<int[,]>();//positions that are empty and have to be checked
        if (positionsEmpty.Count == 0)
        {
            squaresToCheck.Remove(sqr);//if there are no missing numbers in this box, why should we keep checking it?
            return;
        }
        for (int i = 0; i < positionsEmpty.Count; i++)
            worldPositionsEmpty.Add(SqrHolesToAllHoles(positionsEmpty[i]));//get the 9x9 position for every missing spot
        CheckSqrAndPlace(sqr, missing, worldPositionsEmpty);//time to check row's and columns
    }

    void CheckSqrAndPlace(int sqr, List missingNumbers, List<int[,]> positionsToCheck)///checks all the empty spaces and places the numbers
    {
        bool runAgain = false;//if we place something, run this method again
        List<int[,]> numberPossibleAtPosition = new List<int[,]>();//at what positions is number x possible

        for (int i = 0; i < positionsToCheck.Count; i++) //search only empty spots
        {
            List allOnRow = new List();
            List allOnColumn = new List();
            List currentMissingNumbers = new List(missingNumbers);
            for (int j = 0; j < 9; j++) { allOnRow.Add(allNumbers[j, positionsToCheck[i][0, 1]]);//all the numbers on my row allOnColumn.Add(allNumbers[positionsToCheck[i][0, 0], j]);//all the numbers in my column } foreach (int a in allOnRow) { currentMissingNumbers.Remove(a);//we can't put numbers in the same row here! } foreach (int a in allOnColumn) { currentMissingNumbers.Remove(a);//we can't put numbers in the same column here! } if (gambleDepth > 0)//we gonna gamble now
            {
                if (currentMissingNumbers.Count == 2)//this position has 2 possibilities, lets take one random. CANDO remember what you did here to not repeat
                {
                    ChangeNumber(currentMissingNumbers[Random.Range(0, 2)], positionsToCheck[i]);
                    gambleDepth--;//we gambled :(
                    runAgain = true;
                    break;
                }
            }
            if (currentMissingNumbers.Count == 1)//this hole is noly missing one! obv what it is
            {
                ChangeNumber(currentMissingNumbers[0], positionsToCheck[i]);
                runAgain = true;
                break;

            }
            else
            {
                foreach (int currentNumber in currentMissingNumbers)//make array for every number and their possible positions
                {
                    numberPossibleAtPosition.Add(new int[1, 2] { { currentNumber, i } });//hole i is missing number a
                }
            }
        }
        if (!runAgain)
        {
            for (int i = 0; i < missingNumbers.Count; i++)
            {
                int currentNumber = missingNumbers[i];
                int seen = 0;
                int seenPosition = -1;
                foreach (int[,] a in numberPossibleAtPosition)
                {

                    if (a[0, 0] == currentNumber)
                    {
                        seen++;
                        seenPosition = a[0, 1];//last position this number was possible
                    }
                }

                if (seen == 1)//found the spot, it's been "seen" only once, so it an only be placed here!
                {
                    runAgain = true;
                    ChangeNumber(currentNumber, positionsToCheck[seenPosition]);
                }
            }
        }
        if (runAgain)
            MissingInSqr(sqr);
    }

    void ChangeNumber(int number, int[,] position)///Put number $number on position $position
    {
        allNumbers[position[0, 0], position[0, 1]] = number;//set number $number at position $position

        if (gambling)
        {
            gambles.Add(new int[1, 2] { { position[0, 0], position[0, 1] } });//woops, we gambled! add them to the list to delete if we were wrong

        }
        changes = true;//there were changes this run! no need to gamble (yet)
        SplitToSmallerSquares();//remake smaller boxes, CANDO: set number in smallerboxes instead of updating all smaller boxes
    }

    int[,] SqrHolesToAllHoles(int[,] positionsToCheck)/// from small 3x3 sqr to 9x9 matrix position, [1,3] in, [1,2] out
    {
        int bonusX = (positionsToCheck[0, 0] % 3) * 3;
        int bonusY = (positionsToCheck[0, 0] / 3) * 3;

        int[,] toReturn = new int[1, 2] { { positionsToCheck[0, 1] + bonusX, positionsToCheck[0, 2] + bonusY } };
        return toReturn;
    }

    void RefreshText()///refresh sudoku layout and progression bars
    {
        theText.text = "";
        for (int i = 0; i < 9; i++)
        {
            if (i % 3 == 0)
            {
                theText.text += "---------------------------\n";
            }
            theText.text += "| " + allNumbers[0, i] + " " + allNumbers[1, i] + " " + allNumbers[2, i] + " | " + allNumbers[3, i] + " " + allNumbers[4, i] + " " + allNumbers[5, i] + " | " + allNumbers[6, i] + " " + allNumbers[7, i] + " " + allNumbers[8, i] + " |\n";
        }
        //bloating, update progression
        gambledImage.fillAmount = 1 - ((float)emptySpaces / 81);
        surelyCorrectImage.fillAmount = 1 - (((float)emptySpaces + gambles.Count) / 81);
    }

    public void TimesPerSecondUpdate()///when you fill the inputbox
    {
        if(timesPerSecondInput.text != "")
        timesPerSecond = int.Parse(timesPerSecondInput.text);
    }
}