Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
void Main()
{
//testGenerating();
var grid = goodGrid();
//grid.Write().Dump();
grid.MakeGame();
//grid.Write().Dump();
var foundOne = false;
var game = grid.Write();
while(!foundOne)
{
try
{
grid.Assess();
foundOne = grid.FillInTheObvious();
if (foundOne)
{
game.Dump();
}
}
catch (InvalidDataException e)
{
//oookay. let's start again.
//"Oops".Dump();
grid = goodGrid();
grid.MakeGame();
game = grid.Write();
}
}
//grid.cells.Select(p => p.Value == null ? p.Possible.Count : p.Value).Dump();
}
private Grid goodGrid() {
Random r = new Random();
var success = false;
var grid = new Grid() { R = r};
while (!success)
{
//Util.ClearResults();
grid = new Grid() { R = r};
success = grid.Generate();
//grid.Write().Dump();
}
return grid;
}
private void testGenerating() {
Random r = new Random();
int b = 0;
for (int z = 0; z<100; z++) {
int a = 0;
b++;
var success = false;
Grid grid = new Grid() { R = r};
while(!success) {
a++;
//Util.ClearResults();
grid = new Grid() { R = r};
success = grid.Generate();
//grid.Write().Dump();
}
//grid.Write().Dump();
//a.Dump();
if (a >= 1590) {
//a.Dump();
//b.Dump();
//grid.Write().Dump();
}
}
}
// Define other methods and classes here
public class Grid
{
public List<Cell> cells = new List<Cell>();
public Random R { get; set; }
public Grid ()
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
cells.Add(new Cell { RowNumber = i, ColumnNumber = j, Value = null});
}
public string Write()
{
var result = new StringBuilder();
int row = 0;
int column = 0;
foreach(var c in cells)
{
result.Append((c.Value == null? "_" : c.Value.ToString()) + " ");
column++;
if (column >= 9)
{
column = 0;
row++;
result.AppendLine();
if (row % 3 == 0 && row < 9)
{
result.AppendLine("-------------------------------------");
}
} else if (column % 3 == 0)
{
result.Append(" | ");
}
else
{
result.Append(" ");
}
}
return result.ToString();
}
public string WritePossible()
{
var result = new StringBuilder();
int row = 0;
int column = 0;
foreach(var c in cells)
{
result.Append((c.Value != null? "_" : c.Possible.Count().ToString()) + " ");
column++;
if (column>=9) {
column = 0;
row++;
result.AppendLine();
if (row%3 == 0 && row < 9)
{
result.AppendLine("-------------------------------------");
}
}
else if (column % 3 == 0)
{
result.Append(" | ");
}
else
{
result.Append(" ");
}
}
return result.ToString();
}
public IEnumerable<Cell> GetRow(int rowNumber)
{
return this.cells.GetRange(rowNumber*9, 9);
}
public IEnumerable<Cell> GetColumn(int columnNumber)
{
var result = new List<Cell>();
for (int i = 0; i < 9; i++)
{
result.Add(this.cells[columnNumber + (i*9)]);
}
return result;
}
// Return the 3x3 'subgrid' to which this row/col belongs.
public IEnumerable<Cell> GetSubGrid(int columnNumber, int rowNumber)
{
int colN = (columnNumber / 3)*3 ;
int rowN = (rowNumber / 3)*3;
var result = new List<Cell>();
for(int i = 0; i< 3; i++)
{
result.AddRange(this.cells.GetRange((i*9)+(9*rowN) + colN, 3));
}
return result;
}
public bool MakeGame() {
var numbers = new List<int>();
for(int i = 0; i<9; i++)
{
numbers.Add(9);
}
var keepGoing = true;
int numberRemoved = 0;
while(keepGoing)
{
var x = R.Next(81);
var value = this.cells[x].Value;
if (value != null && numbers[(value ?? 1)-1] > 2)
{
this.cells[x].Value = null;
numbers[(value ?? 1)-1] = numbers[(value ?? 1)-1]-1;
numberRemoved++;
}
if (numberRemoved >= 50) {
keepGoing = false;
}
}
return true;
}
public bool FillInTheObvious()
{
var foundOne = false;
var nothingToSolve = true;
foreach(var c in this.cells)
{
if (c.Value == null)
{
nothingToSolve = false;
}
if (c.Possible != null && c.Possible.Count == 1)
{
var x = c.Possible.ToArray()[0];
c.Value = x;
foundOne = true;
}
}
if (nothingToSolve)
{
return true;
//Console.WriteLine("SOLVED!");
}
if (!foundOne)
{
throw new InvalidDataException("Data just not valid enough.");
}
return false;
}
public bool Assess()
{
foreach(var c in this.cells)
{
if (c.Value != null)
{
c.Possible = new HashSet<int>();
}
else
{
var numbers = new HashSet<int>(Enumerable.Range(1, 9));
c.Possible = numbers; //Anything is possible.
var row = this.GetRow(c.RowNumber);
foreach(var cell in row)
{
if (cell.Value != null)
{
c.Possible.Remove(cell.Value.Value);
}
}
var column = this.GetColumn(c.ColumnNumber);
foreach(var cell in column)
{
if (cell.Value != null)
{
c.Possible.Remove(cell.Value.Value);
}
}
var subGrid = this.GetSubGrid(c.ColumnNumber, c.RowNumber);
foreach(var cell in subGrid)
{
if (cell.Value != null)
{
c.Possible.Remove(cell.Value.Value);
}
}
}
}
return true;
}
public bool Generate()
{
for(int i = 1; i<=9; i++)
{
for(int j = 0; j<9; j++)
{
var row = GetRow(j).ToList();
var solved = false;
int tries = 0;
while(!solved)
{
tries++;
var candidatePosition = R.Next(9);
if (row[candidatePosition].Value == null
&& !GetColumn(candidatePosition).Any(c => c.Value == i)
&& !GetSubGrid(candidatePosition, j).Any(c => c.Value == i))
{
row[candidatePosition].Value = i;
solved = true;
}
if (!solved && tries > 50) {
return false;
}
}
}
}
return true;
}
}
public class Cell {
public int RowNumber { get; set; }
public int ColumnNumber { get; set; }
public int? Value { get; set; }
public HashSet<int> Possible { get; set;}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment