|
Submitted for the Degree of B.Sc. in Computer Science 1998-1999 |
Final
Year Project Report Puzzle Solving Gary Duncan |
|
Except where explicitly stated all work in this report, including appendices, is my own and was carried out during my final year. It has not been submitted for assessment in any other context. |
Nonograms are logic puzzles that originated in Japan. Introduced to Britain by their creator Non Ishida and James Dalgety they have become popular puzzles which are featured in The Sunday Telegraph under the name Griddler. A Nonogram puzzle consists of a rectangular grid with one set of clues for each row and column of the grid. Clues are in the form of sets of numbers which correspond to the lengths of blocks of shaded squares on that particular row or column. Each block of shaded squares is separated from any following blocks by at least one blank square and solving the clues enables the grid to be shaded to produce a picture.
Problems such as Nonograms can be expressed as Constraint Satisfaction Problems and as such are well suited to solution by computer. This project identifies a suitable data representation and defines appropriate constraints such that solutions can be produced for any given Nonogram puzzle. The model is implemented in C++ using the Constraint Programming Tool ILOG Solver.
In addition a graphical interface to the Nonogram puzzle has been developed which allows users to solve puzzles on the computer. The interface is linked to the solver in such a way that the user can solve any puzzle currently loaded.
This project would not have been possible without the help and support of the following people.
Ian Gent, project supervisor, for support and ideas provided during the course of this project.
ILOG for kindly giving permission to include the Magic Solver solution.
The loyal group of family and friends who carried out the user interface evaluation of the Helper.
Alex de Jong and Danny Woods the independent testers.
Bert Richardson, Richard Tullett and Tom Pirrie for proof-reading this report.
Ali Richardson for support throughout the project and letting me use the computer when she wasnt solving Nonograms.
Contents
Introduction Nonograms are logic puzzles that originated in Japan. A Nonogram consists of a rectangular grid with one set of clues for each row and column of the grid. Solving the clues determines which cells in the puzzle are to be shaded to produce a picture. Clues are of the form x1.x2. . .xn, which translates as x1 shaded cells followed by at least one blank cell, followed by x2 shaded squares followed by at least one blank cell etc.
For example, the grid
depicted in fig. 1 can be solved to give the picture in fig. 2.
Fig. 1 Blank grid with clues |
Fig. 2 Completed puzzle |
This aim of this project was to identify a suitable representation of the Nonogram puzzle and develop a program capable of solving Nonogram puzzles. This program was to be linked to a graphical front-end which helped the user to solve the puzzles. These aims are summarised in the following three objectives :
The development cycles of both components has been largely based on the prototyping approach described by Pressman (Pressman, 1992). Pressman explains that prototyping is suitable for projects where the customer has defined a set of general objectives but has not identified detailed input, processing and output requirements. In addition, it is also appropriate in situations where the developer is unsure of the efficiency of an algorithm or the facilities provided in a development environment. It was felt that the Solver application fell into both categories as it was developed using a toolkit of which the developer had no prior experience and which has a steep learning curve. To a lesser extent the Helper also fell into the second category because it was implemented in Java, a language in which the developer also had little experience.
The following chapter (Chapter 2) sets this project in the context of other work carried out in the field of Constraint Satisfaction Problems. In addition the facilities provided by the ILOG Solver C++ Toolkit are examined and various Nonogram Helper programs available on the Internet are discussed.
Chapter 3 describes phases 1 and 2 of the ILOG development cycle and details the requirements of the Helper component.
Chapter 4 details the design method chosen for each component and concludes with a high level description of the project architecture. Chapter 5 contains more detailed design and implementation details.
Chapter 6 examines the methods used to verify and validate the software. A more detailed description of test strategy and test cases is included as Appendix C.
Chapter 7 critically evaluates the systems to establish strengths and weaknesses and to identify which objectives have been met.
Chapter 8 summarises the success of the project. Particular attention is paid to problem areas and possible future developments which could enhance the functionality of the system.
Several papers and books have been read in preparation for this project and this chapter seeks to describe areas of work which are related to the Nonogram Solver. Section 3.2 provides an introduction to Constraint Satisfaction Problems and this introduction is expanded in section 2.3 with a discussion of the facilities provided in ILOG Solver. This chapter concludes with an investigation of other Helpers available on the Internet.
An initial background in Constraint Satisfaction Problems was gained by reading Barbara Smiths paper entitled A Tutorial on Constraint Programming (Smith, 1995). This paper provided a thorough introduction to the components of a Constraint Satisfaction Problem (CSP) and the mathematical basis behind the technique. Also discussed were techniques used by tools such as Solver to reduce the problem space and efficiently search for a solution. The paper contains examples in ILOG Solver and although the syntax has changed since 1995 the principles remain the same.
ILOG Solver (hereafter referred to as Solver) has a very steep learning curve and the ILOG Solver User Manual (ILOG, 1997) provided an excellent tutorial in the use of the toolkit. A series of examples examine the techniques used in tackling CSPs and introduce the various variable types and constraints available in the tool. One of these examples is examined in the following section.
Ueda and Nagao of the Tokyo Institute of Technology have investigated the NP-completeness of the Nonogram puzzle (Ueda, 1996) by exploring the concept of a class of NP problems called Another Solution Problems (ASP). An ASP is defined as
For a given NP problem X, ANOTHER SOLUTION PROBLEM for X (ASP for X) is to ask, for a given instance I of X and its solution, whether there is another solution for I.
The paper demonstrates the NP-completeness of ASP for Nonograms.
The Nonogram Solver Repository (Simpson, 1999) maintained by Steven Simpson and hosted at the University of Lancaster is an extremely useful reference website for all aspects of Nonograms. Information is provided about the origin of the puzzles, how to create them, how to solve them and links to other on-line resources. Some example puzzles are supplied, and an automatic solver program is available both on-line, and as downloadable software.
The project supervisor, Ian Gent, has investigated representing the Battleships puzzle in Solver (Gent, 1998). The Foot Note detailing his approach was helpful in pointing out particular issues to be aware of when using Solver for the first time.
Many problems in the real world fall in into the category of CSPs. These problems tend to be in areas such as scheduling and time-tabling where there are a number of different variables which are dependent on the values of other variables for a valid solution to be identified. Problems such as these are generally NP-complete and take an exponential length of time to solve by exhaustive trial and error.
More formally, a CSP is a problem which can be represented in terms of its variables, the domains of those variables and the constraints which are imposed on them. A solution to the problem is an assignment of values to all variables such that all constraints are satisfied simultaneously. These terms are best explained through an example.
In this problem there are several classrooms available, each of a certain size. There is also a set of classes, each of which has a certain number of students in it. The goal is to allocate a room to each class with the constraint that the number of students taking that class is less than or equal to the size of the room. A valid solution is any pairing of rooms and classes where this constraint is satisfied.
Variables : The variables in this problem are the classes and the classrooms. Each class is characterised by the number of students taking it and each classroom is defined by the number of students it can accommodate.
Domains : Viewing the problem as allocating classrooms to classes it is possible to define the domain of each class as the set of all classrooms which can be assigned to it.
Constraints : The constraint described in the paragraph above can be expressed as the number of students in each class must be less than or equal to the size of the assigned room. This automatically implies that any rooms that are too small should be excluded from the domain of each class.
Rather than search exhaustively through all combinations of rooms and classes, a constraint programming tool first uses the information it has been given to reduce the domains of the variables. The process of constraint propagation methodically considers the constraints and their impact on each variable. Any values in the domain of a variable which do not conform to the constraints are removed. The effect of that domain reduction is then considered for other relevant variables and if necessary values are removed from their domains also.
For example, although each class can initially be allocated to any classroom, constraint propagation would consider the domain of each variable and remove any rooms which are too small. In addition, when a classroom is allocated to a class that room must be removed from the domains of all other classes.
One technique for propagating constraints is Arc Consistency. A binary constraint between two variables x and y is arc consistent (AC) if for every value a in the domain of x there is a corresponding value b in the domain of y which, when x = a and y = b, satisfies the constraint. This operation reduces the domain of x and so can be carried out in reverse to ensure that the constraint between y and x is AC. If every arc in a CSP is made AC then the whole problem is said to be AC.
As new constraints are introduced or a domain is reduced the problem can again be made AC. This allows constraint and assignment information to propagate through the problem.
When all domains have been reduced as far as possible the remaining search space must be searched to find a solution. The most common search method used in CSPs is depth first search (DFS). Whenever the DFS algorithm is given the choice of searching several states it always chooses one which is farthest from the start state. The power of a constraint programming language is that it combines propagation with search. This reduces the size of the search tree while searching, so reducing the time taken to find a solution.
DFS is capable of finding all solutions which exist for a problem. By implication it is also capable of concluding that no solution exists if it does not find one after having searched the entire search-space. However, it may not be desirable to identify all solutions as the user may be content with the first solution. Alternatively there may be an optimal solution, where optimal is defined as some function on the variables.
In closing, representing a problem as a CSP rather than adopting a mathematical approach brings two main benefits. Firstly, the representation is often much closer to the problem as CSP variables directly correspond to the entities in the problem. Secondly, CSP algorithms can often find solutions faster than other programming techniques since powerful methods such as propagation during search can be used to reduce the size of the search-space.
The development of constraint programming tools such as the ILOG Solver C++ toolkit allow CSPs to be more easily modelled and solved by computer. In particular, Solver defines classes of constrained variables which are used to represent entities in the problem. Constrained variables are C++ objects and Solver includes classes of variables to represent integers, floating-point numbers, Booleans and sets, among others. It is possible to combine variables with each other and with constants to form expressions that may then be used in constraints. In this way it is possible to define new objects which contain constrained variables.
Each constrained variable has an associated domain a set of the values which the variable could take on. In the room allocation example the room number to which a class is assigned may be represented as a constrained variable. The domain of that variable would be the numbers of the rooms which are available. Solver systematically reduces the domain of constrained variables when new constraints are added. This means that values which do not satisfy constraints are removed.
A constraint is a rule which must be true at all times for the variables it is expressed on. A constraint may be an expression, eg. class_size <= room_size, or more general such as all values in an array must be different. Solver provides a range of appropriate constraints with each class.
Finally, each Solver application requires an instance of the class IlcManager to handle input, output, memory allocation and various other services.
The Solver User Manual (ILOG, 1997) proved to be a very valuable resource when learning to use the toolkit. In particular, the Magic Square puzzle, discussed in section 4.8 of the manual described many of the facilities which were used in the Nonogram Solver. To aid the reader to understand the features available in Solver the following section discusses the Magic Square puzzle and examines the data representation and modelling techniques employed.
A magic square is a square
matrix where the sum of every row, column and diagonal is equal to the
same value; the numbers in the magic square are consecutive and start
with 1. Heres a magic square of size 3:
8 |
3 |
4 |
1 |
5 |
9 |
6 |
7 |
2 |
A suitable representation for a magic square of size n would be as an
array of n2 integers because it is not possible for Solver to search
any data structure which is not one dimensional. Solver provides
a class IlcIntVarArray which represents an array of constrained integer
variables. Each element in the array may take any value from 1
to n2. The following excerpt of code declares an array called
Square of the appropriate size.
IlcIntVarArray Square(m, n*n, 1, n*n);
The parameters correspond to the manager m, the size of the array, the minimum value and the maximum value.
Each element in Square must be different and Solver provides a pre-defined constraint IlcAllDiff to express this. The following line illustrates how constraints are added to the manager.
m.add(IlcAllDiff(Square));
The sum of the numbers from 1 to n2 can be calculated with the formula :
n*n*(n*n + 1) / 2
As there are n rows in the magic square the sum of each row, column and diagonal must be equal to the above sum divided by n :
sum = n*(n*n+1)/2;
One of the limitations of Solver is that it is impossible to express constraints on subsets of an array. For this reason it is necessary to create an array of size n for each row, column and diagonal. The constraint
IlcSum (array) == sum
can then be expressed on the array. The technique used in the Magic Square example uses a macro to create the array and express the constraints. The macro is called for each row, column and major diagonal. For the purpose of clarity the macro has been expanded to show how the row constraints are expressed.
for (row = 0; row < n; row++){
IlcIntVarArray array(m, n);
for(col = 0; col<=n-1; col++)
array[col] = Square[n*row+col];
m.add(IlcSum(array) == sum);
}
In pseudo-code this would be
Solver now has sufficient information about the problem to be able to search the remaining state space. This is achieved by adding the goal IlcGenerate to the manager. In this case a first-fail approach has been adopted, meaning that variables with the smallest domains are assigned to first. This is indicated by specifying IlcChooseMinSizeInt.
m.add(IlcGenerate(Square,IlcChooseMinSizeInt));
The listing of the Magic Square solution is included in Appendix D.
An investigation of Helper software available on the Internet was carried with the intention of capturing possible functionality and user interface requirements for this project. Several Helpers were identified but only three were deemed to be sufficiently different from each other to warrant critical evaluation.
These were :
Location : http://www.pro.or.jp/~fuji/java/try/nonogram/index-eng.html
Location : http://www.phy.hw.ac.uk/~phy_af/nonograms.html
Location : http://www02.so-net.ne.jp/~kajitani/cgi- bin/PBNPuzzle.cgi/10x10/19971229-KAJ.pbn
The features present in each Helper are described in this chapter while a more critical view is taken in Chapter 3 when the requirements for the Nonogram Helper are captured. For each application particular attention was paid to three areas :
This sections deals with the style and colours used to display the Nonogram grid and clues on the screen.
Each cell in a Nonogram puzzle can generally take on three different states : SHADED denotes that the cell is definitely shaded. BLANK denotes that the cell is definitely not shaded; CLEAR denotes that it is not known whether the cell is shaded or not. However, some Helpers provide other states so that the user may make guesses and be able to differentiate these from known cells.
This section describes the functionality present in the Helper. This can range from a simple Helper which only allows the user to shade squares to a more sophisticated application which can check the puzzle or allow the user to create a new puzzle.
Nonogram : Solver, Fujiwara
Several of the online solvers used an applet known as Illust Logic developed by Hirofumi Fujiwara. This applet provided the user with facilities to create new puzzles, generate puzzles and solve the puzzle by hand. In addition, a reduced-functionality version of this applet is available for users who wish to place a single puzzle on a webpage without incorporating the additional functionality described below.
An example of the cut-down version of Fujiwara's solver can be found at http://www.pro.or.jp/~fuji/java/puzzle/nonogram/013-eng.html.
Presentation of the Grid
The grid (Fig.
3) was displayed using grey lines on a white background. Every
fifth line was shaded black to assist the user in counting the number
of squares. Contrary to way Nonogram puzzles are normally set
out Fujiwara's helper displayed clues above and to the left of the grid.
Each clue was displayed in a separate box in the clue grids and could
be shaded grey by clicking on it, thus marking it as used.
Cell States Available
Each cell was initially CLEAR, represented by the cell shaded white. Clicking once on a cell moved it to SHADED by shading the cell black. Clicking again moved the square to BLANK by placing a black dot in the centre. Checking the Hint box in altered the colour from black to yellow allowing the user to mark cells as guesses.
Functionality
This functionality of this applet focuses on three areas : Create a new Nonogram by entering clues; Create a new Nonogram by drawing the picture; Solve the Nonogram. These modes were accessed through the Mode menu with the options Cheat, Make and Play.
The applet was displayed in a new window separate from the instance of Netscape and begins in Cheat mode. Initially space for 20 row and 20 column clues were displayed with a text field for clue entry (Fig. 4). Selecting Size from the Edit allowed the number of clues to be altered.
Fig. 4 Fujiwaras Helper in Cheat mode with 7 rows and 7 columns. Row clues are to the left and column clues above. |
Fig. 5 Fujiwaras Helper in Make mode. |
Make mode allowed Nonograms to be drawn on a blank canvas (Fig. 5). Selecting Check from the Solve menu caused the Helper to create the appropriate clues so that changing to Play mode allowed the puzzle to be solved by hand.
The Play mode allowed the user to attempt to solve the puzzle. When the mouse pointer was placed over the grid the Helper indicated the row and column clues relevant to that cell. In this mode the Check facility in the Solve menu caused red lines to be drawn through unsatisfied lines.
Alex' Nonogram Page, Fritze
Presentation of the Grid
This helper also displayed the puzzle in a separate window. The grid was displayed as black lines on a white background and clues were displayed below and to the right of the grid. The clues were separated by '-' and column clues were rotated through 90 degrees.
Cell States Available
Despite the instructions stating that the left mouse button should be used to change the state of the squares it did not actually work. Clicking with the right button tagged the cell by shading it yellow on the first click, blue on the second and finally back to white on the third.
Functionality
This Helper only allows cells to be. At the top of the screen was a counter showing the number of tiles left. However, as cells could not be properly set this number is not updated. There was also a hint button which, when selected, seemed to make the left button set the cell to its correct answer.
This Helper will not be considered when considering requirements because of the technical problems discovered during evaluation.
Paint by Numbers, Kajitani
Presentation of the Grid
Kajitani also
displayed clues to the left and above the grid. The grid (Fig.
6) was displayed in black on a grey background and every fifth line
was red. The clues were displayed in a futuristic font and blue colour.
Clicking on the clues changed their colour to red, signifying that they
had been used. Between each clue and the grid was a rectangle,
initially set to grey. These rectangles indicated whether or not
the line satisfied the clues. When the mouse was positioned over
a cell on the grid, the row and column were outlined in yellow.
Fig. 6
Kajitanis Helper
Cell States Available
Clicking once on a square moved it from CLEAR to BLANK by shading the cell white. Clicking again moved the square to SHADED by shading the cell blue.
Functionality
There were several features in this Helper which aided the user in completing the puzzle. Firstly, holding the mouse and dragging drew an outline starting from the initial cell. When the mouse was released all cells in-between were shaded. In addition, when all cells in a line were SHADED or BLANK the indicator rectangle was set to either red or green depending on whether the clue was satisfied or not. Upon completion of the puzzle the grid was locked, grid lines removed and the title of the puzzle displayed in the top left of the window.
Chapter 3 builds on the background established in this chapter and describes the processes carried out in evaluating the requirements for both components of the project.
This chapter aims to demonstrate the process carried out in specifying the components of the project and is divided into two components. The first discusses the approach adopted in analysing the Solver application in section 3.1 and the second focuses on the Helper in section 3.2. Each component consists of a specification of the problem which has been solved and a discussion of how that specification was arrived at.
The table below describes
the schedule originally envisaged for this project. Project deliverables
are shaded.
Task |
Duration |
Start Date |
Project Initiation |
3d |
Mon 09/11/98 |
Project Plan |
0d |
Wed 11/11/98 |
Familiarisation with ILOG Solver |
5d |
Thu 12/11/98 |
Preliminary Requirements Capture |
2d |
Thu 12/11/98 |
Prototype Solver |
3d |
Mon 16/11/98 |
Requirements Capture |
5d |
Thu 19/11/98 |
Requirements Specification |
0d |
Wed 25/11/98 |
Testing Specification |
0d |
Wed 25/11/98 |
Design of Solver |
7d |
Thu 26/11/98 |
Solver Design Document |
0d |
Fri 04/12/98 |
Implementation of Solver |
15d |
Mon 07/12/98 |
Progress Report 1 |
0d |
Fri 11/12/98 |
Evaluation and Testing of Solver |
5d |
Wed 06/01/99 |
Design of Helper |
5d |
Mon 07/12/98 |
Helper Design Document |
0d |
Fri 11/12/98 |
Implementation of Helper |
5d |
Mon 14/12/98 |
Evaluation and Testing of Helper |
5d |
Mon 21/12/98 |
Integration |
5d |
Wed 13/01/99 |
Integration Testing |
5d |
Wed 20/01/99 |
Write up |
23d |
Wed 27/01/99 |
Progress Report 2 |
0d |
Fri 29/01/99 |
Project Report |
0d |
Fri 26/02/99 |
In the ILOG Solver Users Manual (ILOG, 1997) ILOG recommended adopting an incremental method of development when designing a solution to a constraint satisfaction problem. The phases followed in this development cycle were :
Define a complete and exhaustive statement of all constraints.
Is the application a black-box which searches for solutions with no user input? Are there response time issues?
Experiment with small-scale models to acquire useful information about the problem. When the problem is well-defined a model can be designed.
Using a prototyping approach implies that there is no clear boundary between designing the model and implementing the solution. Optimising a solution is highly dependent on the sets of data used.
These phases are not
independent of each other and this provided scope for modifying the
design during the course of development when new constraints were discovered
and alternatives experimented with.
The first two phases relate to the specification of the problem and are discussed in this chapter. Phase 3 is described in Chapter 4 and Chapter 5 deals with the activities of phase 4.
The Nonogram puzzle may be summarised by stating that a valid solution is one where the length of groups of contiguous blocks on a row or column must correspond to the clues for that row or column. All clues must be satisfied simultaneously for a solution to be valid. Furthermore, if there is more than one group of blocks on a row or column these groups must be separated by at least one square.
This description immediately suggested two different representations for modelling the problem. The first would be to consider the grid as a two-dimensional array of cells and the solution would be found by allocating the value SHADED or BLANK to each cell in such a way that the appropriate number of SHADED cells were present on each row and column.
The second would be to consider the problem from the perspective of the clues and seek to allocate each cell to a particular clue such that each clue had the correct number of cells.
NB. In this report the term line will be used to mean either row or column.
The objective of the Nonogram Solver component was to develop a solution which read a file containing Nonogram clues, determined a solution to the clues and output the result. This type of application is described as black-box and has a low user acceptance due to the fact that the user is not able to see how the application determines a solution. Aside from producing a correct solution, response time was considered the most critical feature as the user does not interact with the program while it is executing.
CSPs generally consist of a very short problem description as most of the work involves establishing an appropriate model which successfully maps objects in the problem domain to variables in the Constraint Programming Language. Without an appropriate representation it will not be possible to express all constraints required to define a correct solution. It can not be stressed strongly enough how the model chosen can influence the success or failure of a CSP and Chapter 4 describes the steps taken to derive a suitable model for the Nonogram puzzle.
The following sections describe the specification of the Helper component.
The approach adopted
in developing the Helper application follows that proposed by Grand
(Grand, 98). This approach divides the development cycle into
two main phases Detailed Planning and Build which are subdivided
into more manageable steps. As this model is designed to be applicable
to a large range of projects it was decided to omit certain stages (for
example, Database design) as they were not deemed necessary. The
remaining stages were :
|
The phases described under Detailed Planning are discussed in this chapter. Object-oriented analysis and design are described in Chapter 4, Coding in Chapter 5 and Testing in Chapter 6.
The initial requirements for the Helper were derived from discussion with the project supervisor, the authors experience of solving Nonograms on paper and the evaluation of the on-line Helpers described in Chapter 2. This section consists of a critical evaluation of Fujiwaras and Kajitanis Helpers, details of which features were adopted and concludes with a summary of the initial requirements. These requirements form the basis of the Use Cases discussed in section 3.2.2.
Nonogram : Solver, Fujiwara
Presentation of the Grid
The style of presentation evident in this Helper seemed to be a logical choice as it remained reasonably true to the style used in Nonogram puzzle books and the Sunday Telegraph. Displaying the clues in a style similar to the grid enabled clues to be easily differentiated from one another but provided problems when clues of more than one digit were required. Using a different colour for every fifth line helped to divide the puzzle into more manageable sections and enabled the user to quickly count the number of cells on a line.
Cell States Available
The Hint facility appeared to be a good idea though the author did not use it while solving puzzles with this Helper. However, it was felt that it may be useful when solving larger puzzles.
Functionality
There was no indication of the form clues could take in Cheat mode although experimentation showed that a sequence of integers separated by periods or spaces was valid. The application detected and removed leading zeros but incorrectly evaluated a clue of the form '1.0.2'. Clues containing invalid characters were ignored and the Helper moved onto the next clue. Each grid cell was designed to accommodate a single digit and did not cope well with numbers greater than 9. If more than 5 numbers were entered the grid was expanded to the appropriate size but if the clues were subsequently cleared only the last five numbers in each clue were reset.
Make mode provided no indication of how to activate a puzzle which had been drawn. A process of trial and error established that the Solve menu option should be used.
In Play mode shading clues grey was a useful technique for keeping track of which clues had been used. In addition, highlighting the clues corresponding to the cell under the mouse pointer was very helpful in identifying which clue was to be solved. The Check facility proved to be unhelpful as the red line obscured the cells and were not removed unless the applet was forced to redraw the screen.
Summary
The method of entering clues was excellent. It very clearly showed which row or column clue was being entered and allowed the user to easily select and edit them. Highlighting the appropriate row and column clues in Play mode avoided the problem of filling in the wrong line when solving the puzzle.
The main drawbacks
to this application were the cryptic menu items and lack of consistency
between the Play mode and the Make mode. It was also not clear
that Check from the Solve menu must be selected after designing a puzzle
with Make or Cheat before the puzzle is registered in Play mode.
Paint by Numbers, Kajitani
Presentation of the Grid
In the authors opinion the colour scheme and futuristic fonts chosen by Kajitani were too garish and detracted from the puzzle. The rectangle between each clue and the grid was useful in keeping track of which lines had been solved although it was felt unnecessary that the user had to fill in BLANK cells as well as SHADED cells before a line was considered complete. Highlighting the current row and column in yellow was also considered garish.
Cell States Available
This helper contained the standard three states : CLEAR, SHADED and BLANK. Again, the choice of colours were felt to detract from the puzzle.
Functionality
The technique of clicking on a cell and dragging to shade a 2 dimensional area enabled large areas to be completed without having to shade each row or column individually. Locking the puzzle and removing the grid lines upon completion of the puzzle provides the user with confirmation that the puzzle has been completed and also allows the picture to be seen more clearly.
Summary
The red and green indicators were very useful, as was the ability to shade large areas at a time by dragging the mouse diagonally.
The colour scheme used in this Helper was very garish. It was annoying that cells were set to BLANK on the first mouse click and so it required two clicks to set a cell to SHADED. Finally, having to set all cells to SHADED or BLANK before the puzzle is complete seemed to be unnecessary.
Summary of Online Helpers
Each of the online Helpers
adopted a slightly different approach to aiding the user to solve Nonograms.
The features incorporated into the requirements specification were :
|
Several features were considered useful but were omitted due to lack of time. It was intended that these could be added in the future :
The requirements derived from the evaluation are summarised in the following paragraphs. For a more detailed description refer to Appendix B.
The Helper should allow puzzles to be loaded and saved in a file format consistent with that used by the Solver. The grid state should be saved as well as the clues. The user should also be able to create a new Nonogram by specifying the dimensions of the puzzle and then editing clues.
The current puzzle should be represented as a grid on the screen with clues at the end of each row and column. When the user clicks on a square it should move to the next stage in the cycle CLEAR à SHADED à BLANK à CLEAR. Clicking with the right mouse button should move through the states in the opposite direction.
After each move made by the user, the Helper should validate each row and column against its clues. If the clue is satisfied a visual cue should occur to notify the user. If all clues are satisfied the Helper should congratulate the user.
The Helper should write the current set of clues to a designated file and then execute the solver with that file. When the solver has completed the helper should load the solution and display it.
Use Cases were developed
to describe the sequence of steps followed by the user and system when
carrying out a task. These cases improved the understanding of
the requirements, the design necessary to implement those requirements
and test strategies which exercised each requirement. The following
Use Cases were developed :
Note : Requirements
identify which requirements, as described in Appendix B, are exercised
by each Use Case.
Use Case : Loading a Puzzle
Actor : User
Purpose : User loads a puzzle from local disk and uses the Helper to solve the puzzle.
Synopsis : User selects the appropriate file from the directory and the Helper displays the clues and grid on the screen. The user completes the puzzle by using the mouse.
Requirements : R-helper-data-001, R-helper-process-003, R-helper-process-004, R-helper-process-005
Course of Events
User |
System |
1. User selects desired file. |
2. Helper opens the file and creates a grid of appropriate size. The clues are read in, parsed for correctness and displayed. |
3. User fills in some cells. |
4. The system checks the appropriate lines to check if the appropriate clues have been satisfied. If the puzzle has been completed the user is congratulated, else return to 3. |
Use Case : Saving the Puzzle
Actor : User
Purpose : User wishes to save the clues and state of grid to the local disk.
Synopsis : User selects the appropriate filename from the directory and the system writes the file.
Requirements
: R-helper-data-002
Course of Events
User |
System |
1. User selects desired file. |
2. Helper writes the size of the grid, row clues, column clues and grid state to the file. |
Use Case : Creating a new Nonogram by entering clues
Actor : User
Purpose : User wishes to create a new puzzle by entering the clues manually.
Synopsis : User creates a new blank grid and edits the clues appropriately.
Requirements : R-helper-new-001, R-helper-data-004, R-helper-data-005
Course of Events
User |
System |
1. User selects File, New. |
2. Helper displays New Dialog box |
3. User enters number of rows and number of columns and presses OK. |
4. Helper creates grid of appropriate size and displays it. |
5. User selects Edit, Edit Clues. |
6. Helper displays the Clue Dialog box. |
7. User enters appropriate clues. |
8. Helper sets the clues and redraws the screen with the appropriate clues. |
Use Case : Create a new Nonogram by drawing a puzzle
Actor : User
Purpose : User wishes to create a new puzzle by drawing the puzzle.
Synopsis : User creates a new blank grid and draws a puzzle. Helper generates the clues.
Requirements : R-helper-new-001, R-helper-process-003
Course of Events
User |
System |
1. User selects File, New. |
2. Helper displays New Dialog box |
3. User enters number of rows and number of columns and presses OK. |
4. Helper creates grid of appropriate size and displays it. |
5. User draws picture with the mouse and selects Edit, Generate Clues. |
6. Helper calculates the clues from the grid, sets the clues and redraws the screen. |
Use Case : Using the Solver component to solver the puzzle
Actor : User
Purpose : User wishes the system to solve the puzzle.
Synopsis : User already has a file open and instructs the system to solve the puzzle.
Requirements : R-helper-solver-001, R-helper-process-001, R-helper-process-002, R-helper-process-003
Course of Events
User |
System |
1. User selects Tools, Solve |
2. Helper saves the file as input.non. System calls the solver specifying that the output should be a file called output.non in the correct format and the input is input.non. When the Solver completes, the system should load output.non. |
The development of the prototype was used as an opportunity to learn Java and the book Java: First Contact (Garside, 1998) proved to be an excellent resource for this. A subset of the functionality was chosen from the requirements gathered in section 3.2.1 and the Use Cases defined in 3.2.2. This subset can be summarised as :
It was discovered during prototype implementation that the Abstract Windowing Toolkit (AWT) provided all the required User Interface components and this enabled prototyping to take place in a short period of time. This prototype was evaluated by a prospective user and comments noted. These comments are quoted below. Comments were used to establish further requirements and these were added to the specification.
Additional functionality was incorporated into the prototype and further evaluation carried out until the prototype implemented most of the functionality described in the requirements and the user was satisfied that there were no more requirements to be captured. The prototype was then used as a basis for the design stage of the Helper development and this process is described in the following chapter.
Comments
It can be hard to count squares when solid black is there. Can lines show through at all?
The darkening of clues when they are satisfied is extremely helpful. Also very effective is the automatic filling of rows when mouse is clicked at first square and dragged to last. This can be problematic though as it fills in large squares as well as lines if dragged diagonally. Could this be limited to straight lines only?
Would it be possible to display CLEAR cells as BLANK in a row or column when that row or column satisfies its clue?
Save option as well as Save As in the File Menu would be useful.
Is it possible to undo the last action if I make a mistake?
In addition to these comments the project supervisor, Ian Gent, suggested that it would be desirable to be able to generate Nonograms from 2-bit images. This would involve copying the contents of the image to the grid and generating the clues.
This chapter discusses the design process of both the Solver and Helper applications. The Solver section (4.1) follows the structured design approach proposed by ILOG. This traces the evolution of a mini-problem, which describes a subset of the puzzle, through to a solution which models the whole puzzle. Section 4.2 contains the object-oriented design process used in developing the Helper. This was carried out in three phases : identification of objects, specification of attributes and methods and user interface design. Finally Section 4.3 describes the structure of the datafile used to store Nonogram puzzles.
As the Solver was a black-box
application, characterised by a straightforward Input Process Output
model, a Structured Design approach was adopted. The overall architecture
of the project is described in figure 7 and the following sections describe
how the ILOG design recommendations were followed to define a problem
representation. The first stage in identifying the representation is
to define a mini-problem : a subset of the problem which, when
solved, provides useful information which can be used when solving the
larger problem.
Fig. 7
Overall Solver Architecture
As described by ILOG, the first stage to developing a problem representation is to extract the mini-problem As the author initially had no experience of ILOG Solver this period was used as a learning ground to experiment with the various features offered by Solver. Examining the problems defined in the manual provided a valuable insight into using Solver to attack certain problems. One of these was the Magic Square puzzle described in Chapter 3.
The representation chosen for the Magic Square puzzle involved using an array to represent the overall matrix. Smaller arrays representing the rows, columns and diagonals were created from this overall array and used to express constraints on the sum of the rows. This appeared to be a possible model for the Nonogram puzzle following the first representation mentioned in Section 3.1.1 :
. . . consider the grid as a two-dimensional array of cells and the solution would be found by allocating the value SHADED or BLANK to each cell in such a way that the appropriate number of SHADED cells were present on each row and column. (Section 3.1.1)
The Nonogram could be represented as an integer array of suitable size where each element was either a one representing SHADED or zero for BLANK. The sum of each line would have to be equal to the sum of the clues for that line.
It is apparent that significant constraint information is absent from this model. For example, there is no specification that where there is more than one clue for a line the corresponding groups of cells must be separated by at least one blank cell. However, despite this flaw the Solver described by this model was capable of solving extremely simple Nonograms. Unfortunately as the search space for a Nonogram of size n by m is equal to 2m*n this soon proved to be an impractical solution for real problems. This example illustrates the importance of identifying a representation which accurately corresponds to the problem space.
Since a Nonogram is essentially composed of a collection of rows and a collection of columns it was decided to initially consider a single line of arbitrary length and any valid set of clues. A solution to this mini-problem could be extended to two arrays of lines, one corresponding to the rows and the other to columns. The extended model would require suitable constraints which allowed information about rows to be propagated to the columns and vice-versa.
Each line in a Nonogram may be considered to be a sequence of contiguous blocks of blank and shaded squares. For example, a solution to the clue 2.1 could be
S0 S1
Fig. 8 A Sample line with clue 2.1
B0 B1 B2
This representation can be considered as :
B0 : A block of blank squares, length 1
S0 : A block of shaded squares, length 2
B1 : A block of blank squares, length 1
S1 : A block of shaded squares, length 1
B2 : A block of blank squares, length 2
To define all solutions to the above problem the following initial constraints defining the lengths of the blocks were expressed :
This did not provide any information about which cells were contained in which blocks. However, by considering the blocks as sets the row could be defined as
{0}, {1,2}, {3}, {4}, {5,6}
where the numbers in each set are the indices of the cells contained in that set.
Ie. Cell 0 is blank, cells 1 and 2 are shaded, etc.
Clearly the even indexed sets ( {0}, {3}, {5,6} ) describe blank cells and odd indexed sets describe shaded cells.
As ILOG Solver
does not provide methods for extracting the minimum and maximum values
from a set it was useful to store these values in arrays. It was
important to note that two numbers, min and max, were required to describe
each block such that the difference between these was equal to the length
of the block. The diagram below illustrates this.
min max
Hence, given any clue an array of sets and arrays containing minimum and maximum values may be created to describe that line and constraints can be posted. Note that the blank sets at either end of the row may be null; all other blank sets must contain at least one element. The domain of each set can be calculated by identifying the first possible starting and last possible finishing cells for that block. Initially the domain of each set will span the entire row. Solver will reduce the domains as constraints are propagated.
Example
The clue 2.1 with row length 7 generates the following data :
B0 |
S0 |
B1 |
S1 |
B2 | |
Sets |
{0,1,2} |
{0,1,2,3,4} |
{2,3,4,5} |
{3,4,5,6} |
{4,5,6} |
Minimum |
0 |
0 |
2 |
3 |
4 |
Maximum |
3 |
5 |
6 |
7 |
7 |
Using an array of sets to represent each line allowed the following constraints to be expressed :
These constraints describe any individual row or column in a puzzle. To allow row information and column information to propagate properly it is also necessary to link the rows and columns in some way.
These constraints accurately modelled the problem with the representation identified in section 4.1.2. The following section extends the mini-problem to describe a puzzle consisting of multiple rows and columns.
It was intended that
modelling a complete Nonogram puzzle would simply involve creating a
series of arrays of pointers to the variables established in the mini-problem.
For example,
Rows
RowMin
RowClues
Fig. 10 An illustration of using arrays of solver objects to model the problem.
This is a valid representation for the clue, minimum and maximum information. However, as was demonstrated with the Magic Square puzzle it is only possible to search one-dimensional arrays. This implied that an alternative representation for the row and column information must be found.
Two choices were considered. The first was to create two arrays to represent the rows and columns and express the constraints on these. The contents of these two-dimensional arrays could then be copied into a one-dimensional array in a similar way to that used in the Magic Square problem when representing individual rows and columns.
The second choice involved
representing the rows and columns as two one-dimensional arrays.
The rows of the grid would be represented by a one dimensional array
which is the concatenation of all the individual rows (fig. 11).
Row 2 Row 4
Rows :
Row 1 Row 3
Fig. 11 Representing all rows in the puzzle as the concatenation of each row.
The same concept can be applied to the column information. Further information would require to be stored to identify the start and end points of each line. This is essentially the same as above except that the two-dimensional stage is skipped.
It was decided to adopt the second choice as it appeared to be conceptually more straightforward. In addition, problems were discovered when using the Solver class IlcAnyVar to store pointers to the individual rows and columns.
To identify which blocks belong to which row it was necessary to store the number of blocks in each row (numRowBlocks) and the index of the last block of each row (runningNumRowBlocks). runningNumRowBlocks is the running total of numRowBlocks.
I.e., The first block of row i is stored at index runningNumRowBlocks[i] - numRowBlocks[i] and the last is at runningNumRowBlocks[i].
Example
The row clues for the chick puzzle and the number of blocks required for each row are :
Row |
Clue |
Number of clues |
Number of Blocks (2 * clues+ 1) |
RunningNumRow Blocks |
3 |
1 |
3 |
3 | |
2.1 |
2 |
5 |
8 | |
3.2 |
2 |
5 |
13 | |
5 |
1 |
3 |
16 | |
4 |
1 |
3 |
19 | |
1 |
1 |
3 |
22 | |
2 |
1 |
3 |
25 |
The final element in the array runningNumRowBlocks (in the above example, 25) corresponds to the number of blocks required to describe all the rows in the puzzle. Similar calculations can be made for the column clues.
To summarise, the following information must be stored relating to the clues :
This allows arrays of the correct size to be created.
Calculated from the number of rows and columns and used when creating storage space for the clues. It was decided that instead of reading the file twice - the first time to calculate the size of the grid and clues and the second to read the data - room for the maximum number of clues would be created.
Calculated while clues are being read and stored.
This information allowed appropriately sized variables to be constructed to model the grid area. These variables are described below :
The complete description of all these variables, their types and descriptions can be found in Appendix B.
Chapter 5 describes in detail how the model was implemented in Solver. The following section discusses the object-oriented design of the Helper component.
As mentioned in Chapter 3 this section deals with the object-oriented analysis and design of the Helper. Analysis is concerned with identifying the objects, attributes and methods involved in a problem and results in a model of the relationships between various objects. Design develops this model from the problem domain to the computer domain by mapping the objects and methods onto classes and algorithms available in the implementation language. Diagrams are based on the Unified Modelling Language (UML) as described by Grand (Grand, 1998).
The following objects were identified during the requirements analysis phase and most were incorporated into the prototype. The analysis phase considered each object in turn and established that each satisfied either all or most of the object selection criteria described in the course notes for Software Engineering 1 (Wood, 1996).
The prototyping phase involved informally deciding on attributes and methods present in the Helper and this provided much of the input for the design stage. However, the objectives of the prototype were that it should be implemented quickly, demonstrate the user interface and examine possible implementations of the functionality. Consequently the objects did not strictly meet the definition of object-oriented design as attention was not paid to encapsulation and data-hiding. This phase therefore concentrated on correctly assigning attributes and methods to objects.
The attributes were defined by considering which information was required to describe the state of the object. The requirements specification provided much of the initial attributes as it specified items such as the grid and the clues. However, other variables were identified when the desired functionality was considered. For example, to evaluate whether or not the puzzle has been completed it is necessary to record whether or not each line has satisfied its clue.
Methods were defined by considering the services each object would require of the other objects. Methods can generally be of three types :
Applying these concepts to each object ensured that each object provided appropriate methods to allow other objects access to attributes. In addition, it ensured that functionality, such as the generation of clues from the grid, was placed in the correct object. Figure 12 contains the output of this design phase - the overall UML diagram of the Helper application. This diagram shows the relationships between the various objects of the Helper. Partial specifications of each object can be found in Appendix B.
Fig. 12 Top level UML diagram of Helper
Note that the okDialog object is missing from the above diagram because all objects which output error messages to the user use it and it would confuse the diagram. However, a specification for the okDialog object can be found in Appendix B.
This design is extended in Chapter 5 Detailed Design and Implementation.
Grid Design
It was decided that the Helper should display the grid in black on a yellow background. The yellow colour was chosen as it provided a high contrast with the black lines without appearing too pale. Every fifth line was three times as thick as normal to help the user count cells.
The technique for representing clues was chosen to allow the Nonogram Helper to resemble the normal way puzzles are printed in books and newspapers. Row clues were displayed to the right of the grid in the form x1.x2.x3 and column clues were displayed below the grid.
A rectangle was placed between each set of clues and the grid. This rectangle represented a traffic light which was set to red when the clue was unsatisfied and green when the clue was satisfied. Unlike Kajitanis Helper it was only necessary to set the appropriate cells to SHADED to satisfy a clue. The user did not have to also set the other cells to BLANK.
Cell States
Each cell could have
three possible states :
CLEAR The initial state
SHADED The cell is part of one of the clues.
BLANK The cell is definitely blank.
Clicking repeatedly on
a cell with the left mouse button moved it from CLEAR à SHADED à BLANK à CLEAR. Clicking with the right mouse button
reversed the cycle : CLEAR à BLANK à SHADED àCLEAR.
Menu Design
The menu titles were chosen to remain consistent with standard windows applications and such that they described their contents. The menuitems were arranged so that frequently used items were at the top.
File : New Edit : Undo Tools : Solve
Open Clear Grid Create from Image
Save Edit Clues
Save As Generate Clues
Quit Preferences
Dialog Boxes
Dialog boxes were also
designed to correspond with those found in the Windows environment.
The following table describes the dialog boxes present in the application.
okDialog |
This dialog was used for error reporting. It simply displays a message in the dialog box and presents an OK button which dismisses the dialog. |
cancelDialog |
This was displayed when the solver component of the application is called. As the solver can take a very long time depending on the size and complexity of the puzzle it was useful to give the user the option of cancelling at any time. |
newDialog |
The user enters the dimensions of the new puzzle in this dialog. It contains two textfields to hold the row value and column values and the standard OK and Cancel buttons. |
cluesDialog |
The current values for the clues are displayed in text fields in two columns. The first displays the row clues and the second the column clues. If the clues were too big for the dialog it was possible to scroll through them. Again, the standard OK and Cancel buttons were placed at the bottom. |
prefDialog |
This dialog allowed the user to set the offset of the grid from the top left corner, the size of the cells and to turn the AutoFill facility on and off. |
The datafile was required to store details in four sections :
As several puzzles had
been downloaded while researching Nonogram resources on the Internet
it was decided to adopt the same file structure. To ensure that
the file structure could be easily updated in the future each section
of the file was separated by a keyword defined at the beginning of the
code. The structure of the datafile is illustrated in figure 13.
The keywords are displayed in angle brackets.
|
The keywords corresponding
to the downloaded puzzles were :
<No of Columns> |
width |
<No of Rows> |
height |
<Start of Row Clues> |
rows |
<Start of Column Clues> |
columns |
<Start of Grid> |
grid |
The following diagram (fig. 14) shows the top-level file reading process used in the Helper and the Solver applications. During file reading an integer variable status tracks which part of the file is being read. In the diagram the value of status has been enumerated and corresponds to the following processes :
Flowcharts for these
processes, which are identified by bold text in the top-level diagram,
can be found in Appendix B.
Fig. 14 Overall File Handling Process
This chapter describes the activities carried out when implementing the designs. In particular, the most demanding aspects of the design and steps taken to ensure the software demonstrated software qualities such as reliability and maintainability are discussed.
Having decided on a suitable data representation and described the constraints in natural language, the next step was to identify how to express each of the constraints on Solver. Solver provides a data type IlcIntSetVarArray which represents an array of integer set variables. The domain of an integer set variable can be defined at declaration.
The code fragments describing
the constraints below assume that these variables have been declared
:
Solver provides a
function IlcNullIntersect (set1,
set2) which expresses the constraint
that two sets may not intersect. As it is only possible to express
this between two sets it was necessary to iterate across block constraining
that each set may not intersect with any of the following sets.
for (cnt = 0; cnt < number_of_blocks; cnt++)
For (j = i; j < number_of_blocks; j++)
m.add(IlcNullIntersect(block[cnt], block[j]));
This statement is true for all sets and therefore did not require to be posted.
The Solver constraint IlcCard(set1)
expresses the cardinality of a set set1. Each interior blank set in the array should
be constrained to have IlcCard
>= 1. The interior blank
sets were identified by stepping through the array from elements 2 to number_of_blocks - 2,
step 2.
for(cnt = 2; cnt < number_of_blocks 2; cnt += 2)
m.add(IlcCard(block[cnt]) >= 1);
For each shaded set
in the array constrain IlcCard
== clue where clue is the appropriate clue value. The shaded
sets can be identified by stepping through the array from elements 1
to number_of_blocks 1, step 2.
for(cnt = 1, clue=0; cnt < number_of_blocks 1;
cnt += 2, clue++)
m.add(IlcCard(block[cnt]) == Clue[clue]);
In the case where the
clue for a line is equal to 0 the following blank set should have cardinality
0.
if (block[cnt] == 0)
m.add(IlcCard(block[cnt + 1] == 0))
This is expressed with two sets of constraints. The first states :
The function IlcIfThen(condition, constraint) enables a constraint constraint to be posted when condition is true.
for (cnt = 0; cnt < number_of_blocks; cnt++)
{
m.add(max[cnt] min[cnt] == IlcCard(block[cnt]))
IlcIfThen(IlcCard(block[cnt]) > 0,
IlcMember(Max[cnt]1, block[cnt]))
IlcIfThen(IlcCard(block[cnt]) > 0,
IlcMember(Min[cnt], block[cnt]));
}
The second constraint states :
for (cnt = 0; cnt < number_of_blocks; cnt++)
for (j=Min[cnt].getMin();j < Max[cnt].getMax(); j++)
m.add((j >= Min[cnt] && j < Max[cnt])
== IlcMember(j, block[cnt]));
This constraint is necessary because it is not possible to identify the minimum and maximum values of a set.
The maximum of each set
must be equal to the minimum of the subsequent set. Again, this
would be better expressed by stating that the maximum value in one set
must be less than the minimum of the next but this did not seem to be
possible.
for (cnt = 0; cnt < number_of_blocks; cnt++)
m.add(Max[cnt] == Min[cnt+1]);
These constraints proved to be adequate for modelling a single line in a Nonogram puzzle. The next stage involved building a complete puzzle by creating extending the representation to two dimensions.
Having declared the appropriate variables the next step in the implementation was to adapt the constraints as defined for the mini-problem so that they were applicable to multiple rows and columns. Essentially this consisted of iterating across all rows and columns and expressing the constraints as before. However, Solver does not easily allow access to complex data types, for example sets, which are stored in two dimensional arrays. This resulted in very clumsy looking code which is required to explicitly cast each stage of the data access. For example,
RowMax is a two dimensional array which is indexed by row and block.
Eg. RowMax[row][block]
should return the maximum of the set block in row row. The required
code is actually
(*((IlcIntVarArray*)RowMax[row]))[block]
RowMax is an instance of IlcAnyArray. Each element of RowMax is an instance of IlcIntVarArray. Therefore, to access an element the appropriate IlcIntVarArray must be extracted and then indexed by the value block. This proved to be extremely confusing during development as it required much trial and error before the correct combination of accessors were discovered.
The final stage in the implementation was to define a constraint which linked the row and column data together such that when an cell was shaded in a row, the corresponding cell in the appropriate column was also shaded.
This was implemented by defining :
and constraining that
if cell i of row j is shaded, cell j of column i must also be shaded.
This is expressed in using the condition1
== condition2 notation shown below
and states that condition1 and condition2 must both be simultaneously false or simultaneously
true.
for (rowIndex=0; rowIndex<RowCount; rowIndex++)
for (colIndex=0;colIndex<ColCount; colIndex++){
m.add(IlcMember(colIndex,rowShaded[rowIndex]) == IlcMember(rowIndex, colShaded[colIndex]));
m.add(IlcMember(colIndex, rowBlank[rowIndex]) == IlcMember(rowIndex, colBlank[colIndex]));
}
Defining the above sets
also allowed constraint 1 (No blocks may intersect) to be expressed
in a more straightforward manner :
for (rowIndex=0; rowIndex<RowCount; rowIndex++)
m.add(IlcNullIntersect(rowShaded[rowIndex],
rowBlank[rowIndex]));
The complete listing of the Nonogram Solver program can be found in Appendix G.
The implementation of the Helper involved re-implementing the prototype with the improvements gained through formal design. This ensured that the Helper followed a modular design and so would be easily maintainable. The basic Helper functionality implemented in the original prototype was extremely straightforward to implement and will not be discussed here. However, to illustrate the implementation of some of the processing methods the following section describes the design and implementation of two algorithms used in the Helper. Firstly, the algorithm which carries out clue generation and secondly, the process used to build a Nonogram from an image. These were both reasonably complicated processes which required some research and experimentation.
The aim of this process was to examine a row in the grid and produce a string containing the appropriate clues. This involved counting contiguous blocks of shaded cells and recording the number.
The initial design was carried out in pseudo code. It is assumed the algorithm is generating the clues for row row.
Define 3 counters : clue to count the number of clues
total to count the number of cells in a block
index to count the which cell is being considered
Define a string to hold
the result : clueString
For each cell,
Set total to 0
If cell at (row, index) is a 1 then:
Increment total
Increment index
While there are still cells and the current cell holds a 1
Increment total
Increment index
Decrement index (when the while loop fails it should stop at the zero cell)
If this is the first clue then :
set clueString to total
else
set clueString to clueString + . + total
End if
End if
This function is implemented as makeRow in the Grid object. A similar function is also present called makeCol.
The Nonogram Maker was implemented by firstly adapting a piece of code featured in Java : First Contact (G, 1998). This code fragment read an image from disk, created an image object and displayed it in a new window.
Java provides an object called PixelGrabber as part of the AWT and this appeared to be ideal technique to use. A PixelGrabber processes an image object, extracting the RGB values for each pixel and placing them in an array.
It was then possible to read through this array converting pixels with the RGB value of black to 1 and pixels with the RGB value of white to 0 :
The pseudo-code for this
process was :
Record width and height, the width and height of the image to be grabbed.
Create an array of integers of size (width * height).
Create a PixelGrabber, specifying the image to be grabbed, the dimensions and the destination array.
Grab the pixels.
Convert the pixels from RGB values to 1 for black and 0 for white.
Create a new grid to store the new image.
Copy the values to the grid.
This process is implemented in the class Maker.java.
The next chapter describes
the processes used in verifying and validating the software.
Verification and validation were carried out on both applications to ensure both that they matched the appropriate requirements and also that they were robust and reliable. Both black box and white box testing were used in the course of the project as each identifies different classes of defects.
White box testing considers the internal design of a module and is based on the flow of control through the code. In particular, basis path testing analyses the control flow and identifies input data which will cause every independent path to be executed. The set of these independent paths form the basis set a set of paths which ensure that every statement is executed and every condition is evaluated to both true and false.
Black box testing uses the program specification to identify tests which fully exercise all functionality defined in the specification. Equivalence partitioning identifies groups of input values where each member of the group is an equally good test.
The testing was divided into three sections :
Both applications implement
file handling in the style illustrated by the flowcharts in Appendix
B. The flowcharts model the flow of control through the module
and by tracing various paths through the model it was possible to identify
suitable test cases which exercised the loops and data structures. The
table below describes possible errors which the file handling module
was designed to catch :
Section of File |
Possible errors |
Width / Height data |
|
Row / Column clues |
|
Grid data |
|
Equivalence partitioning
was used to identify classes of errors which would cause the failures
described in the table above. The datafile for the chick puzzle
(fig. 15) was used as a test harness and modifications were made to
it so that the error situations were produced.
height 7 | |
width 7 | |
rows | |
3 | |
2.1 | |
3.2 | |
5 | |
4 |
Fig.15 The Chick Datafile |
1 | |
2 | |
columns | |
1 | |
3 | |
1.3 | |
5.1 | |
4 | |
3 | |
2 |
The following table describes the various tests which were carried out and the results which occurred. The test files can be found in Appendix C
.Test 1 |
Set width to 0 |
Description |
width 0 |
Expected result |
Error : There is an error in the column count. |
Actual result |
Error : There is an error in the column count. |
Test 2 |
Do not specify a value |
Description |
width |
Expected result |
Error : There is an error in the column count |
Actual result |
Error : There is an error in the column count |
Test 3 |
Omit whole line |
Description |
No width line |
Expected result |
This file is incorrect |
Actual result |
This file is incorrect |
Test 4 |
Specify a negative value (not negative of correct value) |
Description |
width -3 |
Expected result |
Error : There is an error in the column clues |
Actual result |
Error : There is an error in the column clues |
Test 5 |
Specify illegal values, eg. characters |
Description |
height gary |
Expected result |
Error : There is an error in the row count |
Actual result |
Error : There is an error in the row clues |
Test 6 |
Specify a number larger than number of clues |
Description |
height 9 |
Expected result |
There is an error in the row clues |
Actual result |
There is an error in the row clues |
Test 7 |
Specify a number smaller than number of clues |
Description |
height 3 |
Expected result |
There is an error in the row clues |
Actual result |
There is an error in the row clues |
Test 8 |
Incorrect number of clues |
Description |
Delete the first row clue |
Expected result |
There is an error in the row clues |
Actual result |
There is an error in the row clues |
Test 9 |
Omit heading line |
Description |
Delete the line containing columns |
Expected result |
This file is incorrect |
Actual result |
This file is incorrect |
Test 10 |
Insert blank lines in clues |
Description |
Insert in the middle of the row clues. |
Expected result |
No problems |
Actual result |
No problems |
Test 11 |
Sum of row clues not equal to sum column clues |
Description |
Change first clue to 10 |
Expected result |
Error : The clues are not consistent! |
Actual result |
Error : The clues are not consistent! |
All tests were passed except test 5. This defect was traced to the atoi() function which converts a character string into integer but it was not possibly to establish exactly what the problem was. However, as the error was trapped and the user was notified that there was a problem with the data file it was not considered important.
The next section discusses the validation of the Solver application.
The Solver application was validated by using examples from the 2nd Book of Nonograms (Ishida, 1994). This book contains solutions to its puzzles and these were used as confirmation that the program was producing the correct result.
The puzzles chosen were :
Puzzle 3 Swan
Puzzle 8 One Little Pig
Puzzle 48 Rhino
Puzzle 49 Thunderbird
Puzzle 74 Diplodocus
These puzzles represented a cross section of difficulty and it was felt that these would sufficiently exercise the Solver. In addition to these, many other puzzles were used during the development of the product. The Solver application has correctly solved all puzzles which it has been used with.
The results of these tests can be found in Appendix C.
The test strategy in Appendix C was developed from the Helper requirements specification and enabled all requirements to be validated. It is well documented that it is difficult for developers to impartially test their own code the developer automatically avoids carrying out the unpredictable actions which a novice user would accidentally do. For this reason two independent testers who had no previous experience of using the application carried out the testing.
The strategy led the tester through a series of tasks which explored the full functionality of the Helper. The testers were also encouraged to experiment and try to cause the program to fail.
The Helper passed all the tests described in the strategy which suggests that either the software is robust and reliable or the tests were not suitable.
The critical evaluation of this project was carried out in two parts. The first involved evaluating the strengths and weaknesses of both products and establishing whether or not project objectives were met. In particular, possible improvements to the products were considered and lessons learned analysed.
The second component (section 8.3) of the evaluation involved carrying out a User Interface evaluation with the Helper. This involved producing a task list for users which led them through a subset of the Helpers functionality. At the end of this each user filled in a questionnaire based on Schneidermans Questionnaire for User-Interaction Satisfaction (Schneiderman, 1992). The results of this survey are summarised in section 8.3.
The Critical Evaluation concludes with a discussion of the changes made to the Project Plan during the course of the project.
The objective of the Solver component of the project was to
Develop a Solver program which, when supplied with a list of clues, produces the correct solution to the puzzle. This application should be developed using the ILOG Solver C++ toolkit. (Chapter 2)
The objective was achieved a Solver was produced which read in a set of clues in a defined format, used constraint satisfaction techniques to solve the puzzle and output the result. The product has been successful in tackling all Nonogram puzzles which have been downloaded from the Internet and all puzzles attempted from the 2nd Book of Nonograms (Ishida, 1994). In addition, puzzles created with the Nonogram Helper have also been solved.
The development process proposed by ILOG (ILOG, 1997) was very helpful and appropriate to the project. Developing the mini-problem was especially useful as it allowed experience to be gained and facilitated experimentation enabling the author to become more comfortable with the toolkit. However, Solver is a very complicated tool and it was felt that perhaps there was more straightforward method of tackling the problem which the developer had not discovered.
Although the product satisfies the specification and the objectives there are three areas in which improvement could be made.
The first of these is the problem representation. The current representation requires a large number of variables to be instantiated and it was felt that there may be a more efficient model. The representation would be simplified considerably if there was a method of extracting the minimum and maximum values of a set. This would remove the need for the minimum and maximum arrays and would possibly lead to an increase in efficiency.
Secondly, searching is not very efficient. Most Nonogram puzzles are designed for humans which generally means that they have only one solution and can be solved solely by using propagation. It is very seldom that a human will come to a point where no more information can be extracted logically and a guess must be made. Consequently most Nonogram puzzles used in the course of this project have been solved by propagation alone.
However, using the Create from Image facility in the Helper, a Nonogram puzzle representing the University logo was created. This puzzle consisted of 40 rows and 43 columns. Applying Solver to it resulted in a search time of around 13 minutes and approximately 6500 failures while searching. When the same puzzle was used with a Nonogram solver downloaded from the Nonogram Solver Repository (Simpson, 1999) the puzzle was solved in 1 second.
Clearly there is much room for improvement. ILOG Solver provides powerful features which allow the developer to choose the order in which variables are searched. It was considered that perhaps adopting a First-Fail approach where the Solver tried to assign values to the sets with smallest domains would result in a more efficient product but because Solver is a very complicated product it was not possible to implement this.
Finally, Steven Simpson, maintainer of the Nonogram Repository at Lancashire University (Simpson, 1999), mentions adding a solution checker to his own solver. In situations where there are multiple solutions to a puzzle the checker is able to identify which of these is correct. Further investigation of this concept may lead to heuristics which enable the Solver to discard much of the search space.
The objective of the Helper component of the project can be divided into three areas :
The first objective defined the basic functionality which must be present in the Helper display a Nonogram puzzle on the screen and allow the user to manipulate the puzzle. The Helper fulfils these criteria and satisfies this objective.
The Helper aids the user by automatically changing CLEAR cells to BLANK and setting the traffic lights when clues are satisfied. It would be difficult to ask the Helper to do more as it is the user who should solved the puzzle. Perhaps an improvement would be to enhance the Helper so that when the user made a move the Helper would fill in all the BLANK squares which are implied by that move.
The Helpers available on the Internet contained flaws which were avoided when producing this project. In particular, Fujiwaras Helper contained cryptic menus and it was difficult to understand which features were available in which mode. The Nonogram Helper avoided this by having one screen used for both drawing puzzles and solving them. Kajitanis Helper required two mouse clicks to shade a cell whereas the Nonogram Helper allowed both mouse buttons to be used providing more flexibility to the user.
In some areas, however, Fujiwaras Helper was superior. His Helper was capable of solving the puzzles so that the user can check their progress. In addition, the clue entry method implemented by Fujiwara was superior to that developed here.
This evaluation raises two possible improvements to the Helper :
The aim of this exercise was to quantitatively measure the usability of the Helper package. This was achieved by selecting two user groups one containing users with experience of solving Nonograms on paper and one of users who have had no experience of Nonograms at all. All users were provided with a copy of the user manual (Appendix A) and a set of instructions to follow through (Appendix E). The users were observed during the evaluation and after completion were asked to fill in a questionnaire (Appendix F).
Eleven users participated in the evaluation. Of these, three had no experience of Nonograms and three of the eight who had experience had also used the Helper. The results are discussed below.
Overall Reaction
The results indicated a good user reaction to the system with an average score of 7. One user rated item 2.4 (Difficulty) as a three but querying this indicated the user was evaluating the difficulty of the puzzle rather than the application.
Screen
Presentation of characters and arrangement of information both received 7s and above indicating that the interface was reasonably effective. However some users felt that the puzzle did not resemble a picture.
Terminology and System Information
Six users elicited error messages and of these the average score was 6. This indicated that error messages could be more specific, particularly in the clue entry dialog box.
Learning
There was a correlation of 0.61 between past experience with computers and ease of learning to use the system. This suggested that the interface was similar to that of other Windows applications and this aided the user. Most users rated exploration of features by trial and error as 6, suggesting that the features were not obvious enough. Again this seemed to relate to past experience.
Supplemental reference material was largely ignored.
System Capabilities
The general trend was that the system was both fast enough and robust enough. Generally users found correcting mistakes easy when the mistake was noticed quickly. However, it was possible to wrongly shade a cell and end up completely wrong. The only possibility at this point was to clear the grid and start again.
Helper vs Paper
All users preferred to use the Helper.
Summary
On the whole the Helper was well received by users. Comments indicated that Nonograms were fun puzzles and several users wished to try more. The main flaws exposed related to the clue entry. It was discovered that the tab caused the focus to move from left to right, jumping between row and column clues, rather than allowing the user to enter all row clues then all column clues. In addition, error messages relating to the clue entry could be made more informative. Three users suggested that a facility should be incorporated to designate a cell as a guess.
The project plan was followed reasonably closely through the duration of the project. As more information was gained about the project it was possible to refine the plan. This section describes the changes made to the plan and the rationale behind them.
In general, the complexity of Solver was underestimated. This was reflected both in the time taken to learn to use Solver and also in time spent investigating how to implement a desired piece of functionality. In addition it was not realised initially how important it was to identify a valid problem representation. As the Solver was considered to be the most important part of the project more time was spent on this component than the Helper. Consequently, the time allocated for Helper development was reduced.
It is the opinion of the author that this project has been very successful. Two applications have been produced in a manner which allows them to developed in the future, allowing additional functionality to be incorporated. These applications are capable of communicating with each other such that the Helper can use the functionality of the Solver component. As discussed in the previous chapter this fulfils all objectives for the project. In addition, carrying out the project has enabled the author to become familiar with Constraint Satisfaction Problems, ILOG Solver and the Java development language, as well as experiencing the development of non-trivial software package.
The main difficulty encountered in the course of the project was the steep learning curve of ILOG Solver. The toolkit is extremely powerful and contains so many features that it was only possible to scratch the surface of its functionality. Solver also has some drawbacks. It is not entirely object oriented and the manner in which arrays of Solver objects must be created and accessed makes the code difficult to read and thus difficult to maintain. It was also felt that the constrained set of integers (IlcIntSetVar) class could contain more methods, such as returning the minimum and maximum values in a set and allowing these to be constrained.
The only problem not solved in the time available involved optimising the search. As discussed previously Solver provides techniques allowing the developer to choose the order in which variables were evaluated and it was hoped that this would improve the search time. However, time considerations prevented this avenue from being explored.
To conclude, both applications contain reasonable functionality. The following describes features which could be added in the future to enhance the utility of the packages.
This section contains the user manual for the Nonogram Solver and Nonogram Helper which have been developed as part of the Final Year Project : Puzzle Solving package.
The Solver is a command line application which produces solutions for given Nonogram clues. The application requires a license for the ILOG Solver C++ Toolkit to execute.
The Helper is a graphical application implemented in Java which allows the user to load a Nonogram puzzle and then solve it by hand using the interface as an aid. The Helper also allows the user to create new Nonogram puzzles by either entering the clues or drawing a Nonogram puzzle and allowing the application to generate the clues.
Solver is a command line application which takes as input the name of a Nonogram puzzle file and produces as output a textual representation of the finished grid. The Solver requires a license for the ILOG Solver C++ Toolkit.
The syntax for the Solver
command is as follows :
solver [-c | -g | -h | -i | -u] <Puzzle file>
The effects of the various
options are detailed below.
Default |
All solutions to the puzzle are determined and output on standard output. |
-c |
Displays the clues and solution to standard output. |
-g |
The solution is written to the file output.non in a format which is readable by the Nonogram Helper. Only the first solution found is output. |
-h |
This option produces a help message. |
-i |
All solutions are written to standard output followed by a set of statistics describing the search time and other information. |
-u |
Displays the number of solutions to the puzzle. |
Figure 1 shows the structure
of Nonogram puzzle files. The file contains four components :
The height of the puzzle, the width of the puzzle, a list of the row
clues and a list of the column clues.
height 7 | |
width 7 | |
rows | |
3 | |
2.1 | |
3.2 | |
5 | |
4 |
Fig.1 The Chick Datafile chick.non |
1 | |
2 | |
columns | |
1 | |
3 | |
1.3 | |
5.1 | |
4 | |
3 | |
2 |
When called with the
command
solver chick.non
the puzzle above would
result in the following output :
**************************************
Nonogram Solver
File : chick.non
**************************************
Solution #1
~~~~~~~~~~~
***
** *
*** **
*****
****
*
**
Helper is a graphical application which draws the Nonogram puzzle on the screen and allows the user to shade cells by simply clicking on the grid. The Helper also allows the user to save the state of the puzzle so that it may be returned to at another time.
The Helper is written
in Java and is launched with the command
java Helper &
The user will be presented
with a blank screen similar to that shown in figure 3.
Fig. 3 Helper Startup Screen
To open a file, select
Open from the File menu and navigate to the required location.
Selecting Open will cause the file to be loaded and displayed in the
Helper. Figure 4 shows the Helper after the Chick puzzle, from
the Introduction, has been loaded.
Fig. 4 The Chick Puzzle
Each cell can be either CLEAR, SHADED, or BLANK. Repeatedly left-clicking on a cell results in the state of the cell cycling through the three possibilities.
Ie. Blank à Shaded à Definitely Blank à Blank
Right-clicking cycles through in reverse order :
Ie. Blank à Definitely Blank à Shaded à Blank
It is possible to shade multiple squares at a time by holding down either mouse button over a starting cell then moving the pointer to the end cell. The Helper will shade all intervening cells.
When the clue for a row or column is shaded, the traffic light the box between the clues and the grid will change from red to green.
To save the puzzle select the Save or Save As options from the File menu. The state of the grid will be saved as well as the clues so that the puzzle can be returned to later.
Selecting New from the File menu causes the user to be prompted to enter the dimensions of the new puzzle in rows and columns. Pressing OK will cause the Helper to draw the appropriately sized grid in the Window.
It is possible to create a new puzzle in two ways.
Select Edit Clues from the Edit menu. A dialog box will appear displaying the row clues in the left column and the column clues in the right column. Type the clues into the boxes each clue should be in the form of period separated integers, eg. 2.3.4 and select OK.
Shade the squares so that the final picture is created. Select Generate Clues from the Edit menu to create the clues. Selecting Clear Grid from the Edit menu will reset the grid to Clear so that the puzzle can be solved by hand.
After both of the above procedures it is possible to save the file to disk.
Selecting Create from
Image from the Tools menu prompts the user for a file to be opened.
This file should be a small 2 colour image either in GIF or JPEG format.
When the file is selected a Nonogram Maker window appears containing
the image, a Capture button and a Cancel button (fig. 5).
Fig. 5 The Nonogram
Maker window
Selecting Capture causes the image to be converted into Nonogram form and displayed on the grid. As before, the Generate Clues option from the Edit menu can be used to identify the appropriate clues for the new puzzle.
Selecting Solve from the Tools menu starts the solver process. While the process is active a dialog box is displayed allowing the user to cancel solving at any time. The solver will display the first solution found or if no solution exists, notifies the user.
The Preferences option in the Edit menu allows the following features to be set :
Nonogram Solver Installation
The Nonogram Solver requires ILOG Solver 4.3 to be installed with a valid license. The distribution consists of two files :
The source code (solver.cc) should be compiled with the command.
gmake solver
Nonogram Helper Installation
The Nonogram Helper requires the Java Development Kit version 1.1 or above to compile. The Nonogram Helper distribution consists of the following files :
These files should be copied to a suitable directory and compiled with the command
javac *.java
The command
java Helper
will launch the Nonogram Helper.
The code describing each requirement (eg. R-solver-data-001) uniquely identifies that requirement. This code is used in testing and in Use Cases to refer requirements.
Requirement R-solver-data-001 : The solver should take as input a datafile containing the row clues and column clues. The datafile may be structured in any appropriate form.
Requirement R-solver-data-002 : The solver should produce as output a text representation of the finished grid. This could use, for example, [*] to represent shaded squares and [ ] to represent blank squares.
Requirement R-solver-data-003 : It should be possible to call the Solver component with data from the helper component.
Requirement R-solver-data-004
: The solver should be capable of producing a file containing all clue
details followed by a text representation of the solution.
Requirement R-solver-process-001 : The solver should create appropriate constraints to describe the puzzle and use these to generate a solution.
Requirement R-solver-process-002 : The Solver should carry out reasonable precautions to ensure that the data is sensible. For example, ensure that both row and column clues add up to the same figure.
Requirement R-helper-data-001 : The helper should be able to take as input a datafile containing the row clues and column clues. The datafile should be of the same format as R-solver-data-001.
Requirement R-helper-data-002 : It should be possible to save the current state of solution to disk.
Requirement R-helper-data-003 : It should be possible to reload a previously saved solution state. This includes the clues and the state of the grid.
Requirement R-helper-data-004 : It should be possible to edit the current clues.
Requirement R-helper-data-005 : It should be possible to clear the grid by setting all cells to Blank.
Requirement R-helper-process-001 : After launching the application the user should be presented with a blank window.
Requirement R-helper-process-002 : The window should feature a toolbar containing menus which allow access to features such as load, save and clear grid.
Requirement R-helper-process-003 : Possibilities for cell states are
Clicking on a cell should move it through these states.
Requirement R-helper-process-004 : The Helper should monitor the state of each row and column and mark a row / column if it satisfies its clue.
Requirement R-helper-process-005 : The Helper should carry out reasonable precautions to ensure that the data is sensible. For example, ensure that both row and column clues add up to the same figure.
Requirement R-helper-new-001 : The Helper should allow the user to create a new Nonogram puzzle. The Helper should prompt the user for row and column sizes then display the empty grid in the window.
Requirement R-helper-solve-001 : The Helper should write the current set of clues to a designated file and then execute the solver with that file. When the solver has completed the helper should load the solution and display it.
It is intended that the additional functionality should be added to the Helper should time permit. This functionality will be defined through user feedback and additional customer requirements and will be recorded here as they occur.
Requirement R-helper-process-006 : When a row or column satisfies its clue all CLEAR cells on that row or column should be displayed as BLANK.
Requirement R-helper-process-007 : The user should be able to select Undo which will undo the last mouse action the user has made.
Requirement R-helper-process-008 : It should be possible to generate clues for the current state of the grid.
Requirement R-helper-process-009 : It should be possible to change the length of cells, the indent from the left edge of the window and the indent from the top of the window. It should also be possible to turn the feature described by R-helper-process-006 on and off.
Requirement R-helper-image-001 : It should be possible to load a 2-bit GIF or JPEG image which will be displayed in a second window.
Requirement R-helper-image-002 : The window should contain two buttons : Capture and Cancel.
Requirement R-helper-image-003 : The Capture button should create a grid of appropriate size and create a copy of the image in the grid. Appropriate clues should be generated for each row and column.
The process Get next
line in the diagrams on the following pages correspond to returning
to the top of the top-level diagram labeled Figure 14 in section 4.3..
Fig. 16 Flow diagram for SETUP
Fig. 17 Flow diagram for READING_ROWS
Fig. 18
Flow Diagram for READING_COLS
Fig. 19 Flow Diagram for GRID
Note : As the Solver ignores the grid section of a file this is omitted from the Solver implementation.
Helper Object
Clues Object
Maker Object
Grid Object
Dialog Box Objects
Variables describing
the clue information
Type |
Name |
Description |
Int |
rowCount |
The number of rows |
Int |
colCount |
The number of columns |
IlcIntArray |
NumRowClues |
The number of clues for each row. |
IlcIntArray |
NumColClues |
The number of clues for each column. |
IlcInt |
maxRowClues |
The maximum number of clues for any row |
IlcInt |
maxColClues |
The maximum number of clues for any column |
Int[][] |
RowClues |
The clues for each row |
Int[][] |
ColClues |
The clues for each column |
Variables describing
the grid
Type |
Name |
Description |
IlcInt |
RowSumBlocks |
The total number of blocks making up all rows |
IlcInt |
ColSumBlocks |
Stores the total number of blocks making up all columns. |
IlcIntArray |
NumRowBlocks |
The number of blocks in each row. |
IlcIntArray |
NumColBlocks |
The number of blocks in each column. |
IlcIntArray |
RunningNumRowBlocks |
The running total of blocks. This is used to identify the last block for each row. |
IlcIntArray |
RunningNumRowBlocks |
The running total of blocks. This is used to identify the last block for each column. |
IlcInt |
RowClueSum |
The sum of clues for each row. |
IlcInt |
ColClueSum |
The sum of clues for each column. |
IlcInt |
TotalRowClues |
The sum of all row clues. |
IlcInt |
TotalColClues |
The sum of all column clues |
IlcIntSetVarArray |
Rows |
The array of all blocks in all rows. |
IlcIntSetVarArray |
Cols |
The array of all blocks in all columns. |
IlcIntSetVarArray |
RowShaded |
An array containting the union of all shaded sets for each row. |
IlcIntSetVarArray |
ColShaded |
An array containting the union of all shaded sets for each row. |
IlcIntSetVarArray |
RowBlank |
An array containting the union of all blank sets for each row. |
IlcIntSetVarArray |
ColBlank |
An array containting the union of all blank sets for each column. |
IlcAnyArray |
RowMin |
The minimum value for each block in each row. |
IlcAnyArray |
RowMax |
The maximum value for each block in each row. |
IlcAnyArray |
ColMin |
The minimum value for each block in each col. |
IlcAnyArray |
ColMax |
The minimum value for each block in each col. |
The following test cases
correspond to the tests described in chapter 7. In each example
the erroneous line is shown in bold..
Test
1 Height 7 width 0 rows 3 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test 2 width height 6 rows 3 2.1 3.2 5 4 1 2 columns 1 3 1.3 5 3 3 2 |
Test 3 height 7 rows 3 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test 4 height 7 width
3 rows 3 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test 5 height gary width 7 rows 3 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test 6 height 9 width 7 rows 3 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test
7 height 3 width 7 rows 3 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test 8 height 7 width 7 rows 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test 9 height 7 width 7 rows 3 2.1 3.2 5 4 1 2 1 3 1.3 5.1 4 3 2 |
Test 10 height 7 width 7 rows 3 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test 11 height 7 width 7 rows 5 2.1 3.2 5 4 1 2 columns 1 3 1.3 5.1 4 3 2 |
Test Results for Solver System Testing
The following results describe the solver output for various Nonogram puzzles. The results have been checked against correct solutions.
**************************************
Nonogram Solver
File : Solver_results/3swan.non
**************************************
Solution #1
~~~~~~~~~~~~
** **********
* * *********
*** *********
*** *********
* ** **
*** ** *
*** * **
** *****
** ***
**
****
Number of fails : 0
Running time since creation
: 0.29
**************************************
Nonogram Solver
File : 8onelittlepig.non
**************************************
Solution #1
~~~~~~~~~~~~
*
*
** *
*************** **
*********** **
********** **
*********** *****
* ******** **** ****
******** **********
** ****** *******
** *** ** **********
**** * ******
**** ****
** * **
* * *******
******* *
*********
********
******
* *
Number of fails : 0
Running time since creation
: 1.19
**************************************
Nonogram Solver
File : 48rhino.non
**************************************
Solution #1
~~~~~~~~~~~~
***
**** *****
*** ********
***********
* ***** *******
* ******* ******
** * **** *** *****
** ** ***** ** *****
*** *** ******* ** ****
**** *********** ** ***
***************** ** ** *
******** ****** **** **
******* * ****** *** ***
****** ******* *** ***
*************** ** ****
******************* ****
* **************** ****
***** ********* ** ****
* ********** ******
**********
******
Number of fails : 0
Running time since creation
: 1.29
**************************************
Nonogram Solver
File : 49thunder.non
**************************************
Solution #1
~~~~~~~~~~~~
*
* ***
** *****
********
********
* ********
* *** *
* *** *
* * * ** ***
* * * *
** ** * **
*** * ** *
** ** *
*** ** *
***** *******
***** ******* ***
***** ******** **
***** ******* *
** ******* *
** ******* **
*** ******* **
*** ****** ****
***** *** * ***
***** ** ** ***
**** *
*** **
Number of fails : 0
Running time since creation
: 1.56
**************************************
Nonogram Solver
File : 74dip.non
**************************************
Solution #1
~~~~~~~~~~~~
*****
*********
**** ****
*** ** *
*** ****
*** **
*** **
***
***
*** *********
**** ************
**** ***************
**** **** ************
***** ***** **************
************ **************
*********** ***************
********** ****************
********* ******* ********
******** ****** **********
******* ****** **********
***** ****** **********
**** ****** **********
**** ****** *********
**** ******* ********
***** ****** ********
***** ***** ******
**** **** ******
**** **** ******
**** ***** ******
*** ***** ******
*** ******
*** ******
***** *******
*************
********
Number of fails : 0
Running time since creation : 3.27
The following sequence
of activities exercises all aspects of the Helper and enables the software
to be validated against the requirements defined in Appendix B.
Requirement |
R-helper-process-001, R-helper-process-002 |
Passed? |
|
Description |
Launch the Helper. The Helper should appear displaying a blank window. Various menus are displayed at the top allowing access to File commands, Edit commands and Tools. |
Requirement |
R-helper-data-001 |
Passed? |
|
Description |
Open the file chick.non. The Helper should create a 7x7 grid and display the clues to the right and below the grid. |
Requirement |
R-helper-process-009 |
Passed? |
|
Description |
Select Preferences from the Edit menu. Set the left and top margins to 25 and the cell size to 25. |
Requirement |
R-helper-process-003 |
Passed? |
|
Description |
The first clue to solve is column 4 : 5.1. There is only one solution to this clue. Hold down the left mouse button on the top cell of column 4. Drag the mouse down to the fifth cell and release the mouse button. The first five cells should be SHADED. Left-click twice on the last cell in column four. The cell state should be BLANK, shown by a red dot in the centre of the cell. Right-click on the cell to move it back to SHADED. |
Requirement |
R-helper-process-004, R-helper-process-006 |
Passed? |
|
Description |
The next clue to solve is row 3 : 3.2. The block of three must fill cells 2,3,4 and the block of two must fill 6,7. Use the mouse to set these cells. Did the traffic light at the end of row 3 become green when the clue was satisfied? The cells which have not been set should now contain red dots to indicate that they are definitely blank. |
Requirement |
R-helper-data-002 |
Passed? |
|
Description |
Save the file as req_test.non. |
Requirement |
R-helper-new-001 |
Passed? |
|
Description |
Select New from the File menu and create a new puzzle of size 10 x 10. |
Requirement |
R-helper-process-008 |
Passed? |
|
Description |
Using the mouse to shade cells, draw a picture of your initials. When complete, select Generate Clues from the Edit menu. Check that the clues match the picture you have drawn. |
Requirement |
R-helper-data-005 |
Passed? |
|
Description |
Select Clear Grid from the Edit menu. All cells in the grid should be reset to CLEAR. |
Requirement |
R-helper-process-009 |
Passed? |
|
Description |
Shade in any line in your puzzle so that it satisfies its clue. The CLEAR cells should not be set to BLANK. Use the Preferences dialog to turn AutoFill back on. Has the line been completed? |
Requirement |
R-helper-data-003 |
Passed? |
|
Description |
Open the file which you previously saved (req_test.non). Is it displayed in the same way as before? |
Requirement |
R-helper-solve-001 |
Passed? |
|
Description |
If on a Unix machine, select Solve from the tools menu. Does the Solver correctly solve the puzzle? |
Requirement |
R-helper-process-004, R-helper-process-005 |
Passed? |
|
Description |
Select Edit Clues from the Edit menu and change the value of any clue. Select OK. The Helper should indicate that the sum of the clues is incorrect. Try some other possible entries. Use words, numbers and characters. The Helper should not allow invalid data entry. |
Requirement |
R-helper-process-007 |
Passed? |
|
Description |
Fill in any row by holding down the mouse button and dragging. Select Undo from the Edit menu. The grid should revert to its previous state. |
Requirement |
R-helper-image-001, R-helper-image-002, R-helper-image-003 |
Passed? |
|
Description |
Select Create from Image from the Tools menu. Open the file vsmallstrath.gif. Click on Capture. The image should be copied to the grid and appropriate clues created. |
Requirement |
R-helper-image-001, R-helper-image-002, R-helper-image-003 |
Passed? |
|
Description |
Select Create from Image from the Tools menu. Open the file piper.jpg. Click on Capture. The image should be copied to the grid and appropriate clues created. |
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/magicsq.cc
// --------------------------------------------------------------------------
// Copyright (C) 1990-1997 by ILOG.
// All Rights Reserved.
//
// N O T I C E
//
// THIS MATERIAL IS CONSIDERED A TRADE SECRET BY ILOG.
// UNAUTHORIZED ACCESS, USE, REPRODUCTION OR DISTRIBUTION IS PROHIBITED.
// --------------------------------------------------------------------------
/* ------------------------------------------------------------
Problem Description
-------------------
A magic square is a square matrix where the sum of all rows,
columns, and diagonals are equal, but the numbers in the magic
square are consecutive and start with
1.
Here is a magic square of size 3:
__________
|8 | 3 | 4 |
|1 | 5 | 9 |
|6 | 7 | 2 |
----------
------------------------------------------------------------
*/
// Magic square
#include <ilsolver/ilcint.h>
#define sigma(j,min,max,var,constraint){ \
IlcIntVarArray array(m, n); \
for( j=min;j<=max;j++) array[j]=var;\
m.add(IlcSum(array) constraint); \
}
int main(int argc, char* argv[]){
IlcManager m(IlcEdit);
#if defined(ILCLOGFILE)
m.openLogFile("magicsq.log");
#endif
IlcInt n = (argc > 1) ? atoi(argv[1]) : 5;
IlcInt sum = n*(n*n+1)/2;
IlcInt i, j;
IlcIntVarArray Square(m, n*n, 1, n*n);
// All the tokens must be different
m.add(IlcAllDiff(Square));
// The constraints on lines
for (i = 0; i < n; i++)
sigma(j,
0, n-1, Square[n*i+j], == sum);
// The constraints on cols
for (i = 0; i < n; i++)
sigma(j,
0, n-1, Square[n*j+i], == sum);
// Constraint on 1st diagonal
sigma(i, 0, n-1, Square[n*i+i],
== sum);
// Constraint on 2nd diagonal
sigma(i, 0, n-1, Square[n*i+n-i-1],
== sum);
m.add(IlcGenerate(Square, IlcChooseMinSizeInt));
if (m.nextSolution()){
for (i = 0; i < n; i++){
for (j = 0; j < n; j++)
m.out() << " " << Square[n*i+j];
m.out() << endl;
}
m.out() << endl;
}
else
m.out() << "No solution " << endl;
m.printInformation();
#if defined(ILCLOGFILE)
m.closeLogFile();
#endif
m.end();
return 0;
}
/*
1 2 13 24 25
3 23 17 6 16
20 21 11 8 5
22 4 14 18 7
19 15 10 9 12
*/
This evaluation is divided into two parts. The first will show you how to load a Nonogram, solve it using the Nonogram Helper, and save the file. The second part of the evaluation involves you creating a new Nonogram puzzle. To enable you to do these tasks you will be provided with the Introduction and Getting Started sections of the Nonogram Helper User Manual.
Feel free to ask any questions during the course of this evaluation.
Part 1 : Opening, Solving and Saving
1. Using the Open option in the File menu, open the file swan.non
2. Select Preferences from the Edit menu and set the cell length to 25.
3. Use the Helper and your skill and judgement to solve the puzzle.
4. When the puzzle is complete, save your solution as <name>.non.
NB. Replace <name> with your own name. eg. gary.non
Part 2 : Creating a New Puzzle
Row Clues |
Column Clues |
3 |
1.2 |
2.1 |
3.1 |
3.2 |
1.5 |
2.2 |
7.1 |
6 |
5 |
1.5 |
3 |
6 |
4 |
1 |
3 |
2 |
Thank you very much for your time. Please complete a Nonogram Helper Evaluation Questionnaire.
Nonogram Helper Evaluation Questionnaire
Name : ________________________ Date : __ / __ / 1999
Platform : Windows 95 / X-Windows
1. Past Experience
1.1 How many Nonograms have you previously attempted to solve?
None 1 - 2 3 - 5 6 - 9 10+
1.2 Have you used the Nonogram Helper before? Yes / No
1.3 Of the following devices, software and systems, check those that you have personally used and are familiar with :
__ word processor __ mouse __ file manager
__ PC __ graphics software__ keyboard
__ Unix workstation __ Apple Mac __ computer games
__ Windows 95 __ X-Windows __ spreadsheet
2.1 Overall reactions to the system : terrible wonderful
1 2 3 4 5 6 7 8 9 NA
2.2 frustrating satisfying
1 2 3 4 5 6 7 8 9 NA
2.3 dull stimulating
1 2 3 4 5 6 7 8 9 NA
2.4 difficult easy
1 2 3 4 5 6 7 8 9 NA
2.5 inadequate power adequate power
1 2
3 4 5
6 7 8
9 NA
3. Screen
3.1 Characters on the screen hard to read easy to read
1 2 3 4 5 6 7 8 9 NA
3.2 Was the arrangement of illogical logical
information on the screen 1 2 3 4 5 6 7 8 9 NA
3.3 Did the finished puzzle resemble a not at all very much
picture? 1
2 3 4
5 6 7
8 9 NA
4. Terminology and System Information
4.1 Error messages unhelpful helpful
1 2
3 4 5
6 7 8
9 NA
5. Learning
5.1 Learning to use the system difficult easy
1 2 3 4 5 6 7 8 9 NA
5.2 Exploration of features by trial and discouraging encouraging
error 1 2 3 4 5 6 7 8 9 NA
5.3 Supplemental reference materials confusing clear
1 2
3 4 5
6 7 8
9 NA
6. System Capabilities
6.1 System Speed too slow fast enough
1 2 3 4 5 6 7 8 9 NA
6.2 How reliable is the system? very unreliable very reliable
1 2 3 4 5 6 7 8 9 NA
6.3 Correcting your mistakes difficult easy
1 2
3 4 5
6 7 8
9 NA
7. Comparison with solving Nonograms on paper
7.1 Do you prefer
solving Nonograms using Paper / Nonogram Helper
8. User's Comments
Please write
any comments you have in the space below.