problemgenerator.cs

英国几乎所有的报纸都刊登数独游戏

using System;
using System.Collections;
using System.Drawing;
using System.Windows.Forms;


namespace SuDokuSolution
{
	/// <summary>
	/// Class for generating problems
	/// </summary>
	public class ProblemGenerator
	{
		internal int [,] completeGrid;
		internal int [,] problemGrid;
		internal static bool complete;
		private SuDokuSolution.MainForm mainForm;
		private int level;
		private ProcessingSplash processingSplash;
		
		public ProblemGenerator(SuDokuSolution.MainForm  m)
		{
			problemGrid=new int [Constants.nbOfCells,Constants.nbOfCells];
			completeGrid=new int [Constants.nbOfCells,Constants.nbOfCells];
			this.mainForm=m;
		}
	
		/// <summary>
		/// method for generating complete grid
		/// </summary>
		/// <returns>true if operation is successful</returns>
		private bool creatCompleteGrid()
		{
			for(int row =0;row<9;row++)
			{
				for(int col=0;col<9;col++)
				{ 
					this.problemGrid[row,col]=Constants.NoNumber;
					this.completeGrid[row,col]=Constants.NoNumber;					
				}
			}

			ArrayList freeCols=new ArrayList(9);    
			ArrayList filledPoints=new ArrayList(9); 			//for storing positions of filled ponts so that making roll back easy          

			Random rand=new Random();
			for(int count=1;count<=9;count++)           
			{          
				int repetitions=0;
				filledPoints.Clear();
				for(int row =0;row<9;row+=2)
				{ 
					//rows are being filled at a diff of two, at the end it rolls off to start
					repetitions++;
					if(repetitions==150)
					{
						return false;
					}
					freeCols.Clear();                        
					foreach (int number in new int[9]{0,1,2,3,4,5,6,7,8})
					{
						freeCols.Add(number);
					}       
					int col=0;
					bool repeat=true;
					while(repeat) //find a position in current row for placing current count
					{
						repeat=false;                        
						if(freeCols.Count==0)
						{ 
							//remove no. filled already
							for(int rollBack=0;rollBack<filledPoints.Count;rollBack++)
							{
								Point p=(Point)filledPoints[rollBack];
								completeGrid[p.X,p.Y]=Constants.NoNumber;
							}
							row=-2;
							repeat=true;
							break;
						}
                         
						//select a new column at random and get its value                        
						col=rand.Next(0,freeCols.Count);                      
						col=(int)freeCols[col];
						if(this.completeGrid[row,col]!=Constants.NoNumber)
						{
							freeCols.Remove(col);
							repeat=true;
							continue;
						}                   
                   
						int HB=(int)(row/3);
						int VB=(int) (col/3);
                    
						for(int i=0;i<9;i++)
						{
							if(completeGrid[i,col] ==count)
							{
								freeCols.Remove(col);
								repeat=true;
							}
						}
                    
						if(repeat)
							continue;
                          
						for(int i=HB*3;i<(HB+1)*3;i++)
						{
							for(int j=VB*3;j<(VB+1)*3;j++)
							{
								if(completeGrid[i,j] ==count)
								{
									freeCols.Remove(col);
									repeat=true;
								}
							}
						}                      
					}

					//if while loop is broken and repeat is true than start from row zero again
					if(repeat)
						continue;
                   
					this.completeGrid[row,col]=count;
					filledPoints.Add(new Point(row,col));
					this.problemGrid[row,col]=this.completeGrid[row,col];
					if(row==8) 
						row=-1;
				}               
			}
			return true;
		}


		/// <summary>
		/// for generating probem grid
		/// </summary>
		/// <returns>true if operation is successful</returns>
		private bool creatProblemGrid()
		{
			Random rand=new Random();
			int [,]solArray=new int[Constants.nbOfCells,Constants.nbOfCells];
          
			ArrayList points=new ArrayList();
			for(int row=0;row<Constants.nbOfCells;row++)
			{
				for(int col=0;col<Constants.nbOfCells;col++)
				{
					points.Add(new Point(row,col));
				}
			}
         
			for(int count =0;count<this.level;count++)
			{
				if(points.Count==0)
					return false;

				int pRand=rand.Next(0,points.Count);
				Point p=(Point)points[pRand]; 
				int row=p.X;
				int col=p.Y;
             
				this.problemGrid[row,col]=Constants.NoNumber;
				if(!(hasSolution(problemGrid,ref solArray,true)==true 
					&& areEqualArray(solArray,completeGrid)==true ))
				{                   
					this.problemGrid[row,col]=this.completeGrid[row,col];                  
					count--;                    
					points.RemoveAt(pRand);
					continue;
				}    
				points.RemoveAt(pRand);
              
				this.processingSplash.progressBar.PerformStep();
			}
			return true;
		}

