Make the Sudoku algorithm for checking for duplicates to be Big -O of N, instead of...
Make the Sudoku algorithm for checking for duplicates to be Big -O of N, instead of N-squared. I.E. No nested for loops in rowIsLatin and colIsLatin. Only nested loop allowed in goodSubsquare.
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 + "=================\n";
}
for (int j = 0; j < SIZE; j++) {
if ((j == 3) || (j == 6)) {
temp = temp + " || ";
}
temp = temp + x[i][j];
}
temp = temp + "\n";
}
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;
}
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;
}
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;
}
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;
}
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;
}
}
//end of Sudoku.java
// SudokuSimulation.java
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("--------------------------------------------------");
}
}
Homework Answers
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 + "=================\n";
}
for (int j = 0; j < SIZE; j++) {
if ((j == 3) || (j == 6)) {
temp = temp + " || ";
}
temp = temp + x[i][j];
}
temp = temp + "\n";
}
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;
}
}
//end of Sudoku.java
// SudokuSimulation.java
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("--------------------------------------------------");
}
}
For further assistance please comment
Add Answer to:
Make the Sudoku algorithm for checking for duplicates to be Big
-O of N, instead of...
I am currently using eclipse to write in java. A snapshot of the output would be...
I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify
that the program is indeed working. Thanks in advance for both your
time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in...
This is my code for my game called Reversi, I need to you to make the...
This is my code for my game called Reversi, I need to you to make the Tester program that will run and complete the game. Below is my code, please add comments and Javadoc. Thank you. public class Cell { // Displays 'B' for the black disk player. public static final char BLACK = 'B'; // Displays 'W' for the white disk player. public static final char WHITE = 'W'; // Displays '*' for the possible moves available. public static...
Please modify the following code to NOT have "TicTacToe extends Board" (I don't want any extending)....
Please modify the following code to NOT have "TicTacToe extends Board" (I don't want any extending). Please ensure the resulting code completes EACH part of the following prompt: "Your task is to create a game of Tic-Tac-Toe using a 2-Dimensional String array as the game board. Start by creating a Board class that holds the array. The constructor should use a traditional for-loop to fill the array with "blank" Strings (eg. "-"). You may want to include other instance data......
This is my code for a TicTacToe game. However, I don't know how to write JUnit...
This is my code for a TicTacToe game. However, I don't know how to write JUnit tests. Please help me with my JUnit Tests. I will post below what I have so far. package cs145TicTacToe; import java.util.Scanner; /** * A multiplayer Tic Tac Toe game */ public class TicTacToe { private char currentPlayer; private char[][] board; private char winner; /** * Default constructor * Initializes the board to be 3 by 3 and...
need help..... sudoku.h class sudoku { public: sudoku(); //default constructor //Postcondition: grid is initialized to 0...
need help..... sudoku.h class sudoku { public: sudoku(); //default constructor //Postcondition: grid is initialized to 0 sudoku(int g[][9]); //constructor //Postcondition: grid = g void initializeSudokuGrid(); //Function to prompt the user to specify the numbers of the //partially filled grid. //Postcondition: grid is initialized to the numbers // specified by the user. void initializeSudokuGrid(int g[][9]); //Function to initialize grid to g //Postcondition: grid = g; void printSudokuGrid(); //Function to print the sudoku grid. bool solveSudoku(); //Funtion to solve the sudoku problem....
The first file is an array based list. We have looked at node based implementations of...
The first file is an array based list. We have looked at node based implementations of both stacks and queues. An array based list utilizes an array of nodes to support common operations; note that the node class that we utilize has neither next nor previous references. Integer subscripts are maintained to keep track of both the front and rear. _____________________________________________________________________________________________________ class Node { private int key; public Node() { key = -1; } public Node(int k) { key =...
Please help to make the program working. Can not compile. import java.io.*; import java .util.*; public...
Please help to make the program working. Can not compile. import java.io.*; import java .util.*; public class Puzzlee { static int NN = 9; // Grid Size // sample input static int myGrid[][] = { {0,0,0,1,0,5,0,6,8}, {0,0,0,0,0,0,7,0,1}, {9,0,1,0,0,0,0,3,0}, {0,0,7,0,2,6,0,0,0}, {5,0,0,0,0,0,0,0,3}, {0,0,0,8,7,0,4,0,0}, {0,3,0,0,0,0,8,0,5}, {1,0,5,0,0,0,0,0,0}, {7,9,0,4,0,1,0,0,0} }; static class myCell { int myRow, myColumn; public myCell(int myRow, int myColumn) { super(); ...
I am unsure how to add the following methods onto this code?? please help - rowValuesIncrease(int[][]...
I am unsure how to add the following methods onto this code?? please help - rowValuesIncrease(int[][] t) A method that returns true if from left to right in any row, the integers are increasing, otherwise false. - columnValuesIncrease(int[][] t) A method that returns true if from top to bottom in any column, the integers are increasing, otherwise false. - isSetOf1toN(int[][] t) A method that returns true if the set of integers used is {1, 2, . . . , n}...
Hi I need help with a java program that I need to create a Airline Reservation...
Hi I need help with a java program that I need to create a Airline Reservation System I already finish it but it doesnt work can someone please help me I would be delighted it doesnt show the available seats when running the program and I need it to run until someone says no for booking a seat and if they want to cancel a seat it should ask the user to cancel a seat or continue booking also it...
I'm making a sudoku solver to check if the sudoku grid created is legal. There are...
I'm making a sudoku solver to check if the sudoku grid created
is legal. There are supposed to be no repeated numbers in each row,
column, and block. I got the code for the repeated numbers for row
and column but confused on how to write the code for the blocks.
Here is my code:
134 135 136 / COMPLETE THIS 137 // Returns true if this grid is legal. A grid is legal if no row, column, or //...
I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify
that the program is indeed working. Thanks in advance for both your
time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in...
I'm making a sudoku solver to check if the sudoku grid created
is legal. There are supposed to be no repeated numbers in each row,
column, and block. I got the code for the repeated numbers for row
and column but confused on how to write the code for the blocks.
Here is my code:
134 135 136 / COMPLETE THIS 137 // Returns true if this grid is legal. A grid is legal if no row, column, or //...
Most questions answered within 3 hours.
-
An short-seller in Tesla is worried the latest management
earnings forecast is too aggressive and the...
asked 38 minutes ago -
Question 3 (1 point)
Fill in the blank. Speed Car Rental company found that the tire...
asked 37 minutes ago -
1. A copper wire is 26.61 cm long and weighs 1.265 g. The
density of copper...
asked 15 minutes ago -
Remember that a concept sketch consists of a sketch (or
series of sketches), labels, and complete...
asked 17 minutes ago -
on a newly discovered planet, the period of a pendulum with a
length of 2 m...
asked 19 minutes ago -
Why [M(CN)6] is not organometallic even it has metal
to carbon bond too
asked 26 minutes ago -
mstar electric has a bond issue outstanding that has a 20 year
life, a $1,000 par...
asked 33 minutes ago -
This is a Business Writing Question:
Common Types of Faulty Sentence Logic:
A. Mixed constructions
B....
asked 34 minutes ago -
Skinner asserts that science, and the common view of science, has
been tarnished. Explain his evidence...
asked 37 minutes ago -
A grocery store's receipts show that Sunday customer purchases
have a skewed distribution with a mean...
asked 43 minutes ago -
A 0.035 mol sample of a weak acid, HA, is dissolved in 437 mL of
water...
asked 55 minutes ago -
a sample of Ar gas has a volume of 6.30 L with an unknown
pressure. the...
asked 55 minutes ago