/***************************************************************************
 *   Copyright (C) 2005 by Torben Nielsen   *
 *   torben@t-hoerup.dk   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#include "solution.h"
#include "queens.h"
#include "solutioncontainer.h"


Queens::Queens(GUIUpdate *par, Solution* sol, SolutionContainer *container, int set_size, bool set_debug) : QThread()
{
	m_parent = par;
	m_size = set_size;
	m_solution = sol;
	m_solution->setSize(m_size);
	m_debug = set_debug;
	m_solutions = container;
}

bool Queens::solve()
{
	return solve(0, false);
}

void Queens::findAll()
{
	solve(0,true);
}

bool Queens::solve(int row, bool findAll)
{
	if (m_blocked == true)
		return false;
	for (int col=0; col<m_size; col++) {

		if (checkCols(row,col) == true && 
				checkCross1(row,col) == true && 
				checkCross2(row,col) == true) 
		{

			
			m_solution->setMatrix(row,col,true);
			
			if (row == (m_size-1) ) 
			{
				if (!findAll)
					return true;
				else 
				{
					m_solutions->addSolution( m_solution->copy() );
					m_parent->foundSolution();
				}
			}

			if ( solve(row+1,findAll) )
				return true;

			m_solution->setMatrix(row,col, false);
		}
	}
	return false;
}


bool Queens::checkRows(int row, int col)
{
	for (int c=0; c<m_size; c++) {
		if (m_solution->getMatrix(row,c) == true)
			return false;
	}
		
	return true;
}

bool Queens::checkCols(int row, int col)
{
	for (int r=0; r<m_size; r++) {
		if (m_solution->getMatrix(r,col) == true)
			return false;
	}
	return true;
}

bool Queens::checkCross1(int row, int col)
{
	int r=row;
	int c=col;
	for (int i=0; i<m_size; i++) {
		if (m_solution->getMatrix(r,c) == true)
			return false;
		r++;
		c++;
		if ( r>(m_size-1) || c>(m_size-1) )
			break;		
	}
	r=row;
	c=col;
	for (int i=0; i<m_size;i++) {
		if (m_solution->getMatrix(r,c) == true)
			return false;
		r--;
		c--;
		if (r<0 || c<0)
			break;
	}
	return true;
}

bool Queens::checkCross2(int row, int col)
{
	int r=row;
	int c=col;
	for (int i=0; i<m_size; i++) {
		if (m_solution->getMatrix(r,c) == true)
			return false;
		r++;
		c--;
		if ( r>(m_size-1) || c<0 )
			break;
	}
	r=row;
	c=col;
	for (int i=0; i<m_size; i++) {
		if (m_solution->getMatrix(r,c) == true)
			return false;
		r--;
		c++;
		if (r<0 || c>(m_size-1))
			break;
	}
	return true;
}

void Queens::run()
{
	m_blocked = false;
	findAll();
	
	if (m_blocked == false)
		m_parent->finishedSearch();
}

void Queens::stop()
{
	m_blocked = true;
}