AAD
8 Queen
import java.util.Arrays;
class Main{
static final int N = 8;
static boolean isSafe(int[][] board, int row, int col)
{
// check if there is a queen in the same row to the
// left
for (int x = 0; x < col; x++)
if (board[row][x] == 1)
return false;
for (int x = row, y = col; x >= 0 && y >= 0;
x--, y--)
if (board[x][y] == 1)
return false;
for (int x = row, y = col; x < N && y >= 0;
x++, y--)
if (board[x][y] == 1)
return false;
return true;
}
static boolean solveNQueens(int[][] board, int col)
{
// if all queens are placed, print the board
if (col == N) {
for (int[] row : board)
System.out.println(Arrays.toString(row));
System.out.println();
return true;
}
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1; // place the queen
if (solveNQueens(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
}
public static void main(String[] args)
{
int[][] board = new int[N][N];
if (!solveNQueens(board, 0))
System.out.println("No solution found");
}
}
8
public class mColoringProblem {
final int V = 4;
int color[];
boolean isSafe(int v, int graph[][], int color[], int c)
{
for (int i = 0; i < V; i++)
if (graph[v][i] == 1 && c == color[i])
return false;
return true;
}
boolean graphColoringUtil(int graph[][], int m,
int color[], int v)
{
if (v == V)
return true;
for (int c = 1; c <= m; c++) {
if (isSafe(v, graph, color, c)) {
color[v] = c;
if (graphColoringUtil(graph, m, color,
v + 1))
return true;
color[v] = 0;
}
}
return false;
}
boolean graphColoring(int graph[][], int m)
{
color = new int[V];
for (int i = 0; i < V; i++)
color[i] = 0;
if (!graphColoringUtil(graph, m, color, 0)) {
System.out.println("Solution does not exist");
return false;
}
printSolution(color);
return true;
}
void printSolution(int color[])
{
System.out.println("Solution Exists: Following"
+ " are the assigned colors");
for (int i = 0; i < V; i++)
System.out.print(" " + color[i] + " ");
System.out.println();
}
public static void main(String args[])
{
mColoringProblem Coloring = new mColoringProblem();
int graph[][] = {
{ 0, 1, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 0, 1 },
{ 1, 0, 1, 0 },
};
int m = 3;
Coloring.graphColoring(graph, m);
}
}
Comments
Post a Comment