Answered step by step
Verified Expert Solution
Link Copied!

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

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Oracle RMAN For Absolute Beginners

Authors: Darl Kuhn

1st Edition

1484207637, 9781484207635

More Books

Students also viewed these Databases questions

Question

How often is the code of conduct reviewed?

Answered: 1 week ago

Question

1. Identify an organization to analyze, preferably your employer.

Answered: 1 week ago