Abstract

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.

Acknowledgements

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 wasn’t  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. 

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 :

1. 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.
2. Develop a Helper application which displays the Nonogram on screen and allows the user to input ‘moves’.  The Helper should aid the user by illustrating the consequences of these moves.  A number of Nonogram Helpers available on the Internet should be critically evaluated with regard to their interface and functionality.  The results of this evaluation should become the basis of the requirements for this component of the project.  It is intended that the Helper should improve on the functionality currently available.
3. Combine the two applications so that Solver output is displayed in the Helper.

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.

Related Work and Background

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.

Related Work

An initial background in Constraint Satisfaction Problems was gained by reading Barbara Smith’s 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.

 Introduction to Constraint Satisfaction Problems

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.

Example : Room Allocation

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.

 ILOG Solver C++ Toolkit

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.

Example : Magic Square

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.  Here’s a magic square of size 3: 

 
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

1. For each row r
2. Create a new array with room for n elements
3. Copy the row values from the row r into the array
4. Add the constraint that the sum of the array elements must equal sum.

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.

 Helpers Available on the Internet

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 :

• Nonogram : Solver by Hirofumi Fujiwara

   Location :  http://www.pro.or.jp/~fuji/java/try/nonogram/index-eng.html

• Alex' Nonogram Page by Alexander Fritze

   Location : http://www.phy.hw.ac.uk/~phy_af/nonograms.html

• Paint by Numbers by Mitsuhiro Kajitani

   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 :

1. Presentation of Grid

This sections deals with the style and colours used to display the Nonogram grid and clues on the screen.

2. Cell States Available

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.

3. Functionality

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.

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 – Kajitani’s 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.

Problem Description and Specification

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. 

Nonogram Solver

In the ILOG Solver User’s 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 :

1. Describe the problem

Define a complete and exhaustive statement of all constraints.

2. Specify the objectives of the application

Is the application a ‘black-box’ which searches for solutions with no user input?  Are there response time issues?

3. Design a model and prototype the application

Experiment with small-scale models to acquire useful information about the problem.  When the problem is well-defined a model can be designed.

4. Implement and optimise the application

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 Problem

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 Objectives

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.

Summary of Solver Specification

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.

 Helper Requirements

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.

Define Requirements Specification

The initial requirements for the Helper were derived from discussion with the project supervisor, the author’s 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 Fujiwara’s and Kajitani’s 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 author’s 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 :

• Fujiwara’s clue entry interface
• Clue highlighting
• Clicking on clues to mark them as used

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.

 High Level Essential Use Cases

‘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 : 

1. Loading a puzzle
2. Saving the puzzle
3. Creating a new Nonogram by entering clues
4. Creating a New Nonogram by drawing a puzzle
5. Using the Solver component to solver the puzzle

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

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

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

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

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

 Create Prototype

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 :

• Create a window to display the puzzle
• Add a menubar containing a File menu and the options New, Open, Save As and Exit.
• Draw a 7x7 grid in black on the screen
• Allow the user to click on cells such the cells are shaded as described in section 4.2.3 – User Interface Design.

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.

System Design

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.

Solver System Design

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 
 
 
 
 
 

 A Simple Problem Representation

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.

Identifying a suitable Mini-problem

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 :

1. 0 <= Length B0 <= 3
2. Length S0 = 2
3. 1 <= Length B1 <= 4
4. Length S1 = 1
5. 0 <= Length B2 <= 3
6. The sum of all lengths must equal 7.

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 :

Definition of Constraints

Using an array of sets to represent each line allowed the following constraints to be expressed :

6. None of the sets may intersect because it is impossible for a cell to be shaded and blank at the same time.
7. The cardinality of the end sets of blank cells must be greater than or equal to 0. 

• The cardinality of set B0 must be greater than or equal to 0.
• The cardinality of set B2 must be greater than or equal to 0.

8. The cardinality of other sets of blank squares must be greater than or equal to 1.

• The cardinality of set B1 must be greater than or equal to 1.

9. The sets describing shaded cells must have cardinality equal to the appropriate clue.

• The cardinality of set S1 must equal 2
• The cardinality of set S2 must equal 1

10. Elements in a set must be contiguous.

11. All values in a set must be less than the elements in subsequent sets.

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.

12. When a cell in a row is shaded, the corresponding square in the appropriate column must be shaded.  Mathematically, if cell i of row j is shaded, cell j of column i must also be shaded.

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.

 Evolution of the Mini-Problem

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 :

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 :

• The number of rows and columns in the puzzle.

   This allows arrays of the correct size to be created.

• The maximum number of clues for a row and for a column.

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.

• The number of clues for each row and column.

   Calculated while clues are being read and stored.

• The actual row and column clues.

This information allowed appropriately sized variables to be constructed to model the grid area.  These variables are described below :