		#region Alternative Solution for hasSolution
		/// <summary>
		/// Chhecks if the problem grid passed is solvable
		/// </summary>
		/// <param name="underProcessingGrid">The problem grid under observation</param>
		/// <param name="returnArray">The  solution array if toReturnArray==true</param>
		/// <param name="toReturnSolution">If true the return array argument has the solution of the problem </param>
		/// <returns>True if problem is solvable</returns>
		public static bool hasSolution1(int [,] underProcessingGrid,ref int [,] returnArray,bool toReturnSolution)
		{
			int [,] solution=new int [9,9];
			for(int row=0;row<9;row++)
			{
				for(int col=0;col<9;col++)
				{
					solution[row,col]=underProcessingGrid[row,col];
				}
			}
			complete=false;
			bool canSolve=true;
			bool makeChoice=false;
			while(complete==false)
			{
				if(canSolve==false && makeChoice==true)
					return canSolve;

				else if(canSolve==false && makeChoice==false )
					//MessageBox.Show("a");
					makeChoice=true;
                           
				canSolve=false;
				complete=true;
                
				for(int row=0;row<9;row++)
				{
					for(int col=0;col<9;col++)
					{
						int HB=(int)(row/3);
						int VB=(int) (col/3);
						ArrayList candidateNb=new ArrayList(9);
						foreach (int number in new int[9]{1,2,3,4,5,6,7,8,9})
						{
							candidateNb.Add(number);
						}       
						if(solution[row,col]==Constants.NoNumber)
						{
							complete=false;                            
							for(int i=0;i<9;i++)
							{
								candidateNb.Remove(solution[row,i]);
								candidateNb.Remove(solution[i,col]);
							}
                          
							for(int i=HB*3;i<(HB+1)*3;i++)
							{
								for(int j=VB*3;j<(VB+1)*3;j++)
								{
									candidateNb.Remove(solution[i,j]);                                    
								}
							}
							if(candidateNb.Count==1)
							{
								canSolve=true;      
								solution[row,col]=(int)candidateNb[0];
							}    

							else if(candidateNb.Count==2 && makeChoice==true)
							{
								solution[row,col]=(int)candidateNb[0];
								if(hasSolution1(solution,ref solution,false))
								{
									solution[row,col]=(int)candidateNb[1];
									if(hasSolution1(solution,ref solution,false))  
										return false; //solution is not unique
								
									solution[row,col]=(int)candidateNb[0];
									hasSolution1(solution,ref solution,false); //unique solution retrieve it
									makeChoice=false;
									canSolve=true;
								}
								else
								{
									solution[row,col]=(int)candidateNb[1];
									if(hasSolution1(solution,ref solution,true))
									{
										makeChoice=false;
										canSolve=true;
									}
									else
										solution[row,col]=Constants.NoNumber;
								}
							}
						}                        
					}
				}
			}
			if(toReturnSolution)
				returnArray=solution;
			return true;
		}

		#endregion 

