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