-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNQueens.html
More file actions
321 lines (311 loc) · 10.3 KB
/
NQueens.html
File metadata and controls
321 lines (311 loc) · 10.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
<!DOCTYPE HTML>
<!--
Massively by HTML5 UP
html5up.net | @ajlkn
Free for personal and commercial use under the CCA 3.0 license (html5up.net/license)
-->
<html>
<head>
<title>Joseph Ruff - N Queens</title>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no" />
<link rel="stylesheet" href="assets/css/main.css" />
<noscript><link rel="stylesheet" href="assets/css/noscript.css" /></noscript>
<script
src="https://code.jquery.com/jquery-3.5.1.js"
integrity="sha256-QWo7LDvxbWT2tbbQ97B53yJnYU3WhH/C8ycbRAkjPDc="
crossorigin="anonymous">
</script>
<script>
$(document).ready(function(){
$("#img1").click(function(){
$("#img1").parent().toggleClass("col-4");
});
$("#img2").click(function(){
$("#img2").parent().toggleClass("col-4");
});
$("#img3").click(function(){
$("#img3").parent().toggleClass("col-4");
});
$("#img4").click(function(){
$("#img4").parent().toggleClass("col-6");
});
$("#img5").click(function(){
$("#img5").parent().toggleClass("col-6");
});
});
</script>
<style>
ul.nested {
margin-bottom:0;
}
@media only screen and (max-width: 980px) {
ul.nested {
display: none;
}
}
</style>
</head>
<body class="is-preload">
<!-- Wrapper -->
<div id="wrapper">
<!-- Header -->
<header id="header">
<a href="https://josephruff.github.io" class="logo">Joseph Ruff</a>
</header>
<!-- Nav -->
<nav id="nav">
<ul class="links">
<li><a href="https://josephruff.github.io">Portfolio</a></li>
<li><a href="CurriculumVitae.html">Curriculum Vitae</a></li>
<li class="active"><a href="NQueens.html">N Queens</a></li>
</ul>
<ul class="icons">
<li><a href="Curriculum Vitae Joseph David Ruff.pdf" class="icon solid fa-download"><span class="label">Download CV</span></a></li>
<li><a href="https://www.linkedin.com/in/joseph-ruff-a99062393" class="icon brands fa-linkedin"><span class="label">Instagram</span></a></li>
<li><a href="https://github.com/JosephRuff" class="icon brands fa-github"><span class="label">GitHub</span></a></li>
</ul>
</nav>
<!-- Main -->
<div id="main">
<!-- Post -->
<section class="post">
<header class="major">
<h1>N Queens Problem</h1>
<p>Program written in Python 2 for solving the N Queens problem using a brute force aproach</p>
</header>
<div class="image main">
<img src="images/michal-parzuchowski-6D1lESi9ssU-unsplash.jpg" alt="" />
</div>
<hr>
<h2>
Contents
</h2>
<ul class="alt">
<li>
<a href="#introduction">Intro</a>
<ul class="alt nested">
<li><a href="#8queens">The 8 Queens Problem</a></li>
<li><a href="#nqueens">The n Queens Problem</a></li>
</ul>
</li>
<li>
<a href="#solution">The Solution</a>
</li>
<li>
<a href="#cases">Test cases</a>
<ul class="alt nested">
<li><a href="#lower">Lower numbers</a></li>
<li><a href="#4queens">4 Queens</a></li>
<li><a href="#5queens">5 Queens</a></li>
<li><a href="#higher">6 and above</a></li>
</ul>
</li>
<li>
<a href="#improvements">Possible Improvements</a>
<ul class="alt nested">
<li><a href="#child">Change child generation method</a></li>
<li><a href="#state">Consider board state storage method</a></li>
<li><a href="#language">Different Programming Language</a></li>
</ul>
</li>
<li>
<a href="#links">Source code</a>
</li>
</ul>
<hr>
<a id="introduction"></a>
<h2>
Intro
</h2>
<a id="8queens"></a>
<h3>
The 8 Queens Problem
</h3>
<p>
The eight queens puzzle is the problem of placing eight chess queens on
an 8×8 chessboard so that no two queens threaten each other; thus, a
solution requires that no two queens share the same row, column, or
diagonal.
</p>
<a id="nqueens"></a>
<h3>
The n Queens Problem
</h3>
<p>
The eight queens puzzle is an example of the more general n queens problem of placing n queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n = 2 and n = 3.
</p>
<hr>
<a id="solution"></a>
<h2>
The Solution
</h2>
<p>
My solution takes an input n, and then proceeds to use a brute force
solution to find every possible board set up. When it finds a valid
solution it prints it, and then proceeds to continue to attempt to find
all other possible solutions.
</p>
<hr>
<a id="cases"></a>
<h2>
Test cases
</h2>
<a id="lower"></a>
<header>
<h3>
Lower numbers
</h3>
<p>
Case: 0 < n < 4
</p>
</header>
<p>
For inputs 1 through 3, there are no valid solutions to the N Queens
problem. This program produces the following outputs when n is between 1
and 3.
</p>
<div class="box alt">
<div class="row gtr-50 gtr-uniform">
<div class="col-4">
<a id="img1" class="image fit">
<img src="images/NQueens1.png" alt="" />
</a>
</div>
<div class="col-4">
<a id="img2" class="image fit">
<img src="images/NQueens2.png" alt="" />
</a>
</div>
<div class="col-4">
<a id="img3" class="image fit">
<img src="images/NQueens3.png" alt="" />
</a>
</div>
</div>
</div>
<a id="4queens"></a>
<header>
<h3>
4 Queens
</h3>
<p>
Case: n = 4
</p>
</header>
<p>
For an input of 4, there are only 2 solutions. This program produces the
following output when n is equal to 4.
</p>
<span class="image fit">
<img style="max-width: 643px;" src="images/NQueens4.png" alt="" />
</span>
<a id="5queens"></a>
<header>
<h3>
5 Queens
</h3>
<p>
Case: n = 5
</p>
</header>
<p>
An input of 5 has 10 possible solutions. This program produces the
following output when n is equal to 5.
</p>
<div class="box alt">
<div class="row gtr-50 gtr-uniform">
<div class="col-6">
<a id="img4" id="img-1" class="image fit">
<img src="images/NQueens5.png" alt="" />
</a>
</div>
<div class="col-6">
<a id="img5" class="image fit">
<img src="images/NQueens6.png" alt="" />
</a>
</div>
</div>
</div>
<a id="higher"></a>
<header>
<h3>
6 and above
</h3>
<p>
Case: n > 5
</p>
</header>
<p>
For all input greater than or equal to 6, the program runs very slowly
due to the time complexity of the algorithm used. It will continue to
run until interrupted, outputting any valid solution that it finds.
</p>
<span class="image fit">
<img style="max-width: 643px;" src="images/NQueens7.png" alt="" />
</span>
<hr>
<a id="improvements"></a>
<h2>
Possible Improvements
</h2>
<a id="child"></a>
<h3>
Change child generation method
</h3>
<p>
At the moment every time the program generates a board state, it doesn't
consider the potential rotations of that board state. The program could
be improved by considering rotations of a given board state, when
generating it's child state.
</p>
<a id="state"></a>
<h3>
Consider board state storage method
</h3>
<p>
At the moment a given board state is stored as a list of n numbers,
between 0 and n - 1, where each index in the list represents a column of
the board, and the value at that index indicates the position of the
queen in that column.
</p>
<p>
This method works as we do not need to consider the possibility of 2
queens in the same column.
</p>
<p>
We can improve this further, by requiring that every number in the list be
unique. This works, because 2 of the same number in the array indicates 2
queens being in the same row, which is not allowed. This will eliminate a
large amount incorrect board states, from ever being considered.
</p>
<h3>
Different Programming Language
</h3>
<a id="language"></a>
<p>
Using a compiled programming language rather than an interpreted one like
Python, could improve the speed greatly.
</p>
<hr>
<a id="links"></a>
<p style="text-align:center">
<a href="https://github.com/JosephRuff/N-Queens" class="button icon brands fa-github">Source Code</a>
</p>
</section>
</div>
<!-- Copyright -->
<div id="copyright">
<ul><li>© Joseph Ruff</li><li>Design: <a href="https://html5up.net">HTML5 UP</a></li></ul>
</div>
</div>
<!-- Scripts -->
<script src="assets/js/jquery.min.js"></script>
<script src="assets/js/jquery.scrollex.min.js"></script>
<script src="assets/js/jquery.scrolly.min.js"></script>
<script src="assets/js/browser.min.js"></script>
<script src="assets/js/breakpoints.min.js"></script>
<script src="assets/js/util.js"></script>
<script src="assets/js/main.js"></script>
</body>
</html>