Answered step by step
Verified Expert Solution
Question
1 Approved Answer
(Java) write source codes for the BFS and DFS algorithms to solve the Sudoku Puzzle The program should solve the Sudoku puzzle for two board
(Java) write source codes for the BFS and DFS algorithms to solve the Sudoku Puzzle
The program should solve the Sudoku puzzle for two board configurations - 6x6 and 9x9 boards
fill in the TO DO BFS and DFS functions in the code template
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; class Sudoku_Solver_question { public static int type = 0; public static int height = 0; // Node exploration holds the sudoku board in every iteration private static class Exploration { char[][] board; int curCell = 0; // constructor method public Exploration(char[][] board, int curCell) { this.board = cloneBoard(board); this.curCell = curCell; } // clones the board for every state private char[][] cloneBoard(char[][] board) { char[][] newBoard = new char[board.length][board[0].length]; copyIntoBoard(board, newBoard); return newBoard; } } public static boolean BFS(char[][] board) { // TODO write BFS search algorithm } public static boolean DFS(char[][] board) { // TODO write DFS search algorithm }
/** * parameter: index * return: index * Returns the index of a row based on type(6x6 / 9x9) of the board */ private static int getRowForIndex(int idx) { return idx / type; } /** * parameter: index * return: index * Returns the index of a column based on type(6x6 / 9x9) of the board */ private static int getColumnForIndex(int idx) { return idx % type; } /** * Parameters: source board & destination board * return: null * Copies the source board to destination board in every state */ protected static void copyIntoBoard(char[][] src, char[][] dst) { for (int i = 0; i < src.length; i++) { System.arraycopy(src[i], 0, dst[i], 0, src[i].length); } } /** * Parameters: Board & box index number * returns: true / false * Validates the box, returns true if there is no duplicate number in the box else false */ private static boolean isValidSquare(char[][] board, int s) { boolean[] isPresent = new boolean[board.length+1]; for (int r = (s / 3) * height; r < ((s / 3) + 1) * height; r++) { for (int c = (s % 3) * height; c < ((s % 3) + 1) * height; c++) { char value = board[r][c]; if (value == '.') { continue; } int intVal = Character.getNumericValue(value); if (isPresent[intVal]) { return false; } isPresent[intVal] = true; } } return true; } /** * Parameters: Board & column index number * returns: true / false * Validates the box, returns true if there is no duplicate number in the column else false */ private static boolean isValidColumn(char[][] board, int c) { boolean[] isPresent = new boolean[board.length+1]; for (int i = 0; i < board.length; i++) { char value = board[i][c]; if (value == '.') { continue; } int intVal = Character.getNumericValue(value); if (isPresent[intVal]) { return false; } isPresent[intVal] = true; } return true; } /** * Parameters: Board & row index number * returns: true / false * Validates the box, returns true if there is no duplicate number in the row else false */ private static boolean isValidRow(char[][] board, int r) { boolean[] isPresent = new boolean[board.length+1]; for (int i = 0; i < board.length; i++) { char value = board[r][i]; if (value == '.') { continue; } int intVal = Character.getNumericValue(value); if (isPresent[intVal]) { return false; } isPresent[intVal] = true; } return true; } /** * parameter: board * return: null * prints the board/matrix in the console */ public static void print_matrix(char[][] board){ int type = board.length; for(int i = 0; i
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started