Abstract In this lab you will implement recursive solutions to classic CS ques-
ID: 3730784 • Letter: A
Question
Abstract In this lab you will implement recursive solutions to classic CS ques- tions. One will be a chess problem, and the other is Towers of Hanoi. 1 Backtracking with Recursion - Featuring Chess Choose and complete one of the two following chess problems. These problems can be solved using the backtracking algorithm shown below. boolean solve(board, pos) if( pos is such that there is nothing left to solve) ( return true; for each possible choice t if(valid (choice)) mark board at pos with choice; if(solve(board, pos + 1) == true){ return true; clear any choices entered at pos on board; return false; // backtrackExplanation / Answer
2)Sudoku code using Backtracking
It prints the solution of Sudoku
import java.util.*;
import java.lang.*;
import java.io.*;
class Chegg
{
public static void main (String[] args)
{
//code
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t!=0)
{
int mat[][] = new int[9][9];
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
mat[i][j]=sc.nextInt();
}
}
if(sudo(mat))
printGrid(mat);
System.out.println();
t--;
}
}
static void printGrid(int grid[][])
{
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
System.out.print( grid[row][col]+" ");
}
}
static boolean sudo(int[][] mat){
int rowcol[] = findUnass(mat);
if(rowcol[0] == -1 && rowcol[1] == -1)
return true;
for(int i=1;i<=9;i++)
{
if(issafe(mat,rowcol[0],rowcol[1],i))
{
mat[rowcol[0]][rowcol[1]]=i;
if(sudo(mat))
return true;
mat[rowcol[0]][rowcol[1]]=0;
}
}
return false;
}
static int[] findUnass(int[][] mat){
int rowcol[]={-1,-1};
int row=0,col=0;
for(row=0;row<9;row++)
{
for(col=0;col<9;col++)
{
if(mat[row][col]==0){
rowcol[0]=row;
rowcol[1]=col;
}
}
}
return rowcol;
}
static boolean issafe(int[][] mat,int row,int col,int num){
return (!checkRow(mat,row,num)
&& !checkCol(mat,col,num)
&& !checkBox(mat,row-row%3,col-col%3,num));
}
static boolean checkRow(int[][] mat,int row,int num){
for(int i=0;i<9;i++)
if(mat[row][i]==num)
return true;
return false;
}
static boolean checkCol(int[][] mat,int col,int num){
for(int i=0;i<9;i++)
if(mat[i][col]==num)
return true;
return false;
}
static boolean checkBox(int[][] mat,int row,int col,int num){
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(mat[i+row][j+col]==num)
return true;
}
}
return false;
}
}
1) The chess question is more like N Queen Problem of the chessboard.Here is the code
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main (String[] args) {
//code
BufferedReader inpt = new BufferedReader(new InputStreamReader(System.in));
try {
int numTests = Integer.parseInt(inpt.readLine());
for (int i = 0; i < numTests; i++) {
int boardSize = Integer.parseInt(inpt.readLine());
placeQueens(boardSize);
}
} catch(IOException ex) {
System.out.println("Exception");
}
}
// Place the queens in multiple arrangements
private static void placeQueens(int size) {
// Holds the possible solutions
ArrayList<Integer[]> arrangements = new ArrayList<Integer[]>();
// Chessboard
Integer[][] board = new Integer[size][size];
ArrayList<Integer> arrangement = new ArrayList<Integer>();
arrangeQueens(0, arrangement, board, arrangements);
if (arrangements.size() < 1) {
System.out.println("-1");
} else {
// Show solutions
for (Integer[] solution : arrangements) {
printSolutions(solution);
}
System.out.println();
}
}
private static void arrangeQueens(int col, ArrayList<Integer> arrangement, Integer[][] board, ArrayList<Integer[]> arrangements) {
// Boundary check
if (col >= board.length) {
Integer[] solution = new Integer[board.length];
for (int i = 0; i < solution.length; i++) {
solution[i] = arrangement.get(i);
}
// Add solution to arrangements
arrangements.add(solution);
return;
} else {
for (int row = 0; row < board.length; row++) {
// Place queen
if (canPlace(row, col, board)) {
arrangement.add(row + 1);
placeQueen(row, col, board);
// Recurse
arrangeQueens(col + 1, arrangement, board, arrangements);
// clear row for next iteration
unsetQueen(row, col, board);
arrangement.remove(arrangement.size() - 1);
}
}
}
}
// Place an individual queen at a location
private static void placeQueen(int row, int col, Integer[][] board) {
// Place queen
board[row][col] = 1;
// Block Row
board[row][board.length - 1] = 1;
}
private static void unsetQueen(int row, int col, Integer[][] board) {
// Reset location
board[row][col] = null;
// Unblock row
board[row][board.length - 1] = null;
}
// Check if a queen can be put here
private static boolean canPlace(int row, int col, Integer[][] board) {
// Check if row is blocked
if (board[row][board.length - 1] != null || board[row][col] != null) {
return false;
} else {
return checkDiagonals(row, col, board);
}
}
private static boolean checkDiagonals(int row, int col, Integer[][] board) {
int rD = row + 1,
rU = row - 1,
cR = col + 1,
cL = col - 1;
while (rD < board.length || rU >= 0) {
// Upward
if (rU >= 0 && cL >= 0 && board[rU][cL] != null) {
return false;
}
// Downard
if (rD < board.length && cL >= 0 && board[rD][cL] != null) {
return false;
}
rU--;
rD++;
cL--;
}
return true;
}
// Helper method prints the solutions and surrounding brackets
private static void printSolutions(Integer[] locations) {
System.out.print("[");
for (int i = 0; i < locations.length; i++) {
System.out.print(locations[i] + " ");
}
System.out.print("] ");
}
} // Class