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	5
52	torben	1	if (checkCols(row,col) == true &&
53			checkCross1(row,col) == true &&
54	torben	5	checkCross2(row,col) == true)
55			{
56	torben	1
57
58	torben	4	m_solution->setMatrix(row,col,true);
59
60	torben	5	if (row == (m_size-1) )
61			{
62	torben	1	if (!findAll)
63			return true;
64	torben	5	else
65			{
66	torben	4	m_solutions->addSolution( m_solution->copy() );
67			m_parent->foundSolution();
68	torben	1	}
69			}
70
71			if ( solve(row+1,findAll) )
72			return true;
73
74	torben	4	m_solution->setMatrix(row,col, false);
75	torben	1	}
76			}
77			return false;
78			}
79
80
81			bool Queens::checkRows(int row, int col)
82			{
83	torben	4	for (int c=0; c<m_size; c++) {
84			if (m_solution->getMatrix(row,c) == true)
85	torben	1	return false;
86			}
87
88			return true;
89			}
90
91			bool Queens::checkCols(int row, int col)
92			{
93	torben	4	for (int r=0; r<m_size; r++) {
94			if (m_solution->getMatrix(r,col) == true)
95	torben	1	return false;
96			}
97			return true;
98			}
99
100			bool Queens::checkCross1(int row, int col)
101			{
102			int r=row;
103			int c=col;
104	torben	4	for (int i=0; i<m_size; i++) {
105			if (m_solution->getMatrix(r,c) == true)
106	torben	1	return false;
107			r++;
108			c++;
109	torben	4	if ( r>(m_size-1) \|\| c>(m_size-1) )
110	torben	1	break;
111			}
112			r=row;
113			c=col;
114	torben	4	for (int i=0; i<m_size;i++) {
115			if (m_solution->getMatrix(r,c) == true)
116	torben	1	return false;
117			r--;
118			c--;
119			if (r<0 \|\| c<0)
120			break;
121			}
122			return true;
123			}
124
125			bool Queens::checkCross2(int row, int col)
126			{
127			int r=row;
128			int c=col;
129	torben	4	for (int i=0; i<m_size; i++) {
130			if (m_solution->getMatrix(r,c) == true)
131	torben	1	return false;
132			r++;
133			c--;
134	torben	4	if ( r>(m_size-1) \|\| c<0 )
135	torben	1	break;
136			}
137			r=row;
138			c=col;
139	torben	4	for (int i=0; i<m_size; i++) {
140			if (m_solution->getMatrix(r,c) == true)
141	torben	1	return false;
142			r--;
143			c++;
144	torben	4	if (r<0 \|\| c>(m_size-1))
145	torben	1	break;
146			}
147			return true;
148			}
149
150			void Queens::run()
151			{
152	torben	4	m_blocked = false;
153	torben	1	findAll();
154
155	torben	4	if (m_blocked == false)
156			m_parent->finishedSearch();
157	torben	1	}
158
159			void Queens::stop()
160			{
161	torben	4	m_blocked = true;
162	torben	1	}