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, SolutionContainer *sol, int set_size, bool set_debug) : QThread(), solution(set_size)
{
        parent = par;
        size = set_size;
        solution.setSize(size);
        debug = set_debug;
        solutions = sol;
}

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

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

bool Queens::solve(int row, bool findAll)
{
        if (blocked == true)
                return false;
        for (int col=0; col<size; col++) {
                if (checkCols(row,col) == true && 
                                checkCross1(row,col) == true && 
                                checkCross2(row,col) == true) {

                        solution.matrix[row][col] = true;
                        
                        if (row == (size-1) ) {
                                if (!findAll)
                                        return true;
                                else {
                                        solutions->addSolution( solution );
                                        parent->foundSolution();
                                }
                        }

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

                        solution.matrix[row][col] = false;
                }
        }
        return false;
}


bool Queens::checkRows(int row, int col)
{
        for (int c=0; c<size; c++) {
                if (solution.matrix[row][c] == true)
                        return false;
        }
                
        return true;
}

bool Queens::checkCols(int row, int col)
{
        for (int r=0; r<size; r++) {
                if (solution.matrix[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<size; i++) {
                if (solution.matrix[r][c] == true)
                        return false;
                r++;
                c++;
                if ( r>(size-1) || c>(size-1) )
                        break;          
        }
        r=row;
        c=col;
        for (int i=0; i<size;i++) {
                if (solution.matrix[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<size; i++) {
                if (solution.matrix[r][c] == true)
                        return false;
                r++;
                c--;
                if ( r>(size-1) || c<0 )
                        break;
        }
        r=row;
        c=col;
        for (int i=0; i<size; i++) {
                if (solution.matrix[r][c] == true)
                        return false;
                r--;
                c++;
                if (r<0 || c>(size-1))
                        break;
        }
        return true;
}

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

void Queens::stop()
{
        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			Queens::Queens(GUIUpdate par, SolutionContainer sol, int set_size, bool set_debug) : QThread(), solution(set_size)
27			{
28			parent = par;
29			size = set_size;
30			solution.setSize(size);
31			debug = set_debug;
32			solutions = sol;
33			}
34
35			bool Queens::solve()
36			{
37			return solve(0, false);
38			}
39
40			void Queens::findAll()
41			{
42			solve(0,true);
43			}
44
45			bool Queens::solve(int row, bool findAll)
46			{
47			if (blocked == true)
48			return false;
49			for (int col=0; col<size; col++) {
50			if (checkCols(row,col) == true &&
51			checkCross1(row,col) == true &&
52			checkCross2(row,col) == true) {
53
54			solution.matrix[row][col] = true;
55
56			if (row == (size-1) ) {
57			if (!findAll)
58			return true;
59			else {
60			solutions->addSolution( solution );
61			parent->foundSolution();
62			}
63			}
64
65			if ( solve(row+1,findAll) )
66			return true;
67
68			solution.matrix[row][col] = false;
69			}
70			}
71			return false;
72			}
73
74
75			bool Queens::checkRows(int row, int col)
76			{
77			for (int c=0; c<size; c++) {
78			if (solution.matrix[row][c] == true)
79			return false;
80			}
81
82			return true;
83			}
84
85			bool Queens::checkCols(int row, int col)
86			{
87			for (int r=0; r<size; r++) {
88			if (solution.matrix[r][col] == true)
89			return false;
90			}
91			return true;
92			}
93
94			bool Queens::checkCross1(int row, int col)
95			{
96			int r=row;
97			int c=col;
98			for (int i=0; i<size; i++) {
99			if (solution.matrix[r][c] == true)
100			return false;
101			r++;
102			c++;
103			if ( r>(size-1) \|\| c>(size-1) )
104			break;
105			}
106			r=row;
107			c=col;
108			for (int i=0; i<size;i++) {
109			if (solution.matrix[r][c] == true)
110			return false;
111			r--;
112			c--;
113			if (r<0 \|\| c<0)
114			break;
115			}
116			return true;
117			}
118
119			bool Queens::checkCross2(int row, int col)
120			{
121			int r=row;
122			int c=col;
123			for (int i=0; i<size; i++) {
124			if (solution.matrix[r][c] == true)
125			return false;
126			r++;
127			c--;
128			if ( r>(size-1) \|\| c<0 )
129			break;
130			}
131			r=row;
132			c=col;
133			for (int i=0; i<size; i++) {
134			if (solution.matrix[r][c] == true)
135			return false;
136			r--;
137			c++;
138			if (r<0 \|\| c>(size-1))
139			break;
140			}
141			return true;
142			}
143
144			void Queens::run()
145			{
146			blocked = false;
147			findAll();
148
149			if (blocked == false)
150			parent->finishedSearch();
151			}
152
153			void Queens::stop()
154			{
155			blocked = true;
156			}