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


Download 471 Kb.
NameAbstract 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’.
page1/23
A typeAbstract
  1   2   3   4   5   6   7   8   9   ...   23



Submitted for the Degree of B.Sc. in Computer Science

1998-1999


Final Year Project Report
Puzzle Solving
Gary Duncan




Except where explicitly stated all work in this report, including appendices, is my own and was carried out during my final year. It has not been submitted for assessment in any other context.

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

Abstract 2

Acknowledgements 3

2 Related Work and Background 9

3 Related Work 9

4 Introduction to Constraint Satisfaction Problems 10

5 Example : Room Allocation 10

6 ILOG Solver C++ Toolkit 12

7 Example : Magic Square 12

8 Helpers Available on the Internet 15

9 Problem Description and Specification 19

10 Nonogram Solver 20

11 The Problem 20

12 The Objectives 21

13 Summary of Solver Specification 21

14 Helper Requirements 22

15 Define Requirements Specification 23

16 High Level Essential Use Cases 27

17 Create Prototype 30

18 System Design 32

19 Solver System Design 32

20 A Simple Problem Representation 34

21 Identifying a suitable Mini-problem 34

22 Definition of Constraints 36

23 Evolution of the Mini-Problem 37

24 Helper System Design 40

25 Identifying Objects 40

26 Specifying Attributes and Methods 40

27 User Interface Design 43

28 File Handling 45

29 Detailed Design / Implementation 48

30 Implementation of Constraints on Mini-Problem 48

31 Extension to complete puzzle 50

32 Implementation of the Helper 52

33 Clue Generation 52

34 Development of Nonogram Maker 53

35 Verification and Validation 54

36 Module Testing of File Handling 54

37 Systems testing of the Solver 59

38 Validation testing of the Helper 59

39 Critical Evaluation 60

40 Evaluation of Nonogram Solver 60

41 Evaluation of Helper 61

42 Results of User Interface Evaluation 62

43 Project Plan Review 63

44 Summary and Conclusions 64

45 References 66

46 Appendix A : User Guide 68

47 Nonogram Solver 69

48 Nonogram Helper 71

49 Opening a File 71

50 Starting to Solve 72

51 Saving 72

52 Creating a New Puzzle 72

53 Creating a Puzzle from an Image 73

54 Using Solver to Solve the Puzzle 73

55 Changing preferences 73

56 Installation 75

57 Appendix B : Detailed Specification and Design 76

58 Functional Specification – Solver 76

59 Data requirements 76

60 General Process Requirements 76

61 Functional Specification – Helper 77

62 Data Requirements 77

63 General Process Requirements 77

64 New Nonogram Requirements 78

65 Solve Requirements 78

66 Additional Helper Requirements 78

67 Additional Process Requirements 78

68 Image Requirements 78

69 Additional Flow Diagrams for File Reading 80

70 UML Diagrams for Helper Objects 84

71 Variables required to model the Nonogram puzzle 86

72 Appendix C : Detailed Test Strategy and Test Cases 88

73 Test Cases for File Handling Module 88

74 Test Results for Solver System Testing 91

75 Helper Test Strategy 95

76 Appendix D : Magic Square Listing 99

77 Appendix E : Nonogram Helper Evaluation Tasks 102

78 Appendix F : Questionnaire 104

79 Appendix G : Program Listing 106

1 IntroductionNonograms are logic puzzles that originated in Japan. A Nonogram consists of a rectangular grid with one set of clues for each row and column of the grid. Solving the clues determines which cells in the puzzle are to be shaded to produce a picture. Clues are of the form ‘x1.x2. . .xn’, which translates as x1 shaded cells followed by at least one blank cell, followed by x2 shaded squares followed by at least one blank cell etc.

For example, the grid depicted in fig. 1 can be solved to give the picture in fig. 2.




Fig. 1 – Blank grid with clues



Fig. 2 – Completed puzzle


This aim of this project was to identify a suitable representation of the Nonogram puzzle and develop a program capable of solving Nonogram puzzles. This program was to be linked to a graphical front-end which helped the user to solve the puzzles. These aims are summarised in the following three objectives :

  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.
  1   2   3   4   5   6   7   8   9   ...   23

Share in:

Related:

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’. iconAlphabet and number puzzles

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’. iconQuizzes, crossword puzzles, flashcards, animations, interactive maps, timelines, etc

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’. iconIs an approach to programming introduced by Donald Knuth in which...

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’. iconAbstract: Fuzzy logic is a rule-based decision process that seeks...

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’. iconAbstract: As attachment parenting has become more popular, many feminists...

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’. iconAbstract Freshmen engineering students are being introduced to electronic...

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’. iconNewsletter featured products/solutions/updates/npi

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’. iconNewsletter featured products/solutions/updates/npi

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’. iconThe following are some suggestions from John Dunbar, the developer...

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’. iconFsd-218 Every formal radiogram message originated and handled should...

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’. iconNothing but stars, scattered across the blackness as though the Creator had

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’. iconBootable Media Creator version 50. 2860a

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’. iconThe poem is drawn from the story of Little Red Riding Hood, a tale...

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’. iconMini great Britain

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’. iconFirst published in Great Britain by

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’. iconMasthead: Easy Media creator™ 9 Deluxe Suite

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’. icon2006 Academia, d o. o. Hastings, Great Britain

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’. iconBritain’s High Class Are Flocking to Islam

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’. iconBooks popular Interest

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’. iconThe Best of the Popular Newspaper Column




manual


When copying material provide a link © 2017
contacts
manual-guide.com
search