Results 1 to 2 of 2
  1. #1
    bdl1127 is offline Member
    Join Date
    Jan 2012
    Posts
    26
    Rep Power
    0

    Default 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

    Java 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;
      }
          
      
      
    }
    Last edited by bdl1127; 09-21-2012 at 01:03 AM.

  2. #2
    bdl1127 is offline Member
    Join Date
    Jan 2012
    Posts
    26
    Rep Power
    0

    Default 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?

    Java 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;
      }
    }

Similar Threads

  1. Anagram solver help using recursive backtracking
    By Schooling in forum New To Java
    Replies: 2
    Last Post: 05-24-2012, 03:47 AM
  2. Recursion Backtracking
    By 6thDAY in forum Advanced Java
    Replies: 1
    Last Post: 03-28-2011, 04:06 PM
  3. Backtracking
    By pali185 in forum New To Java
    Replies: 2
    Last Post: 12-17-2010, 01:08 PM
  4. need help with backtracking
    By Dumisan in forum Advanced Java
    Replies: 9
    Last Post: 02-17-2010, 01:02 PM
  5. help to solve tis problem in method
    By alrebatsd in forum New To Java
    Replies: 4
    Last Post: 06-07-2009, 03:35 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •