queensgui/src/queens.cpp

/***************************************************************************
 *   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;
}
1	torben	1	/***************************************************************************
2			* Copyright (C) 2005 by Torben Nielsen *
3			* torben@t-hoerup.dk *
4			* *
5			* This program is free software; you can redistribute it and/or modify *
6			* it under the terms of the GNU General Public License as published by *
7			* the Free Software Foundation; either version 2 of the License, or *
8			* (at your option) any later version. *
9			* *
10			* This program is distributed in the hope that it will be useful, *
11			* but WITHOUT ANY WARRANTY; without even the implied warranty of *
12			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13			* GNU General Public License for more details. *
14			* *
15			* You should have received a copy of the GNU General Public License *
16			* along with this program; if not, write to the *
17			* Free Software Foundation, Inc., *
18			* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19			***************************************************************************/
20
21			#include "solution.h"
22			#include "queens.h"
23			#include "solutioncontainer.h"
24
25
26	torben	4	Queens::Queens(GUIUpdate par, Solution sol, SolutionContainer *container, int set_size, bool set_debug) : QThread()
27	torben	1	{
28	torben	4	m_parent = par;
29			m_size = set_size;
30			m_solution = sol;
31			m_solution->setSize(m_size);
32			m_debug = set_debug;
33			m_solutions = container;
34	torben	1	}
35
36			bool Queens::solve()
37			{
38			return solve(0, false);
39			}
40
41			void Queens::findAll()
42			{
43			solve(0,true);
44			}
45
46			bool Queens::solve(int row, bool findAll)
47			{
48	torben	4	if (m_blocked == true)
49	torben	1	return false;
50	torben	4	for (int col=0; col<m_size; col++) {
51	torben	1	if (checkCols(row,col) == true &&
52			checkCross1(row,col) == true &&
53			checkCross2(row,col) == true) {
54
55
56	torben	4	m_solution->setMatrix(row,col,true);
57
58			if (row == (m_size-1) ) {
59	torben	1	if (!findAll)
60			return true;
61			else {
62	torben	4	m_solutions->addSolution( m_solution->copy() );
63			m_parent->foundSolution();
64	torben	1	}
65			}
66
67			if ( solve(row+1,findAll) )
68			return true;
69
70	torben	4	m_solution->setMatrix(row,col, false);
71	torben	1	}
72			}
73			return false;
74			}
75
76
77			bool Queens::checkRows(int row, int col)
78			{
79	torben	4	for (int c=0; c<m_size; c++) {
80			if (m_solution->getMatrix(row,c) == true)
81	torben	1	return false;
82			}
83
84			return true;
85			}
86
87			bool Queens::checkCols(int row, int col)
88			{
89	torben	4	for (int r=0; r<m_size; r++) {
90			if (m_solution->getMatrix(r,col) == true)
91	torben	1	return false;
92			}
93			return true;
94			}
95
96			bool Queens::checkCross1(int row, int col)
97			{
98			int r=row;
99			int c=col;
100	torben	4	for (int i=0; i<m_size; i++) {
101			if (m_solution->getMatrix(r,c) == true)
102	torben	1	return false;
103			r++;
104			c++;
105	torben	4	if ( r>(m_size-1) \|\| c>(m_size-1) )
106	torben	1	break;
107			}
108			r=row;
109			c=col;
110	torben	4	for (int i=0; i<m_size;i++) {
111			if (m_solution->getMatrix(r,c) == true)
112	torben	1	return false;
113			r--;
114			c--;
115			if (r<0 \|\| c<0)
116			break;
117			}
118			return true;
119			}
120
121			bool Queens::checkCross2(int row, int col)
122			{
123			int r=row;
124			int c=col;
125	torben	4	for (int i=0; i<m_size; i++) {
126			if (m_solution->getMatrix(r,c) == true)
127	torben	1	return false;
128			r++;
129			c--;
130	torben	4	if ( r>(m_size-1) \|\| c<0 )
131	torben	1	break;
132			}
133			r=row;
134			c=col;
135	torben	4	for (int i=0; i<m_size; i++) {
136			if (m_solution->getMatrix(r,c) == true)
137	torben	1	return false;
138			r--;
139			c++;
140	torben	4	if (r<0 \|\| c>(m_size-1))
141	torben	1	break;
142			}
143			return true;
144			}
145
146			void Queens::run()
147			{
148	torben	4	m_blocked = false;
149	torben	1	findAll();
150
151	torben	4	if (m_blocked == false)
152			m_parent->finishedSearch();
153	torben	1	}
154
155			void Queens::stop()
156			{
157	torben	4	m_blocked = true;
158	torben	1	}