XXXXXXXXXXXXXXXXXXX ANSWERS TO THIS QUESTION ARE ALREADY ONLINE BUT INCOMPLETE.
ID: 3691003 • Letter: X
Question
XXXXXXXXXXXXXXXXXXX ANSWERS TO THIS QUESTION ARE ALREADY ONLINE BUT INCOMPLETE. DO NOT JUST COPY AND PASTE FROM THEMXXXXXXXXXXXXXXXXXXXXXXXXXX Sudoku is a popular logic puzzle that uses a 9 by 9 array of squares that are organized into 3 by 3 subarrays. The puzzle solver must fill in the squares with the digits 1 to 9 such that no digit is repeated in any row, any column, or any of the nine 3 by 3 subgroups of squares. Initially, some squares are filled in already and cannot be changed. For example, the following might be a starting congiguration for a Sudoku puzzle: Create a class sudokuPuzzle that has the attributes board- a 9 by 9 array of integers that represents the curretn state of the puzzle, where 0 indicate a blank square start- a 9 by 9 array of boolean values that indicates which squares in board are given values that cannot be changed and the following methiods: sudokupuzzle- a constructor that creates an empty puzzle toString- returns a string representation of the puzzle that can be printed addInitial(row,col, value)- sets the given square to the given value as an inital value that cannot be changed by the puzzle solver addGuess(row,col,value)-sets the given square to the given value; the value can be changed later by another call to addGuess checkPuzzle- returns true if the values in the puzzle do not violate the restrictions getValueIn(row,col)- returns the value in the given square getAllowedValues(row, col)- returns a one dimensional array of nine booleans, each of which corresponds to a digit and is true if the digit can be placed in the given square without violating the restrictions isFull- returns true if every square has a value reset- changes all of the nonpermanent squares back to blanks(0s) XXXXXXXXXXXXXXXXXX PAY ATTENTION TO THIS NEXT PART. IT IS MISSING FROM ALL PREVIOUS ANSWERS TO THIS QUESTION XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX write a main method in the class Sudoku that creates a SudokuPuzzle obkect and sets its initial configuration. Then use a loop to allow someone to play Sudoku. Display the current configuration and ask for a row, column, and value. Update the game board and display it again. If the configuration does not satisfy the restrictions, let the user know. Indicate when the puzzle has been solved correctly. In that case, both checkPuzzle and isFull would return true. You should also allow options for resetting the puzzle and displaying the values that can be placed in a given squareExplanation / Answer
public class sudoku {
// Is every number 1-9 in the given rectangle 0..1 times?
public static boolean isRectangleLegal(int[][] board, int x1, int x2, int y1, int y2, String errormsg) {
boolean[] isPresent = {false, false, false, false, false, false, false, false, false, false};
for (int x=x1; x<=x2; x++) {
for (int y=y1; y<=y2; y++) {
if (board[x][y] > 0) {
if (isPresent[board[x][y]]) {
//System.out.println(errormsg + ": multiple " + board[x][y] + "s");
return false;
}
isPresent[board[x][y]] = true;
}
}
}
return true;
}
public static boolean isLegal(int[][] board) {
// Check the nine blocks.
if (!isRectangleLegal(board, 0, 2, 0, 2, "Block 1")) return false;
if (!isRectangleLegal(board, 3, 5, 0, 2, "Block 2")) return false;
if (!isRectangleLegal(board, 6, 8, 0, 2, "Block 3")) return false;
if (!isRectangleLegal(board, 0, 2, 3, 5, "Block 4")) return false;
if (!isRectangleLegal(board, 3, 5, 3, 5, "Block 5")) return false;
if (!isRectangleLegal(board, 6, 8, 3, 5, "Block 6")) return false;
if (!isRectangleLegal(board, 0, 2, 6, 8, "Block 7")) return false;
if (!isRectangleLegal(board, 3, 5, 6, 8, "Block 8")) return false;
if (!isRectangleLegal(board, 6, 8, 6, 8, "Block 9")) return false;
// check the nine columns
if (!isRectangleLegal(board, 0, 0, 0, 8, "Column 0")) return false;
if (!isRectangleLegal(board, 1, 1, 0, 8, "Column 1")) return false;
if (!isRectangleLegal(board, 2, 2, 0, 8, "Column 2")) return false;
if (!isRectangleLegal(board, 3, 3, 0, 8, "Column 3")) return false;
if (!isRectangleLegal(board, 4, 4, 0, 8, "Column 4")) return false;
if (!isRectangleLegal(board, 5, 5, 0, 8, "Column 5")) return false;
if (!isRectangleLegal(board, 6, 6, 0, 8, "Column 6")) return false;
if (!isRectangleLegal(board, 7, 7, 0, 8, "Column 7")) return false;
if (!isRectangleLegal(board, 8, 8, 0, 8, "Column 8")) return false;
// check the nine rows
if (!isRectangleLegal(board, 0, 8, 0, 0, "Row 0")) return false;
if (!isRectangleLegal(board, 0, 8, 1, 1, "Row 1")) return false;
if (!isRectangleLegal(board, 0, 8, 2, 2, "Row 2")) return false;
if (!isRectangleLegal(board, 0, 8, 3, 3, "Row 3")) return false;
if (!isRectangleLegal(board, 0, 8, 4, 4, "Row 4")) return false;
if (!isRectangleLegal(board, 0, 8, 5, 5, "Row 5")) return false;
if (!isRectangleLegal(board, 0, 8, 6, 6, "Row 6")) return false;
if (!isRectangleLegal(board, 0, 8, 7, 7, "Row 7")) return false;
if (!isRectangleLegal(board, 0, 8, 8, 8, "Row 8")) return false;
return true;
}
public static boolean solve(int[][] board) {
// Find a position that's still empty.
for (int x=0; x<9; x++) {
for (int y=0; y<9; y++) {
if (board[x][y] == 0) {
// Try each possibile value in this space
// and see if the rest of the puzzle can be filled in.
for (board[x][y]=1; board[x][y]<=9; board[x][y]++) {
if (isLegal(board) && solve(board)) {
return true;
}
}
// There is no value that we can put in the first
// empty space that was found, so the puzzle is
// unsolvable given the values put in up to this
// point.
board[x][y] = 0;
return false;
}
}
}
// There were no empty spaces to fill in, so the
// puzzle must be solved.
return true;
}
public static void printBoard(int[][] board) {
for (int x=0; x<9; x++) {
System.out.println(x%3==0 ? "+-----+-----+-----+" : "| | | |");
for (int y=0; y<9; y++)
System.out.print((y%3==0 ? "|" : " ") + board[x][y]);
System.out.println("|");
}
System.out.println("+-----+-----+-----+");
}
public static void main(String[] argv) {
int board[][] = {{0,0,0, 0,0,0, 0,1,2},
{0,0,0, 0,5,1, 3,8,0},
{0,8,0, 0,0,6, 0,0,0},
{1,0,0, 2,4,0, 0,7,0},
{0,0,0, 0,3,0, 0,0,0},
{0,7,0, 0,6,5, 0,0,3},
{0,0,0, 4,0,0, 0,2,0},
{0,5,9, 6,8,0, 0,0,0},
{8,1,0, 0,0,0, 0,0,0} };
if (solve(board))
printBoard(board);
else
System.out.println("no solution");
}
}
Had some fun with it in Scala. You can remove more cells to make it more difficult.Scala
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.