		/// <summary>
		/// Checks if the problem grid passed is solvable
		/// </summary>
		/// <param name="underProcessingGrid">The problem grid under observation</param>
		/// <param name="returnArray">The  solution array if toReturnArray==true</param>
		/// <param name="toReturnSolution">If true the return array argument has the solution of the problem </param>
		/// <returns>True if problem is solvable</returns>
		internal static bool hasSolution(int [,] underProcessingGrid,ref int [,] returnArray,bool toReturnSolution)
		{
            CellData [,] solution=new CellData[Constants.nbOfCells,Constants.nbOfCells];
			for(int row=0;row<Constants.nbOfCells;row++)
			{
				for(int col=0;col<Constants.nbOfCells;col++)
				{
					solution[row,col]=new CellData();
					solution[row,col].candidateNb.Clear();
					solution[row,col].originalNb=underProcessingGrid[row,col];
				}
			}
            
			#region search for candidate nbs and_ set the candidate nb list of each unfilled cell
			for(int row=0;row<Constants.nbOfCells;row++)
			{
				for(int col=0;col<Constants.nbOfCells;col++)
				{
					if(solution[row,col].originalNb!=Constants.NoNumber)
						continue;            
					int HB=(int)(row/Constants.nbOfLines);
					int VB=(int) (col/Constants.nbOfLines);
					ArrayList candidateNb=new ArrayList(9);
					foreach (int number in new int[9]{1,2,3,4,5,6,7,8,9})
					{
						candidateNb.Add(number);
					}                   
            
					for(int i=0;i<9;i++)
					{
						candidateNb.Remove(solution[row,i].originalNb);
						candidateNb.Remove(solution[i,col].originalNb);
					}
                          
					for(int i=HB*3;i<(HB+1)*3;i++)
					{
						for(int j=VB*3;j<(VB+1)*3;j++)
						{
							candidateNb.Remove(solution[i,j].originalNb);                                    
						}
					}
					for(int i=0;i<candidateNb.Count;i++)
						solution[row,col].candidateNb.Add(candidateNb[i]);
				}
			}
			#endregion
            
			bool complete=false;
			bool canSolve=true;
			while(!complete)
			{  
				if(!canSolve)
					return false;
				complete=true;
				canSolve=false;
				for(int row=0;row<Constants.nbOfCells;row++)
				{
					for(int col=0;col<Constants.nbOfCells;col++)
					{
						if(solution[row,col].originalNb==Constants.NoNumber)						
						{
							if(complete)
								complete=false;
						}
						else
							continue;
						int HB=(int)(row/Constants.nbOfLines);
						int VB=(int) (col/Constants.nbOfLines);
						if(solution[row,col].candidateNb.Count==1)
						{
							canSolve=true;
							int nb=solution[row,col].originalNb=(int)solution[row,col].candidateNb[0];
							solution[row,col].candidateNb.Clear();
							//now modify other cell's  candidates
							for(int i=0;i<Constants.nbOfCells;i++)
							{
								solution[row,i].candidateNb.Remove(nb);
								solution[i,col].candidateNb.Remove(nb);
							}
                          
							for(int i=HB*3;i<(HB+1)*3;i++)
							{
								for(int j=VB*3;j<(VB+1)*3;j++)
								{
									solution[i,j].candidateNb.Remove(nb);
								}
							}
						}
                        
						else  //find nb that cannot come into any cell of that block
						{
							for(int index=0;index<solution[row,col].candidateNb.Count;index++)
							{
								int number=(int)solution[row,col].candidateNb[index];
								bool found=false;
								for(int i=HB*Constants.nbOfLines;i<(HB+1)*Constants.nbOfLines;i++)                                
									for(int j=VB*Constants.nbOfLines;j<(VB+1)*Constants.nbOfLines;j++)                                    
										if(solution[i,j].candidateNb.Contains(number) && !(i==row && j==col))
										{
											j=(VB+1)*Constants.nbOfLines; //exit from loop
											i=(HB+1)*Constants.nbOfLines;
											found=true;
										}   
                                
								if(!found)
								{
									//the candidate  nb is found
									solution[row,col].originalNb=number;
									canSolve=true;
									solution[row,col].candidateNb.Clear();
									for(int i=0;i<9;i++) //remove that num from other lists
									{
										solution[row,i].candidateNb.Remove(number);
										solution[i,col].candidateNb.Remove(number);
									}
									index=100; //exit from loop
								}
							}
						}
					}
				}              
			}

			if(toReturnSolution)
				for(int row=0;row<9;row++)
				{
					for(int col=0;col<9;col++)
					{
						returnArray[row,col]=solution[row,col].originalNb;
						solution[row,col].Dispose(true);
					}
				}                      
			return true;
		}

       
		/// <summary>
        /// Checks if the two array passed are equal
        /// </summary>
        /// <param name="first">The first array</param>
        /// <param name="second">Second array</param>
        /// <returns>True if the two array passed are equal</returns>
		private bool areEqualArray(int [,]first,int [,]second)
		{
			if(first.Length!=second.Length)
				return false;
			
			for(int row=0;row<Constants.nbOfCells;row++)
			{
				for(int col=0;col<Constants.nbOfCells;col++)
				{
					if(first[row,col]!=second[row,col])
					{
						//MessageBox.Show("Method areequal returning false ");
						return false;
					}
				}
			}
			return true;
		}


		/// <summary>
		/// Generates the problem and return true if success
		/// </summary>
		public bool GenerateProblem()
		{
			processingSplash =new ProcessingSplash();
			mainForm.Enabled=false;                

			//this.statusBar1.Text="Creating Puzzle";
			try
			{
				using(SuDokuSolution.difficultyDialog dd=new SuDokuSolution.difficultyDialog())
				{
					dd.ShowDialog();
					this.level=dd.Level;
					if(this.level==0)
						return false;
				}

				//clearClicked(sender,e);
				//if(autoFillItem.Checked==true)
				//	showcandItem_Click(autoFillItem,e);
				processingSplash.Show();
				processingSplash.Update();
				this.processingSplash.progressBar.Maximum=this.level;
                
				processingSplash.progressBar.Value=0;
				
				while(! this.creatCompleteGrid())
					System.GC.Collect();
				//MessageBox.Show("No Problem");
                
				while(!this.creatProblemGrid())
				{
					problemGrid=(int[,])completeGrid.Clone();
					processingSplash.progressBar.Value=0;
					processingSplash.progressBar.Refresh();
				}    
			}
			catch(Exception ex)
			{
				MessageBox.Show("Some error has occured to the application"
					+",Retry or close the program and start again\n"+ex.Message,"Error");
			}
			finally
			{  
				this.processingSplash.progressBar.Value=processingSplash.progressBar.Maximum;
				processingSplash.Close();
				mainForm.TopMost=true;
				mainForm.TopMost=false;
				processingSplash.Dispose();
				System.GC.Collect();
				mainForm.Enabled=true;
			}
			return true;
		}

	}
}