NQueen’s Problem using Backtracking

JAVA CODE

import java.util.Scanner;

public class Main {

static Scanner scan;
static int N = 4;

static void printBoard(int board[][]) {
int i;
for (i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
if (board[i][j] == 1) {
System.out.print(“Q\t”);
} else {
System.out.print(“_\t”);
}
System.out.println(“\n”);
}
}

static boolean toPlaceOrNotToPlace(int board[][], int row, int col) {
int i, j;
for (i = 0; i < col; i++) {
if (board[row][i] == 1)
return false;
}
for (i = row, j = col; i >= 0 && j >= 0; i–, j–) {
if (board[i][j] == 1)
return false;
}
for (i = row, j = col; j >= 0 && i < N; i++, j–) {
if (board[i][j] == 1)
return false;
}
return true;
}

static boolean theBoardSolver(int board[][], int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (toPlaceOrNotToPlace(board, i, col)) {
board[i][col] = 1;
if (theBoardSolver(board, col + 1))
return true;
// Backtracking is hella important in this one.
board[i][col] = 0;
}
}
return false;
}

public static void main(String[] args) {
scan = new Scanner(System.in);
System.out.println(“State the value of N in this program!”);
N = scan.nextInt();
int[][] board = new int[N][N];
if (!theBoardSolver(board, 0)) {
System.out.println(“Solution not found.”);
}
printBoard(board);
}
}

 

C++ CODE

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 4
using namespace std;

/* print solution */
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout<<board[i][j]<<” “;
cout<<endl;
}
}

/* check if a queen can be placed on board[row][col]*/
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
{
if (board[row][i])
return false;
}
for (i = row, j = col; i >= 0 && j >= 0; i–, j–)
{
if (board[i][j])
return false;
}

for (i = row, j = col; j >= 0 && i < N; i++, j–)
{
if (board[i][j])
return false;
}

return true;
}

/*solve N Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++)
{
if ( isSafe(board, i, col) )
{
board[i][col] = 1;
if (solveNQUtil(board, col + 1) == true)
return true;
board[i][col] = 0;
}
}
return false;
}

/* solves the N Queen problem using Backtracking.*/
bool solveNQ()
{
int board[N][N] = {0};
if (solveNQUtil(board, 0) == false)
{
cout<<“Solution does not exist”<<endl;
return false;
}
printSolution(board);
return true;
}

// Main
int main()
{
solveNQ();
return 0;
}

Advertisements
Categories: Algorithm | Leave a comment

Post navigation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.