Beginner Java: Sudoku grid

SUDOKU Rules: A puzzle looks like the one on the previous page: a 9x9 grid with some numbers filled in. The challenge is to fill in each empty space with a digit 1 through 9, so that no digit is repeated in any row, column or block. Block is my name for the nine 3x3 blocks outlined in thicker black lines in the picture.

Your Assignment: In the Eclipse workspace of your choice, create a new Java project containing package sudoku. Import the 4 starter files that you downloaded with this assignment(they are at the bottom of this post): Evaluation.java, Grid.java, Solver.java, and TestGridSupplier.java. You won't need to change Evaluation.java or TestGridSupplier.java. Your assignment is to finish Grid.java and Solver.java.

Grid: This class models a Sudoku puzzle that is unsolved, partially solved, or completely solved. The class has a 9x9 array of ints, called values. If a Sudoku square is empty, the corresponding cell in values is zero; otherwise the cell in values contains the number in the Sudoku square. The starter class has a ctor and a toString() method that you should not change. It also has 4 empty methods that you need to write: next9Grids(), isLegal(), isFull(), and equals(). Do not change their names, arg lists, or return types. The comments on the unfinished methods tell you all you need to know about what they should do. Its ok to add more methods to this class. You dont need to provide this class with hashCode() or compareTo() methods. The equals() method is just so that you can compare your puzzle solutions to solutions in TestGridSupplier. (That is, you wont be collecting Grid instances into a hash set a tree set.)

Evaluation.java:

package sudoku;

enum Evaluation

{

ACCEPT, ABANDON, CONTINUE;

}

Grid.java:

package sudoku;

import java.util.*;

public class Grid

{

private int[][] values;

//

// DON'T CHANGE THIS.

//

// Constructs a Grid instance from a string[] as provided by TestGridSupplier.

// See TestGridSupplier for examples of input.

// Dots in input strings represent 0s in values[][].

//

public Grid(String[] rows)

{

values = new int[9][9];

for (int j=0; j<9; j++)

{

String row = rows[j];

char[] charray = row.toCharArray();

for (int i=0; i<9; i++)

{

char ch = charray[i];

if (ch != '.')

values[j][i] = ch - '0';

}

}

}

//

// DON'T CHANGE THIS.

//

public String toString()

{

String s = "";

for (int j=0; j<9; j++)

{

for (int i=0; i<9; i++)

{

int n = values[j][i];

if (n == 0)

s += '.';

else

s += (char)('0' + n);

}

s += " ";

}

return s;

}

//

// DON'T CHANGE THIS.

// Copy ctor. Duplicates its source. Youll call this 9 times in next9Grids.

//

Grid(Grid src)

{

values = new int[9][9];

for (int j=0; j<9; j++)

for (int i=0; i<9; i++)

values[j][i] = src.values[j][i];

}

//

// COMPLETE THIS

//

// Finds an empty member of values[][]. Returns an array list of 9 grids that look like the current grid,

// except the empty member contains 1, 2, 3 .... 9. Returns null if the current grid is full. Dont change

// this grid. Build 9 new grids.

//

//

// Example: if this grid = 1........

// .........

// .........

// .........

// .........

// .........

// .........

// .........

// .........

//

// Then the returned array list would contain:

//

// 11....... 12....... 13....... 14....... and so on 19.......

// ......... ......... ......... ......... .........

// ......... ......... ......... ......... .........

// ......... ......... ......... ......... .........

// ......... ......... ......... ......... .........

// ......... ......... ......... ......... .........

// ......... ......... ......... ......... .........

// ......... ......... ......... ......... .........

// ......... ......... ......... ......... .........

//

public ArrayList next9Grids()

{

int xOfNextEmptyCell;

int yOfNextEmptyCell;

// Find x,y of an empty cell.

// Construct array list to contain 9 new grids.

ArrayList grids = new ArrayList();

// Create 9 new grids as described in the comments above. Add them to grids.

return grids;

}

//

// COMPLETE THIS

//

// Returns true if this grid is legal. A grid is legal if no row, column, or

// 3x3 block contains a repeated 1, 2, 3, 4, 5, 6, 7, 8, or 9.

//

public boolean isLegal()

{

// Check every row. If you find an illegal row, return false.

// Check every column. If you find an illegal column, return false.

// Check every block. If you find an illegal block, return false.

// All rows/cols/blocks are legal.

return true;

}

//

// COMPLETE THIS

//

// Returns true if every cell member of values[][] is a digit from 1-9.

//

public boolean isFull()

{

}

//

// COMPLETE THIS

//

// Returns true if x is a Grid and, for every (i,j),

// x.values[i][j] == this.values[i][j].

//

public boolean equals(Object x)

{

}

}

