5

I have started an introductory Java class and the material is absolutely horrendous and I have to get excellent grades to be accepted into the master's degree, hence my very beginner question:

In my assignment I have to write algorithms (no pseudo-code yet) to solve a board game (Sudoku). Essentially, the notes say that an algorithm is specification of the input(s), the output(s) and the treatments applied to the input to get the output. My question lies on the wording of algorithms because I could probably code it but I can't seem to put it on paper in a coherent way.

The game has a 9x9 board and one of the algorithms to write has to find the solution by looking at 3 squares (either horizontal or vertical) and see if one of the three sub-squares match the number you are looking for. If none match then the number you are looking to place is in one of the other 2 set of 3 sub-squares (see image to get a better idea).

Note: The task is not to write a complete solver. Only an algorithm to solve the particular case I have described.

I really can't get my head around how to formulate the solution into the terms described above or maybe it's just too simple, here's what I was thinking:

Input: A 2-dimensional set of data of size 9 by 9 to be solved and a number to search for.

Ouput: A 2-dimensional set of data of size 9 by 9 either solved or partially solved.

Treatment: Scan each set of 3x9 and 9x3 squares. For each line or column of a 3x3 square check if the number matches a line (or column). If it does then move to the next line (or column). If not then proceed to the next 3x3 square in the same line (or column). Rinse and repeat.

Does that make sense as an algorithm written in plain english ? I'm not looking for an answer to the algorithm per se but rather on the formulation of algorithms in plain english.

enter image description here

Note: Apparently this isn't clear: this is not about solving for all possible solutions. This is about solving only this very particular set of rules. I did not make the assignment. In any case, this is not even remotely relevant as this is not the focus of my question.

8
  • 1
    Your description of the problem is not good enough. What you have described is not Sudoku. Make sure you fully understand the problem. Also understand whether your program is to create the game or play the game. Many references exist on the net, try for instance:en.wikipedia.org/wiki/Sudoku
    – NoChance
    Oct 27, 2012 at 4:00
  • How is it not Sudoku ? For the moment the algorithm is only to solve a few situations but I suspect the project will be a full game (create, play, solve) in the last few assignments.
    – ApplePie
    Oct 27, 2012 at 4:04
  • 2
    the only thing that says Sudoku in your description - is the image. You completely left out the requirement of unique number per row, column and 3x3 square. Keep working.
    – c69
    Oct 27, 2012 at 4:55
  • Yes... Because I felt that this one was way easier. I can't just write the entire Sudoku solving rules here just for the sake of completeness...
    – ApplePie
    Oct 27, 2012 at 10:53
  • I want to discuss this specific subtask. I added a note to my OP to make it clearer. I know it's not very intuitive, but as I said this course is absolutely horrible and I plan to file a complaint about it. My 40$ book bought on Amazon is much more useful than the course material...
    – ApplePie
    Oct 29, 2012 at 16:39

1 Answer 1

2

Be annoyingly complete. For instance you don't describe how you take the 9x9 input and create the set of smaller squares. Also that first sentence talks about 9x3, 3x9 squares the second looks at 3x3 squares typo or missed step? It may help to write the pseudo-code(or real code) first then work backwards to a detailed description until you get the hang of it.

It ought to be something like: Break 9x9 input into a set of 9 sub squares by taking the intersection of the first 3 rows, and columns then the next three columns etc. Then examine each sub square for the following property zzz. If it holds preform transformation xyz and continue with the next sub square. If it doesn't hold skip it and continue. etc. Reassemble the 9x9 square from the 3x3 sub squares by this transformation and return it.

2
  • +1. That seems exactly to be the problem - the description is incomplete, so impossible to understand (at least, for me). For example, what is meant by "a number matches a line"? Does it mean the number is already in that line? Or that it could be placed there acoording to SuDoKu rules?
    – Doc Brown
    Oct 29, 2012 at 16:46
  • That's the kind of answer I need ! I will award check mark if no other good answer is posted today.
    – ApplePie
    Oct 29, 2012 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.