Submission details
This is a small group project. While the best group size is 4, I will allow groups of 2 or 4, though a group of 4 will be expected to do more to get a high mark. You should attempt to form the groups yourself – please do so by the end of Week 9 of semester and let me know your group members. I will, over the weekend before Monday of Week 10, organise those not in a group into groups, and send emails out to the different group members.
Eventual assignment submission will be by groups. Ensure only one person does the submission of the assignment per group. The organisation of the marking is difficult enough with groups without having multiple submissions per group to look out for.
You should ensure all group member’s names and email addresses are part the code files and document files that you submit.
You should submit:
The Qt project and all associated files. This must include the .pro project file, any .ui form files, and all the .h and .cpp files. Zip these up together.
A document stating clearly the features that you have implemented, along with a few screen shots to illustrate these features. If a feature is partially implemented or have problems, please indicate this.
Any example Kakuro input files that your program can read.
A short document (I don’t want to use the term ‘user manual’ as some of you will interpret this as a formal document) that describes how to use the program. Don’t make this a big part of what you do – enough so that I can easily start up and know how to play with your application. The screen shots you used in the ‘features implemented’ document above can likely be re-used here.
For a bonus of up to 5% of the assignment marks (but can’t take your mark above 100%), a video (produced by your phone for example) where you demonstrate the features of your working assignment.
Your assignment will be marked primarily on what works, rather than the details of the code. This is not a User Interface class, so for the advanced features that you implement, while a nice user interface may receive a slightly higher mark (within the grade ranges), you are just starting with using Qt, and using the UI components well is something that develops with experience.
Overview of Kakuro
Kakuro puzzles are similar to crosswords, but instead of letters the digits (from 1 to 9) are used. Instead of clues going across and down, you are given the sum of the values across or down. There is the constraint that the digits 1 to 9 can only be used once in any ‘word’ going across or down. The board’s squares need to be filled in with these digits in order to sum up to the specified numbers. Below is an example Kakuro problem with a 13x13 grid (effectively a 12x12 problem as you need an extra row at the top, and a column at the left, in which to put ‘down’ or ‘across’ clues.
At any point you can use the down or across clues to deduce some values in the puzzle, and then use these values to help deduce other values.
For example, in the bottom middle there is the section shown to the right. For the column with sum of 4, the two values have to be 1 and 3 (as 2 and 2 not allowed). The 3 has to be at the top, as if it is at the bottom, then as the bottom ‘across’ adds to 8, the left value will be 5. But then the ‘down’ that sums to 16 does not have a solution, as you can’t have 5+ (value from 1 to 9) that sums to 16. This means that you have to have 3, 1 in the ‘down’ that sums to 4, and 9, 7 in the column that adds to 16: as shown on the
left.
You can try the puzzle online at www.kakuros.com, which provides an interactive web page to help you play Kakuro.
The Assignment
In this assignment I would like you to use Qt to develop a program with a graphical user interface to help the user solve Kakuro problems.
A minimal program that will give you at least a P1 grade should:
- Display the grid for a Kakuro problem – you program should at least display a 13x13 grid, but you can allow the program to display a range of sizes – smaller and possibly larger.
- Allow the user to initialise the Kakuro puzzle. This could be done, for example, by:
- a. Reading the information from a text file. Possible formats for the text file will be discussed in a lecture.
- b. Selecting a cell with the mouse and setting up the problem interactively.
- c. Generating a random problem (this is one of the possible extensions for a higher grade)
- Allow the user to select a grid location and ask that the possible values be determined and displayed in the grid location. Note that if there is only one possible value, you should not make this the grid location’s final value – the user needs to do this (but see extensions below).
- Allow the user to select a value from the possible values displayed in a grid location as the final value. When this occurs, the other grid locations where you have asked for the possible values to be displayed should all be updated to use this additional information.
For particularly good implementations of 3 and 4 you can receive a small number of additional marks.
For a higher grade you need to do more. Below are some possible extensions you can do to your ‘P1’ level program, along with some examples of sensible combinations of extensions that will get you a HD grade.
Possible Extensions to obtain a higher grade
Highlight cells where there is only one possible value. How you highlight the cell is up to you.
Provide an option to calculate and display the possible values for every grid location where the value is not yet specified.
Determine if a solution can’t be found using the current values set in the grid - for example by conflicting requirements for down or across values or sums. For example, a ‘down’ clue may require a particular grid location to have a value of (say) 2, but the ‘across’ set of values already has a 2 in it. This means that a wrong choice was made by the user previously.
Keep track of changes to the grid values, and allow the user to ‘back-track’ if they have made an error.
Keep track of the operations requested by the user to the grid locations, and allow the user to ‘replay’ the way the solution was found (for example, using time delay between ‘steps’, or to use a key or button to ‘step’ forward in the replay. The way you do this is up to you. You will get additional marks for an easy to follow replay of the steps taken.
If you do option 5 above, try to automate the finding of a solution. This is not trivial as sometimes you need to consider the possible values of multiple grid positions to determine the correct value of a grid position. You may be able to do a partial automation - do what you can and then let the user set a grid position’s value before continuing on. You should be able to step through the automated solution. This is a hard extension - you can get a good mark for this part for a reasonable attempt.
Save a puzzle at any point, along with the information about the steps taken, so that can reload the puzzle and either backtrack or continue from the current set of values.
Generate random Kakuro puzzles - generate a random (but reasonable) puzzle ‘boards’, then generate a random ‘solution’ (fill the board consistently with digits 1 to 9), and then generate the appropriate down and across clues.
You can obtain a HD by implementing:
- Extensions 1, 2, 3, 4, or:
- Extensions 4, 5, 6, or:
- Extensions 4, 5, 7, or:
- Extension 1 and 8, or:
- Suggesting an alternative set of extensions to the course coordinator and obtaining approval for this being the goal for achieving a HD.
Generally, you will need 3 or 4 extensions to get a HD, depending on how hard the extensions are. For reasonably sized extensions, each working extension takes you up a grade (C, D, HD). Some easy extensions (such as 1 and 2 above) are too small to take you up a whole grade, so in the first suggested set of extensions above, 1 and 2 together take you to a Credit grade. Some extensions are difficult, and a reasonable attempt will get you the additional grade. An example of this is extension 6.