Program to Solve Sudoku
So I have a programming assignment to write a program that solves any sudoku puzzle its given. We've been doing simple stuff so far and this is kind of a cullmination of everything.
Here is the important stuff in the assignment:
Your program, which will be called Sudoku.java, will read from an input file whose name is given on the command line, solve the puzzle encoded in that file, print the original puzzle and its solution to standard output, then quit. The input file will consist of a space separated list of 81 numbers giving the nine rows of the puzzle from left to right, and top to bottom. Extra intervening white space (spaces, tabs, and newlines) will be ignored by your program. In this file, a blank cell will be represented by the number zero. Thus an input file for the above puzzle would look like:
Input file:
0 0 0 5 3 0 0 0 4
0 8 3 9 0 1 0 0 0
6 1 0 0 2 8 7 0 0
0 0 0 0 0 0 2 0 7
0 4 0 1 0 7 0 8 0
7 0 9 0 0 0 0 0 0
0 0 1 7 4 0 0 5 8
0 0 0 6 0 3 9 7 0
2 0 0 0 9 5 0 0 0
Notice that extra lines and spaces may be included in order to make the 揵ox?structures more visible, but this is not part of the file format. A single line of 81 numbers would look the same to your program. You are not required to check the validity of the input file in any way, and you may therefore assume that your program will be tested only on files representing valid Sudoku puzzles.
Program output will be formatted in a similar manner, except that blank cells will be represented by dashes rather than zeros. Extra lines and spaces will be included to reveal the box structure, and one extra line will separate puzzle from solution. Thus the corresponding output (to standard out) would look like:
Output:
- - - 5 3 - - - 4
- 8 3 9 - 1 - - -
6 1 - - 2 8 7 - -
- - - - - - 2 - 7
- 4 - 1 - 7 - 8 -
7 - 9 - - - - - -
- - 1 7 4 - - 5 8
- - - 6 - 3 9 7 -
2 - - - 9 5 - - -
9 2 7 5 3 6 8 1 4
4 8 3 9 7 1 5 2 6
6 1 5 4 2 8 7 9 3
1 6 8 3 5 9 2 4 7
5 4 2 1 6 7 3 8 9
7 3 9 2 8 4 1 6 5
3 9 1 7 4 2 6 5 8
8 5 4 6 1 3 9 7 2
2 7 6 8 9 5 4 3 1
Your program will represent the puzzle grid as a 2-dimensional int array. It is recommended (though not required) that this array be of size , so that if you call the array grid for example, you can ignore index zero, and refer the seventh row, fifth column of the puzzle as grid[7][5] rather than grid[6][4]. A small amount of memory is wasted in doing this, but it is worth the gain in clarity.
Required Features
If too many or too few command line arguments are given, or if the file specified on the command line does not exist or cannot be opened, your program will follow the same procedure outlined in programming assignment 3. Your program will define and use static methods with the following names and signatures:
static void usage()
static void getGrid(int[][] G, Scanner sc)
static void printGrid(int[][] G)
static boolean isSolved(int[][] G)
Method usage() will print a usage message to standard error then quit, as in programming assignment 3 and in the example ReadIntegers.java on the webpage.Method getGrid() will extract integers from the Scanner object sc and place them in the int array G, row by row. At the time getGrid() is called, the Scanner sc will have been initialized to point to the input file by the calling function main() in a try-catch statement. Method printGrid() will print the contents of its array argument to standard output in the format described above. In particular, zeros will be printed as dashes and the box structure will be apparent from the spacing. Method isSolved() will return true if all entries in its array argument are non-zero, and false otherwise.
Wow thats long. Looking at the assignment I'm just totally overwhelmed and I don't know where to start. Could someone help me break this down into smaller less overwhelming steps. Cause Im lost.
[4129 byte] By [
mrfredmana] at [2007-11-27 6:25:42]
Hi
Seems like a nice excercise, :)
The way i would tackle this is by doing the stuff i know first. I know assignments can be overwhelming, i used to have the same problem, until someone told me the most obvious thing...." Take it one line at a time".
1) You need to be comfortable enough with reading lines from a file. Just take any *.txt file and read from it, whatever it may contain. then play around with carriage returns and such things.
2) Play around with the Scanner class, it will become your best friend in this assignment by the looks of it, :).
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Scanner.html
3)Try to become a Sudoku expert and see exactly how they get solved.
And well ...take it one line at a time, see what you can do and come back with questions that have a specific topic, otherwise most people on this forum will, not be so happy reading through all that lol
Smilies all round
:) :) :) :)
Message was edited by:
monk3y
Some of the chunks I'd consider easier would be reading from standard input and writing to output.
The more interesting part, IMHO, is how to solve the su doku. Contrary to what I do as a human, I'd use a simple backtracking algorithm. If a cell is already filled (contains non-zero), just go ahead with the next one. If it wasn't, try all numbers from 1 to 9, see which ones generate conflicts; for any that don't conflict with anything, go ahead with the next field. If there's no next field, you have a complete solution.
You will need some conflict detectors for the su doku rules, like is the same number already in the same row, column or box.
I did write a Java program dealing with (6 by 6) su doku puzzles once, I believe I have it on a CD-ROM somewhere. I considered writing Row, Column and Box classes for manageing the rules, but rather just wrote a Group class, so a group could be either a row, box or column, in any case the rule was that the same number could only appear once in the group.
OleVVa at 2007-7-12 17:45:46 >
Just understand that it's been done before and can be done again. Break down big steps into small steps, solve the small steps along the way, combine and you'll have your solution before you know it.
Understand though that thoughout, it will be your solution and yours alone. We can help with specific stumbling blocks that you hit along the way, but ultimately, you will be the one creating, coding, testing, and running.
Good luck!
So I'm having trouble with the getGrid class. Because I've only written a few arrays before. I've got it scanned. But I don't know how to print it into an array. This is all I have:
static void getGrid(int[][] G, Scanner sc)
Scanner sc = new Scanner(System.in);
while(sc.hasNextint()){
G = sc.nextInt();
Hi
I'm guessing you want to read whatever value you get in sc.nextInt() int the array G? if so, you have to specify which spot in the array you would like it to go into
So you code would look something like this
G [row][column] = sc.nextInt();
Where row and column are integer representations of where the value is been getting placed in the G array.
If you leave your statement the way you have it now in your code
G = sc.nextInt();
That means..."Hey i want to put whatever sc.nextInt()'s value is in a Object array G"...and the compiler is all like..."WTF mate?" but if you want to save the value you need to give it a specific storage space within the object by refrencing the row and column
HTH
Smilies all round
:) :) :) :)
I believe the assignment said you could assume that the input contains 81 numbers? If so, you don't need hasNextInt() to determine if there is another number. It's probably simpler to use a double for loop to iterate over the cells of your two-dimensional array and just use sc.netInt() to read the next number into the current cell.
OleVVa at 2007-7-12 17:45:46 >
I would advise you to use recursion. When the program comes to each "cell", it should check the whole grid for each option from 0-9. If done correctly, you can do it, but that approach might take loads of time, like O( N^4 ) or something...
I couldn't agree more. When I said "a simple backtracking algorithm", that implied recursion.
OleVVa at 2007-7-12 17:45:46 >
But the advantage of such a recursion algorithm would be not having your head explode while trying to devise an iterative solution... As always it's a tradeoff between your mental capacity and the pc's capacity.
> So you code would look something like this
>
> G [row][column] = sc.nextInt();
I'm a bit confused as to how I would actually code that. Do variables go in the place of 'row' and 'column' or do i leave them blank? How does it know to use the numbers from the scanner or does it just do all that automatically?
You'd want to use 2 for loops or 2 while loops to iterate through the data.
For instance:
for(int Row = 0, While Row is < LENGTH, Increment Row)
for(int Col = 0, While Col is < LENGTH, Increment Row)
data[Row][Col] = next piece of data in file.
I'm very interested in how you will begin to solve this. What ideas did you have in mind?
Another idea to perhaps confuse things even more:
Realize that while sudoku seems like it's dealing with numbers, they aren't numbers in the normal sense. You're not adding, subtracting or doing anything "numerical" with the data. Rather you're just seeing if a symbol is used once and only once in each collection of rows, columns and small 3x3 grids. The data is more closely represented by a an enum clas than by numbers. You might want to consider using enum and enum collections here. I've done this successfully with a Sudoku program before.
/P
Here is an example:
import java.util.HashSet;
import java.util.Set;
/**
* enumeration of objects numbered one through nine
* @author Pete
*
*/
enum SudokuNumber
{
noNumber(""), // to give one an ordinal of 1
one("1"),
two("2"),
three("3"),
four("4"),
five("5"),
six("6"),
seven("7"),
eight("8"),
nine("9");
private String numString;
/**
* static set that has all of the real SudokuNumbers. Doesn't have noNumber
*/
private static Set<SudokuNumber> fullSet = new HashSet<SudokuNumber>();
private SudokuNumber(String numStr)
{
this.numString = numStr;
}
public String getNumberString()
{
return numString;
}
/**
* static getter for fullSet
* @return
*/
public static Set<SudokuNumber> getFullSet()
{
return fullSet;
}
/**
*Static initializer code
*initialize fullSet to contain all of the SudokuNumbers
*/
static
{
for (int i = 1; i < SudokuNumber.values().length; i++)
{
fullSet.add(SudokuNumber.values()[i]);
}
}
}
Message was edited by:
petes1234
> > So you code would look something like this
> >
> > G [row][column] = sc.nextInt();
>
> I'm a bit confused as to how I would actually code
> that. Do variables go in the place of 'row' and
> 'column' or do i leave them blank? How does it know
> to use the numbers from the scanner or does it just
> do all that automatically?
Have you used arrays before? That might be a place to start. If you are more comfortable calling the variables i and j rather than row and column, you can just do that, or rowNumber and columnNumber or what you find appropriate.
OleVVa at 2007-7-12 17:45:47 >
> > So you code would look something like this
> >
> > G [row][column] = sc.nextInt();
>
> I'm a bit confused as to how I would actually code
> that. Do variables go in the place of 'row' and
> 'column' or do i leave them blank? How does it know
> to use the numbers from the scanner or does it just
> do all that automatically?
It's important what you put i those arrays. My recommendation is that you don't just put in "numbers" at each spot. Rather, put in something much "smarter" than numbers -- objects. You can have a "cell" object that knows its location (its array indices), that knows how to connect with other objects that keep track of the contents of each row, or column, or small 3x3 grid. With these connections, it can find out what numbers have been used up, what numbers are available to itself, and it knows what entities to contact when it itself has been filled with a number. You can make it so flexible that it is able to interact w/ a console interface or a GUI if desired. Also the cell could have a boolean that determines whether it is "fixed" (contains one of the starting condition numbers) and would thus be immutable, or not-fixed and thus could possibly hold most any number.
The possibilities are endless.
Good luck!
/Pete
Addendum: please also note that in my situation ,substitute "enum SudokuNumber" for every place in the statements above where I mention the word "number". My setup thus is an array of SudokuCells that each can hold a single SudokuNumber, and each cell knows what SudokuNumbers its rowmates, columnmates, and smallGridMates (3x3 grid) are holding. Also note that I use Sets a lot to hold this info since order is not important and duplication is not desired.
