Solving Paint-by-numbers puzzles in C#

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
using System.Drawing;

namespace hanjie
{
	public class Brain
	{
		protected internal HanjieBoard mBoard;
		private Size mSize;
		private colorRow[] mcolorRow;
		//private colorLine[] mAllLines;
		private int mNbRowCols;
		private Int64[,] PascalTriangle;

		public Brain(HanjieBoard board)
		{
			mBoard = board;
			mSize = board.BoardSize;
			
			int triangleWidth=max(mSize.Width,mSize.Height)+1;
			int triangleHeight=max(board.fixedRows,board.fixedCols)+1;
			int x, y;
			
			// We pre-calculate a Pascal triangle for two reasons
			// first is it is a great name
			// second it is use to find out how many possiblities there is for a row.
			// lets say I got 8 spaces to distribute amongst 3 lines, I just have to
			// read the pascal triangle on [3,8] to get the number of possibilities
			PascalTriangle = new Int64[triangleWidth,triangleHeight];
			for (y = 0; y < triangleHeight; y++) PascalTriangle[0,y] = 1;
			for (x = 1; x < triangleWidth; x++) PascalTriangle[x,0] = 1;
			
			for (x = 1; x < triangleWidth; x++)
			{
				for (y = 1; y < triangleHeight; y++)
				{
					PascalTriangle[x, y] = PascalTriangle[x - 1, y] + PascalTriangle[x, y - 1];
				}
			}
		}

		int max(int a, int b)
		{
			if (a > b) return a;
			return b;
		}

		void initArrays()
		{
			// lets start by building columns and rows classes		
			ArrayList rowCells = new ArrayList();
			ArrayList allLines = new ArrayList();
			
			mNbRowCols = mSize.Width + mSize.Height;
			mcolorRow = new colorRow[mNbRowCols];

			for (int x = 0; x < mSize.Width; x++)
			{
				for (int y = 0; y < mSize.Height; y++)
				{
					Cell c = mBoard.GetCell(MatrixLocation.mainCells, x, y);
					c.color = -1;
				}
			}

			colorRow rl;

			for (int y = 0; y < mSize.Height; y++)
			{
				rowCells.Clear();
				for (int x = 0; x < mBoard.fixedCols; x++)
					rowCells.Add(mBoard.GetCell(MatrixLocation.fixedCols, x, y));

				rl = new colorRow(this, true, y, mSize.Width, rowCells);

				rowCells.Clear();
				for (int x = 0; x < mSize.Width; x++)
					rowCells.Add(mBoard.GetCell(MatrixLocation.mainCells, x, y));

				rl.mCells = (Cell[])rowCells.ToArray(typeof(Cell));
				mcolorRow[y] = rl;
			}
			
			for (int x = 0; x < mSize.Width; x++)
			{
				rowCells.Clear();
				for (int y = 0; y < mBoard.fixedRows; y++)
					rowCells.Add(mBoard.GetCell(MatrixLocation.fixedRows, x, y));
				rl = new colorRow(this, false, x, mSize.Height, rowCells);

				rowCells.Clear();
				for (int y = 0; y < mSize.Height; y++)
					rowCells.Add(mBoard.GetCell(MatrixLocation.mainCells, x, y));

				rl.mCells = (Cell[])rowCells.ToArray(typeof(Cell));
				mcolorRow[mSize.Height + x] = rl;
			}

		}

		private delegate void CompletedDelegate();

		public void Resolve()
		{
			initArrays();
			recurseNextLine();
			Finish();
		}

		public void Finish()
		{
			Form1.instance.Invoke(new CompletedDelegate(Form1.instance.Completed));
			System.Threading.Thread.CurrentThread.Abort();
		}

