Know a bit about the Queen piece in a game of Chess
A solution for the “8 queens” problem
Numberphile video:
In this exercise, you will solve the classic 8-queens problem: place 8 queens on an 8-by-8 chess board so that no two queens are in the same row, column, or diagonal.
There are 8! = 40,320 ways in which no two queens are placed in the same row or column. Any permutation p[] of the integers 0 to 7 gives such a placement: put queen i in row i, column p[i]. Your program Queens_YI.java should take an integer command-line argument n and enumerate all solutions to the n-queens problem by drawing the location of the queens in ASCII like the two solutions below.
Hint: to determine whether setting
q[n] = i conflicts with q[0] through q[n-1]
if q[i] equals q[n]: two queens are placed in the same column
if q[i] – q[n] equals n – i: two queens are on same major diagonal
if q[n] – q[i] equals n – i: two queens are on same minor diagonal
Know a bit about the Queen piece in a game of Chess
A solution for the “8 queens” problem
Numberphile video:
You can have access to all the Lynda.com resources with your own Princeton Public Library card.
The problem: Design and implement a recursive program that solves the Non- Attacking Queens problem. That is, write a program to determine how eight queens can be positioned on an eight-by-eight chessboard so that none of them are in the same row, column, or diagonal as any other queen. There are no other chess pieces on the board.
Assignment:
If you already implemented the solution to the problem, answer the following questions:
How does your implementation compare to the one below?
Is your implementation better than this one?
What is the time complexity (for now we can say the big-O notation)?
If you have not implemented yet, do the following:
Trace the code for 4 queens. It only has 2 solutions but 1 unique.
Explain how the implementation works
What is the time complexity (for now we can say the big-O notation)?
//********************************************************************
//
// A recursive program that solves the Non-attacking Queens problem.
//********************************************************************
public class NonAttackingQueens {
int[] queens; // Queen i is always placed in row i. The
// column is variable.
// queens[i] represents the column of the ith row
// where the ith queen is
final int NUM_QUEENS = 8;
public NonAttackingQueens()
{
queens = new int[NUM_QUEENS];
}
//-----------------------------------------------------------------
// Returns true if a queen queenNumber can be placed in column
//-----------------------------------------------------------------
boolean canPlace(int queenNumber, int column)
{
for (int row = 0; row < queenNumber; row++) // check all rows above queenNumber row
{
if (queens[row] == column) // in the same column
return false;
if (Math.abs(queens[row] - column) == Math.abs(row - queenNumber)) // same diagonal
return false;
}
return true;
}
//-----------------------------------------------------------------
// Starting with the row represented by queenNumber, find all correct
// placements in the row and below the row.
//-----------------------------------------------------------------
public void solve(int queenNumber)
{
for (int column = 0; column < NUM_QUEENS; column++) // iterate through all columns
{
if (canPlace(queenNumber, column)) // queen can be placed in current column
{
queens[queenNumber] = column; // place queen in current column
if (queenNumber + 1 >= NUM_QUEENS) // solved
printSolution();
else // keep looking
solve(queenNumber + 1);
}
}
}
//-----------------------------------------------------------------
// Computes and displays all solutions to the problem
//-----------------------------------------------------------------
public void showSolutions()
{
solve(0); // start with the first row
}
//-----------------------------------------------------------------
// Prints a grid showing the position of the queens on the chessboard.
// Queen = X
// Empty space = O
//-----------------------------------------------------------------
private void printSolution()
{
int column;
for (int row=0; row<num_queens; row++)="" {="" for="" (column="0;" column<num_queens;="" column++)="" if="" (queens[row]="=" column)="" system.out.print("="" x");="" else="" 0");="" system.out.print("\n");="" }="" system.out.println("\n-----------------------");="" public="" static="" void="" main="" (string="" args[])="" new="" nonattackingqueens().showsolutions();="" <="" pre=""></num_queens;>
We introduce in this section a type of binary search tree where costs are guaranteed to be logarithmic. Our trees have near-perfect balance, where the height is guaranteed to be no larger than 2 lg N.
Proposition.
Search and insert operations in a 2-3 tree with N keys are guaranteed to visit at most lg N nodes.
However, we are only part of the way to an implementation. Although it would be possible to write code that performs transformations on distinct data types representing 2- and 3-nodes, most of the tasks that we have described are inconvenient to implement in this direct representation.
Introductions and the Enigma machine: 8:00 -> 16:35
Christopher: 46:24
Christopher’s ineffectiveness: 51:06
The game and frustration: 1:06:43
C-I-L-L-Y: 1:11:30
Glossary. Here are some definitions that we use.
1. A self-loop is an edge that connects a vertex to itself.
2. Two edges are parallel if they connect the same pair of vertices.
3. When an edge connects two vertices, we say that the vertices are adjacent to one another and that the edge is incident on both vertices.
4. The degree of a vertex is the number of edges incident on it.
5. A subgraph is a subset of a graph’s edges (and associated vertices) that constitutes a graph.
6. A path in a graph is a sequence of vertices connected by edges. A simple path is one with no repeated vertices.
7. A cycle is a path (with at least one edge) whose first and last vertices are the same. A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
8. The length of a path or a cycle is its number of edges.
9. We say that one vertex is connected to another if there exists a path that contains both of them.
10. A graph is connected if there is a path from every vertex to every other vertex.
11. A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.
12. An acyclic graph is a graph with no cycles.
13. A tree is an acyclic connected graph.
14. A forest is a disjoint set of trees.
15. A spanning tree of a connected graph is a subgraph that contains all of that graph’s vertices and is a single tree.
16. A spanning forest of a graph is the union of the spanning trees of its connected components.
17. A bipartite graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.
Robert Sedgewick and Kevin Wayne.
Classwork:
Video: Watch 14.1 and 14.2 in classroomsalon.com and answer the questions.
PU Book Site PU Lectures
Visit Classroom Salon for videos 1.1, 1.2 and 1.3 and related questions.
Visit edmodo.com to answer the following questions:
1. What are the three assumptions so “is connected to” is an equivalence relation?
2. What are the differences and similarities between the Quick Find and Quick Union operations?
