*Comment Sudoku Class public class Sudoku { public String[][] makeSudoku(String
ID: 3747958 • Letter: #
Question
*Comment Sudoku Class
public class Sudoku {
public String[][] makeSudoku(String s) {
int SIZE = 9;
int k = 0;
String[][] x = new String[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
x[i][j] = s.substring(k, k + 1);
k++;
}
}
return x;
}
public String getPrintableSudoku(String[][] x) {
int SIZE = 9;
String temp = "";
for (int i = 0; i < SIZE; i++) {
if ((i == 3) || (i == 6)) {
temp = temp + "================= ";
}
for (int j = 0; j < SIZE; j++) {
if ((j == 3) || (j == 6)) {
temp = temp + " || ";
}
temp = temp + x[i][j];
}
temp = temp + " ";
}
return temp;
}
public boolean isValidSudoku(String[][] x) {
return rowsAreLatin(x) && colsAreLatin(x) && goodSubsquares(x);
}
public boolean rowsAreLatin(String[][] x) {
boolean test = true;
for (int i = 0; i < x.length; i++) {
test = test && rowIsLatin(x,i);
}
return test;
}
//This function works in BIG O(n) and found is if there are duplicates
public boolean rowIsLatin(String[][] x, int i) {
boolean found[] = new boolean[9];
int n;
for(n=0;n<found.length;n++)
found[n] = false;
for(int j=0;j<x[i].length;j++)
{
n = Integer.parseInt(x[i][j]);
found[n-1]=true;
}
//If any of the found variable is false means that particular was not present before and hence duplicate must be present
for( n=0;n<found.length;n++)
if(!found[n])
return false;
return true;
}
public boolean colsAreLatin(String[][] x) {
boolean test = true;
for (int j = 0; j < x.length; j++) {
test = test && colIsLatin(x,j);
}
return test;
}
//This function works in BIG O(n) and found is if there are duplicates
public boolean colIsLatin(String[][] x, int j) {
boolean found[] = new boolean[9];
int n;
for(n=0;n<found.length;n++)
found[n] = false;
for(int i=0;i<x.length;i++)
{
n = Integer.parseInt(x[i][j]);
found[n-1]=true;
}
//If any of the found variable is false means that particular was not present before and hence duplicate must be present
for( n=0;n<found.length;n++)
if(!found[n])
return false;
return true;
}
public boolean goodSubsquares(String[][] x) {
boolean test = true;
for (int i = 0; i < x.length;i=i+3) {
for(int j=0;j<x[i].length;j=j+3)
test = test && goodSubsquare(x,i,j);
}
return test;
}
public boolean goodSubsquare(String[][] x, int i, int j) {
boolean found[] = new boolean[9];
int n;
for(n=0;n<found.length;n++)
found[n] = false;
for(int row=i;row<(i+3);row++)
for(int col=j;col<(j+3);col++)
{
n = Integer.parseInt(x[row][col]);
found[n-1]=true;
}
for( n=0;n<found.length;n++)
if(!found[n])
return false;
return true;
}
}
public class SudokuSimulation {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Sudoku mySudokuPuzzle = new Sudoku();
// Row and subsquares are invalid
String config0 = "9234567892345678913456789124567891235678912346"
+ "78912345789123456891234567912345678";
String[][] puzzle0 = mySudokuPuzzle.makeSudoku(config0);
if (mySudokuPuzzle.isValidSudoku(puzzle0)) {
System.out.println("This puzzle is valid.");
} else {
System.out.println("This puzzle is invalid.");
}
System.out.println(mySudokuPuzzle.getPrintableSudoku(puzzle0));
System.out.println("--------------------------------------------------");
// Col and subsquares are invalid
String config00 = "9234567899345678913456789124567891235678912346"
+ "78912345789123456891234567912345678";
String[][] puzzle00 = mySudokuPuzzle.makeSudoku(config00);
if (mySudokuPuzzle.isValidSudoku(puzzle00)) {
System.out.println("This puzzle is valid.");
} else {
System.out.println("This puzzle is invalid.");
}
System.out.println(mySudokuPuzzle.getPrintableSudoku(puzzle00));
System.out.println("--------------------------------------------------");
// Row and column Latin but with invalid subsquares
String config1 = "1234567892345678913456789124567891235678912346"
+ "78912345789123456891234567912345678";
String[][] puzzle1 = mySudokuPuzzle.makeSudoku(config1);
if (mySudokuPuzzle.isValidSudoku(puzzle1)) {
System.out.println("This puzzle is valid.");
} else {
System.out.println("This puzzle is invalid.");
}
System.out.println(mySudokuPuzzle.getPrintableSudoku(puzzle1));
System.out.println("--------------------------------------------------");
// Row Latin but column not Latin and with invalid subsquares
String config2 = "12345678912345678912345678912345678912345678"
+ "9123456789123456789123456789123456789";
String[][] puzzle2 = mySudokuPuzzle.makeSudoku(config2);
if (mySudokuPuzzle.isValidSudoku(puzzle2)) {
System.out.println("This puzzle is valid.");
} else {
System.out.println("This puzzle is invalid.");
}
System.out.println(mySudokuPuzzle.getPrintableSudoku(puzzle2));
System.out.println("--------------------------------------------------");
// A valid sudoku
String config3 = "25813764914698532779324685147286319558149273663"
+ "9571482315728964824619573967354218";
String[][] puzzle3 = mySudokuPuzzle.makeSudoku(config3);
if (mySudokuPuzzle.isValidSudoku(puzzle3)) {
System.out.println("This puzzle is valid.");
} else {
System.out.println("This puzzle is invalid.");
}
System.out.println(mySudokuPuzzle.getPrintableSudoku(puzzle3));
System.out.println("--------------------------------------------------");
}
}
Explanation / Answer
package sudoku;
public class Sudoku {
/*
* INPUT: string of length 81
* String contains digits from 1 to 9
* corresponding to each cell of Sudoku.
* RETURN: 2D matrix of sudoku
*/
public String[][] makeSudoku(String s) {
int SIZE = 9;
int k = 0;
// make a 2D matrix to store all the digits
// and store respective digits in each cell
String[][] x = new String[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
x[i][j] = s.substring(k, k + 1);
k++;
}
}
return x;
}
/*
* INPUT: Sudoku matrix
* RETURN: String that can print sudoku
*/
public String getPrintableSudoku(String[][] x) {
int SIZE = 9;
String temp = "";
for (int i = 0; i < SIZE; i++) {
// for making separators after 3rd and 6th row
if ((i == 3) || (i == 6)) {
temp = temp + "================= ";
}
for (int j = 0; j < SIZE; j++) {
// for making separators after 3rd and 6th column
if ((j == 3) || (j == 6)) {
temp = temp + " || ";
}
// store the current cell in string
temp = temp + x[i][j];
}
// after each row, add a new line
temp = temp + " ";
}
return temp;
}
/*
* INPUT: Sudoku matrix
* RETURN: AND of outputs of rowsAreLatin, colsAreLatin and goodSubsquares
*/
public boolean isValidSudoku(String[][] x) {
return rowsAreLatin(x) && colsAreLatin(x) && goodSubsquares(x);
}
/*
* INPUT: sudoku matrix
* RETURN: true or false
* Checks if each row is valid by calling rowIsLatin function
*/
public boolean rowsAreLatin(String[][] x) {
boolean test = true;
for (int i = 0; i < x.length; i++) {
test = test && rowIsLatin(x, i);
}
return test;
}
/*
* INPUT: a row and its row number
* RETURN: true or false
* COMPLEXITY: O(n)
* Finds if there are any duplicates
*/
public boolean rowIsLatin(String[][] x, int i) {
/* make a found array of length 9
* set true to only those elements that appear in the current row
* For e.g. if 1 appears in the row, set found[0] = true
* If 9 appears in the row, set found[8] = true
* The goal is to find repeating digits
* If any digit repeats, some other digit will be absent
* And that element will be false in found array.
*/
boolean found[] = new boolean[9];
int n;
for (n = 0; n < found.length; n++)
found[n] = false;
for (int j = 0; j < x[i].length; j++) {
n = Integer.parseInt(x[i][j]);
found[n - 1] = true;
}
//If any of the found variable is false means that particular was not
//present before and hence duplicate must be present
for (n = 0; n < found.length; n++)
if (!found[n])
return false;
return true;
}
/*
* INPUT: sudoku matrix
* RETURN: true or false
* Checks if each col is valid by calling colIsLatin function
*/
public boolean colsAreLatin(String[][] x) {
boolean test = true;
for (int j = 0; j < x.length; j++) {
test = test && colIsLatin(x, j);
}
return test;
}
/*
* INPUT: a column and its column number
* RETURN: true or false
* COMPLEXITY: O(n)
* Finds if there are any duplicates
*/
public boolean colIsLatin(String[][] x, int j) {
/* make a found array of length 9
* set true to only those elements that appear in the current column
* For e.g. if 1 appears in the column, set found[0] = true
* If 9 appears in the column, set found[8] = true
* The goal is to find repeating digits
* If any digit repeats, some other digit will be absent
* And that element will be false in found array.
*/
boolean found[] = new boolean[9];
int n;
for (n = 0; n < found.length; n++)
found[n] = false;
for (int i = 0; i < x.length; i++) {
n = Integer.parseInt(x[i][j]);
found[n - 1] = true;
}
//If any of the found variable is false means that particular was not
//present before and hence duplicate must be present
for (n = 0; n < found.length; n++)
if (!found[n])
return false;
return true;
}
/*
* INPUT: sudoku matrix
* RETURN: true or false
* Checks if each 3x3 square is valid by calling goodSubsquare function
*/
public boolean goodSubsquares(String[][] x) {
boolean test = true;
for (int i = 0; i < x.length; i = i + 3) {
for (int j = 0; j < x[i].length; j = j + 3)
test = test && goodSubsquare(x, i, j);
}
return test;
}
/*
* INPUT: a square and its i and j position in the Sudoku
* i and j are the position of top left cell in the square
* RETURN: true or false
* COMPLEXITY: O(n)
* Finds if there are any duplicates
*/
public boolean goodSubsquare(String[][] x, int i, int j) {
/* make a found array of length 9
* set true to only those elements that appear in the current square
* For e.g. if 1 appears in the square, set found[0] = true
* If 9 appears in the square, set found[8] = true
* The goal is to find repeating digits
* If any digit repeats, some other digit will be absent
* And that element will be false in found array.
*/
boolean found[] = new boolean[9];
int n;
for (n = 0; n < found.length; n++)
found[n] = false;
for (int row = i; row < (i + 3); row++)
for (int col = j; col < (j + 3); col++) {
n = Integer.parseInt(x[row][col]);
found[n - 1] = true;
}
//If any of the found variable is false means that particular was not
//present before and hence duplicate must be present
for (n = 0; n < found.length; n++)
if (!found[n])
return false;
return true;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.