using System;
using System.Windows.Forms;
using System.Drawing;
namespace SS
{
//draw the grid manually...
public class SSolveGUI : Form
{
int[,] inGrid,outGrid;
int curCellX=0,curCellY=0;
int status=0;
public SSolveGUI()
{
this.Size=new Size(361,410);
this.SetStyle(ControlStyles.DoubleBuffer |
ControlStyles.AllPaintingInWmPaint |
ControlStyles.UserPaint,true);
this.inGrid = new int[9,9];
this.outGrid = new int[9,9];
this.Text="Sudoku Solver";
}
protected override void OnPaintBackground(PaintEventArgs pe)
{
}
protected override void OnPaint(PaintEventArgs pe) {
int boxWidth=40;
Graphics g = pe.Graphics;
Brush black = new SolidBrush(Color.LightGray);
Brush bWhite = new SolidBrush(Color.Black);
Brush bGreen = new SolidBrush(Color.Green);
g.FillRectangle(black,new RectangleF(0,0,600,600));
Pen white = new Pen(Color.Black,1);
Pen whiteWide = new Pen(Color.Black,3);
Pen cyan = new Pen(Color.Cyan,3);
//draw gridlines
for (int i=0;i<10;i++)
{
if (i%3==0)
{
g.DrawLine(whiteWide,i*boxWidth,0,i*boxWidth,boxWidth*9);
g.DrawLine(whiteWide,0,i*boxWidth,boxWidth*9,i*boxWidth);
}
else
{
g.DrawLine(white,i*boxWidth,0,i*boxWidth,boxWidth*9);
g.DrawLine(white,0,i*boxWidth,boxWidth*9,i*boxWidth);
}
}
//border around selected cell
g.DrawRectangle(cyan,curCellX*boxWidth,curCellY*boxWidth,boxWidth,boxWidth);
//numerals
Font f = new Font("Courier New",30);
for (int i=0;i<9;i++)
for (int j=0;j<9;j++)
{
if (inGrid[i,j] != 0)
g.DrawString(inGrid[i,j].ToString(),f,bGreen,i*boxWidth+8,j*boxWidth);
else if (outGrid[i,j] != 0)
g.DrawString(outGrid[i,j].ToString(),f,bWhite,i*boxWidth+8,j*boxWidth);
}
//Help text
f=new Font("Courier New",12);
g.DrawString("R - Reset Puzzle",f,bWhite,0,boxWidth*9+10);
g.DrawString("S - Solve Puzzle",f,bWhite,0,boxWidth*9+30);
//Status
string statLine="";
switch (status)
{
case 0:
statLine="Waiting";
break;
case 1:
statLine="Solved";
break;
case 2:
statLine="Unsolvable";
break;
}
g.DrawString(statLine,new Font("Courier New",20),bWhite,180,boxWidth*9+15);
g.Flush();
}
private void advanceCurCell()
{
curCellX++;
if (curCellX >= 9)
{
curCellX=0;
curCellY++;
}
if (curCellY >= 9)
curCellY=0;
}
protected override void OnKeyPress(KeyPressEventArgs e)
{
if (status!=0) return;
int val = e.KeyChar - '0';
if (val >= 0 && val <=9)
{
inGrid[curCellX,curCellY]=val;
advanceCurCell();
this.Refresh();
}
}
protected override void OnKeyDown(KeyEventArgs e)
{
switch (e.KeyCode)
{
case Keys.Left:
if (curCellX>0)
curCellX--;
break;
case Keys.Right:
if (curCellX <8)
curCellX++;
break;
case Keys.Up:
if (curCellY>0)
curCellY--;
break;
case Keys.Down:
if (curCellY<8)
curCellY++;
break;
case Keys.R:
inGrid=new int[9,9];
outGrid=new int[9,9];
curCellX=0;
curCellY=0;
status=0;
break;
case Keys.S:
solve();
break;
}
this.Refresh();
base.OnKeyDown(e);
}
private void solve()
{
int[,] newTable=new int[9,9];
System.Array.Copy(inGrid,newTable,81);
State start = new State(newTable);
State result = SSolve.solve(start);
if (result != null)
{
status=1;
outGrid=result.table;
}
else
status=2;
}
}
public class State
{
public int[,] table;
bool[,,] impossible; //1 less
public bool consistent=true;
public State(int[,] table)
{
this.table=table;
buildImpossible();
}
//Checks whether this state is possible
private bool checkConsistency()
{
for (int i=0;i<9;i++) for(int j=0;j<9;j++)
{
bool con=false;
for (int k=0;k<9;k++)
{
if(!impossible[i,j,k])
{
con=true;
break;
}
}
if (!con) return false;
}
return true;
}
//build a list of impossible numbers in each point
private void buildImpossible()
{
impossible=new bool[9,9,9];
for(int i=0;i<9;i++)
{
for (int j=0;j<9;j++)
{
if (table[i,j] == 0)
continue;
markImpossibleH(i,j,table[i,j]-1);
markImpossibleV(i,j,table[i,j]-1);
markImpossibleS(i,j,table[i,j]-1);
}
}
consistent=checkConsistency();
}
//marks horizontal impossibles
private void markImpossibleH(int row,int col,int val)
{
for (int i=0;i<9;i++)
if (i != col)
impossible[row,i,val]=true;
}
//and vertical
private void markImpossibleV(int row,int col,int val)
{
for (int i=0;i<9;i++)
if (i != row)
impossible[i,col,val]=true;
}
//and squares
private void markImpossibleS(int row, int col,int val)
{
int sqrRow=row/3*3,sqrCol=col/3*3;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
{
if (sqrRow+i != row && sqrCol+j != col)
impossible[sqrRow+i,sqrCol+j,val]=true;
}
}
//output this table
public void printTable()
{
for (int i=0;i<9;i++)
{
for (int j=0;j<9;j++)
Console.Write(table[i,j]);
Console.WriteLine();
}
}
//out the number of possible numbers for each cell
public void printPossibility()
{
for(int i=0;i<9;i++)
{
for (int j=0;j<9;j++)
{
int count=0;
for (int k=0;k<9;k++)
{
if (!impossible[i,j,k])
count++;
}
Console.Write(count);
}
Console.WriteLine();
}
Console.WriteLine();
}
//can new cell values be deduced?
public bool hasMoreToFill()
{
for (int i=0;i<9;i++)
for (int j=0;j<9;j++)
{
if (table[i,j]!=0) continue;
int count=0;
for (int k=0;k<9;k++)
if (!impossible[i,j,k])
count++;
if (count==1)
return true;
}
return false;
}
//deduce cell values and rebuild impossible cells
public void fillPossible()
{
for (int i=0;i<9;i++)
for (int j=0;j<9;j++)
{
if (table[i,j]!=0) continue;
int count=0;
int line=0;
for (int k=0;k<9;k++)
if (!impossible[i,j,k])
{
count++;
line=k;
}
if (count==1)
table[i,j]=line+1;
}
buildImpossible();
}
//is this state the complete state for the puzzle
public bool isComplete()
{
foreach (int num in table)
if (num==0) return false;
return true;
}
//take the cell with lowest number of possibilies
//and create states with those possibilities filled in
public State[] generateMostPossibleStates()
{
int lowest=100,lRow=-1,lCol=-1;
for (int i=0;i<9;i++)
for (int j=0;j<9;j++)
{
if (table[i,j]!=0) continue;
int count=0;
for (int k=0;k<9;k++)
if (!impossible[i,j,k])
count++;
if (count < lowest)
{
lRow=i;
lCol=j;
lowest=count;
}
}
State[] ret = new State[lowest];
int curIndex=0;
for (int i=0;i<9;i++)
{
if (!impossible[lRow,lCol,i])
{
int[,] newTable=new int[9,9];
System.Array.Copy(table,newTable,81);
newTable[lRow,lCol]=i+1;
ret[curIndex++]=new State(newTable);
}
}
return ret;
}
}
public class SSolve
{
public static void Main(string[] args)
{
System.Windows.Forms.Application.Run(new SSolveGUI());
}
public static State solve(State s)
{
while (!s.isComplete())
{
if (!s.consistent)
return null;
if (s.hasMoreToFill())
s.fillPossible();
else
{
State[] p = s.generateMostPossibleStates();
foreach(State t in p)
{
State res=solve(t);
if (res != null) return res;
}
return null;
}
}
return s;
}
}
}