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