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);
}
}