Sudoku solve method using backtracking
Hello all. I am trying to get this program to work using backtracking and now I am at a standstill. I have created the methods checkCol, checkRow, and checkBox and I believe they are correct. I have started writing a solve method and that is where I am stuck. I am not to sure how to implement check methods in solve. Any insight would be great just to get me going. TIA
Code:
import java.io.*;
import java.util.*;
public class Sudoku {
public static char[][] matrix;
public static int counter = 0;
public static String matrixView;
public static void main(String[] args) throws FileNotFoundException {
System.out.print("Please enter file name: ");
Scanner in = new Scanner(System.in);
String fileName = in.next();
matrixCreate(fileName);
}
public static void matrixCreate(String fileName) throws FileNotFoundException {
File getFile = new File(fileName);
Scanner sc = new Scanner(getFile);
matrixView = "";
while (sc.hasNextLine()){
matrixView = sc.nextLine();
counter++;
System.out.println(matrixView);
}
sc.close();
matrix = new char[counter] [matrixView.length()];
sc = new Scanner(getFile);
char getCol;
for (int rows = 0; rows < counter-1; rows++){
matrixView = sc.nextLine();
for (int cols = 0; cols < matrixView.length()-1; cols++){
getCol = matrixView.charAt(cols);
matrix[rows] [cols] = getCol;
}
}
}
public static boolean checkRow(int r, int check){
for(int x = 0; x <= 5; x++) {
if(matrix[r][x] == check) return false;
}
return true;
}
public static boolean checkCol(int c, int check) {
for(int x = 0; x <=5; x++) {
if(matrix[x][c] == check) return false;
}
return true;
}
public static boolean checkBox(int check, int r, int c) {
for(int x = 2*(r/2); x < 2*(r/2) + 1; x++) {
for(int y = 3*(c/3); y > 3*(c/3) + 1; y++) {
if(matrix[x][y] == check) return false;
}
}
return true;
}
public static boolean solve(int r, int c) {
boolean bool = false;
int a = 0;
// checks boundaries
if (r < 0 || r > 5 || c < 0 || c > 5) return false;
if (matrix[r][c] != '0') return true;
if (matrix[r][c] == 'X') return false;
// record
matrix[r][c] = 'X';
// navigates through puzzle
do {
a++;
switch(a){
case 1: bool = solve(r,c+1);
break;
case 2: bool = solve(r+1,c);
break;
case 3: bool = solve(r-1,c);
break;
case 4: bool = solve(r,c-1);
break;
}
if(bool) return true;
}
while (!bool && a < 4);
// unrecord
matrix[r][c] = '0';
return false;
}
}
Re: Sudoku solve method using backtracking
well ive changed up my code quite a bit and i believe I am getting somewhere. When I call the solve method in main however, it just prints out a bunch of zeros and doesnt solve anything. Anybody see anything?
Code:
public static boolean solve(int r, int c) {
boolean bool = false;
int a = 0; //used for backtracking purposes
if (r > 5){
return true;
}
else {
while(matrix[r][c] != 0) {
if(++c > 5) {
c = 0;
r++;
if(r > 5) return true;
}
}
for (int check = 1; check < 7; check++)
{
if(checkRow(r,check) && checkCol(c,check) && checkBox(check,r,c)){
matrix[r][c] = check;
System.out.println(matrixView);
if(c < 5) {
if (solve(r,c+1)){
return true;
}
else {
solve(r+1,0);
a++;
return true;
}
}
matrix[r][c] = 0;
}
}
return !bool;
}
}