In this exercise you will implement your design from Assignment 2 relating to ge
ID: 3664090 • Letter: I
Question
In this exercise you will implement your design from Assignment 2 relating to generating (not solving) sudoku problems. We’ll start with a reminder about what sudoku arrays look like, then we’ll talk about generating problems from the sudoku arrays. A Sudoku array is a 9x9 Latin Square, with an additional restriction. Recall from assignment 2 that a Latin Square is an array of NxN integers. Each row and each column contains all the numbers 1-N (inclusive). The additional restriction for a sudoku problem is that the 9x9 grid is subdivided into 3x3 regions which must contain all the numbers 1-9 exactly. For example, the following is a sudoku array, but not a very interesting one. It will be the basis of your implementation, though.
936-47258 825 93-6147 714 825-936 693 711525 582 693-71-4 471-5 82-593 3 6 9 4 7-15-82 2583-69-47 147 258-369Explanation / 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");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.