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 + "================= ";

}

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;

}

public boolean rowIsLatin(String[][] x, int i) {

boolean found[] = new boolean[9];

int n;

for(n=0;n

found[n] = false;

for(int j=0;j

{

n = Integer.parseInt(x[i][j]);

found[n-1]=true;

}

for( n=0;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[n] = false;

for(int i=0;i

{

n = Integer.parseInt(x[i][j]);

found[n-1]=true;

}

for( n=0;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

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[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

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("--------------------------------------------------"); }

}