• The total number of blocks in all rows and in all columns.  This allowed two arrays of sets to be created to represent the rows and columns
• The number of blocks in each row and column.  This was calculated from the number of clues in each row and column.
• The running total of blocks for each row and for each column.  When combined with the number of blocks in each row or column this allowed the blocks corresponding to a particular line to be extracted.
• The sum of all row clues and all column clues for each row and column.
• The sum of all row clues and all column clues for the entire puzzle.  If these are different there is an error in the puzzle.
• Arrays of sets to store the rows and columns.
• The minimum and maximum values for each block.
• The union of shaded sets for each row and each column.
• The union of blank sets for each row and each column.

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.

 Helper System Design

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).

Identifying Objects

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).

• Helper – The overall system
• Solver – The Solver application
• Grid – The ‘playing area’
• Clues – The row clues or column clues
• Maker – A class which creates a puzzle from an image
• OK Dialog box – A dialog box which displays a message and an OK button
• Cancel Dialog box – A dialog box which allows the user to cancel the Solver
• New Dialog box – Allows the user to specify the dimensions of the grid
• Clues Dialog box – Allows the user to specify the clues for the puzzle
• Preferences Dialog box – Allows the user to set the size of the cells etc.

Specifying Attributes and Methods

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 :

13. Methods which manipulate data, eg. get or set the values of attributes.
14. Methods which perform computations on the attributes, eg. check if the grid is satisfied.
15. Methods which monitor the state of an object and perform an action when a specified event occurs, eg. objects which contain buttons or menus monitor for an ‘ActionEvent’ and use the value of this to carry out some action.

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.

 User Interface Design

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 Kajitani’s 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. 

  File Handling

The datafile was required to store details in four sections :

16. The dimensions of the Nonogram.  This simplified implementation as it was not necessary to count the number of clue lines before creating sufficient space for the clues.
17. The set of row clues, delimited by a given character.
18. The set of column clues, delimited by a given character.
19. A representation of the grid so that the state of play can be saved.  This is required for the Helper but not the Solver.

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 : 

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 :

20. SETUP
21. ROW_HEADER
22. READING_ROW
23. READING_COL
24. GRID

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

Detailed Design / Implementation

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.

Implementation of Constraints on Mini-Problem

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 : 

• an instance of IlcIntSetVarArray called block
• an instance of IlcIntVarArray called Clues which holds the clues
• an instance of integer called number_of_clues which holds the number of clues in Clues
• an instance of IlcIntVarArray called Max which holds the maximum index of each block
• an instance of IlcIntVarArray called Min which holds the minimum index of each block
• an instance of integer called number_of_blocks which holds the number of sets contained in block.  This value can be calculated for a line with n clues as 2 * n + 1.

1. None of the sets may intersect.

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]));

2. The cardinality of the end sets of blank squares must be greater than or equal to 0.

This statement is true for all sets and therefore did not require to be posted.

3. The cardinality of other sets of blank squares must be greater than or equal to 1.

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);

4. The sets describing shaded squares must have cardinality equal to the appropriate clue.

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))

5. Elements in a set must be contiguous.

This is expressed with two sets of constraints.  The first states :

• The difference between the max and min values of a block is equal to the cardinality of that block.
• If the cardinality is greater than 0, max must be a member of that set.
• If the cardinality is greater than 0, min must be a member of that set.

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 :

• From the lowest possible min to the highest possible max for a set, if a value is between min and max, it must be a member of the set.  getMin() is a method which returns the minimum value in the domain of a variable.  Similarly, getMax() returns the maximum.  IlcMember (value, set) constrains value to be a member of set set.

       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.

6. All values in a set must be less than the elements in subsequent sets.

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.

Extension to complete puzzle

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.

7. When a cell in a row is shaded, the corresponding square in the appropriate column must be shaded.  Mathematically, if cell i of row j is shaded, cell j of column i must also be shaded.

This was implemented by defining :

• the union of shaded blocks for each row
• the union of shaded blocks for each column
• the union of blank blocks for each row
• the union of blank blocks for each column

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.

 Implementation of the Helper

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.

Clue Generation

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.

Development of Nonogram Maker

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

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 :

1. Module testing of the File Handling code.
2. Systems testing of the Solver, ensuring that inputs result in expected outputs.
3. Validation testing of the Helper, ensuring that all requirements were exercised.

Module Testing of File Handling

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 : 

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. 

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

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.

 Systems testing of the Solver

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.

Validation testing of the Helper

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.

Critical Evaluation

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 Helper’s functionality.  At the end of this each user filled in a questionnaire based on Schneiderman’s 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.

Evaluation of Nonogram Solver

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.

Evaluation of Helper

The objective of the Helper component of the project can be divided into three areas :

1. Develop a Helper application which displays the Nonogram on screen and allows the user to input ‘moves’.
2. The Helper should aid the user by illustrating the consequences of these moves.
3. It is intended that the Helper should improve on the functionality currently available.

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, Fujiwara’s 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.  Kajitani’s 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, Fujiwara’s 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 :

• A method of designating squares as guesses
• Re-designing the clue entry dialog box, possibly along the lines of that used by Fujiwara

Results of User Interface Evaluation

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. 

Project Plan Review

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.

Summary and Conclusions

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.

