Package algs13.xbacktrack.xsudoku

Class MySudoku

java.lang.Object

algs13.xbacktrack.xsudoku.MySudoku

All Implemented Interfaces:

XBacktrackProblem<XMutableCell>

public final class MySudoku
extends Object
implements XBacktrackProblem<XMutableCell>

A Sudoker solver, implemented as a BacktrackProblem where each choice is represented by a MutableCell (a cell we can assign a digit as part of a possible solution to Sudoku). This project represents a more substantial Java program than what we have been working with so far in the course. Search in this file and in algs13.xbacktrack.xframework.MyBacktrackDriver (MyBacktrackDriver.java)for some TODOs that will direct you to what you need to do for this assignment.

Field Summary

Fields

Modifier and Type	Field	Description
private MyBacktrackDriver<XMutableCell>	driver
(package private) final XMutableCell	firstCell
private final XSudokuCell[][]	grid
static final int	GRID_SIZE
(package private) final XMutableCell	lastCell
static final int	SUBGRID_DIMENSION
private final HashMap<Integer,Set<XSudokuCell>>	subgrids

Constructor Summary

Constructors

Constructor	Description
MySudoku(String[] input)	The constructor takes GRID_SIZE array of strings, each of which must be GRID_SIZE in length.

Method Summary

Modifier and Type	Method	Description
boolean	advance(XMutableCell previous)	Determine if the backtracking driver can advance in searching for a solution from the state represented by previous choice.
private XMutableCell	findNextMove(XMutableCell current)
void	initialize(MyBacktrackDriver<XMutableCell> driver)	Initialize the problem.
private boolean	isValid(XSudokuCell cell)
static void	main(String[] args)
String	toString()
private boolean	verify()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

SUBGRID_DIMENSION

public static final int SUBGRID_DIMENSION

See Also:

• Constant Field Values

GRID_SIZE

public static final int GRID_SIZE

See Also:

• Constant Field Values

grid

private final XSudokuCell[][] grid

subgrids

private final HashMap<Integer,Set<XSudokuCell>> subgrids

firstCell

final XMutableCell firstCell

lastCell

final XMutableCell lastCell

driver

private MyBacktrackDriver<XMutableCell> driver

Constructor Details

MySudoku

MySudoku(String[] input)

The constructor takes GRID_SIZE array of strings, each of which must be GRID_SIZE in length. Each character must be a digit. The index of the string corresponds to the row in the grid and the index of the digit in the string corresponds to the column in the grid. If a digit is 0, that signifies that the cell in the grid is mutable and the digit in that cell will be assigned by the solver.

Method Details

initialize

public void initialize(MyBacktrackDriver<XMutableCell> driver)

Description copied from interface: XBacktrackProblem

Initialize the problem. The initialize method must call the track method on the driver to track the starting state.

Specified by:

initialize in interface XBacktrackProblem<XMutableCell>

Parameters:

driver - The driver orchestrating the search for the solution.

findNextMove

private XMutableCell findNextMove(XMutableCell current)

verify

private boolean verify()

isValid

private boolean isValid(XSudokuCell cell)

advance

public boolean advance(XMutableCell previous)

Description copied from interface: XBacktrackProblem

Determine if the backtracking driver can advance in searching for a solution from the state represented by previous choice. If it can, this method must either call the track method on the driver to track the next choice, or it must call the driver's setDone() method.

Specified by:

advance in interface XBacktrackProblem<XMutableCell>

Parameters:

previous - The previous choice

Returns:

true if the current state consists of a valid partial solution, or the current state represents a complete solution (i.e. the last choice required to solve the problem has been made).

toString

public String toString()

Overrides:

toString in class Object

main

public static void main(String[] args)