		public void recurseNextLine()
		{
			colorLine line;
			int min, max;

			colorLine bestLine = null;
			int bestMin=0;
			int bestMax=0;
			Int64 bestNbCombination = Int64.MaxValue;
					
			
			// find the line which need to be moved the less
			for (int i = 0; i < mNbRowCols; i++)
			{
				colorRow row = mcolorRow[i];
				
				int[] savedRow = new int[row.mRowLength];
				saveRow(row, savedRow);

				int nbBlank = row.mRowLength; ;
				for (int j = 0; j < row.mLen; j++) nbBlank -= row.mLines[j].count;

				Int64 nbCombination = PascalTriangle[nbBlank, row.mLen];

				for (int j = 0; j < row.mLen; j++)
				{
					line = row.mLines[j];
					if (line.mLineDone == false)
					{
						min =line.posMin();
						if (min < 0)
						{
							// this line does not fit anymore
							return;
						}
						max = line.posMax();
						if (max < 0)
						{
							// this line does not fit anymore
							return;
						}
						
						int range = (max - min);
						if (range>0 && range < line.count)
						{
							// cool we might have a nice 
							int newFixRange = line.count - range;

							bool somethingChanged = false;
							int oldFixRange = line.mFixRange;
							line.mFixRange = newFixRange;
							somethingChanged |= setColor(row, max, max + newFixRange - 1, line.color);
							// now try to see if we can clear before or after

							if (line.prevLine == null) somethingChanged |= clear(row, 0, min - 1);
							else somethingChanged |= clear(row, line.prevLine.posMax() + line.prevLine.count, min - 1);

							if (line.nextLine == null) somethingChanged |= clear(row, max + line.count, line.mRow.mRowLength - 1);
							else somethingChanged |= clear(row, max + line.count, line.nextLine.posMin() - 1);

							if (somethingChanged)
							{
								recurseNextLine();
								restoreRow(savedRow, row);
								return;
							}
						}
						if (min>=0 && min == max) nbCombination = 0;
						if (nbCombination < bestNbCombination)
						{
							bestNbCombination = nbCombination;
							bestMin = min;
							bestMax = max;
							bestLine = line;
						}
					}
					if (bestNbCombination == 0) break;
				}
				if (bestNbCombination == 0) break;
			}
			
			// try to move this line
			if (bestLine != null)
			{
				line = bestLine;
				min = bestMin;
				max = bestMax;
				line.mLineDone = true;
				colorRow row = line.mRow;

				int[] savedRow = new int[row.mRowLength];
				
				saveRow(row,savedRow);
			
				for (int pos = min; pos <= max; pos++)
				{
					if (line.canGo(pos))
					{
						line.actualPos = pos;
						if (pos > 0)
						{
							if (line.prevLine == null) clear(row, 0, pos - 1);
							else if (line.prevLine.mLineDone) clear(row, line.prevLine.actualPos + line.prevLine.count, pos - 1);
							else if (line.spaceBefore) row.mCells[pos - 1].color = 0; 
						}
						setColor(row, pos, pos + line.count - 1, line.color);

						if ((pos + line.count) < line.mRow.mRowLength)
						{
							if (line.nextLine == null) clear(row, pos + line.count, line.mRow.mRowLength - 1);
							else if (line.nextLine.mLineDone) clear(row, pos + line.count, line.nextLine.actualPos - 1);
							else if (line.spaceAfter) row.mCells[pos + line.count].color = 0; 
						}
						recurseNextLine();
						restoreRow(savedRow, row);
					}
				}
				line.mLineDone = false;
			}
			else
			{
				Finish();
			}
		}

		bool clear(colorRow row, int min, int max)
		{
			return setColor(row, min, max, 0);
		}

		bool setColor(colorRow row, int min, int max,int color)
		{
			bool somethingChanged = false;
			if (min < 0) min = 0;
			if (max >= row.mRowLength) max = row.mRowLength - 1;
			for (int j = min; j <= max; j++)
			{
				if (row.mCells[j].color != color)
				{
					row.mCells[j].color = color;
					somethingChanged = true;
				}
			}
			return somethingChanged;
		}


		void saveRow(colorRow row, int[] savedRow)
		{
			for (int j=row.mRowLength-1;j>=0;j--) savedRow[j]=row.mCells[j].color;
		}

		void restoreRow(int[] savedRow, colorRow row)
		{
			for (int j = row.mRowLength - 1; j >= 0; j--) row.mCells[j].color = savedRow[j];				
		}
	}
}