• Refining the Create from Image so that a GIF or JPG image of any size and number of colours could be imported.  This would involve adding image processing functionality which would half-tone and scale the image.
• The presentation of the user-interface could be improved by displaying the grid in a more eye-catching manner.
• Adapting the Solver so that it can run as a CGI script.  Users could submit clues across the Internet and the Solver would display the result as a table.
• Converting the Helper to an applet would enable the current interface to be used with the CGI Solver.
• Many users requested an extra cell state to be added so that guesses could be made and differentiated from other cells.  This is especially useful in large puzzles.
• Extend the Helper so that a puzzle created in the Helper could be checked to see if it is a ‘good’ puzzle.  ‘Good’ could be defined as, for example, it can be solved by propagation, has only one solution and takes less than 15 seconds to be solved by the Solver.
• Help the user by propagating BLANK cells when a user designates a cell as SHADED.

References

25. Garside, R and Mariani, J., 1998, Java: First Contact, Course Technology.
26. Gent, I., 1998, Battling Battleships : A (failed?) experiment in dual representation in Solver, University of Strathclyde Department of Computer Science, Foot Note 320.
27. Grand, M., 1998, Patterns in Java, Wiley.
28. ILOG, 1997, ILOG Solver 4.0 User’s Manual.
29. Ishida,N. and Dalgety, J., 1994, 2nd Book of Nonograms, Pan Books.
30. Pressman, R., 1992,  Software Engineering : A Practitioner’s Approach, McGraw-Hill.
31. Smith, Barbara M., 1995, A Tutorial on Constraint Programming, University of Leeds School of Computer Studies, Report 95.14.
32. Schneiderman, B., 1992, Designing the User Interface : Strategies for Effective Human-Computer Interaction, Addison-Wesley.
33. Simpson, S., 1999, Nonogram Solver Repository, http://www.comp.lancs.ac.uk/computing/users/ss/pub/nonogram
34. Ueda, N. and Nagao, T., 1996, NP-Completeness Results for NONOGRAM via Parsimonious Reductions, Titech Technical Report (Dept. of CS)
35. Wood, M., 1996, Software Engineering 1 Coursenotes, University of Strathclyde Department of Computer Science.

Appendix A : User Guide

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.

 Nonogram Solver

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. 

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. 

When called with the command 

             solver chick.non

the puzzle above would result in the following output : 

**************************************

Nonogram Solver

File : chick.non

************************************** 

Solution #1

~~~~~~~~~~~ 

***

** *

*** **

  *****

  ****

    *

   **

 Nonogram Helper

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

Opening a File

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

 Starting to Solve

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.

Saving

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.

Creating a New Puzzle

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.

1. By entering the clues.

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.

2. By drawing the finished picture and allowing the Helper to generate the clues.

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.

Creating a Puzzle from an Image

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.

Using Solver to Solve the 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.

Changing preferences

The Preferences option in the Edit menu allows the following features to be set :

• The distance between the puzzle and the left margin
• The distance between the puzzle and the top margin
• The length of the cells
• Toggle AutoCompleteLines on and off.  This feature automatically fills in CLEAR cells as BLANK when a row or column satisfies its clue.

 Installation

Nonogram Solver Installation

The Nonogram Solver requires ILOG Solver 4.3 to be installed with a valid license.  The distribution consists of two files :

1. Solver.cc  The source code
2. Makefile  Makefile

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 :

1. CluesDialog.java
2. Clues.java
3. Maker.java
4. Grid.java
5. Helper.java
6. CancelDialog.java
7. OkDialog.java
8. PrefDialog.java
9. NewDialog.java

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.

Appendix B : Detailed Specification and Design

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.

Functional Specification – Solver

Data 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. 

General Process Requirements

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.

 Functional Specification – Helper

Data Requirements

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’.

General Process Requirements

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

36. CLEAR – The initial state.
37. SHADED – The cell is definitely shaded.
38. BLANK – The cell is definitely blank.

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.

New Nonogram Requirements

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.

Solve Requirements

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.

Additional Helper Requirements

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.

Additional Process Requirements

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.

Image Requirements

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.

 Additional Flow Diagrams for File Reading

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.

 UML Diagrams for Helper Objects

Helper Object 
 
 
 
 
 
 

Clues Object 
 
 
 
 
 
 
 
 
 

Maker Object 
 
 
 
 

Grid Object 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Dialog Box Objects 
 
 

 Variables required to model the Nonogram puzzle

Variables describing the clue information 

Variables describing the grid 

Appendix C : Detailed Test Strategy and Test Cases

Test Cases for File Handling Module

The following test cases correspond to the tests described in chapter 7.  In each example the erroneous line is shown in bold.. 

 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

 Helper Test Strategy

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. 

Appendix D : Magic Square Listing

// -------------------------------------------------------------- -*- 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

*/

Appendix E : Nonogram Helper Evaluation Tasks

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

1. The puzzle you will create contains 9 rows and 8 columns.  Using the New option in the File menu create a new puzzle with the appropriate dimensions.
2. Select Edit Clues from the Edit menu and enter the following clues :

3. Solve the puzzle.

4. Save your solution as <name>_new.non

Thank you very much for your time.  Please complete a Nonogram Helper Evaluation Questionnaire.

Appendix F : 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. Overall User Reactions

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. 

Appendix G : Program Listing