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	/***************************************************************************
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	Queens::Queens(GUIUpdate par, Solution sol, SolutionContainer *container, int set_size, bool set_debug) : QThread()
27	{
28	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	}
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	if (m_blocked == true)
49	return false;
50	for (int col=0; col<m_size; col++) {
51
52	if (checkCols(row,col) == true &&
53	checkCross1(row,col) == true &&
54	checkCross2(row,col) == true)
55	{
56
57
58	m_solution->setMatrix(row,col,true);
59
60	if (row == (m_size-1) )
61	{
62	if (!findAll)
63	return true;
64	else
65	{
66	m_solutions->addSolution( m_solution->copy() );
67	m_parent->foundSolution();
68	}
69	}
70
71	if ( solve(row+1,findAll) )
72	return true;
73
74	m_solution->setMatrix(row,col, false);
75	}
76	}
77	return false;
78	}
79
80
81	bool Queens::checkRows(int row, int col)
82	{
83	for (int c=0; c<m_size; c++) {
84	if (m_solution->getMatrix(row,c) == true)
85	return false;
86	}
87
88	return true;
89	}
90
91	bool Queens::checkCols(int row, int col)
92	{
93	for (int r=0; r<m_size; r++) {
94	if (m_solution->getMatrix(r,col) == true)
95	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	for (int i=0; i<m_size; i++) {
105	if (m_solution->getMatrix(r,c) == true)
106	return false;
107	r++;
108	c++;
109	if ( r>(m_size-1) \|\| c>(m_size-1) )
110	break;
111	}
112	r=row;
113	c=col;
114	for (int i=0; i<m_size;i++) {
115	if (m_solution->getMatrix(r,c) == true)
116	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	for (int i=0; i<m_size; i++) {
130	if (m_solution->getMatrix(r,c) == true)
131	return false;
132	r++;
133	c--;
134	if ( r>(m_size-1) \|\| c<0 )
135	break;
136	}
137	r=row;
138	c=col;
139	for (int i=0; i<m_size; i++) {
140	if (m_solution->getMatrix(r,c) == true)
141	return false;
142	r--;
143	c++;
144	if (r<0 \|\| c>(m_size-1))
145	break;
146	}
147	return true;
148	}
149
150	void Queens::run()
151	{
152	m_blocked = false;
153	findAll();
154
155	if (m_blocked == false)
156	m_parent->finishedSearch();
157	}
158
159	void Queens::stop()
160	{
161	m_blocked = true;
162	}