Solver.java:

package sudoku;

import java.util.*;

public class Solver

{

private Grid problem;

private ArrayList solutions;

public Solver(Grid problem)

{

this.problem = problem;

}

public void solve()

{

solutions = new ArrayList<>();

solveRecurse(problem);

}

//

// FINISH THIS.

//

// Standard backtracking recursive solver.

//

private void solveRecurse(Grid grid)

{

Evaluation eval = evaluate(grid);

if (eval == Evaluation.ABANDON)

{

// Abandon evaluation of this illegal board.

}

else if (eval == Evaluation.ACCEPT)

{

// A complete and legal solution. Add it to solutions.

}

else

{

// Here if eval == Evaluation.CONTINUE. Generate all 9 possible next grids. Recursively

// call solveRecurse() on those grids.

}

}

//

// COMPLETE THIS

//

// Returns Evaluation.ABANDON if the grid is illegal.

// Returns ACCEPT if the grid is legal and complete.

// Returns CONTINUE if the grid is legal and incomplete.

//

public Evaluation evaluate(Grid grid)

{

}

public ArrayList getSolutions()

{

return solutions;

}

public static void main(String[] args)

{

Grid g = TestGridSupplier.getPuzzle1(); // or any other puzzle

Solver solver = new Solver(g);

System.out.println(Will solve + g);

solver.solve();

// Print out your solution, or test if it equals() the solution in TestGridSupplier.

}

}

TestGridSupplier.java:

package sudoku;

//

// All puzzles modeled here are copyright 2016.

//

public class TestGridSupplier

{

//

// A simple puzzle and its solution. Took less than 1 second on my MacBook Pro.

//

private final static String[] PUZZLE_1 =

{

"..3.1.5..",

"8..395..1",

"15.....27",

".8..7..5.",

"62.9.4.13",

".9..2..7.",

"91.....34",

"2..748..9",

"..6.3.2.."

};

private final static String[] SOLUTION_1 =

{

"463217598",

"872395641",

"159486327",

"384671952",

"627954813",

"591823476",

"918562734",

"235748169",

"746139285"

};

static Grid getPuzzle1() { return new Grid(PUZZLE_1); }

static Grid getSolution1() { return new Grid(SOLUTION_1); }

private final static String[] PUZZLE_2 =

{

".........",

"8.1...9.7",

"..75493..",

"7..9.2..8",

"....1....",

"1..3.8..5",

"..84312..",

"2.5...1.9",

"........."

};

private final static String[] SOLUTION_2 =

{

"439187562",

"851623947",

"627549381",

"763952418",

"582714693",

"194368725",

"978431256",

"245876139",

"316295874"

};

static Grid getPuzzle2() { return new Grid(PUZZLE_2); }

static Grid getSolution2() { return new Grid(SOLUTION_2); }

private final static String[] PUZZLE_3 =

{

".97..1.6.",

"2....7..5",

"....9...3",

"85.......",

"..9...5..",

".......32",

"3...7....",

"5..6....1",

".4.1..37."

};

private final static String[] SOLUTION_3 =

{

"497351268",

"236847195",

"185296743",

"853924617",

"629713584",

"714568932",

"361472859",

"578639421",

"942185376"

};

static Grid getPuzzle3() { return new Grid(PUZZLE_3); }

static Grid getSolution3() { return new Grid(SOLUTION_3); }

//

// You can use these to test your Grid's evaluate() method.

//

private final static String[] REJECT_1 =

{

"11.......",

".........",

".........",

".........",

".........",

".........",

".........",

".........",

"........."

};

private final static String[] REJECT_2 =

{

"2........",

"2........",

".........",

".........",

".........",

".........",

".........",

".........",

"........."

};

private final static String[] REJECT_3 =

{

"3........",

"..3......",

".........",

".........",

".........",

".........",

".........",

".........",

"........."

};

private final static String[] REJECT_4 =

{

".........",

".........",

".........",

"....4....",

".....4...",

".........",

".........",

".........",

"........."

};

private final static String[] CONTINUE =

{

"123456789",

".........",

".........",

".........",

".........",

".........",

".........",

".........",

"........."

};

static Grid getReject1() { return new Grid(REJECT_1); }

static Grid getReject2() { return new Grid(REJECT_2); }

static Grid getReject3() { return new Grid(REJECT_3); }

static Grid getReject4() { return new Grid(REJECT_4); }

static Grid getContinue() { return new Grid(CONTINUE); }

static Grid getAccept() { return getSolution1(); }

}