EvilZone
Programming and Scripting => Java => : Lykos December 03, 2012, 05:23:19 PM
-
This program solves a hard-coded sudoku puzzle. When I get time over break, I'll add some more features. Should solve any puzzle though, as long as you have the patience to type it in.
/**
* A program to solve "easy" Sudoku puzzles.
*
* @author Lykos
* @version 1.0
*/
public class Sudoku
{
private int[][] problem;
/**
* Creates a 9x9 array of numbers and sets it up as a
* Sudoku problem. Zeros in the array indicate places to be filled in.
* This method is complete. Do not change this method.
*/
public Sudoku()
{
problem = new int[][] { { 0, 0, 4, 0, 0, 0, 0, 6, 7 },
{ 3, 0, 0, 4, 7, 0, 0, 0, 5 },
{ 1, 5, 0, 8, 2, 0, 0, 0, 3 },
{ 0, 0, 6, 0, 0, 0, 0, 3, 1 },
{ 8, 0, 2, 1, 0, 5, 6, 0, 4 },
{ 4, 1, 0, 0, 0, 0, 9, 0, 0 },
{ 7, 0, 0, 0, 8, 0, 0, 4, 6 },
{ 6, 0, 0, 0, 1, 2, 0, 0, 0 },
{ 9, 3, 0, 0, 0, 0, 7, 1, 0 } };
}
/**
* Takes a 9x9 array of numbers and sets it up as a Sudoku problem.
*
* @param problem The array representing the Sudoku problem.
* This method is complete. Do not change this method.
*/
public Sudoku(int[][] problem)
{
this.problem = problem;
}
/**
* Solves this Sudoku problem.
* This method is complete. Do not change this method.
*/
public void solve()
{
if (!solve(0, 0))
{
System.out.println("No solution possible!");
}
}
/**
* Recursively solves this Sudoku problem.
* This method is complete. Do not change this method.
*/
private boolean solve(int row, int col)
{
// Go to next row if at the end
if (col >= 9)
{
++row;
col = 0;
}
// If all spaces are filled, then the puzzle is solved
if (row >= 9)
{
print();
return true;
}
// If the space is marked, go to the next one
if (0 != problem[row][col])
{
return solve(row, col + 1);
}
else
{
// Try all possible numbers
boolean solved = false;
for (int i = 1; i <= 9; ++i)
{
if (isPossibleDigit(i, row, col))
{
// Mark it and recurse on the next box
problem[row][col] = i;
solved = solved || solve(row, col + 1);
// Unmark it after recursing
problem[row][col] = 0;
}
}
return solved;
}
}
/**
* Prints the 9x9 array (problem) as a Sudoku board.
* If the array element is 0, print a . instead of the 0.
*/
public void print()
{
//complete this method
for(int index = 0; index < 9; index++)
{
if((index % 3) == 0)
{
System.out.println("+-------+-------+-------+");
}
for(int i = 0; i < 9; i++)
{
if((i % 3) == 0)
{
System.out.print("| ");
}
if(problem[index][i] == 0)
{
System.out.print(". ");
}
else
{
System.out.print(problem[index][i] + " ");
}
}
System.out.println("|");
}
System.out.println("+-------+-------+-------+");
}
/**
* Returns a 3x3 array representing a "box" of the 9x9 array.
* The parameters boxRow and boxColumn are in the range 0 to 2,
* since there are three rows and three columns of "boxes."
*
* @param boxRow The row number, 0, 1, or 2.
* @param boxColumn The column number, 0, 1, or 2.
* @return The 3x3 array representing a "box" of the 9x9 array.
*/
public int[][] getBox(int boxRow, int boxColumn)
{
int[][] box = new int[3][3];
//complete this method
if(boxRow > 2)
{
boxRow = 2;
}
else if(boxRow < 0)
{
boxRow = 0;
}
if(boxColumn > 2)
{
boxColumn = 2;
}
else if(boxColumn < 0)
{
boxColumn = 0;
}
int rowOffset = boxRow * 3;
int colOffset = boxColumn * 3;
for(int index = 0; index < 3; index++)
{
for(int i = 0; i < 3; i++)
{
box[index][i] = problem[rowOffset + index][colOffset + i];
}
}
return box;
}
/**
* Returns true if the given digit (which must be 1..9) occurs
* in the given row (rows are 0..8), and false otherwise.
*
* @param digit The digit to be searched for in the given row.
* @param row The row to search.
* @return true if the digit is found, otherwise return false.
*/
public boolean occursInRow(int digit, int row)
{
boolean digitCheck = false;
if(digit > 9)
{
System.out.println("Digit too high. Setting to 9.");
digit = 9;
}
else if(digit < 1)
{
System.out.println("Digit is too small. Setting to 1");
digit = 1;
}
for(int index = 0; index < 9; index++)
{
if(problem[row][index] == digit)
{
digitCheck = true;
}
}
return digitCheck;
}
/**
* Returns true if the given digit (which must be 1..9) occurs
* in the given column (columns are 0..8), and false otherwise.
*
* @param digit The digit to be searched for in the given column.
* @param column The column to search.
* @return true if the digit is found, otherwise return false.
*/
public boolean occursInColumn(int digit, int column)
{
//complete this method
boolean digitCheck = false;
if(digit > 9)
{
System.out.println("Digit too high. Setting to 9.");
digit = 9;
}
else if(digit < 1)
{
System.out.println("Digit is too small. Setting to 1");
digit = 1;
}
for(int index = 0; index < 9; index++)
{
if(problem[index][column] == digit)
{
digitCheck = true;
}
}
return digitCheck;
}
/**
* Returns true if the given digit (which must be 1..9) occurs
* in the given 3x3 box, and false otherwise.
*
* @param digit The digit to search for.
* @param box A 3x3 array in in which to search.
* @return true if the given digit is found, otherwise return false.
*/
public boolean occursInBox(int digit, int[][] box)
{
//complete this method
boolean digitCheck = false;
if(digit > 9)
{
System.out.println("Digit too high. Setting to 9.");
digit = 9;
}
else if(digit < 1)
{
System.out.println("Digit is too small. Setting to 1");
digit = 1;
}
for(int index = 0; index < 3; index++)
{
for(int i = 0; i < 3; i++)
{
if(box[index][i] == digit)
{
digitCheck = true;
}
}
}
return digitCheck;
}
/**
* Returns true if the given digit (which must be 1..9) occurs in the box
* containing the location at the given row and column of the 9x9 array, and
* false otherwise. Note that this method is given a row and column in the
* complete 9x9 array, but must search for the given digit in the box containing
* that (row, column) location.
*
* @param digit The digit to be searched for in the appropriate box.
* @param row A row number in the range 0 to 8.
* @param column A column number in the range 0 to 8.
* @return true if the given digit is found in the same box
* that contains the given row and column, otherwise return false.
*/
public boolean occursInBox(int digit, int row, int column)
{
if(digit > 9)
{
System.out.println("Digit too high. Setting to 9.");
digit = 9;
}
else if(digit < 1)
{
System.out.println("Digit is too small. Setting to 1");
digit = 1;
}
if(row > 8)
{
row = 8;
}
else if(row < 0)
{
row = 0;
}
if(column > 8)
{
column = 8;
}
else if(column < 0)
{
column = 0;
}
boolean digitCheck = false;
int[][] boxCheck = getBox((row / 3), (column / 3));
if(occursInBox(digit, boxCheck))
{
digitCheck = true;
}
return digitCheck;
}
/**
* Returns true if the given digit (which must be 1..9) does not occur in the
* given row, or in the given column, or in the box containing this row and
* column, and false otherwise. That is, this digit is a possible candidate for
* putting in this location; there may be other candidates.
*
* @param digit The candidate digit.
* @param row The row in which we wish to place the digit.
* @param column The column in which we wish to place the digit.
* @return true if the candidate digit does not already occur
* in the same row, or in the same column, or in the same box.
*/
public boolean isPossibleDigit(int digit, int row, int column)
{
//complete this method
boolean digitCheck = true;
if(occursInRow(digit, row) || occursInColumn(digit, column) || occursInBox(digit, row, column))
{
digitCheck = false;
}
return digitCheck;
}
}
And pastebin if you want highlighting/more viewing area: http://pastebin.com/L9PKaZHV (http://pastebin.com/L9PKaZHV)
-
IDEA FOR UPDATE
Able to scan a picture as opposed to manually enter it in.
Also since its Java, make it for Android, would be awesome :P
-
IDEA FOR UPDATE
Able to scan a picture as opposed to manually enter it in.
Also since its Java, make it for Android, would be awesome :P
That already exists lol.
-
That already exists lol.
Still gives him a challenge wouldn't you say? :P
I believe in you buddy!
-
Where is the 'main' method?
-
Where is the 'main' method?
Doesn't have one. Just write
new Sudoku().solve();
into your main to try it out.
@Lykos: This looks like an assignment where you only implemented some of the methods.
There are still comments like
//complete this method* This method is complete. Do not change this method.
That means you didn't program all of it and not saying so isn't a nice way.
-
@Deque, nice catch, that's my bad. Yes this was part of an assignment. Credit for a couple of the methods goes to my professor. I'll be sure to specify in the future. This was the last assignment where there was stuff already in there for us, so I forgot about that. My bad, won't happen again :)