Home > DeveloperSection > Forums > Sudoku puzzle implemented in Java
Mayank Tripathi
Mayank Tripathi

Total Post:397

Points:3117
Posted on    April-23-2015 1:14 AM

 Java Java 
Ratings:


 1 Reply(s)
 531  View(s)
Rate this:
There is a puzzle that is becoming very popular called SuDuko. It is like a cross-word puzzle but with digits 1 thru 9 instead of letters. It started in the U.S. and became very popular in Japan

The board has 9 X 9 boxes laid out in a square. Each box has 9 fields laid out in a 3 x 3 square. Some of the fields are initiated with numbers. An easy game has many initial numbers and a more difficult game has fewer initial numbers.
0,0,0, 0,0,0, 0,1,2
0,0,0, 0,5,1, 3,8,0
0,8,0, 0,0,6, 0,0,0

1,0,0, 2,4,0, 0,7,0
0,0,0, 0,3,0, 0,0,0
0,7,0, 0,6,5, 0,0,3

0,0,0, 4,0,0, 0,2,0
0,5,9, 6,8,0, 0,0,0
8,1,0, 0,0,0, 0,0,0

The object of the puzzle is to replace the 0's (blanks) with numbers 1 thru 9 such that each row, each column and each 3 x 3 box has only the numbers 1 thru 9. Can anyone write a Java code that would solve this very hard puzzle with only 25 starting numbers



Mayank Tripathi
Mayank Tripathi

Total Post:397

Points:3117
Posted on    April-23-2015 6:59 AM

public class sudoku {
  
    // Is every number 1-9 in the given rectangle 0..1 times?
    public static boolean isRectangleLegal(int[][] board, int x1, int x2, int y1, int y2, String errormsg) {
boolean[] isPresent = {false, false, false, false, false, false, false, false, false, false};
  
for (int x=x1; x<=x2; x++) {
    for (int y=y1; y<=y2; y++) {
if (board[x][y] > 0) {
    if (isPresent[board[x][y]]) {
//System.out.println(errormsg + ": multiple " + board[x][y] + "s");
return false;
    }
    isPresent[board[x][y]] = true;
}
    }
}
return true;
    }
  
    public static boolean isLegal(int[][] board) {
// Check the nine blocks.
if (!isRectangleLegal(board, 0, 2, 0, 2, "Block 1")) return false;
if (!isRectangleLegal(board, 3, 5, 0, 2, "Block 2")) return false;
if (!isRectangleLegal(board, 6, 8, 0, 2, "Block 3")) return false;
if (!isRectangleLegal(board, 0, 2, 3, 5, "Block 4")) return false;
if (!isRectangleLegal(board, 3, 5, 3, 5, "Block 5")) return false;
if (!isRectangleLegal(board, 6, 8, 3, 5, "Block 6")) return false;
if (!isRectangleLegal(board, 0, 2, 6, 8, "Block 7")) return false;
if (!isRectangleLegal(board, 3, 5, 6, 8, "Block 8")) return false;
if (!isRectangleLegal(board, 6, 8, 6, 8, "Block 9")) return false;
  
// check the nine columns
if (!isRectangleLegal(board, 0, 0, 0, 8, "Column 0")) return false;
if (!isRectangleLegal(board, 1, 1, 0, 8, "Column 1")) return false;
if (!isRectangleLegal(board, 2, 2, 0, 8, "Column 2")) return false;
if (!isRectangleLegal(board, 3, 3, 0, 8, "Column 3")) return false;
if (!isRectangleLegal(board, 4, 4, 0, 8, "Column 4")) return false;
if (!isRectangleLegal(board, 5, 5, 0, 8, "Column 5")) return false;
if (!isRectangleLegal(board, 6, 6, 0, 8, "Column 6")) return false;
if (!isRectangleLegal(board, 7, 7, 0, 8, "Column 7")) return false;
if (!isRectangleLegal(board, 8, 8, 0, 8, "Column 8")) return false;
  
// check the nine rows
if (!isRectangleLegal(board, 0, 8, 0, 0, "Row 0")) return false;
if (!isRectangleLegal(board, 0, 8, 1, 1, "Row 1")) return false;
if (!isRectangleLegal(board, 0, 8, 2, 2, "Row 2")) return false;
if (!isRectangleLegal(board, 0, 8, 3, 3, "Row 3")) return false;
if (!isRectangleLegal(board, 0, 8, 4, 4, "Row 4")) return false;
if (!isRectangleLegal(board, 0, 8, 5, 5, "Row 5")) return false;
if (!isRectangleLegal(board, 0, 8, 6, 6, "Row 6")) return false;
if (!isRectangleLegal(board, 0, 8, 7, 7, "Row 7")) return false;
if (!isRectangleLegal(board, 0, 8, 8, 8, "Row 8")) return false;
return true;
    }
  
    public static boolean solve(int[][] board) {
 
// Find a position that's still empty.
for (int x=0; x<9; x++) {
    for (int y=0; y<9; y++) {
if (board[x][y] == 0) {
  
    // Try each possibile value in this space
    // and see if the rest of the puzzle can be filled in.
    for (board[x][y]=1; board[x][y]<=9; board[x][y]++) {
if (isLegal(board) && solve(board)) {
    return true;
}
    }
  
    // There is no value that we can put in the first
    // empty space that was found, so the puzzle is
    // unsolvable given the values put in up to this
    // point.
    board[x][y] = 0;
    return false;
}
    }
}
  
// There were no empty spaces to fill in, so the
// puzzle must be solved.
return true;
    }
  
    public static void printBoard(int[][] board) {
        for (int x=0; x<9; x++) {
    System.out.println(x%3==0 ? "+-----+-----+-----+" : "|     |     |     |");
    for (int y=0; y<9; y++)
System.out.print((y%3==0 ? "|" : " ") + board[x][y]); 
    System.out.println("|");
}
System.out.println("+-----+-----+-----+");
    }
  
    public static void main(String[] argv) {
  
int board[][] = {{0,0,0, 0,0,0, 0,1,2},
{0,0,0, 0,5,1, 3,8,0},
{0,8,0, 0,0,6, 0,0,0},
 
{1,0,0, 2,4,0, 0,7,0},
{0,0,0, 0,3,0, 0,0,0},
{0,7,0, 0,6,5, 0,0,3},
 
{0,0,0, 4,0,0, 0,2,0},
{0,5,9, 6,8,0, 0,0,0},
{8,1,0, 0,0,0, 0,0,0} };
  
if (solve(board))
    printBoard(board);
else
    System.out.println("no solution");
    }
}

Don't want to miss updates? Please click the below button!

Follow MindStick