1
Course Name:
Student Name:
Student Number:
Exercise No:
2
Question 1:
The 8-queens problem is a problem of placing n queens on an n× n chessboard, where solutions.
The question of the problem is how to place eight queens on a chess board in a way that they are
not able to attack each other. There should not be any 2 queens in the same horizontal, vertical or
diagonal line. The goal is not just to find one possible solution, but all of them. An advanced way
of looking at the problem is by trying to solve the problem for any number of queens. The
number of queens can be defined in the source code and the amount of horizontal and vertical
lines of the board are defied according to number of queens.
The idea is to place queens one by one in different columns, starting from the leftmost column.
When we place a queen in a column, there should not be two queens in same rows or columns or
diagonals. If we find a row for which there is no repeating queue, we mark this row and column
as part of the solution. If we do not find such a row due to attack, then we backtrack.
INTRODUCTION
N - Queens problem is to place n - queens in such a manner on an n x n chessboard that no
queens attack each other by being in the same row, column or diagonal.
3
SOLUTION
Solution Using Recursion Technique
Algorithmic/Pseudocode
START
Place the first queen in the first row and column
Place the second queen in the first column of the second row and then check whether
corresponds with the rules, if not put in the second row and the second column .do that
until the position is correct
Put the third queen in the first column and the third row and see whether it corresponds
with the law. Repeat that until the position is reasonable such that there is no conflict
between the 8 queens.
END
Source Code
Package Assignment;
import java.util.*;
public class Queen8 {
4
static int arr[]=new int[8];
static int count=0; //Number of statistical results
public static void main(String[] args) {
//
System.out.println("All in all"+count+"Secondary placement method");
}
//Place the n th queen
public static void check (int n)
{
//If n=8, then the eight queens have been placed in the correct position, and a solution has
been obtained, then the output
if(n==8)
{
printResult ();
}
//Put the queen in turn and judge whether there is a conflict
else
{
for(int i=0;i<8;i++)
{
//Since the queen is placed from the first column every time, the current queen n is
placed in the first column first
5
arr[n]=i; //i start at 0, so this means that we first put queen n in column 1
//Judge whether the placement position is reasonable
//If the location is reasonable, the next queen will be placed
if(judge(n))
{
check(n+1);
}
//If the placement is unreasonable, it will move to the right, that is, it will jump to
continue the for loop
}
}
}
//When placing a queen, it detects whether the current position to be placed conflicts with the
previous position of the queen
//n is the queen, 0 ~ 7
public static boolean judge(int n)
{
for(int i=0;i<n;i++)
{
//1. arr[n]==arr[i], check whether the queen is in the same column
//2. Math.abs(n-i)==Math.abs(arr[n]-arr[i]), check whether it is on the same diagonal line
6
if(arr[n]==arr[i] || (Math.abs(n-i)==Math.abs(arr[n]-arr[i])))
{
return false;
}
}
return true;
}
//Print results
public static void printResult()
{
count++;
for (int i=0;i<arr.length;i++)
{
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
7
Solution Using Backtracking Technique
This is one of the techniques that is used in solving the problems that resemble the N- Queens
Pseudocode
START
1. Begin from the leftmost column
2. If all the queens are placed well return true
3. Check if all the rows are placed correctly in their appropriate columns
if they are placed in their right position, mark column and row and then
recursively check if we approach in the current configuration
if the placing gives a solution, return true else unmark and try other rows
4. if the rows are tried and the solution is not obtained, return false and backtrack
END
Source Code
public class QueenP {
CCCCfinal int N = 8;
C
8
CCCCvoid printSolution(int board[][])
CCCC{
CCCCCCCCfor (int i = 0; i < N; i++) {
CCCCCCCCCCCCfor (int j = 0; j < N; j++)
CCCCCCCCCCCCCCCCSystem.out.print(" " + board[i][j]
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC+ " ");
CCCCCCCCCCCCSystem.out.println();
CCCCCCCC}
CCCC}
C
CCCCboolean is Safe(int board[][], int row, int col)
CCCC{
CCCCCCCCint i, j;
C
CCCCCCCC/* Check this row on left side */
CCCCCCCCfor (i = 0; i < col; i++)
CCCCCCCCCCCCif (board[row][i] == 1)
CCCCCCCCCCCCCCCCreturn false;
C
CCCCCCCC/* Check upper diagonal on left side */
CCCCCCCCfor (i = row, j = col; i >= 0 && j >= 0; i--, j--)
CCCCCCCCCCCCif (board[i][j] == 1)
CCCCCCCCCCCCCCCCreturn false;
9
C
CCCCCCCC/* Check lower diagonal on left side */
CCCCCCCCfor (i = row, j = col; j >= 0 && i < N; i++, j--)
CCCCCCCCCCCCif (board[i][j] == 1)
CCCCCCCCCCCCCCCCreturn false;
C
CCCCCCCCreturn true;
CCCC}
C
CCCC/* A recursive utility function to solve N
CCCCCCCQueen problem */
CCCCboolean solveNQUtil(int board[][], int col)
CCCC{
CCCCCCCC/* base case: If all queens are placed
CCCCCCCCCCCthen return true */
CCCCCCCCif (col >= N)
CCCCCCCCCCCCreturn true;
C
CCCCCCCC/* Consider this column and try placing
CCCCCCCCCCCthis queen in all rows one by one */
CCCCCCCCfor (int i = 0; i < N; i++) {
CCCCCCCCCCCC/* Check if the queen can be placed on
CCCCCCCCCCCCCCCboard[i][col] */
10
CCCCCCCCCCCCif (isSafe(board, i, col)) {
CCCCCCCCCCCCCCCC/* Place this queen in board[i][col] */
CCCCCCCCCCCCCCCCboard[i][col] = 1;
C
CCCCCCCCCCCCCCCC/* recur to place rest of the queens */
CCCCCCCCCCCCCCCCif (solveNQUtil(board, col + 1) == true)
CCCCCCCCCCCCCCCCCCCCreturn true;
C
CCCCCCCCCCCCCCCC/* If placing queen in board[i][col]
CCCCCCCCCCCCCCCCCCCdoesn't lead to a solution then
CCCCCCCCCCCCCCCCCCCremove queen from board[i][col] */
CCCCCCCCCCCCCCCCboard[i][col] = 0; // BACKTRACK
CCCCCCCCCCCC}
CCCCCCCC}
C
CCCCCCCC/* If the queen cannot be placed in any row in
CCCCCCCCCCCthis column col, then return false */
CCCCCCCCreturn false;
CCCC}
C
CCCCboolean solveNQ()
CCCC{
CCCCCCCCint board [][] = { { 0, 0, 0, 0 },
11
CCCCCCCCCCCCCCCCCCCCCCCCCC{ 0, 0, 0, 0 },
CCCCCCCCCCCCCCCCCCCCCCCCCC{ 0, 0, 0, 0 },
CCCCCCCCCCCCCCCCCCCCCCCCCC{ 0, 0, 0, 0 } };
C
CCCCCCCCif (solveNQUtil (board, 0) == false) {
CCCCCCCCCCCCSystem.out.print("Solution does not exist");
CCCCCCCCCCCCreturn false;
CCCCCCCC}
C
CCCCCCCCprintSolution(board);
CCCCCCCCreturn true;
CCCC}
C
CCCC// driver program to test above function
CCCCpublic static void main (String args [])
CCCC{
CCCCCCCCNQueenProblem Queen = new NQueenProblem();
CCCCCCCCQueen.solveNQ();
CCCC}
12
Outputs
13
Conclusion
The main difference between recursion and backtracking is that in recursion technique, the
function calls itself until it attains the base case. In backtracking, there is the use of recursion to
explore all the possibilities until the best result is achieved. Recursion method is a bottom -up
procedure while backtracking is a top-down process.
In recursion you can solve a problem by just checking at the result of the sub- problem while in
backtracking some circumstances you can’t solve the problem by the use of the sub-problem.
you need to pass the information that you already have achieved from the sub-problems.
14
