/**
* Solve Soduku using backtracking
*
* @author Prateek
*/
class SolveSoduku {
private static final int BLANK = 0;
// Soduku to be solved
private static int[][] soduku;
// Size of Soduku
private final int size;
// Size of the Block in which checking to be done, it is sqrt of size of
// soduku
private int boxSize;
/**
* Constructor
*
* @param soduku
* @throws Exception
*/
public SolveSoduku
(int[][] soduku
) throws Exception { this.soduku = soduku;
if (soduku.length == soduku[0].length) {// Square marix required
this.size = soduku.length;
this.
boxSize = (int) Math.
sqrt(this.
size); } else
}
/**
* Subroutine to solve the Soduku
* @return true if soduku is solvable
*/
public boolean solve(int row, int col) {
if (soduku[row][col] != BLANK)
nextCell(row, col);
else {
// Try the vacant cell with every Number
for (int num = 1; num <= size; num++) {
// check if current number can fit the cell with the given
// constraints
if (isValid(row, col, num)) {
soduku[row][col] = num; // Assuming to be true
if (row == size - 1 && col == size - 1) {
printSoduku();
return true;
}
if (solve(row, col)) // will be called again and other cells
return true; // will be processed
// printSoduku();
soduku[row][col] = BLANK; // Reverting
}
}
}
return false; // will be reached if for any cell none of the number(1-9)
// fit
}
/**
* Find the next free cell
* @return , true if free cell found and currentRow and currentColumn are set
*/
private void nextCell(int row, int col) {
if (col < size - 1)
solve(row, col + 1);
else if (row < size - 1)
solve(row + 1, 0);
}
/**
* check validity of number at the given position, combining the result of 3
* conditions
* @return true, if the number can fit at the current position
*/
private boolean isValid(int row, int col, int num) {
return checkRow(row, col, num) && checkCol(row, col, num)
&& checkBox(row - row % boxSize, col - col % boxSize, num);
}
/**
* Check particular for the existance of given number (in a particular row)
* @return true if the number does not exist
*/
private boolean checkRow(int row, int col, int num) {
for (int c = 0; c < size; c++)
if (soduku[row][c] == num)
return false;
return true;
}
/**
* Check particular for the existance of given number (in a particular col)
* @return true if the number does not exist
*/
private boolean checkCol(int row, int col, int num) {
for (int r = 0; r < size; r++)
if (soduku[r][col] == num)
return false;
return true;
}
/**
* Check particular for the existance of given given BOX
* @return true if the number does not exist
*/
private boolean checkBox(int row, int col, int num) {
for (int r = 0; r < boxSize; r++) {
for (int c = 0; c < boxSize; c++) {
if (soduku[r + row][c + col] == num)
return false;
}
}
return true;
}
int[][] soduku = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 8, 7, 0, 0, 0, 0, 3, 1 },
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 }, { 9, 0, 0, 8, 6, 3, 0, 0, 5 },
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };
SolveSoduku obj = new SolveSoduku(soduku);
obj.solve(0, 0);
// obj.printSoduku();
}
private void printSoduku() {
for (int row = 0; row < size; ++row) {
if (row % boxSize == 0)
System.
out.
println("+-------+-------+-------+");
for (int col = 0; col < size; col++) {
if (col % boxSize == 0)
System.
out.
print(soduku
[row
][col
] == 0 ? " " : soduku[row][col] + " ");
}
}
System.
out.
println("+-------+-------+-------+"); }
}
Ci8qKgogKiBTb2x2ZSBTb2R1a3UgdXNpbmcgYmFja3RyYWNraW5nCiAqIAogKiBAYXV0aG9yIFByYXRlZWsKICovCiBjbGFzcyBTb2x2ZVNvZHVrdSB7CgoJcHJpdmF0ZSBzdGF0aWMgZmluYWwgaW50IEJMQU5LID0gMDsKCgkvLyBTb2R1a3UgdG8gYmUgc29sdmVkCglwcml2YXRlIHN0YXRpYyBpbnRbXVtdIHNvZHVrdTsKCgkvLyBTaXplIG9mIFNvZHVrdQoJcHJpdmF0ZSBmaW5hbCBpbnQgc2l6ZTsKCS8vIFNpemUgb2YgdGhlIEJsb2NrIGluIHdoaWNoIGNoZWNraW5nIHRvIGJlIGRvbmUsIGl0IGlzIHNxcnQgb2Ygc2l6ZSBvZgoJLy8gc29kdWt1Cglwcml2YXRlIGludCBib3hTaXplOwoKCS8qKgoJICogQ29uc3RydWN0b3IKCSAqIAoJICogQHBhcmFtIHNvZHVrdQoJICogQHRocm93cyBFeGNlcHRpb24KCSAqLwoJcHVibGljIFNvbHZlU29kdWt1KGludFtdW10gc29kdWt1KSB0aHJvd3MgRXhjZXB0aW9uIHsKCQl0aGlzLnNvZHVrdSA9IHNvZHVrdTsKCgkJaWYgKHNvZHVrdS5sZW5ndGggPT0gc29kdWt1WzBdLmxlbmd0aCkgey8vIFNxdWFyZSBtYXJpeCByZXF1aXJlZAoJCQl0aGlzLnNpemUgPSBzb2R1a3UubGVuZ3RoOwoJCQl0aGlzLmJveFNpemUgPSAoaW50KSBNYXRoLnNxcnQodGhpcy5zaXplKTsKCQl9IGVsc2UKCQkJdGhyb3cgbmV3IEV4Y2VwdGlvbigiSW52YWxpZCBNYXRyaXgiKTsKCX0KCgkvKioKCSAqIFN1YnJvdXRpbmUgdG8gc29sdmUgdGhlIFNvZHVrdQoJICogQHJldHVybiB0cnVlIGlmIHNvZHVrdSBpcyBzb2x2YWJsZQoJICovCglwdWJsaWMgYm9vbGVhbiBzb2x2ZShpbnQgcm93LCBpbnQgY29sKSB7CgoJCWlmIChzb2R1a3Vbcm93XVtjb2xdICE9IEJMQU5LKQoJCQluZXh0Q2VsbChyb3csIGNvbCk7CgoJCWVsc2UgewoJCQkvLyBUcnkgdGhlIHZhY2FudCBjZWxsIHdpdGggZXZlcnkgTnVtYmVyCgkJCWZvciAoaW50IG51bSA9IDE7IG51bSA8PSBzaXplOyBudW0rKykgewoKCQkJCS8vIGNoZWNrIGlmIGN1cnJlbnQgbnVtYmVyIGNhbiBmaXQgdGhlIGNlbGwgd2l0aCB0aGUgZ2l2ZW4KCQkJCS8vIGNvbnN0cmFpbnRzCgkJCQlpZiAoaXNWYWxpZChyb3csIGNvbCwgbnVtKSkgewoJCQkJCXNvZHVrdVtyb3ddW2NvbF0gPSBudW07IC8vIEFzc3VtaW5nIHRvIGJlIHRydWUKCgkJCQkJaWYgKHJvdyA9PSBzaXplIC0gMSAmJiBjb2wgPT0gc2l6ZSAtIDEpIHsKCQkJCQkJcHJpbnRTb2R1a3UoKTsKCQkJCQkJcmV0dXJuIHRydWU7CgkJCQkJfQoKCQkJCQlpZiAoc29sdmUocm93LCBjb2wpKSAvLyB3aWxsIGJlIGNhbGxlZCBhZ2FpbiBhbmQgb3RoZXIgY2VsbHMKCQkJCQkJcmV0dXJuIHRydWU7CQkJCS8vIHdpbGwgYmUgcHJvY2Vzc2VkCgkJCQkJCQoJCQkJCS8vIHByaW50U29kdWt1KCk7CgkJCQkJc29kdWt1W3Jvd11bY29sXSA9IEJMQU5LOyAvLyBSZXZlcnRpbmcKCQkJCX0KCQkJfQoJCX0KCQlyZXR1cm4gZmFsc2U7IC8vIHdpbGwgYmUgcmVhY2hlZCBpZiBmb3IgYW55IGNlbGwgbm9uZSBvZiB0aGUgbnVtYmVyKDEtOSkKCQkJCQkJLy8gZml0Cgl9CgoJLyoqCgkgKiBGaW5kIHRoZSBuZXh0IGZyZWUgY2VsbAoJICogQHJldHVybiAsIHRydWUgaWYgZnJlZSBjZWxsIGZvdW5kIGFuZCBjdXJyZW50Um93IGFuZCBjdXJyZW50Q29sdW1uIGFyZSBzZXQKCSAqLwoJcHJpdmF0ZSB2b2lkIG5leHRDZWxsKGludCByb3csIGludCBjb2wpIHsKCQlpZiAoY29sIDwgc2l6ZSAtIDEpCgkJCXNvbHZlKHJvdywgY29sICsgMSk7CgkJZWxzZSBpZiAocm93IDwgc2l6ZSAtIDEpCgkJCXNvbHZlKHJvdyArIDEsIDApOwoJfQoKCS8qKgoJICogY2hlY2sgdmFsaWRpdHkgb2YgbnVtYmVyIGF0IHRoZSBnaXZlbiBwb3NpdGlvbiwgY29tYmluaW5nIHRoZSByZXN1bHQgb2YgMwoJICogY29uZGl0aW9ucwoJICogQHJldHVybiB0cnVlLCBpZiB0aGUgbnVtYmVyIGNhbiBmaXQgYXQgdGhlIGN1cnJlbnQgcG9zaXRpb24KCSAqLwoJcHJpdmF0ZSBib29sZWFuIGlzVmFsaWQoaW50IHJvdywgaW50IGNvbCwgaW50IG51bSkgewoJCXJldHVybiBjaGVja1Jvdyhyb3csIGNvbCwgbnVtKSAmJiBjaGVja0NvbChyb3csIGNvbCwgbnVtKQoJCQkJJiYgY2hlY2tCb3gocm93IC0gcm93ICUgYm94U2l6ZSwgY29sIC0gY29sICUgYm94U2l6ZSwgbnVtKTsKCX0KCgkvKioKCSAqIENoZWNrIHBhcnRpY3VsYXIgZm9yIHRoZSBleGlzdGFuY2Ugb2YgZ2l2ZW4gbnVtYmVyIChpbiBhIHBhcnRpY3VsYXIgcm93KQoJICogQHJldHVybiB0cnVlIGlmIHRoZSBudW1iZXIgZG9lcyBub3QgZXhpc3QKCSAqLwoJcHJpdmF0ZSBib29sZWFuIGNoZWNrUm93KGludCByb3csIGludCBjb2wsIGludCBudW0pIHsKCQlmb3IgKGludCBjID0gMDsgYyA8IHNpemU7IGMrKykKCQkJaWYgKHNvZHVrdVtyb3ddW2NdID09IG51bSkKCQkJCXJldHVybiBmYWxzZTsKCQlyZXR1cm4gdHJ1ZTsKCX0KCgkvKioKCSAqIENoZWNrIHBhcnRpY3VsYXIgZm9yIHRoZSBleGlzdGFuY2Ugb2YgZ2l2ZW4gbnVtYmVyIChpbiBhIHBhcnRpY3VsYXIgY29sKQoJICogQHJldHVybiB0cnVlIGlmIHRoZSBudW1iZXIgZG9lcyBub3QgZXhpc3QKCSAqLwoJcHJpdmF0ZSBib29sZWFuIGNoZWNrQ29sKGludCByb3csIGludCBjb2wsIGludCBudW0pIHsKCQlmb3IgKGludCByID0gMDsgciA8IHNpemU7IHIrKykKCQkJaWYgKHNvZHVrdVtyXVtjb2xdID09IG51bSkKCQkJCXJldHVybiBmYWxzZTsKCQlyZXR1cm4gdHJ1ZTsKCX0KCgkvKioKCSAqIENoZWNrIHBhcnRpY3VsYXIgZm9yIHRoZSBleGlzdGFuY2Ugb2YgZ2l2ZW4gZ2l2ZW4gQk9YCgkgKiBAcmV0dXJuIHRydWUgaWYgdGhlIG51bWJlciBkb2VzIG5vdCBleGlzdAoJICovCglwcml2YXRlIGJvb2xlYW4gY2hlY2tCb3goaW50IHJvdywgaW50IGNvbCwgaW50IG51bSkgewoJCWZvciAoaW50IHIgPSAwOyByIDwgYm94U2l6ZTsgcisrKSB7CgkJCWZvciAoaW50IGMgPSAwOyBjIDwgYm94U2l6ZTsgYysrKSB7CgkJCQlpZiAoc29kdWt1W3IgKyByb3ddW2MgKyBjb2xdID09IG51bSkKCQkJCQlyZXR1cm4gZmFsc2U7CgkJCX0KCQl9CgkJcmV0dXJuIHRydWU7Cgl9CgoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgdGhyb3dzIEV4Y2VwdGlvbiB7CgkJaW50W11bXSBzb2R1a3UgPSB7IHsgMywgMCwgNiwgNSwgMCwgOCwgNCwgMCwgMCB9LAoJCQkJeyA1LCAyLCAwLCAwLCAwLCAwLCAwLCAwLCAwIH0sIHsgMCwgOCwgNywgMCwgMCwgMCwgMCwgMywgMSB9LAoKCQkJCXsgMCwgMCwgMywgMCwgMSwgMCwgMCwgOCwgMCB9LCB7IDksIDAsIDAsIDgsIDYsIDMsIDAsIDAsIDUgfSwKCQkJCXsgMCwgNSwgMCwgMCwgOSwgMCwgNiwgMCwgMCB9LAoKCQkJCXsgMSwgMywgMCwgMCwgMCwgMCwgMiwgNSwgMCB9LCB7IDAsIDAsIDAsIDAsIDAsIDAsIDAsIDcsIDQgfSwKCQkJCXsgMCwgMCwgNSwgMiwgMCwgNiwgMywgMCwgMCB9IH07CgoJCVNvbHZlU29kdWt1IG9iaiA9IG5ldyBTb2x2ZVNvZHVrdShzb2R1a3UpOwoJCW9iai5zb2x2ZSgwLCAwKTsKCQkvLyBvYmoucHJpbnRTb2R1a3UoKTsKCX0KCglwcml2YXRlIHZvaWQgcHJpbnRTb2R1a3UoKSB7CgkJZm9yIChpbnQgcm93ID0gMDsgcm93IDwgc2l6ZTsgKytyb3cpIHsKCQkJaWYgKHJvdyAlIGJveFNpemUgPT0gMCkKCQkJCVN5c3RlbS5vdXQucHJpbnRsbigiKy0tLS0tLS0rLS0tLS0tLSstLS0tLS0tKyIpOwoKCQkJZm9yIChpbnQgY29sID0gMDsgY29sIDwgc2l6ZTsgY29sKyspIHsKCQkJCWlmIChjb2wgJSBib3hTaXplID09IDApCgkJCQkJU3lzdGVtLm91dC5wcmludCgifCAiKTsKCgkJCQlTeXN0ZW0ub3V0LnByaW50KHNvZHVrdVtyb3ddW2NvbF0gPT0gMCA/ICIgICIKCQkJCQkJOiBzb2R1a3Vbcm93XVtjb2xdICsgIiAiKTsKCQkJfQoJCQlTeXN0ZW0ub3V0LnByaW50bG4oInwiKTsKCQl9CgkJU3lzdGVtLm91dC5wcmludGxuKCIrLS0tLS0tLSstLS0tLS0tKy0tLS0tLS0rIik7Cgl9Cn0K