java 使用回溯递归的 8 个皇后问题
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6337765/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
8 queens problem using backtracking recurison
提问by Nath
I've been working on the 8 queens problem but I got stuck. I don't want code. I would love guidance and directions in order to understand how to solve this problem myself using backtracking recursion.
我一直在研究 8 个皇后的问题，但我被卡住了。我不要代码。我希望得到指导和指导，以了解如何使用回溯递归自己解决这个问题。
The program should enumerate all solutions to the N-queens problem by drawing the location of the queens in ASCII like the two solutions here.
程序应该通过在 ASCII 中绘制皇后的位置来枚举 N-皇后问题的所有解决方案，就像这里的两个解决方案一样。
My pseudocode so far is:
到目前为止，我的伪代码是：
void queen(int n){
for( int i = 0; i < n; i++){
place queen[ i ] on row i;
for(int j = 0 ; j < n ; j++){
if( queen[ i ] is not in the same column as queen[0] through queen[ i - 1 ] &&
queen[ i ] is not on the same major diagonal with queen[0] through queen[ i -1 ] &&
queen[ i ] is not on the same minor diagonal with queen[0] through queen[ i -1 ] ) {
print 'Q ';
}
else{
print '* ';
}
System.out.println();
}
System.out.println();
}
}
There is no any backtracking recursion in my pseudocode because I don't know how to do it.
我的伪代码中没有任何回溯递归，因为我不知道该怎么做。
Any help is greatly appreciated.No code, please.
非常感谢任何帮助。请不要代码。
(Update in response to Nemo):
（更新响应 Nemo）：
solver(int n, Board b){
for(int i = 0; i < b.length; i++){
place queen in column i;
for(int j = 0; j < b.length; j++){
change b;
solver(n+1,changed b);
}
}
}
Is it correct?
这是正确的吗？
(Update 2):
（更新 2）：
solver8(board /* with queens presented in first 7 columns */){
// place a queen in the 8th column;
for(each possible placement of the queen in column 8
or in other words int i = 0; i < board.length; i++ ){
place the queen and print the board
}
}
solver7(board /* with queens presented in first 6 columns */){
// place a queen in the 7th column;
for(each possible placement of the queen in column 7
or in other words int i = 0; i < board.length; i++ ){
solver8(board with queens placed in first 7 columns);
}
}
solver6(board /* with queens presented in first 5 columns */ ){
// place a queen in the 6th column;
for(each possible placement of the queen in column 6
or in other words int i = 0; i < board.length; i++ ){
solver7(board with queens presented in first 6 columns);
}
}
and so on until
依此类推直到
solver1(1, empty board){
for(int i = 0; i < board.length; i++){
place queen in row[i] of column 1;
solver2(board with queen in row[i] of column 1);
}
}
Update 3 (Edited):
更新 3（已编辑）：
private int numberOfQueens = 8;
solver(int n, Board b){
for(int r = 0; r < b.length; r++){
place queen in row[r] of column[n];
if(n == numberOfQueens){
print the board;
return;
}
else{
solver(n+1, board with queen in row[r] of column[n]);
}
}
}
}
采纳答案by Aasmund Eldhuset
The purpose of using recursion for these kinds of problems is that they allow you to think in terms of "I have now placed kqueens; how can I place the remaining ones if the total number of queens is n?" So the recursive function should take twoparameters: the target number of queens, and the number of queens placed so far. When writing the function, your goal is first and foremost to try out different ways of placing the kth queen. But when you have selected a possible placement and found it to be valid, you need to place the remaining n - k - 1queens. How can we do this? The answer: recursion! Call the function (from within itself) with the parameter k - 1to indicate that you want to place the remaining k - 1queens. Whenever you exhaust all possibilities (or find that none are possible), simply return from the function - you will then get back to the previous function call (e.g. the one that tries to place the kth queen).
对这类问题使用递归的目的是让你思考“我现在已经放置了k 个皇后；如果皇后总数为n ，我如何放置剩余的皇后？” 所以递归函数应该有两个参数：目标皇后数，以及到目前为止放置的皇后数。在编写函数时，您的首要目标是尝试放置第k个皇后的不同方式。但是当您选择了一个可能的放置并发现它有效时，您需要放置剩余的n - k - 1 个皇后。我们应该怎么做？答案是：递归！使用参数k - 1调用函数（从自身内部）表示您要放置剩余的k - 1 个皇后。每当您用尽所有可能性（或发现没有可能）时，只需从函数返回 - 然后您将返回到前一个函数调用（例如，试图放置第k个皇后的那个）。
Edit: You will also need to create a two-dimensional array to represent the current state of your board; this array must either be sent as an additional parameter to the recursive function, or be kept as a field of the class that contains the method.
编辑：您还需要创建一个二维数组来表示您的电路板的当前状态；此数组必须作为附加参数发送到递归函数，或者作为包含该方法的类的字段保留。
As for the backtracking, that is accomplished simply by making sure that the function that gets called with k + 1removes the k + 1th queen from the board before returning; this essentially says "We've now (unsuccessfully) tried all ways of placing the remainder of the queens - based on the positions of the k queens that have already been placed. None of them succeeded, so please adjust the positions of the first kqueens (which will be done by the function that was called with k, and the function which called that function, and so on) and try again."
至于回溯，只需确保使用k + 1调用的函数在返回之前从棋盘上删除第k + 1个皇后即可完成；这基本上是说“我们现在（失败）尝试了所有放置剩余皇后的方法 -基于已经放置的 k 个皇后的位置。他们都没有成功，所以请调整第一个k的位置皇后（这将由使用k调用的函数完成，以及调用该函数的函数，依此类推）并重试。”
回答by Nemo
Generally speaking, a recursive backtracking search looks something like this:
一般来说，递归回溯搜索看起来像这样：
// On input, s represents a valid State up to depth d-1
sub do_it(int d, State s)
if (d == MAX_DEPTH+1)
// State s represents an answer! Print it and return.
else
(augment s to make it valid for depth d)
for each augmented_s
do_it(d+1, augmented_s)
end for
end if
end sub
// top level
do_it(0, empty_state)
Note that for a given svalid up to depth d-1, there could be multiple ways to augment it into a state valid up to depth d. The idea is to call yourself with each of them.
请注意，对于给定的s有效达深度d-1，可能有多种方法将其扩充为有效达深度的状态d。这个想法是用他们每个人来称呼自己。
For this problem, the "state" is the board. The depth "d-1" might mean the first d-1 columns are populated. The legal augmented states would be those with a queen in column d such that she cannot be captured.
对于这个问题，“状态”就是董事会。深度“d-1”可能意味着前 d-1 列已填充。合法的增强状态将是那些在 d 列中有一个女王的状态，这样她就不能被捕获。
[update]
[更新]
Here is another way to look at it. Work the problem backwards.
这是另一种看待它的方式。向后解决问题。
Suppose I ask you to write a simple function called solver8(). This function takes as input a board with queens already present in the first 7 columns. All it has to do is take that board, find all ways to add a queen to the 8th column, and print out those boards. Do you think you could write this function? Good; write it.
假设我要求您编写一个名为solver8(). 此函数将前 7 列中已经存在皇后的棋盘作为输入。它所要做的就是拿那个板子，想办法在第 8 列中添加一个皇后，然后打印出这些板子。你认为你能写出这个函数吗？好的; 写下来。
Now suppose I ask you to write an almost-as-simple function called solver7(). This function takes as input a board with queens already present in the first 6 columns. All it has to do is take that board, find all ways to add a queen to the 7th column, and pass each of those boards as an argument to solver8(). Could you write this function?
现在假设我要求您编写一个几乎同样简单的函数，称为solver7(). 此函数将前 6 列中已经存在皇后的棋盘作为输入。它所要做的就是拿那个板子，找到所有方法将一个皇后添加到第 7 列，并将这些板子中的每一个作为参数传递给solver8()。你会写这个函数吗？
Now suppose I ask you to write another function called solver6(). As input, it takes a board with queens present in the first 5 columns. All it has to do is take that board, find all ways to add a queen to the 6th column, and then pass each of those boards to solver7().
现在假设我要求你编写另一个名为solver6(). 作为输入，它需要一个在前 5 列中出现皇后的棋盘。它所要做的就是拿下那块棋盘，找到所有方法将皇后添加到第 6 列，然后将每个棋盘传递给solver7()。
And so on, until we get to solver1(). This one takes an empty board, finds all ways to place a queen in the first column, and passes each of those boards to solver2().
依此类推，直到我们到达solver1()。这个人拿一个空板，找到所有方法在第一列放置一个皇后，然后将这些板中的每一个传递给solver2()。
You have just written 8 functions that together solve the 8 queens problem. If this does not make sense, write it out as 8 functions and stare at it until you do.
您刚刚编写了 8 个共同解决 8 个皇后问题的函数。如果这没有意义，把它写成 8 个函数，然后盯着它看，直到你知道为止。
Now, if you look at all of these functions, you will find they are pretty similar. So instead of writing solver8, solver7, solver6, ..., solver1, you write a single function:
现在，如果您查看所有这些功能，您会发现它们非常相似。因此，不要编写solver8、solver7、solver6、...、solver1，而是编写一个函数：
solver(int n, Board b)
...such that solver(1, b) is the same as solver1(b), solver(2, b) is the same as solver2(b), ..., and solver(8, b) is the same as solver8(b). And instead of solver2(...) calling solver3(...), for instance, you will just have solver(2, ...) calling solver(3, ...). One function instead of 8, but doing the same thing.
...使得solver(1, b) 与solver1(b) 相同，solver(2, b) 与solver2(b) 相同，...，solver(8, b) 与solver(8, b) 相同求解器 8(b)。例如，您将只需要solver(2, ...) 调用solver(3, ...) 而不是solver2(...) 调用solver3(...)。一个函数而不是 8 个，但做同样的事情。
You will pretty quickly discover that the final code is cleaner if you start with a solver9()that just takes a fully populated board and prints it out, and have solver8()call that.
你很快就会发现最终的代码更简洁，如果你从一个solver9()只需要一个完全填充的板子并将它打印出来，然后solver8()调用它。
回答by sgokhales
See this nice animation here on 8 queen's problem using recursion.
在这里看到这个漂亮的动画 8 queen's problem using recursion.
Also, check out : 8 queens problem - Java/C++.
另外，请查看：8 queens problem - Java/C++。
Check out the logicexplained here.
查看logic这里的解释。
回答by sgokhales
Put the first queen in [0][0], then find a spot for the second. lets say you found one go to the next, so on and so forth. Assumingly your 5th queen cant be placed anywhere in the 5th column or row (whichever you follow). Go back to the 4th and find another spot to that. Than go to the 5th again.Lets say you are in the 8th one and there are no spots available. Go to 7th and still nothing back there. You will kep on going back until the 2nd and find a spot to the 2nd again, and go to the 3rd. Does it make sense...
将第一个皇后放在 [0][0] 中，然后为第二个找到一个位置。假设您找到了下一个，依此类推。假设您的第 5 个皇后不能放置在第 5 列或第 5 行（无论您遵循哪个）中的任何位置。回到第 4 处，找到另一个位置。然后再去第 5 个。假设您在第 8 个并且没有可用的位置。转到第 7 层，那里仍然什么都没有。一直往回走到2号，再找个去2号的地方，再去3号。是否有意义...
回答by jatin Goyal
Hope this Solution helps
希望这个解决方案有帮助
Main Points are
要点是
1.Recursionsimple to under
1.递归简单到下
2.IsValid position2.1 cross Queen found in same column like
2. IsValid position2.1 cross Queen 在同一列中找到，如
*
*
2.2 cross Queen found diagonally like
2.2 交叉皇后发现对角线喜欢
*--
---
--*
or
或者
--*
---
*--
Code :
代码 ：
package queenproblem;
public class QueenProblem
{
int numQueens[];// hold columns postion
int numQueen;
QueenProblem(int noOfQueens) {
this.numQueen = noOfQueens;
numQueens = new int[noOfQueens];
}
public static void main(String[] args) {
new QueenProblem(8).solveProblem();
}
public void solveProblem() {
arrange(0);
}
// recursive Function
void arrange(int rowIndex) {
// 1.to check valid Postion of not.
// 2. to check all Queens postion is found or not.
for (int i = 0; i < numQueen; i++)
{
if (isValid(rowIndex, i))
{
numQueens[rowIndex] = i;// save col index
if (rowIndex == numQueen - 1)
{
printsBoard();
} else
{
arrange(rowIndex + 1);
}
}
}
}
private void printsBoard() {
for (int i = 0; i < numQueen; i++)
{
for (int j = 0; j < numQueen; j++)
{
if (numQueens[i] == j)
{
System.out.print(" * ");
} else System.out.print(" - ");
}
System.out.println();
}
System.out.println();
}
boolean isValid(int rowIndex, int colIndex) {
for (int i = 0; i < rowIndex; i++)
{
// on the save columns
if (numQueens[i] == colIndex) return false;
if ((i - rowIndex) == (numQueens[i] - colIndex)) return false;
if ((i - rowIndex) == (colIndex - numQueens[i])) return false;
}
return true;
}
}
92Possible Solutions to 8 Queens Problem:
8皇后问题的92种可能解决方案：
* - - - - - - -
- - - - * - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
- - - - - - * -
- - - * - - - -
- * - - - - - -
- - - - * - - -
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
* - - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- * - - - - - -
- - - - - * - -
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - - - *
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - * - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- - - - * - - -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
* - - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - * - - -
- - - - - - - *
- - - * - - - -
* - - - - - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - - - - - *
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
* - - - - - - -
- - - - - - - *
- - - * - - - -
- - * - - - - -
- - - - - * - -
- - - * - - - -
* - - - - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - * - - - - -
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
* - - - - - - -
- - - * - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
* - - - - - - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - - - - - *
- - - - * - - -
* - - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - * - - - - -
- - - - - - - *
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - - - * -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - - - - *
* - - - - - - -
- - - - * - - -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- - - - * - - -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
* - - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
* - - - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
- - * - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - - - - - - *
- - - - * - - -
- * - - - - - -
- - - - - * - -
- - * - - - - -
- - - * - - - -
- - - - - - * -
- - * - - - - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
* - - - - - - -
- - - - - * - -
- - - * - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - * - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - - - *
* - - - - - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
- - - * - - - -
- - - - - - - *
* - - - - - - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - - - * - - -
* - - - - - - -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - * - - -
* - - - - - - -
- - - - - - - *
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - * - - -
* - - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - - * -
- - * - - - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - - - * - - -
- * - - - - - -
- - - - - * - -
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - - - *
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
* - - - - - - -
- - - * - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- - - - * - - -
- - * - - - - -
- - - - - - - *
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- - - - - - - *
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - - - - - *
- - - * - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - - - - - *
- - - * - - - -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
- - - * - - - -
* - - - - - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
- - - - - * - -
* - - - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
- - * - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - - *
- - - * - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - * - - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - - - - - *
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - - - - - *
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - - * -
- - - - - * - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - * - - -
- - - - - - - *
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- - - - - - - *
* - - - - - - -
- - - - * - - -
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - - - - - *
- - - - * - - -
* - - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- - - - - - * -
- - - * - - - -
* - - - - - - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
- - - - - * - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - - - *
- - - - * - - -
- - * - - - - -
- - - - - * - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
- - * - - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - - * -
- - * - - - - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
* - - - - - - -
- - - - - * - -
- - - * - - - -
- - - - - - * -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - - *
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - - - - * -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
- - - - - - - *
- - - * - - - -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
