diff options
| -rw-r--r-- | COPYING | 340 | ||||
| -rw-r--r-- | Doxyfile | 1218 | ||||
| -rw-r--r-- | HISTORY | 6 | ||||
| -rw-r--r-- | Makefile | 96 | ||||
| -rw-r--r-- | README | 81 | ||||
| -rw-r--r-- | backtrack.cpp | 140 | ||||
| -rw-r--r-- | backtrack.h | 159 | ||||
| -rw-r--r-- | bitmap.cpp | 151 | ||||
| -rw-r--r-- | bitmap.h | 53 | ||||
| -rw-r--r-- | generator.cpp | 128 | ||||
| -rw-r--r-- | generator.h | 77 | ||||
| -rw-r--r-- | i18n.cpp | 247 | ||||
| -rw-r--r-- | i18n.h | 23 | ||||
| -rw-r--r-- | menu.cpp | 244 | ||||
| -rw-r--r-- | menu.h | 66 | ||||
| -rw-r--r-- | puzzle.cpp | 260 | ||||
| -rw-r--r-- | puzzle.h | 163 | ||||
| -rw-r--r-- | setup.cpp | 80 | ||||
| -rw-r--r-- | setup.h | 60 | ||||
| -rw-r--r-- | solver.cpp | 95 | ||||
| -rw-r--r-- | solver.h | 104 | ||||
| -rw-r--r-- | sudoku.cpp | 114 | ||||
| -rw-r--r-- | sudoku.h | 24 | ||||
| -rw-r--r-- | tools/Makefile | 41 | ||||
| -rw-r--r-- | tools/sudoku_generator.cpp | 378 |
25 files changed, 4348 insertions, 0 deletions
@@ -0,0 +1,340 @@ + GNU GENERAL PUBLIC LICENSE + Version 2, June 1991 + + Copyright (C) 1989, 1991 Free Software Foundation, Inc. + 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +License is intended to guarantee your freedom to share and change free +software--to make sure the software is free for all its users. This +General Public License applies to most of the Free Software +Foundation's software and to any other program whose authors commit to +using it. (Some other Free Software Foundation software is covered by +the GNU Library General Public License instead.) You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +this service if you wish), that you receive source code or can get it +if you want it, that you can change the software or use pieces of it +in new free programs; and that you know you can do these things. + + To protect your rights, we need to make restrictions that forbid +anyone to deny you these rights or to ask you to surrender the rights. +These restrictions translate to certain responsibilities for you if you +distribute copies of the software, or if you modify it. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must give the recipients all the rights that +you have. You must make sure that they, too, receive or can get the +source code. And you must show them these terms so they know their +rights. + + We protect your rights with two steps: (1) copyright the software, and +(2) offer you this license which gives you legal permission to copy, +distribute and/or modify the software. + + Also, for each author's protection and ours, we want to make certain +that everyone understands that there is no warranty for this free +software. If the software is modified by someone else and passed on, we +want its recipients to know that what they have is not the original, so +that any problems introduced by others will not reflect on the original +authors' reputations. + + Finally, any free program is threatened constantly by software +patents. We wish to avoid the danger that redistributors of a free +program will individually obtain patent licenses, in effect making the +program proprietary. To prevent this, we have made it clear that any +patent must be licensed for everyone's free use or not licensed at all. + + The precise terms and conditions for copying, distribution and +modification follow. + + GNU GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License applies to any program or other work which contains +a notice placed by the copyright holder saying it may be distributed +under the terms of this General Public License. The "Program", below, +refers to any such program or work, and a "work based on the Program" +means either the Program or any derivative work under copyright law: +that is to say, a work containing the Program or a portion of it, +either verbatim or with modifications and/or translated into another +language. (Hereinafter, translation is included without limitation in +the term "modification".) Each licensee is addressed as "you". + +Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running the Program is not restricted, and the output from the Program +is covered only if its contents constitute a work based on the +Program (independent of having been made by running the Program). +Whether that is true depends on what the Program does. + + 1. You may copy and distribute verbatim copies of the Program's +source code as you receive it, in any medium, provided that you +conspicuously and appropriately publish on each copy an appropriate +copyright notice and disclaimer of warranty; keep intact all the +notices that refer to this License and to the absence of any warranty; +and give any other recipients of the Program a copy of this License +along with the Program. + +You may charge a fee for the physical act of transferring a copy, and +you may at your option offer warranty protection in exchange for a fee. + + 2. You may modify your copy or copies of the Program or any portion +of it, thus forming a work based on the Program, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) You must cause the modified files to carry prominent notices + stating that you changed the files and the date of any change. + + b) You must cause any work that you distribute or publish, that in + whole or in part contains or is derived from the Program or any + part thereof, to be licensed as a whole at no charge to all third + parties under the terms of this License. + + c) If the modified program normally reads commands interactively + when run, you must cause it, when started running for such + interactive use in the most ordinary way, to print or display an + announcement including an appropriate copyright notice and a + notice that there is no warranty (or else, saying that you provide + a warranty) and that users may redistribute the program under + these conditions, and telling the user how to view a copy of this + License. (Exception: if the Program itself is interactive but + does not normally print such an announcement, your work based on + the Program is not required to print an announcement.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Program, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Program, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Program. + +In addition, mere aggregation of another work not based on the Program +with the Program (or with a work based on the Program) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may copy and distribute the Program (or a work based on it, +under Section 2) in object code or executable form under the terms of +Sections 1 and 2 above provided that you also do one of the following: + + a) Accompany it with the complete corresponding machine-readable + source code, which must be distributed under the terms of Sections + 1 and 2 above on a medium customarily used for software interchange; or, + + b) Accompany it with a written offer, valid for at least three + years, to give any third party, for a charge no more than your + cost of physically performing source distribution, a complete + machine-readable copy of the corresponding source code, to be + distributed under the terms of Sections 1 and 2 above on a medium + customarily used for software interchange; or, + + c) Accompany it with the information you received as to the offer + to distribute corresponding source code. (This alternative is + allowed only for noncommercial distribution and only if you + received the program in object code or executable form with such + an offer, in accord with Subsection b above.) + +The source code for a work means the preferred form of the work for +making modifications to it. For an executable work, complete source +code means all the source code for all modules it contains, plus any +associated interface definition files, plus the scripts used to +control compilation and installation of the executable. However, as a +special exception, the source code distributed need not include +anything that is normally distributed (in either source or binary +form) with the major components (compiler, kernel, and so on) of the +operating system on which the executable runs, unless that component +itself accompanies the executable. + +If distribution of executable or object code is made by offering +access to copy from a designated place, then offering equivalent +access to copy the source code from the same place counts as +distribution of the source code, even though third parties are not +compelled to copy the source along with the object code. + + 4. You may not copy, modify, sublicense, or distribute the Program +except as expressly provided under this License. Any attempt +otherwise to copy, modify, sublicense or distribute the Program is +void, and will automatically terminate your rights under this License. +However, parties who have received copies, or rights, from you under +this License will not have their licenses terminated so long as such +parties remain in full compliance. + + 5. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Program or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Program (or any work based on the +Program), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Program or works based on it. + + 6. Each time you redistribute the Program (or any work based on the +Program), the recipient automatically receives a license from the +original licensor to copy, distribute or modify the Program subject to +these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties to +this License. + + 7. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Program at all. For example, if a patent +license would not permit royalty-free redistribution of the Program by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Program. + +If any portion of this section is held invalid or unenforceable under +any particular circumstance, the balance of the section is intended to +apply and the section as a whole is intended to apply in other +circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system, which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 8. If the distribution and/or use of the Program is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Program under this License +may add an explicit geographical distribution limitation excluding +those countries, so that distribution is permitted only in or among +countries not thus excluded. In such case, this License incorporates +the limitation as if written in the body of this License. + + 9. The Free Software Foundation may publish revised and/or new versions +of the General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + +Each version is given a distinguishing version number. If the Program +specifies a version number of this License which applies to it and "any +later version", you have the option of following the terms and conditions +either of that version or of any later version published by the Free +Software Foundation. If the Program does not specify a version number of +this License, you may choose any version ever published by the Free Software +Foundation. + + 10. If you wish to incorporate parts of the Program into other free +programs whose distribution conditions are different, write to the author +to ask for permission. For software which is copyrighted by the Free +Software Foundation, write to the Free Software Foundation; we sometimes +make exceptions for this. Our decision will be guided by the two goals +of preserving the free status of all derivatives of our free software and +of promoting the sharing and reuse of software generally. + + NO WARRANTY + + 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY +FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN +OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES +PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED +OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS +TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE +PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, +REPAIR OR CORRECTION. + + 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR +REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, +INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING +OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED +TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY +YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER +PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE +POSSIBILITY OF SUCH DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + <one line to give the program's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + +Also add information on how to contact you by electronic and paper mail. + +If the program is interactive, make it output a short notice like this +when it starts in an interactive mode: + + Gnomovision version 69, Copyright (C) year name of author + Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, the commands you use may +be called something other than `show w' and `show c'; they could even be +mouse-clicks or menu items--whatever suits your program. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the program, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the program + `Gnomovision' (which makes passes at compilers) written by James Hacker. + + <signature of Ty Coon>, 1 April 1989 + Ty Coon, President of Vice + +This General Public License does not permit incorporating your program into +proprietary programs. If your program is a subroutine library, you may +consider it more useful to permit linking proprietary applications with the +library. If this is what you want to do, use the GNU Library General +Public License instead of this License. diff --git a/Doxyfile b/Doxyfile new file mode 100644 index 0000000..42a1785 --- /dev/null +++ b/Doxyfile @@ -0,0 +1,1218 @@ +# Doxyfile 1.4.2 + +# This file describes the settings to be used by the documentation system +# doxygen (www.doxygen.org) for a project +# +# All text after a hash (#) is considered a comment and will be ignored +# The format is: +# TAG = value [value, ...] +# For lists items can also be appended using: +# TAG += value [value, ...] +# Values that contain spaces should be placed between quotes (" ") + +#--------------------------------------------------------------------------- +# Project related configuration options +#--------------------------------------------------------------------------- + +# The PROJECT_NAME tag is a single word (or a sequence of words surrounded +# by quotes) that should identify the project. + +PROJECT_NAME = "VDR plugin 'Sudoku'" + +# The PROJECT_NUMBER tag can be used to enter a project or revision number. +# This could be handy for archiving the generated documentation or +# if some version control system is used. + +PROJECT_NUMBER = $(VERSION) + +# The OUTPUT_DIRECTORY tag is used to specify the (relative or absolute) +# base path where the generated documentation will be put. +# If a relative path is entered, it will be relative to the location +# where doxygen was started. If left blank the current directory will be used. + +OUTPUT_DIRECTORY = + +# If the CREATE_SUBDIRS tag is set to YES, then doxygen will create +# 4096 sub-directories (in 2 levels) under the output directory of each output +# format and will distribute the generated files over these directories. +# Enabling this option can be useful when feeding doxygen a huge amount of +# source files, where putting all generated files in the same directory would +# otherwise cause performance problems for the file system. + +CREATE_SUBDIRS = NO + +# The OUTPUT_LANGUAGE tag is used to specify the language in which all +# documentation generated by doxygen is written. Doxygen will use this +# information to generate all constant output in the proper language. +# The default language is English, other supported languages are: +# Brazilian, Catalan, Chinese, Chinese-Traditional, Croatian, Czech, Danish, +# Dutch, Finnish, French, German, Greek, Hungarian, Italian, Japanese, +# Japanese-en (Japanese with English messages), Korean, Korean-en, Norwegian, +# Polish, Portuguese, Romanian, Russian, Serbian, Slovak, Slovene, Spanish, +# Swedish, and Ukrainian. + +OUTPUT_LANGUAGE = English + +# This tag can be used to specify the encoding used in the generated output. +# The encoding is not always determined by the language that is chosen, +# but also whether or not the output is meant for Windows or non-Windows users. +# In case there is a difference, setting the USE_WINDOWS_ENCODING tag to YES +# forces the Windows encoding (this is the default for the Windows binary), +# whereas setting the tag to NO uses a Unix-style encoding (the default for +# all platforms other than Windows). + +USE_WINDOWS_ENCODING = NO + +# If the BRIEF_MEMBER_DESC tag is set to YES (the default) Doxygen will +# include brief member descriptions after the members that are listed in +# the file and class documentation (similar to JavaDoc). +# Set to NO to disable this. + +BRIEF_MEMBER_DESC = YES + +# If the REPEAT_BRIEF tag is set to YES (the default) Doxygen will prepend +# the brief description of a member or function before the detailed description. +# Note: if both HIDE_UNDOC_MEMBERS and BRIEF_MEMBER_DESC are set to NO, the +# brief descriptions will be completely suppressed. + +REPEAT_BRIEF = YES + +# This tag implements a quasi-intelligent brief description abbreviator +# that is used to form the text in various listings. Each string +# in this list, if found as the leading text of the brief description, will be +# stripped from the text and the result after processing the whole list, is +# used as the annotated text. Otherwise, the brief description is used as-is. +# If left blank, the following values are used ("$name" is automatically +# replaced with the name of the entity): "The $name class" "The $name widget" +# "The $name file" "is" "provides" "specifies" "contains" +# "represents" "a" "an" "the" + +ABBREVIATE_BRIEF = + +# If the ALWAYS_DETAILED_SEC and REPEAT_BRIEF tags are both set to YES then +# Doxygen will generate a detailed section even if there is only a brief +# description. + +ALWAYS_DETAILED_SEC = NO + +# If the INLINE_INHERITED_MEMB tag is set to YES, doxygen will show all +# inherited members of a class in the documentation of that class as if those +# members were ordinary class members. Constructors, destructors and assignment +# operators of the base classes will not be shown. + +INLINE_INHERITED_MEMB = NO + +# If the FULL_PATH_NAMES tag is set to YES then Doxygen will prepend the full +# path before files name in the file list and in the header files. If set +# to NO the shortest path that makes the file name unique will be used. + +FULL_PATH_NAMES = YES + +# If the FULL_PATH_NAMES tag is set to YES then the STRIP_FROM_PATH tag +# can be used to strip a user-defined part of the path. Stripping is +# only done if one of the specified strings matches the left-hand part of +# the path. The tag can be used to show relative paths in the file list. +# If left blank the directory from which doxygen is run is used as the +# path to strip. + +STRIP_FROM_PATH = + +# The STRIP_FROM_INC_PATH tag can be used to strip a user-defined part of +# the path mentioned in the documentation of a class, which tells +# the reader which header file to include in order to use a class. +# If left blank only the name of the header file containing the class +# definition is used. Otherwise one should specify the include paths that +# are normally passed to the compiler using the -I flag. + +STRIP_FROM_INC_PATH = + +# If the SHORT_NAMES tag is set to YES, doxygen will generate much shorter +# (but less readable) file names. This can be useful is your file systems +# doesn't support long names like on DOS, Mac, or CD-ROM. + +SHORT_NAMES = NO + +# If the JAVADOC_AUTOBRIEF tag is set to YES then Doxygen +# will interpret the first line (until the first dot) of a JavaDoc-style +# comment as the brief description. If set to NO, the JavaDoc +# comments will behave just like the Qt-style comments (thus requiring an +# explicit @brief command for a brief description. + +JAVADOC_AUTOBRIEF = YES + +# The MULTILINE_CPP_IS_BRIEF tag can be set to YES to make Doxygen +# treat a multi-line C++ special comment block (i.e. a block of //! or /// +# comments) as a brief description. This used to be the default behaviour. +# The new default is to treat a multi-line C++ comment block as a detailed +# description. Set this tag to YES if you prefer the old behaviour instead. + +MULTILINE_CPP_IS_BRIEF = NO + +# If the DETAILS_AT_TOP tag is set to YES then Doxygen +# will output the detailed description near the top, like JavaDoc. +# If set to NO, the detailed description appears after the member +# documentation. + +DETAILS_AT_TOP = NO + +# If the INHERIT_DOCS tag is set to YES (the default) then an undocumented +# member inherits the documentation from any documented member that it +# re-implements. + +INHERIT_DOCS = YES + +# If member grouping is used in the documentation and the DISTRIBUTE_GROUP_DOC +# tag is set to YES, then doxygen will reuse the documentation of the first +# member in the group (if any) for the other members of the group. By default +# all members of a group must be documented explicitly. + +DISTRIBUTE_GROUP_DOC = NO + +# If the SEPARATE_MEMBER_PAGES tag is set to YES, then doxygen will produce +# a new page for each member. If set to NO, the documentation of a member will +# be part of the file/class/namespace that contains it. + +SEPARATE_MEMBER_PAGES = NO + +# The TAB_SIZE tag can be used to set the number of spaces in a tab. +# Doxygen uses this value to replace tabs by spaces in code fragments. + +TAB_SIZE = 8 + +# This tag can be used to specify a number of aliases that acts +# as commands in the documentation. An alias has the form "name=value". +# For example adding "sideeffect=\par Side Effects:\n" will allow you to +# put the command \sideeffect (or @sideeffect) in the documentation, which +# will result in a user-defined paragraph with heading "Side Effects:". +# You can put \n's in the value part of an alias to insert newlines. + +ALIASES = + +# Set the OPTIMIZE_OUTPUT_FOR_C tag to YES if your project consists of C +# sources only. Doxygen will then generate output that is more tailored for C. +# For instance, some of the names that are used will be different. The list +# of all members will be omitted, etc. + +OPTIMIZE_OUTPUT_FOR_C = NO + +# Set the OPTIMIZE_OUTPUT_JAVA tag to YES if your project consists of Java sources +# only. Doxygen will then generate output that is more tailored for Java. +# For instance, namespaces will be presented as packages, qualified scopes +# will look different, etc. + +OPTIMIZE_OUTPUT_JAVA = NO + +# Set the SUBGROUPING tag to YES (the default) to allow class member groups of +# the same type (for instance a group of public functions) to be put as a +# subgroup of that type (e.g. under the Public Functions section). Set it to +# NO to prevent subgrouping. Alternatively, this can be done per class using +# the \nosubgrouping command. + +SUBGROUPING = YES + +#--------------------------------------------------------------------------- +# Build related configuration options +#--------------------------------------------------------------------------- + +# If the EXTRACT_ALL tag is set to YES doxygen will assume all entities in +# documentation are documented, even if no documentation was available. +# Private class members and static file members will be hidden unless +# the EXTRACT_PRIVATE and EXTRACT_STATIC tags are set to YES + +EXTRACT_ALL = YES + +# If the EXTRACT_PRIVATE tag is set to YES all private members of a class +# will be included in the documentation. + +EXTRACT_PRIVATE = YES + +# If the EXTRACT_STATIC tag is set to YES all static members of a file +# will be included in the documentation. + +EXTRACT_STATIC = YES + +# If the EXTRACT_LOCAL_CLASSES tag is set to YES classes (and structs) +# defined locally in source files will be included in the documentation. +# If set to NO only classes defined in header files are included. + +EXTRACT_LOCAL_CLASSES = YES + +# This flag is only useful for Objective-C code. When set to YES local +# methods, which are defined in the implementation section but not in +# the interface are included in the documentation. +# If set to NO (the default) only methods in the interface are included. + +EXTRACT_LOCAL_METHODS = NO + +# If the HIDE_UNDOC_MEMBERS tag is set to YES, Doxygen will hide all +# undocumented members of documented classes, files or namespaces. +# If set to NO (the default) these members will be included in the +# various overviews, but no documentation section is generated. +# This option has no effect if EXTRACT_ALL is enabled. + +HIDE_UNDOC_MEMBERS = NO + +# If the HIDE_UNDOC_CLASSES tag is set to YES, Doxygen will hide all +# undocumented classes that are normally visible in the class hierarchy. +# If set to NO (the default) these classes will be included in the various +# overviews. This option has no effect if EXTRACT_ALL is enabled. + +HIDE_UNDOC_CLASSES = NO + +# If the HIDE_FRIEND_COMPOUNDS tag is set to YES, Doxygen will hide all +# friend (class|struct|union) declarations. +# If set to NO (the default) these declarations will be included in the +# documentation. + +HIDE_FRIEND_COMPOUNDS = NO + +# If the HIDE_IN_BODY_DOCS tag is set to YES, Doxygen will hide any +# documentation blocks found inside the body of a function. +# If set to NO (the default) these blocks will be appended to the +# function's detailed documentation block. + +HIDE_IN_BODY_DOCS = NO + +# The INTERNAL_DOCS tag determines if documentation +# that is typed after a \internal command is included. If the tag is set +# to NO (the default) then the documentation will be excluded. +# Set it to YES to include the internal documentation. + +INTERNAL_DOCS = NO + +# If the CASE_SENSE_NAMES tag is set to NO then Doxygen will only generate +# file names in lower-case letters. If set to YES upper-case letters are also +# allowed. This is useful if you have classes or files whose names only differ +# in case and if your file system supports case sensitive file names. Windows +# and Mac users are advised to set this option to NO. + +CASE_SENSE_NAMES = YES + +# If the HIDE_SCOPE_NAMES tag is set to NO (the default) then Doxygen +# will show members with their full class and namespace scopes in the +# documentation. If set to YES the scope will be hidden. + +HIDE_SCOPE_NAMES = NO + +# If the SHOW_INCLUDE_FILES tag is set to YES (the default) then Doxygen +# will put a list of the files that are included by a file in the documentation +# of that file. + +SHOW_INCLUDE_FILES = YES + +# If the INLINE_INFO tag is set to YES (the default) then a tag [inline] +# is inserted in the documentation for inline members. + +INLINE_INFO = YES + +# If the SORT_MEMBER_DOCS tag is set to YES (the default) then doxygen +# will sort the (detailed) documentation of file and class members +# alphabetically by member name. If set to NO the members will appear in +# declaration order. + +SORT_MEMBER_DOCS = YES + +# If the SORT_BRIEF_DOCS tag is set to YES then doxygen will sort the +# brief documentation of file, namespace and class members alphabetically +# by member name. If set to NO (the default) the members will appear in +# declaration order. + +SORT_BRIEF_DOCS = NO + +# If the SORT_BY_SCOPE_NAME tag is set to YES, the class list will be +# sorted by fully-qualified names, including namespaces. If set to +# NO (the default), the class list will be sorted only by class name, +# not including the namespace part. +# Note: This option is not very useful if HIDE_SCOPE_NAMES is set to YES. +# Note: This option applies only to the class list, not to the +# alphabetical list. + +SORT_BY_SCOPE_NAME = NO + +# The GENERATE_TODOLIST tag can be used to enable (YES) or +# disable (NO) the todo list. This list is created by putting \todo +# commands in the documentation. + +GENERATE_TODOLIST = YES + +# The GENERATE_TESTLIST tag can be used to enable (YES) or +# disable (NO) the test list. This list is created by putting \test +# commands in the documentation. + +GENERATE_TESTLIST = YES + +# The GENERATE_BUGLIST tag can be used to enable (YES) or +# disable (NO) the bug list. This list is created by putting \bug +# commands in the documentation. + +GENERATE_BUGLIST = YES + +# The GENERATE_DEPRECATEDLIST tag can be used to enable (YES) or +# disable (NO) the deprecated list. This list is created by putting +# \deprecated commands in the documentation. + +GENERATE_DEPRECATEDLIST= YES + +# The ENABLED_SECTIONS tag can be used to enable conditional +# documentation sections, marked by \if sectionname ... \endif. + +ENABLED_SECTIONS = + +# The MAX_INITIALIZER_LINES tag determines the maximum number of lines +# the initial value of a variable or define consists of for it to appear in +# the documentation. If the initializer consists of more lines than specified +# here it will be hidden. Use a value of 0 to hide initializers completely. +# The appearance of the initializer of individual variables and defines in the +# documentation can be controlled using \showinitializer or \hideinitializer +# command in the documentation regardless of this setting. + +MAX_INITIALIZER_LINES = 30 + +# Set the SHOW_USED_FILES tag to NO to disable the list of files generated +# at the bottom of the documentation of classes and structs. If set to YES the +# list will mention the files that were used to generate the documentation. + +SHOW_USED_FILES = YES + +# If the sources in your project are distributed over multiple directories +# then setting the SHOW_DIRECTORIES tag to YES will show the directory hierarchy +# in the documentation. + +SHOW_DIRECTORIES = YES + +# The FILE_VERSION_FILTER tag can be used to specify a program or script that +# doxygen should invoke to get the current version for each file (typically from the +# version control system). Doxygen will invoke the program by executing (via +# popen()) the command <command> <input-file>, where <command> is the value of +# the FILE_VERSION_FILTER tag, and <input-file> is the name of an input file +# provided by doxygen. Whatever the progam writes to standard output +# is used as the file version. See the manual for examples. + +FILE_VERSION_FILTER = + +#--------------------------------------------------------------------------- +# configuration options related to warning and progress messages +#--------------------------------------------------------------------------- + +# The QUIET tag can be used to turn on/off the messages that are generated +# by doxygen. Possible values are YES and NO. If left blank NO is used. + +QUIET = NO + +# The WARNINGS tag can be used to turn on/off the warning messages that are +# generated by doxygen. Possible values are YES and NO. If left blank +# NO is used. + +WARNINGS = YES + +# If WARN_IF_UNDOCUMENTED is set to YES, then doxygen will generate warnings +# for undocumented members. If EXTRACT_ALL is set to YES then this flag will +# automatically be disabled. + +WARN_IF_UNDOCUMENTED = YES + +# If WARN_IF_DOC_ERROR is set to YES, doxygen will generate warnings for +# potential errors in the documentation, such as not documenting some +# parameters in a documented function, or documenting parameters that +# don't exist or using markup commands wrongly. + +WARN_IF_DOC_ERROR = YES + +# This WARN_NO_PARAMDOC option can be abled to get warnings for +# functions that are documented, but have no documentation for their parameters +# or return value. If set to NO (the default) doxygen will only warn about +# wrong or incomplete parameter documentation, but not about the absence of +# documentation. + +WARN_NO_PARAMDOC = NO + +# The WARN_FORMAT tag determines the format of the warning messages that +# doxygen can produce. The string should contain the $file, $line, and $text +# tags, which will be replaced by the file and line number from which the +# warning originated and the warning text. Optionally the format may contain +# $version, which will be replaced by the version of the file (if it could +# be obtained via FILE_VERSION_FILTER) + +WARN_FORMAT = "$file:$line: $text" + +# The WARN_LOGFILE tag can be used to specify a file to which warning +# and error messages should be written. If left blank the output is written +# to stderr. + +WARN_LOGFILE = + +#--------------------------------------------------------------------------- +# configuration options related to the input files +#--------------------------------------------------------------------------- + +# The INPUT tag can be used to specify the files and/or directories that contain +# documented source files. You may enter file names like "myfile.cpp" or +# directories like "/usr/src/myproject". Separate the files or directories +# with spaces. + +INPUT = + +# If the value of the INPUT tag contains directories, you can use the +# FILE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp +# and *.h) to filter out the source-files in the directories. If left +# blank the following patterns are tested: +# *.c *.cc *.cxx *.cpp *.c++ *.java *.ii *.ixx *.ipp *.i++ *.inl *.h *.hh *.hxx +# *.hpp *.h++ *.idl *.odl *.cs *.php *.php3 *.inc *.m *.mm + +FILE_PATTERNS = + +# The RECURSIVE tag can be used to turn specify whether or not subdirectories +# should be searched for input files as well. Possible values are YES and NO. +# If left blank NO is used. + +RECURSIVE = YES + +# The EXCLUDE tag can be used to specify files and/or directories that should +# excluded from the INPUT source files. This way you can easily exclude a +# subdirectory from a directory tree whose root is specified with the INPUT tag. + +EXCLUDE = + +# The EXCLUDE_SYMLINKS tag can be used select whether or not files or +# directories that are symbolic links (a Unix filesystem feature) are excluded +# from the input. + +EXCLUDE_SYMLINKS = NO + +# If the value of the INPUT tag contains directories, you can use the +# EXCLUDE_PATTERNS tag to specify one or more wildcard patterns to exclude +# certain files from those directories. + +EXCLUDE_PATTERNS = */tools/* */.svn/* */CVS/* + +# The EXAMPLE_PATH tag can be used to specify one or more files or +# directories that contain example code fragments that are included (see +# the \include command). + +EXAMPLE_PATH = + +# If the value of the EXAMPLE_PATH tag contains directories, you can use the +# EXAMPLE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp +# and *.h) to filter out the source-files in the directories. If left +# blank all files are included. + +EXAMPLE_PATTERNS = + +# If the EXAMPLE_RECURSIVE tag is set to YES then subdirectories will be +# searched for input files to be used with the \include or \dontinclude +# commands irrespective of the value of the RECURSIVE tag. +# Possible values are YES and NO. If left blank NO is used. + +EXAMPLE_RECURSIVE = NO + +# The IMAGE_PATH tag can be used to specify one or more files or +# directories that contain image that are included in the documentation (see +# the \image command). + +IMAGE_PATH = + +# The INPUT_FILTER tag can be used to specify a program that doxygen should +# invoke to filter for each input file. Doxygen will invoke the filter program +# by executing (via popen()) the command <filter> <input-file>, where <filter> +# is the value of the INPUT_FILTER tag, and <input-file> is the name of an +# input file. Doxygen will then use the output that the filter program writes +# to standard output. If FILTER_PATTERNS is specified, this tag will be +# ignored. + +INPUT_FILTER = + +# The FILTER_PATTERNS tag can be used to specify filters on a per file pattern +# basis. Doxygen will compare the file name with each pattern and apply the +# filter if there is a match. The filters are a list of the form: +# pattern=filter (like *.cpp=my_cpp_filter). See INPUT_FILTER for further +# info on how filters are used. If FILTER_PATTERNS is empty, INPUT_FILTER +# is applied to all files. + +FILTER_PATTERNS = + +# If the FILTER_SOURCE_FILES tag is set to YES, the input filter (if set using +# INPUT_FILTER) will be used to filter the input files when producing source +# files to browse (i.e. when SOURCE_BROWSER is set to YES). + +FILTER_SOURCE_FILES = NO + +#--------------------------------------------------------------------------- +# configuration options related to source browsing +#--------------------------------------------------------------------------- + +# If the SOURCE_BROWSER tag is set to YES then a list of source files will +# be generated. Documented entities will be cross-referenced with these sources. +# Note: To get rid of all source code in the generated output, make sure also +# VERBATIM_HEADERS is set to NO. + +SOURCE_BROWSER = YES + +# Setting the INLINE_SOURCES tag to YES will include the body +# of functions and classes directly in the documentation. + +INLINE_SOURCES = NO + +# Setting the STRIP_CODE_COMMENTS tag to YES (the default) will instruct +# doxygen to hide any special comment blocks from generated source code +# fragments. Normal C and C++ comments will always remain visible. + +STRIP_CODE_COMMENTS = NO + +# If the REFERENCED_BY_RELATION tag is set to YES (the default) +# then for each documented function all documented +# functions referencing it will be listed. + +REFERENCED_BY_RELATION = YES + +# If the REFERENCES_RELATION tag is set to YES (the default) +# then for each documented function all documented entities +# called/used by that function will be listed. + +REFERENCES_RELATION = YES + +# If the VERBATIM_HEADERS tag is set to YES (the default) then Doxygen +# will generate a verbatim copy of the header file for each class for +# which an include is specified. Set to NO to disable this. + +VERBATIM_HEADERS = YES + +#--------------------------------------------------------------------------- +# configuration options related to the alphabetical class index +#--------------------------------------------------------------------------- + +# If the ALPHABETICAL_INDEX tag is set to YES, an alphabetical index +# of all compounds will be generated. Enable this if the project +# contains a lot of classes, structs, unions or interfaces. + +ALPHABETICAL_INDEX = NO + +# If the alphabetical index is enabled (see ALPHABETICAL_INDEX) then +# the COLS_IN_ALPHA_INDEX tag can be used to specify the number of columns +# in which this list will be split (can be a number in the range [1..20]) + +COLS_IN_ALPHA_INDEX = 5 + +# In case all classes in a project start with a common prefix, all +# classes will be put under the same header in the alphabetical index. +# The IGNORE_PREFIX tag can be used to specify one or more prefixes that +# should be ignored while generating the index headers. + +IGNORE_PREFIX = + +#--------------------------------------------------------------------------- +# configuration options related to the HTML output +#--------------------------------------------------------------------------- + +# If the GENERATE_HTML tag is set to YES (the default) Doxygen will +# generate HTML output. + +GENERATE_HTML = YES + +# The HTML_OUTPUT tag is used to specify where the HTML docs will be put. +# If a relative path is entered the value of OUTPUT_DIRECTORY will be +# put in front of it. If left blank `html' will be used as the default path. + +HTML_OUTPUT = srcdoc + +# The HTML_FILE_EXTENSION tag can be used to specify the file extension for +# each generated HTML page (for example: .htm,.php,.asp). If it is left blank +# doxygen will generate files with .html extension. + +HTML_FILE_EXTENSION = .html + +# The HTML_HEADER tag can be used to specify a personal HTML header for +# each generated HTML page. If it is left blank doxygen will generate a +# standard header. + +HTML_HEADER = + +# The HTML_FOOTER tag can be used to specify a personal HTML footer for +# each generated HTML page. If it is left blank doxygen will generate a +# standard footer. + +HTML_FOOTER = + +# The HTML_STYLESHEET tag can be used to specify a user-defined cascading +# style sheet that is used by each HTML page. It can be used to +# fine-tune the look of the HTML output. If the tag is left blank doxygen +# will generate a default style sheet. Note that doxygen will try to copy +# the style sheet file to the HTML output directory, so don't put your own +# stylesheet in the HTML output directory as well, or it will be erased! + +HTML_STYLESHEET = + +# If the HTML_ALIGN_MEMBERS tag is set to YES, the members of classes, +# files or namespaces will be aligned in HTML using tables. If set to +# NO a bullet list will be used. + +HTML_ALIGN_MEMBERS = YES + +# If the GENERATE_HTMLHELP tag is set to YES, additional index files +# will be generated that can be used as input for tools like the +# Microsoft HTML help workshop to generate a compressed HTML help file (.chm) +# of the generated HTML documentation. + +GENERATE_HTMLHELP = NO + +# If the GENERATE_HTMLHELP tag is set to YES, the CHM_FILE tag can +# be used to specify the file name of the resulting .chm file. You +# can add a path in front of the file if the result should not be +# written to the html output directory. + +CHM_FILE = + +# If the GENERATE_HTMLHELP tag is set to YES, the HHC_LOCATION tag can +# be used to specify the location (absolute path including file name) of +# the HTML help compiler (hhc.exe). If non-empty doxygen will try to run +# the HTML help compiler on the generated index.hhp. + +HHC_LOCATION = + +# If the GENERATE_HTMLHELP tag is set to YES, the GENERATE_CHI flag +# controls if a separate .chi index file is generated (YES) or that +# it should be included in the master .chm file (NO). + +GENERATE_CHI = NO + +# If the GENERATE_HTMLHELP tag is set to YES, the BINARY_TOC flag +# controls whether a binary table of contents is generated (YES) or a +# normal table of contents (NO) in the .chm file. + +BINARY_TOC = NO + +# The TOC_EXPAND flag can be set to YES to add extra items for group members +# to the contents of the HTML help documentation and to the tree view. + +TOC_EXPAND = NO + +# The DISABLE_INDEX tag can be used to turn on/off the condensed index at +# top of each HTML page. The value NO (the default) enables the index and +# the value YES disables it. + +DISABLE_INDEX = NO + +# This tag can be used to set the number of enum values (range [1..20]) +# that doxygen will group on one line in the generated HTML documentation. + +ENUM_VALUES_PER_LINE = 4 + +# If the GENERATE_TREEVIEW tag is set to YES, a side panel will be +# generated containing a tree-like index structure (just like the one that +# is generated for HTML Help). For this to work a browser that supports +# JavaScript, DHTML, CSS and frames is required (for instance Mozilla 1.0+, +# Netscape 6.0+, Internet explorer 5.0+, or Konqueror). Windows users are +# probably better off using the HTML help feature. + +GENERATE_TREEVIEW = NO + +# If the treeview is enabled (see GENERATE_TREEVIEW) then this tag can be +# used to set the initial width (in pixels) of the frame in which the tree +# is shown. + +TREEVIEW_WIDTH = 250 + +#--------------------------------------------------------------------------- +# configuration options related to the LaTeX output +#--------------------------------------------------------------------------- + +# If the GENERATE_LATEX tag is set to YES (the default) Doxygen will +# generate Latex output. + +GENERATE_LATEX = NO + +# The LATEX_OUTPUT tag is used to specify where the LaTeX docs will be put. +# If a relative path is entered the value of OUTPUT_DIRECTORY will be +# put in front of it. If left blank `latex' will be used as the default path. + +LATEX_OUTPUT = latex + +# The LATEX_CMD_NAME tag can be used to specify the LaTeX command name to be +# invoked. If left blank `latex' will be used as the default command name. + +LATEX_CMD_NAME = latex + +# The MAKEINDEX_CMD_NAME tag can be used to specify the command name to +# generate index for LaTeX. If left blank `makeindex' will be used as the +# default command name. + +MAKEINDEX_CMD_NAME = makeindex + +# If the COMPACT_LATEX tag is set to YES Doxygen generates more compact +# LaTeX documents. This may be useful for small projects and may help to +# save some trees in general. + +COMPACT_LATEX = NO + +# The PAPER_TYPE tag can be used to set the paper type that is used +# by the printer. Possible values are: a4, a4wide, letter, legal and +# executive. If left blank a4wide will be used. + +PAPER_TYPE = a4wide + +# The EXTRA_PACKAGES tag can be to specify one or more names of LaTeX +# packages that should be included in the LaTeX output. + +EXTRA_PACKAGES = + +# The LATEX_HEADER tag can be used to specify a personal LaTeX header for +# the generated latex document. The header should contain everything until +# the first chapter. If it is left blank doxygen will generate a +# standard header. Notice: only use this tag if you know what you are doing! + +LATEX_HEADER = + +# If the PDF_HYPERLINKS tag is set to YES, the LaTeX that is generated +# is prepared for conversion to pdf (using ps2pdf). The pdf file will +# contain links (just like the HTML output) instead of page references +# This makes the output suitable for online browsing using a pdf viewer. + +PDF_HYPERLINKS = NO + +# If the USE_PDFLATEX tag is set to YES, pdflatex will be used instead of +# plain latex in the generated Makefile. Set this option to YES to get a +# higher quality PDF documentation. + +USE_PDFLATEX = NO + +# If the LATEX_BATCHMODE tag is set to YES, doxygen will add the \\batchmode. +# command to the generated LaTeX files. This will instruct LaTeX to keep +# running if errors occur, instead of asking the user for help. +# This option is also used when generating formulas in HTML. + +LATEX_BATCHMODE = NO + +# If LATEX_HIDE_INDICES is set to YES then doxygen will not +# include the index chapters (such as File Index, Compound Index, etc.) +# in the output. + +LATEX_HIDE_INDICES = NO + +#--------------------------------------------------------------------------- +# configuration options related to the RTF output +#--------------------------------------------------------------------------- + +# If the GENERATE_RTF tag is set to YES Doxygen will generate RTF output +# The RTF output is optimized for Word 97 and may not look very pretty with +# other RTF readers or editors. + +GENERATE_RTF = NO + +# The RTF_OUTPUT tag is used to specify where the RTF docs will be put. +# If a relative path is entered the value of OUTPUT_DIRECTORY will be +# put in front of it. If left blank `rtf' will be used as the default path. + +RTF_OUTPUT = rtf + +# If the COMPACT_RTF tag is set to YES Doxygen generates more compact +# RTF documents. This may be useful for small projects and may help to +# save some trees in general. + +COMPACT_RTF = NO + +# If the RTF_HYPERLINKS tag is set to YES, the RTF that is generated +# will contain hyperlink fields. The RTF file will +# contain links (just like the HTML output) instead of page references. +# This makes the output suitable for online browsing using WORD or other +# programs which support those fields. +# Note: wordpad (write) and others do not support links. + +RTF_HYPERLINKS = NO + +# Load stylesheet definitions from file. Syntax is similar to doxygen's +# config file, i.e. a series of assignments. You only have to provide +# replacements, missing definitions are set to their default value. + +RTF_STYLESHEET_FILE = + +# Set optional variables used in the generation of an rtf document. +# Syntax is similar to doxygen's config file. + +RTF_EXTENSIONS_FILE = + +#--------------------------------------------------------------------------- +# configuration options related to the man page output +#--------------------------------------------------------------------------- + +# If the GENERATE_MAN tag is set to YES (the default) Doxygen will +# generate man pages + +GENERATE_MAN = NO + +# The MAN_OUTPUT tag is used to specify where the man pages will be put. +# If a relative path is entered the value of OUTPUT_DIRECTORY will be +# put in front of it. If left blank `man' will be used as the default path. + +MAN_OUTPUT = man + +# The MAN_EXTENSION tag determines the extension that is added to +# the generated man pages (default is the subroutine's section .3) + +MAN_EXTENSION = .3 + +# If the MAN_LINKS tag is set to YES and Doxygen generates man output, +# then it will generate one additional man file for each entity +# documented in the real man page(s). These additional files +# only source the real man page, but without them the man command +# would be unable to find the correct page. The default is NO. + +MAN_LINKS = NO + +#--------------------------------------------------------------------------- +# configuration options related to the XML output +#--------------------------------------------------------------------------- + +# If the GENERATE_XML tag is set to YES Doxygen will +# generate an XML file that captures the structure of +# the code including all documentation. + +GENERATE_XML = NO + +# The XML_OUTPUT tag is used to specify where the XML pages will be put. +# If a relative path is entered the value of OUTPUT_DIRECTORY will be +# put in front of it. If left blank `xml' will be used as the default path. + +XML_OUTPUT = xml + +# The XML_SCHEMA tag can be used to specify an XML schema, +# which can be used by a validating XML parser to check the +# syntax of the XML files. + +XML_SCHEMA = + +# The XML_DTD tag can be used to specify an XML DTD, +# which can be used by a validating XML parser to check the +# syntax of the XML files. + +XML_DTD = + +# If the XML_PROGRAMLISTING tag is set to YES Doxygen will +# dump the program listings (including syntax highlighting +# and cross-referencing information) to the XML output. Note that +# enabling this will significantly increase the size of the XML output. + +XML_PROGRAMLISTING = YES + +#--------------------------------------------------------------------------- +# configuration options for the AutoGen Definitions output +#--------------------------------------------------------------------------- + +# If the GENERATE_AUTOGEN_DEF tag is set to YES Doxygen will +# generate an AutoGen Definitions (see autogen.sf.net) file +# that captures the structure of the code including all +# documentation. Note that this feature is still experimental +# and incomplete at the moment. + +GENERATE_AUTOGEN_DEF = NO + +#--------------------------------------------------------------------------- +# configuration options related to the Perl module output +#--------------------------------------------------------------------------- + +# If the GENERATE_PERLMOD tag is set to YES Doxygen will +# generate a Perl module file that captures the structure of +# the code including all documentation. Note that this +# feature is still experimental and incomplete at the +# moment. + +GENERATE_PERLMOD = NO + +# If the PERLMOD_LATEX tag is set to YES Doxygen will generate +# the necessary Makefile rules, Perl scripts and LaTeX code to be able +# to generate PDF and DVI output from the Perl module output. + +PERLMOD_LATEX = NO + +# If the PERLMOD_PRETTY tag is set to YES the Perl module output will be +# nicely formatted so it can be parsed by a human reader. This is useful +# if you want to understand what is going on. On the other hand, if this +# tag is set to NO the size of the Perl module output will be much smaller +# and Perl will parse it just the same. + +PERLMOD_PRETTY = YES + +# The names of the make variables in the generated doxyrules.make file +# are prefixed with the string contained in PERLMOD_MAKEVAR_PREFIX. +# This is useful so different doxyrules.make files included by the same +# Makefile don't overwrite each other's variables. + +PERLMOD_MAKEVAR_PREFIX = + +#--------------------------------------------------------------------------- +# Configuration options related to the preprocessor +#--------------------------------------------------------------------------- + +# If the ENABLE_PREPROCESSING tag is set to YES (the default) Doxygen will +# evaluate all C-preprocessor directives found in the sources and include +# files. + +ENABLE_PREPROCESSING = YES + +# If the MACRO_EXPANSION tag is set to YES Doxygen will expand all macro +# names in the source code. If set to NO (the default) only conditional +# compilation will be performed. Macro expansion can be done in a controlled +# way by setting EXPAND_ONLY_PREDEF to YES. + +MACRO_EXPANSION = NO + +# If the EXPAND_ONLY_PREDEF and MACRO_EXPANSION tags are both set to YES +# then the macro expansion is limited to the macros specified with the +# PREDEFINED and EXPAND_AS_PREDEFINED tags. + +EXPAND_ONLY_PREDEF = NO + +# If the SEARCH_INCLUDES tag is set to YES (the default) the includes files +# in the INCLUDE_PATH (see below) will be search if a #include is found. + +SEARCH_INCLUDES = YES + +# The INCLUDE_PATH tag can be used to specify one or more directories that +# contain include files that are not input files but should be processed by +# the preprocessor. + +INCLUDE_PATH = + +# You can use the INCLUDE_FILE_PATTERNS tag to specify one or more wildcard +# patterns (like *.h and *.hpp) to filter out the header-files in the +# directories. If left blank, the patterns specified with FILE_PATTERNS will +# be used. + +INCLUDE_FILE_PATTERNS = + +# The PREDEFINED tag can be used to specify one or more macro names that +# are defined before the preprocessor is started (similar to the -D option of +# gcc). The argument of the tag is a list of macros of the form: name +# or name=definition (no spaces). If the definition and the = are +# omitted =1 is assumed. To prevent a macro definition from being +# undefined via #undef or recursively expanded use the := operator +# instead of the = operator. + +PREDEFINED = VDRVERSNUM=$(VDRVERSNUM) + +# If the MACRO_EXPANSION and EXPAND_ONLY_PREDEF tags are set to YES then +# this tag can be used to specify a list of macro names that should be expanded. +# The macro definition that is found in the sources will be used. +# Use the PREDEFINED tag if you want to use a different macro definition. + +EXPAND_AS_DEFINED = + +# If the SKIP_FUNCTION_MACROS tag is set to YES (the default) then +# doxygen's preprocessor will remove all function-like macros that are alone +# on a line, have an all uppercase name, and do not end with a semicolon. Such +# function macros are typically used for boiler-plate code, and will confuse +# the parser if not removed. + +SKIP_FUNCTION_MACROS = YES + +#--------------------------------------------------------------------------- +# Configuration::additions related to external references +#--------------------------------------------------------------------------- + +# The TAGFILES option can be used to specify one or more tagfiles. +# Optionally an initial location of the external documentation +# can be added for each tagfile. The format of a tag file without +# this location is as follows: +# TAGFILES = file1 file2 ... +# Adding location for the tag files is done as follows: +# TAGFILES = file1=loc1 "file2 = loc2" ... +# where "loc1" and "loc2" can be relative or absolute paths or +# URLs. If a location is present for each tag, the installdox tool +# does not have to be run to correct the links. +# Note that each tag file must have a unique name +# (where the name does NOT include the path) +# If a tag file is not located in the directory in which doxygen +# is run, you must also specify the path to the tagfile here. + +TAGFILES = + +# When a file name is specified after GENERATE_TAGFILE, doxygen will create +# a tag file that is based on the input files it reads. + +GENERATE_TAGFILE = + +# If the ALLEXTERNALS tag is set to YES all external classes will be listed +# in the class index. If set to NO only the inherited external classes +# will be listed. + +ALLEXTERNALS = NO + +# If the EXTERNAL_GROUPS tag is set to YES all external groups will be listed +# in the modules index. If set to NO, only the current project's groups will +# be listed. + +EXTERNAL_GROUPS = YES + +# The PERL_PATH should be the absolute path and name of the perl script +# interpreter (i.e. the result of `which perl'). + +PERL_PATH = /usr/bin/perl + +#--------------------------------------------------------------------------- +# Configuration options related to the dot tool +#--------------------------------------------------------------------------- + +# If the CLASS_DIAGRAMS tag is set to YES (the default) Doxygen will +# generate a inheritance diagram (in HTML, RTF and LaTeX) for classes with base +# or super classes. Setting the tag to NO turns the diagrams off. Note that +# this option is superseded by the HAVE_DOT option below. This is only a +# fallback. It is recommended to install and use dot, since it yields more +# powerful graphs. + +CLASS_DIAGRAMS = YES + +# If set to YES, the inheritance and collaboration graphs will hide +# inheritance and usage relations if the target is undocumented +# or is not a class. + +HIDE_UNDOC_RELATIONS = YES + +# If you set the HAVE_DOT tag to YES then doxygen will assume the dot tool is +# available from the path. This tool is part of Graphviz, a graph visualization +# toolkit from AT&T and Lucent Bell Labs. The other options in this section +# have no effect if this option is set to NO (the default) + +HAVE_DOT = YES + +# If the CLASS_GRAPH and HAVE_DOT tags are set to YES then doxygen +# will generate a graph for each documented class showing the direct and +# indirect inheritance relations. Setting this tag to YES will force the +# the CLASS_DIAGRAMS tag to NO. + +CLASS_GRAPH = YES + +# If the COLLABORATION_GRAPH and HAVE_DOT tags are set to YES then doxygen +# will generate a graph for each documented class showing the direct and +# indirect implementation dependencies (inheritance, containment, and +# class references variables) of the class with other documented classes. + +COLLABORATION_GRAPH = YES + +# If the GROUP_GRAPHS and HAVE_DOT tags are set to YES then doxygen +# will generate a graph for groups, showing the direct groups dependencies + +GROUP_GRAPHS = YES + +# If the UML_LOOK tag is set to YES doxygen will generate inheritance and +# collaboration diagrams in a style similar to the OMG's Unified Modeling +# Language. + +UML_LOOK = YES + +# If set to YES, the inheritance and collaboration graphs will show the +# relations between templates and their instances. + +TEMPLATE_RELATIONS = YES + +# If the ENABLE_PREPROCESSING, SEARCH_INCLUDES, INCLUDE_GRAPH, and HAVE_DOT +# tags are set to YES then doxygen will generate a graph for each documented +# file showing the direct and indirect include dependencies of the file with +# other documented files. + +INCLUDE_GRAPH = YES + +# If the ENABLE_PREPROCESSING, SEARCH_INCLUDES, INCLUDED_BY_GRAPH, and +# HAVE_DOT tags are set to YES then doxygen will generate a graph for each +# documented header file showing the documented files that directly or +# indirectly include this file. + +INCLUDED_BY_GRAPH = YES + +# If the CALL_GRAPH and HAVE_DOT tags are set to YES then doxygen will +# generate a call dependency graph for every global function or class method. +# Note that enabling this option will significantly increase the time of a run. +# So in most cases it will be better to enable call graphs for selected +# functions only using the \callgraph command. + +CALL_GRAPH = NO + +# If the GRAPHICAL_HIERARCHY and HAVE_DOT tags are set to YES then doxygen +# will graphical hierarchy of all classes instead of a textual one. + +GRAPHICAL_HIERARCHY = YES + +# If the DIRECTORY_GRAPH, SHOW_DIRECTORIES and HAVE_DOT tags are set to YES +# then doxygen will show the dependencies a directory has on other directories +# in a graphical way. The dependency relations are determined by the #include +# relations between the files in the directories. + +DIRECTORY_GRAPH = YES + +# The DOT_IMAGE_FORMAT tag can be used to set the image format of the images +# generated by dot. Possible values are png, jpg, or gif +# If left blank png will be used. + +DOT_IMAGE_FORMAT = png + +# The tag DOT_PATH can be used to specify the path where the dot tool can be +# found. If left blank, it is assumed the dot tool can be found in the path. + +DOT_PATH = + +# The DOTFILE_DIRS tag can be used to specify one or more directories that +# contain dot files that are included in the documentation (see the +# \dotfile command). + +DOTFILE_DIRS = + +# The MAX_DOT_GRAPH_WIDTH tag can be used to set the maximum allowed width +# (in pixels) of the graphs generated by dot. If a graph becomes larger than +# this value, doxygen will try to truncate the graph, so that it fits within +# the specified constraint. Beware that most browsers cannot cope with very +# large images. + +MAX_DOT_GRAPH_WIDTH = 1024 + +# The MAX_DOT_GRAPH_HEIGHT tag can be used to set the maximum allows height +# (in pixels) of the graphs generated by dot. If a graph becomes larger than +# this value, doxygen will try to truncate the graph, so that it fits within +# the specified constraint. Beware that most browsers cannot cope with very +# large images. + +MAX_DOT_GRAPH_HEIGHT = 1024 + +# The MAX_DOT_GRAPH_DEPTH tag can be used to set the maximum depth of the +# graphs generated by dot. A depth value of 3 means that only nodes reachable +# from the root by following a path via at most 3 edges will be shown. Nodes +# that lay further from the root node will be omitted. Note that setting this +# option to 1 or 2 may greatly reduce the computation time needed for large +# code bases. Also note that a graph may be further truncated if the graph's +# image dimensions are not sufficient to fit the graph (see MAX_DOT_GRAPH_WIDTH +# and MAX_DOT_GRAPH_HEIGHT). If 0 is used for the depth value (the default), +# the graph is not depth-constrained. + +MAX_DOT_GRAPH_DEPTH = 0 + +# Set the DOT_TRANSPARENT tag to YES to generate images with a transparent +# background. This is disabled by default, which results in a white background. +# Warning: Depending on the platform used, enabling this option may lead to +# badly anti-aliased labels on the edges of a graph (i.e. they become hard to +# read). + +DOT_TRANSPARENT = NO + +# Set the DOT_MULTI_TARGETS tag to YES allow dot to generate multiple output +# files in one run (i.e. multiple -o and -T options on the command line). This +# makes dot run faster, but since only newer versions of dot (>1.8.10) +# support this, this feature is disabled by default. + +DOT_MULTI_TARGETS = YES + +# If the GENERATE_LEGEND tag is set to YES (the default) Doxygen will +# generate a legend page explaining the meaning of the various boxes and +# arrows in the dot generated graphs. + +GENERATE_LEGEND = YES + +# If the DOT_CLEANUP tag is set to YES (the default) Doxygen will +# remove the intermediate dot files that are used to generate +# the various graphs. + +DOT_CLEANUP = YES + +#--------------------------------------------------------------------------- +# Configuration::additions related to the search engine +#--------------------------------------------------------------------------- + +# The SEARCHENGINE tag specifies whether or not a search engine should be +# used. If set to NO the values of all tags below this one will be ignored. + +SEARCHENGINE = NO @@ -0,0 +1,6 @@ +VDR Plugin 'sudoku' Revision History +------------------------------------ + +2005-10-28: Version 0.1.0 + +- Initial revision. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..36917d3 --- /dev/null +++ b/Makefile @@ -0,0 +1,96 @@ +# +# Sudoku: A plugin for the Video Disk Recorder +# +# See the README file for copyright information and how to reach the author. +# +# $Id: Makefile 11 2005-10-28 01:00:01Z tom $ + +# The official name of this plugin. +# This name will be used in the '-P...' option of VDR to load the plugin. +# By default the main source file also carries this name. +# +PLUGIN = sudoku + +### The version number of this plugin (taken from the main source file): + +VERSION = $(shell grep 'static const char\* VERSION *=' $(PLUGIN).cpp | \ + awk '{ print $$6 }' | sed -e 's/[";]//g') + +### The C++ compiler and options: + +CXX ?= g++ +CXXFLAGS ?= -fPIC -O2 -Wall -Woverloaded-virtual + +### The directory environment: + +DVBDIR = ../../../../DVB +VDRDIR = ../../.. +LIBDIR = ../../lib +TMPDIR = /tmp + +### Allow user defined options to overwrite defaults: + +-include $(VDRDIR)/Make.config + +### The version number of VDR (taken from VDR's "config.h"): + +VDRVERSION = $(shell grep 'define VDRVERSION ' $(VDRDIR)/config.h | \ + awk '{ print $$3 }' | sed -e 's/"//g') +VDRVERSNUM = $(shell grep 'define VDRVERSNUM ' $(VDRDIR)/config.h | \ + awk '{ print $$3 }') + +### The name of the distribution archive: + +ARCHIVE = $(PLUGIN)-$(VERSION) +PACKAGE = vdr-$(ARCHIVE) + +### Includes and Defines (add further entries here): + +INCLUDES += -I$(VDRDIR)/include -I$(DVBDIR)/include + +DEFINES += -D_GNU_SOURCE -DPLUGIN_NAME_I18N='"$(PLUGIN)"' + +### The object files (add further files here): + +OBJS = $(PLUGIN).o setup.o i18n.o bitmap.o menu.o \ + puzzle.o generator.o solver.o backtrack.o + +### Implicit rules: + +%.o: %.cpp + $(CXX) $(CXXFLAGS) -c $(DEFINES) $(INCLUDES) $< + +# Dependencies: + +MAKEDEP = $(CXX) -MM -MG +DEPFILE = .dependencies +$(DEPFILE): Makefile + @$(MAKEDEP) $(DEFINES) $(INCLUDES) $(OBJS:%.o=%.cpp) > $@ + +-include $(DEPFILE) + +### Targets: + +all: libvdr-$(PLUGIN).so + @cd tools && $(MAKE) + +libvdr-$(PLUGIN).so: $(OBJS) + $(CXX) $(CXXFLAGS) -shared $(OBJS) -o $@ + @cp $@ $(LIBDIR)/$@.$(VDRVERSION) + +dist: clean + @-rm -rf $(TMPDIR)/$(ARCHIVE) + @mkdir $(TMPDIR)/$(ARCHIVE) + @cp -a * $(TMPDIR)/$(ARCHIVE) + @tar czf $(PACKAGE).tgz -C $(TMPDIR) \ + --exclude debian --exclude CVS --exclude .svn $(ARCHIVE) + @-rm -rf $(TMPDIR)/$(ARCHIVE) + @echo Distribution package created as $(PACKAGE).tgz + +srcdoc: Doxyfile $(OBJS:%.o=%.cpp) $(OBJS:%.o=%.h) + VERSION=$(VERSION) VDRVERSNUM=$(VDRVERSNUM) /usr/bin/doxygen + +clean: + @-rm -f $(OBJS) $(DEPFILE) *.so* *.tgz core* *~ + @-rm -rf srcdoc + @cd tools && $(MAKE) clean @@ -0,0 +1,81 @@ +This is a "plugin" for the Video Disk Recorder (VDR). + +Written by: Thomas Günther <tom@toms-cafe.de> + +Project's homepage: http://toms-cafe.de/vdr/sudoku + +Latest version available at: http://toms-cafe.de/vdr/sudoku + +See the file COPYING for license information. + + +Description: +------------ + +'Sudoku' is a VDR plugin to generate and solve Number Place puzzles, so called +Sudokus. + +A Sudoku puzzle consists of 9 x 9 cells subdivided into 9 regions with 3 x 3 +cells. The rules are simple. There have to be the numbers from 1 to 9 in every +row, column and region. In the beginning some numbers are given. These cells are +painted with cyan background color. The aim of the puzzle is to find the missing +numbers. There is only one solution of a Sudoku puzzle. + +The Sudoku puzzles are generated on-the-fly. The number of givens can be set in +the plugin's setup page down to a minimum of 26 givens. The generation of +puzzles with less than 26 givens takes too long. By default the cells with +givens are symmetrically ordered. But this can be disabled in the setup. + +To solve difficult Sudoku puzzles some hints can be used. Incorrect cells are +red and cells with ambiguous numbers are magenta. These hints can be disabled in +the setup. With the green key a cell can be marked. A marked cell has green +background color. With the yellow key the cursor is moved to the next free cell +with minimal possible numbers. The red key set the next possible number for the +current cell. + +Each time the plugin is started from the main menu the same puzzle is shown. A +new puzzle is only generated on VDR startup or if it has been requested by +pressing the blue key. This key has two functions. If no numbers are set a new +puzzle is generated. Otherwise all numbers are reset so that only the givens are +shown. + + +Setup: +------ + +- Givens count Givens count of the generated puzzles (26-81). + Default is 36. +- Symmetric givens Cells with givens are symmetrically ordered (yes/no). + Default is yes. +- Mark errors Incorrect cells are marked with red color (yes/no). + Default is yes. +- Mark ambiguous numbers Cells with ambiguous numbers are marked with magenta + color (yes/no). + Default is yes. +- Transparency (%) Set the transparency of the menu (0-100). + Default is 50. + + +Keys: +----- + +- Left/Right/Up/Down Move the cursor in the puzzle. +- 1-9 Set the number in the current cell. +- 0 Remove the number from the current cell. +- Green Mark/unmark the current cell. +- Yellow Move the cursor to the next free cell with minimal + possible numbers. +- Red Set the next possible number for the current cell - + reset the number if greater numbers are not possible. +- Blue Reset the puzzle (if some numbers set). + Start a new puzzle (if no numbers set). +- Back Quit the plugin. + + +Cell colors: +------------ + +- Cyan Givens +- Green Marked cells +- Red Incorrect cells +- Magenta Ambiguous numbers diff --git a/backtrack.cpp b/backtrack.cpp new file mode 100644 index 0000000..963724a --- /dev/null +++ b/backtrack.cpp @@ -0,0 +1,140 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: backtrack.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#include "backtrack.h" + +using namespace BackTrack; + + +//--- class BackTrack::Algorithm ----------------------------------------------- + +/** Constructor + * + * Constructs an backtracking algorithm to solve a problem. The problem is + * implemented in 'solution' which represents a path through the decision + * tree from the root to one leaf. + */ +Algorithm::Algorithm (Solution& solution, unsigned int max_iter) : + solution(solution), max_iter(max_iter) +{ + first = true; + valid = false; + level = -1; + iter = 0; +} + +/** Find the next valid solution to the problem. + * + * Repeated calls will find all solutions to a problem if multiple solutions + * exist. + */ +void Algorithm::find_next_solution() +{ + valid = find_solution(); +} + +/** Is the current solution a valid solution? */ +bool Algorithm::solution_is_valid() +{ + return valid; +} + +/** Reset the decision tree, i.e. the next call to 'find_solution' finds + * the first valid solution. + */ +void Algorithm::reset() +{ + while (level >= 0) + { + solution.reset_at(level); + --level; + } + first = true; +} + +/** Create the next leaf on the end of the solution. */ +void Algorithm::create_left_leaf() +{ + ++level; + solution.set_first_at(level); +} + +/** Backtrack through the decision tree until a node was found that hasn't + * been visited, return true if an unvisited node was found. + */ +bool Algorithm::visit_new_node() +{ + // If the current node is the rightmost child we must backtrack + // one level because there are no more children at this level. + // So we back up until we find a non-rightmost child, then + // generate the child to the right. If we back up to the top + // without finding an unvisted child, then all nodes have been + // generated. + while (level >= 0 && solution.is_last_at(level)) + { + solution.reset_at(level); + --level; + } + if (level < 0) + return false; + solution.set_next_at(level); + return true; +} + +/** Find the next valid sibling of the last leaf, return true if a valid + * sibling was found. + */ +bool Algorithm::find_valid_sibling() +{ + // If the current node is not valid pass through all siblings until either + // a valid sibling is found or the last sibling is reached. + for (;;) + { + ++iter; + if (max_iter != 0 && iter > max_iter) + return false; + if (solution.is_valid_at(level)) + return true; + if (solution.is_last_at(level)) + return false; + solution.set_next_at(level); + } +} + +/** Find the next valid solution to the problem, return true if a solution + * was found. + */ +bool Algorithm::find_solution() +{ + // If first time, need to create a root. + if (first) + { + first = false; + level = -1; + if (solution.is_last_level(level)) + return solution.is_valid_at(level); + create_left_leaf(); + } + // Otherwise visit new node since solution contains the last solution. + else if (!visit_new_node()) + return false; + + for (;;) + { + if (find_valid_sibling()) + { + if (solution.is_last_level(level)) + return true; + create_left_leaf(); + } + else if (max_iter != 0 && iter > max_iter) + return false; + else if (!visit_new_node()) + return false; // The tree has been exhausted, so no solution exists. + } +} diff --git a/backtrack.h b/backtrack.h new file mode 100644 index 0000000..263e1dc --- /dev/null +++ b/backtrack.h @@ -0,0 +1,159 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: backtrack.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_BACKTRACK_H +#define VDR_SUDOKU_BACKTRACK_H + +#include "sudoku.h" + + +/** Generic backtracking algorithm + * + * Inspired by an article by Roger Labbe "Solving Combinatorial Problems with + * STL and Backtracking" in C/C++-Users Journal, February 2000, pp. 56-64. + * + * The solution to a combinatorial problem can be described as a sequence of + * decisions. The backtracking algorithm traverses the decision tree + * depth-first. Each solution of the problem is a path through the tree from the + * root to one leaf. The algorithm traverses the tree by changing the elements + * of the solution. An element passes through all siblings on a certain level, + * i.e. through all possible decisions. Each step is checked if it makes the + * solution invalid, in which case the traversal of the whole branch is + * cancelled. Otherwise the algorithm either goes one level deeper or if this is + * the last level it has found one valid solution. After the last sibling on a + * level has been processed the algorithm goes back one level. Finally all valid + * solutions have been found if it comes back to the root node. + * + * This implementation of the backtracking algorithm consists of two classes. + * The Algorithm class contains the generic backtracking algorithm itself. The + * Solution class is the virtual base class for all specific solution classes. + * To solve a certain problem the specific solution class has to inherit from + * Solution implementing all virtual methods. + * + * Example: + * + * \code + * class ColorStatesList : public Solution + * { + * int clist[NUMBER_STATES]; + * void set_first_at(unsigned int level) { clist[level] = 0; } + * void set_next_at(unsigned int level) { ++clist[level]; } + * void reset_at(unsigned int level) {} + * bool is_last_at(unsigned int level) { return clist[level] >= LAST_COLOR; } + * bool is_valid_at(int level) { return check_all_neighbors_until(level); } + * bool is_last_level(int level) [ return level >= NUMBER_STATES-1; } + * ... + * }; + * + * void find_all_solutions() + * { + * ColorStatesList color_states_list(...); + * Algorithm algorithm(color_states_list); + * algorithm.find_next_solution(); + * while (algorithm.solution_is_valid()) + * { + * // Do something with the solution. + * ... + * algorithm.find_next_solution(); + * } + * } + * \endcode + */ +namespace BackTrack +{ + + //--- virtual base class BackTrack::Solution --------------------------------- + + /** Virtual base class of solutions for the backtracking algorithm */ + class Solution + { + public: + + /** Destructor */ + virtual ~Solution() {}; + + /** Set the element to the first sibling. */ + virtual void set_first_at(unsigned int level) = 0; + + /** Set the element to the next sibling. */ + virtual void set_next_at(unsigned int level) = 0; + + /** Reset the element. */ + virtual void reset_at(unsigned int level) = 0; + + /** Check if the element is set to the last sibling. */ + virtual bool is_last_at(unsigned int level) const = 0; + + /** Check if the element is valid (following elements ignored). */ + virtual bool is_valid_at(int level) const = 0; + + /** Check if the level is the last possible level. */ + virtual bool is_last_level(int level) const = 0; + }; + + + //--- class BackTrack::Algorithm --------------------------------------------- + + /** Implementation of a generic backtracking algorithm */ + class Algorithm + { + Solution& solution; + bool first; + bool valid; + int level; + unsigned int max_iter, iter; + + public: + + /** Constructor + * + * Constructs an backtracking algorithm to solve a problem. The problem is + * implemented in 'solution' which represents a path through the decision + * tree from the root to one leaf. + */ + Algorithm(Solution& solution, unsigned int max_iter = 0); + + /** Find the next valid solution to the problem. + * + * Repeated calls will find all solutions to a problem if multiple solutions + * exist. Return true if a solution was found. + */ + void find_next_solution(); + + /** Is the current solution a valid solution? */ + bool solution_is_valid(); + + /** Reset the decision tree, i.e. the next call to 'find_solution' finds + * the first valid solution. + */ + virtual void reset(); + + private: + + /** Create the next leaf on the end of the solution. */ + void create_left_leaf(); + + /** Backtrack through the decision tree until a node was found that hasn't + * been visited, return true if an unvisited node was found. + */ + bool visit_new_node(); + + /** Find the next valid sibling of the last leaf, return true if a valid + * sibling was found. + */ + bool find_valid_sibling(); + + /** Find the next valid solution to the problem, return true if a solution + * was found. + */ + bool find_solution(); + }; + +} // namespace BackTrack + +#endif // VDR_SUDOKU_BACKTRACK_H diff --git a/bitmap.cpp b/bitmap.cpp new file mode 100644 index 0000000..f41ca73 --- /dev/null +++ b/bitmap.cpp @@ -0,0 +1,151 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: bitmap.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#include "bitmap.h" +#include <vdr/config.h> +#include <vdr/osdbase.h> +#include <vdr/osd.h> +#include <ctype.h> + +// Compatibility to older vdr versions +#if VDRVERSNUM < 10307 + #define tColor eDvbColor + #define DrawRectangle Fill +#endif + +using namespace SudokuPlugin; + + +//--- class SudokuPlugin::Bitmap ----------------------------------------------- + +/** Constructor */ +Bitmap::Bitmap(int width, int height) : + cBitmap(width, height, 4) +{ +} + +/** Constructor for a bitmap with frame */ +Bitmap::Bitmap(int width, int height, tColor frameColor, + tColor backgroundColor) : + cBitmap(width, height, 4) +{ + DrawRectangle(0, 0, width - 1, height - 1, backgroundColor); + frame(0, 0, width - 1, height - 1, frameColor); +} + +/** Write a text into the bitmap. */ +void Bitmap::text(const char* text, bool centered) +{ + DrawRectangle(0, 0, Width() - 1, Height() - 1, clrWhite); + frame(0, 0, Width() - 1, Height() - 1, clrRed); + +#if VDRVERSNUM < 10307 + SetFont(fontOsd); + int lineCount; + char* wrapper = textWrapper(text, &lineCount); + int y = max((Height() - lineCount * cOsd::LineHeight()) / 2, 0); + char* line = wrapper; + while (*line) + { + char* newline = strchr(line, '\n'); + if (newline) + *newline = 0; + int x = 0; + if (centered) + x = max((Width() - Width(line)) / 2, 0); + Text(x, y, line, clrBlack, clrWhite); + if (newline) + *newline = '\n'; + if (!newline) + break; + line = newline + 1; + y += cOsd::LineHeight(); + } + free(wrapper); +#else + const cFont* font = cFont::GetFont(fontOsd); + cTextWrapper wrapper(text, font, Width()); + int y = max((Height() - wrapper.Lines() * font->Height()) / 2, 0); + for (int l = 0; l < wrapper.Lines(); ++l, y += font->Height()) + { + int x = 0; + if (centered) + x = max((Width() - font->Width(wrapper.GetLine(l))) / 2, 0); + DrawText(x, y, wrapper.GetLine(l), clrBlack, clrWhite, font); + } +#endif +} + +/** Draw a frame into the bitmap. */ +void Bitmap::frame(int x1, int y1, int x2, int y2, tColor frameColor) +{ + DrawRectangle(x1, y1, x2, y1 + 1, frameColor); + DrawRectangle(x1, y1, x1 + 1, y2, frameColor); + DrawRectangle(x1, y2 - 1, x2, y2, frameColor); + DrawRectangle(x2 - 1, y1, x2, y2, frameColor); +} + +#if VDRVERSNUM < 10307 +/** Wrap the text to fit into the bitmap (taken from font.c / VDR 1.3.7). */ +char *Bitmap::textWrapper(const char *Text, int *p_lines) +{ + char *text = strdup(Text); + int lines = 1; + + char *Blank = NULL; + char *Delim = NULL; + int w = 0; + + stripspace(text); // strips trailing newlines + + for (char *p = text; *p; ) { + if (*p == '\n') { + lines++; + w = 0; + Blank = Delim = NULL; + p++; + continue; + } + else if (isspace(*p)) + Blank = p; + int cw = Width(*p); + if (w + cw > Width()) { + if (Blank) { + *Blank = '\n'; + p = Blank; + continue; + } + else { + // Here's the ugly part, where we don't have any whitespace to + // punch in a newline, so we need to make room for it: + if (Delim) + p = Delim + 1; // let's fall back to the most recent delimiter + char *s = MALLOC(char, strlen(text) + 2); // The additional '\n' plus the terminating '\0' + int l = p - text; + strncpy(s, text, l); + s[l] = '\n'; + strcpy(s + l + 1, p); + free(text); + text = s; + p = text + l; + continue; + } + } + else + w += cw; + if (strchr("-.,:;!?_", *p)) { + Delim = p; + Blank = NULL; + } + p++; + } + if (p_lines != NULL) + *p_lines = lines; + return text; +} +#endif diff --git a/bitmap.h b/bitmap.h new file mode 100644 index 0000000..c212570 --- /dev/null +++ b/bitmap.h @@ -0,0 +1,53 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: bitmap.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_BITMAP_H +#define VDR_SUDOKU_BITMAP_H + +#include "sudoku.h" +#include <vdr/config.h> +#include <vdr/osdbase.h> +#include <vdr/osd.h> + +// Compatibility to older vdr versions +#if VDRVERSNUM < 10307 + #define tColor eDvbColor +#endif + + +namespace SudokuPlugin +{ + + //--- class SudokuPlugin::Bitmap --------------------------------------------- + + /** Plugin-specific version of the bitmap class */ + class Bitmap : public cBitmap + { + public: + + /** Constructor */ + Bitmap(int width, int height); + + /** Constructor for a bitmap with frame */ + Bitmap(int width, int height, tColor frameColor, tColor backgroundColor); + + /** Write a text into the bitmap. */ + void text(const char* text, bool centered = true); + + /** Draw a frame into the bitmap. */ + void frame(int x1, int y1, int x2, int y2, tColor frameColor); + +#if VDRVERSNUM < 10307 + /** Wrap the text to fit into the bitmap (taken from font.c / VDR 1.3.7). */ + char *textWrapper(const char *Text, int *p_lines); +#endif + }; + +} // namespace SudokuPlugin + +#endif // VDR_SUDOKU_BITMAP_H diff --git a/generator.cpp b/generator.cpp new file mode 100644 index 0000000..47e5e35 --- /dev/null +++ b/generator.cpp @@ -0,0 +1,128 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: generator.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#define USE_RAND +#include "generator.h" +#include "solver.h" +#include "backtrack.h" +#include "puzzle.h" +#include <assert.h> + +using namespace Sudoku; +using namespace BackTrack; + + +//--- class Sudoku::Generator -------------------------------------------------- + +/** Constructor */ +Generator::Generator(Puzzle& puzzle, unsigned int givens_count, + bool symmetric, unsigned int max_iter) : + Algorithm(*this, max_iter), puzzle(puzzle), symmetric(symmetric) +{ + assert(givens_count <= SDIM); + + // Search a random Sudoku solution. + for (bool found = false; !found;) + { + sudoku.reset(); + Solver solver(sudoku, true); + solver.find_next_solution(); + found = solver.solution_is_valid(); + } + + // If symmetric pos_list contains only the first halve of all positions. + pos_count = SDIM; + free_count = SDIM - givens_count; + free_center = symmetric && pos_count % 2 != 0 && free_count % 2 != 0; + if (symmetric) + pos_count /= 2, free_count /= 2; + + // Fill pos_list with positions in random order. + bool list[pos_count]; + unsigned int p, i, c; + for (p = 0; p < pos_count; ++p) + list[p] = true; + for (i = 0; i < pos_count; ++i) + { + c = rand(pos_count - i) + 1; + for (p = 0; p < pos_count; ++p) + if (list[p]) + if (--c == 0) + break; + assert(p < pos_count); + list[p] = false; + pos_list[i] = p; + } +} + +/** Set the element to the first sibling. */ +void Generator::set_first_at(unsigned int level) +{ + assert(level < free_count); + free_list[level] = 0; +} + +/** Set the element to the next sibling. */ +void Generator::set_next_at(unsigned int level) +{ + assert(level < free_count); + ++free_list[level]; +} + +/** Reset the element. */ +void Generator::reset_at(unsigned int level) +{ +} + +/** Check if the element is set to the last sibling. */ +bool Generator::is_last_at(unsigned int level) const +{ + assert(level < free_count); + return free_list[level] >= pos_count - 1; +} + +/** Check if the element is valid (following elements ignored). */ +bool Generator::is_valid_at(int level) const +{ + assert(level < int(free_count)); + + // free_list contains ordered indices to pos_list. + if (level > 0 && free_list[level] <= free_list[level - 1]) + return false; + if (level >= 0 && free_list[level] > pos_count - (free_count - level)) + return false; + + // Fill list with marks for givens. + bool given_marks[SDIM]; + int i; + for (i = 0; i < SDIM; ++i) + given_marks[i] = true; + for (i = 0; i <= level; ++i) + { + Pos p = pos_list[free_list[i]]; + given_marks[p] = false; + if (symmetric) + given_marks[p.symmetric()] = false; + } + if (free_center) + given_marks[Pos::center()] = false; + + // Set givens in puzzle and check if it has only one solution. + puzzle.set_givens(sudoku, given_marks); + Solver solver(puzzle); + solver.find_next_solution(); + assert(solver.solution_is_valid()); + solver.find_next_solution(); + return !solver.solution_is_valid(); +} + +/** Check if the level is the last possible level. */ +bool Generator::is_last_level(int level) const +{ + return level >= int(free_count) - 1; +} diff --git a/generator.h b/generator.h new file mode 100644 index 0000000..8266b84 --- /dev/null +++ b/generator.h @@ -0,0 +1,77 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: generator.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_GENERATOR_H +#define VDR_SUDOKU_GENERATOR_H + +#include "sudoku.h" +#include "backtrack.h" +#include "puzzle.h" + + +namespace Sudoku +{ + + //--- class Sudoku::Generator ------------------------------------------------ + + /** Implementation of a backtracking algorithm to generate Sudoku puzzles + * + * To generate Sudoku puzzles two nested backtracking algorithms are used. + * First a random Sudoku solution is searched. Then the algorithm tries to + * remove some numbers so that only the requested number of givens remains. + * Each puzzle is checked with the nested solver algorithm if there is only + * one solution. + * + * Example: + * + * \code + * Puzzle puzzle; + * Generator generator(puzzle, 36); + * generator.find_next_solution(); + * bool found = generator.solution_is_valid(); + * \endcode + */ + class Generator : public BackTrack::Algorithm, public BackTrack::Solution + { + Puzzle& puzzle; + Puzzle sudoku; + unsigned int free_list[SDIM]; + unsigned int free_count; + Pos pos_list[SDIM]; + unsigned int pos_count; + bool symmetric; + bool free_center; + + public: + + /** Constructor */ + Generator(Puzzle& puzzle, unsigned int givens_count, + bool symmetric = true, unsigned int max_iter = 0); + + /** Set the element to the first sibling. */ + virtual void set_first_at(unsigned int level); + + /** Set the element to the next sibling. */ + virtual void set_next_at(unsigned int level); + + /** Reset the element. */ + virtual void reset_at(unsigned int level); + + /** Check if the element is set to the last sibling. */ + virtual bool is_last_at(unsigned int level) const; + + /** Check if the element is valid (following elements ignored). */ + virtual bool is_valid_at(int level) const; + + /** Check if the level is the last possible level. */ + virtual bool is_last_level(int level) const; + }; + +} // namespace Sudoku + +#endif // VDR_SUDOKU_GENERATOR_H diff --git a/i18n.cpp b/i18n.cpp new file mode 100644 index 0000000..62ef544 --- /dev/null +++ b/i18n.cpp @@ -0,0 +1,247 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: i18n.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#include "i18n.h" +#include <vdr/config.h> + + +const tI18nPhrase SudokuPlugin::Phrases[] = { + { "Sudoku", // English + "Sudoku", // Deutsch / German + "", // Slovenski / Slovenian + "", // Italiano / Italian + "", // Nederlands / Dutch + "", // Português / Portuguese + "", // Français / French + "", // Norsk / Norwegian + "", // suomi / Finnish + "", // Polski / Polish + "", // Español / Spanish + "", // ÅëëçíéêÜ / Greek + "", // Svenska / Swedish + "", // Românã / Romanian + "", // Magyar / Hungarian + "", // Català / Catalanian +#if VDRVERSNUM > 10302 + "", // ÀãááÚØÙ / Russian +#if VDRVERSNUM > 10307 + "", // Hrvatski / Croatian +#if VDRVERSNUM > 10313 + "", // Eesti / Estonian +#if VDRVERSNUM > 10316 + "", // Dansk / Danish +#endif +#endif +#endif +#endif + }, + { "Sudoku - generate and solve Number Place puzzles", // English + "Sudoku - Erzeugen und Lösen von Zahlenpuzzles", // Deutsch / German + "", // Slovenski / Slovenian + "", // Italiano / Italian + "", // Nederlands / Dutch + "", // Português / Portuguese + "", // Français / French + "", // Norsk / Norwegian + "", // suomi / Finnish + "", // Polski / Polish + "", // Español / Spanish + "", // ÅëëçíéêÜ / Greek + "", // Svenska / Swedish + "", // Românã / Romanian + "", // Magyar / Hungarian + "", // Català / Catalanian +#if VDRVERSNUM > 10302 + "", // ÀãááÚØÙ / Russian +#if VDRVERSNUM > 10307 + "", // Hrvatski / Croatian +#if VDRVERSNUM > 10313 + "", // Eesti / Estonian +#if VDRVERSNUM > 10316 + "", // Dansk / Danish +#endif +#endif +#endif +#endif + }, + { "Givens count", // English + "Anzahl vorgegebener Zahlen", // Deutsch / German + "", // Slovenski / Slovenian + "", // Italiano / Italian + "", // Nederlands / Dutch + "", // Português / Portuguese + "", // Français / French + "", // Norsk / Norwegian + "", // suomi / Finnish + "", // Polski / Polish + "", // Español / Spanish + "", // ÅëëçíéêÜ / Greek + "", // Svenska / Swedish + "", // Românã / Romanian + "", // Magyar / Hungarian + "", // Català / Catalanian +#if VDRVERSNUM > 10302 + "", // ÀãááÚØÙ / Russian +#if VDRVERSNUM > 10307 + "", // Hrvatski / Croatian +#if VDRVERSNUM > 10313 + "", // Eesti / Estonian +#if VDRVERSNUM > 10316 + "", // Dansk / Danish +#endif +#endif +#endif +#endif + }, + { "Symmetric givens", // English + "Vorgegebene Zahlen symmetrisch anordnen", // Deutsch / German + "", // Slovenski / Slovenian + "", // Italiano / Italian + "", // Nederlands / Dutch + "", // Português / Portuguese + "", // Français / French + "", // Norsk / Norwegian + "", // suomi / Finnish + "", // Polski / Polish + "", // Español / Spanish + "", // ÅëëçíéêÜ / Greek + "", // Svenska / Swedish + "", // Românã / Romanian + "", // Magyar / Hungarian + "", // Català / Catalanian +#if VDRVERSNUM > 10302 + "", // ÀãááÚØÙ / Russian +#if VDRVERSNUM > 10307 + "", // Hrvatski / Croatian +#if VDRVERSNUM > 10313 + "", // Eesti / Estonian +#if VDRVERSNUM > 10316 + "", // Dansk / Danish +#endif +#endif +#endif +#endif + }, + { "Mark errors", // English + "Fehler markieren", // Deutsch / German + "", // Slovenski / Slovenian + "", // Italiano / Italian + "", // Nederlands / Dutch + "", // Português / Portuguese + "", // Français / French + "", // Norsk / Norwegian + "", // suomi / Finnish + "", // Polski / Polish + "", // Español / Spanish + "", // ÅëëçíéêÜ / Greek + "", // Svenska / Swedish + "", // Românã / Romanian + "", // Magyar / Hungarian + "", // Català / Catalanian +#if VDRVERSNUM > 10302 + "", // ÀãááÚØÙ / Russian +#if VDRVERSNUM > 10307 + "", // Hrvatski / Croatian +#if VDRVERSNUM > 10313 + "", // Eesti / Estonian +#if VDRVERSNUM > 10316 + "", // Dansk / Danish +#endif +#endif +#endif +#endif + }, + { "Mark ambiguous numbers", // English + "Unklare Zahlen markieren", // Deutsch / German + "", // Slovenski / Slovenian + "", // Italiano / Italian + "", // Nederlands / Dutch + "", // Português / Portuguese + "", // Français / French + "", // Norsk / Norwegian + "", // suomi / Finnish + "", // Polski / Polish + "", // Español / Spanish + "", // ÅëëçíéêÜ / Greek + "", // Svenska / Swedish + "", // Românã / Romanian + "", // Magyar / Hungarian + "", // Català / Catalanian +#if VDRVERSNUM > 10302 + "", // ÀãááÚØÙ / Russian +#if VDRVERSNUM > 10307 + "", // Hrvatski / Croatian +#if VDRVERSNUM > 10313 + "", // Eesti / Estonian +#if VDRVERSNUM > 10316 + "", // Dansk / Danish +#endif +#endif +#endif +#endif + }, + { "Transparency (%)", // English + "Transparenz (%)", // Deutsch / German + "", // Slovenski / Slovenian + "", // Italiano / Italian + "", // Nederlands / Dutch + "", // Português / Portuguese + "", // Français / French + "", // Norsk / Norwegian + "", // suomi / Finnish + "", // Polski / Polish + "", // Español / Spanish + "", // ÅëëçíéêÜ / Greek + "", // Svenska / Swedish + "", // Românã / Romanian + "", // Magyar / Hungarian + "", // Català / Catalanian +#if VDRVERSNUM > 10302 + "", // ÀãááÚØÙ / Russian +#if VDRVERSNUM > 10307 + "", // Hrvatski / Croatian +#if VDRVERSNUM > 10313 + "", // Eesti / Estonian +#if VDRVERSNUM > 10316 + "", // Dansk / Danish +#endif +#endif +#endif +#endif + }, + { "Congratulations!\nPress OK to start a new puzzle", // English + "Herzlichen Glückwunsch!\nOK startet ein neues Puzzle", // Deutsch / German + "", // Slovenski / Slovenian + "", // Italiano / Italian + "", // Nederlands / Dutch + "", // Português / Portuguese + "", // Français / French + "", // Norsk / Norwegian + "", // suomi / Finnish + "", // Polski / Polish + "", // Español / Spanish + "", // ÅëëçíéêÜ / Greek + "", // Svenska / Swedish + "", // Românã / Romanian + "", // Magyar / Hungarian + "", // Català / Catalanian +#if VDRVERSNUM > 10302 + "", // ÀãááÚØÙ / Russian +#if VDRVERSNUM > 10307 + "", // Hrvatski / Croatian +#if VDRVERSNUM > 10313 + "", // Eesti / Estonian +#if VDRVERSNUM > 10316 + "", // Dansk / Danish +#endif +#endif +#endif +#endif + }, + { NULL } +}; @@ -0,0 +1,23 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: i18n.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_I18N_H +#define VDR_SUDOKU_I18N_H + +#include "sudoku.h" +#include <vdr/i18n.h> + + +namespace SudokuPlugin +{ + + extern const tI18nPhrase Phrases[]; + +} // namespace SudokuPlugin + +#endif // VDR_SUDOKU_I18N_H diff --git a/menu.cpp b/menu.cpp new file mode 100644 index 0000000..2a4e422 --- /dev/null +++ b/menu.cpp @@ -0,0 +1,244 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: menu.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#include "menu.h" +#include "puzzle.h" +#include "setup.h" +#include "bitmap.h" +#include "i18n.h" +#include <vdr/config.h> +#include <vdr/osdbase.h> +#include <vdr/osd.h> +#include <vdr/font.h> + +// Compatibility to older vdr versions +#if VDRVERSNUM < 10307 + #define tColor eDvbColor + #define DrawRectangle Fill + #define DrawBitmap SetBitmap + #define cOsdProvider cOsd + #define NewOsd OpenRaw + struct tArea { int x1, y1, x2, y2, bpp; }; + #define SetAreas(a,n) Create(a->x1, a->y1,\ + a->x2 - a->x1 + 1, a->y2 - a->y1 + 1,\ + a->bpp, true) + #define Color GetColor + #define savePalette(bitmap) savePalette(2) + #define SetPalette(palette, area) Width('X') +#endif + +using namespace SudokuPlugin; +using namespace Sudoku; + + +// Definitions for grid structure +#define CELL_SIZE 42 +#define CELL_POS(i) ((i) * (CELL_SIZE + 2) + (i)/RDIM * 3 + 5) +#define GRID_SIZE (DIM * (CELL_SIZE + 2) + DIM/RDIM * 3 + 5) + +// Definitions for grid colors +#define TRANS(c,t) tColor(((c) & 0x00FFFFFF) | (0xFF * (100-(t))/100)<<24) +#define GRID_COLOR clrWhite +#define CURSUR_COLOR clrBlue +#define NUMBER_FG clrWhite +#define NUMBER_BG clrBlack +#define ERROR_FG clrWhite +#define ERROR_BG clrRed +#define AMBIG_FG clrWhite +#define AMBIG_BG clrMagenta +#define MARKED_FG clrWhite +#define MARKED_BG clrGreen +#define GIVEN_FG clrBlack +#define GIVEN_BG clrCyan + + +//--- class SudokuPlugin::Menu ------------------------------------------------- + +/** Constructor */ +Menu::Menu(const SetupData& setup, Puzzle& puzzle, Pos& curr) : + cOsdObject(true), setup(setup), puzzle(puzzle), curr(curr) +{ + xPos = (720 - GRID_SIZE) / 2; + yPos = (576 - GRID_SIZE) / 2; + osd = NULL; + info = NULL; + infoText = NULL; + new_puzzle_request = false; +} + +/** Destructor */ +Menu::~Menu() +{ + delete info; + delete osd; +} + +/** Display the menu on the OSD. */ +void Menu::Show() +{ + int x1 = xPos, y1 = yPos; + int x2 = xPos + GRID_SIZE - 1, y2 = yPos + GRID_SIZE -1; + + osd = cOsdProvider::NewOsd(0, 0); + if (osd) + { + tArea areas[] = { x1, y1, x2, y2, 4 }; + osd->SetAreas(areas, 1); + paint(); + } +} + +/** Process user events. */ +eOSState Menu::ProcessKey(eKeys key) +{ + eOSState state = cOsdObject::ProcessKey(key); + if (state == osUnknown) + { + if (key == kBack) + return osEnd; + if (new_puzzle_request) + { + if (key == kOk) + { + new_puzzle_request = false; + puzzle.generate(setup.givens_count, setup.symmetric); + } + } + else + { + switch (key) + { + case kLeft: + case kLeft|k_Repeat: + curr = curr.prev_col(); + break; + case kRight: + case kRight|k_Repeat: + curr = curr.next_col(); + break; + case kUp: + case kUp|k_Repeat: + curr = curr.prev_row(); + break; + case kDown: + case kDown|k_Repeat: + curr = curr.next_row(); + break; + case k0: + case k1: + case k2: + case k3: + case k4: + case k5: + case k6: + case k7: + case k8: + case k9: + puzzle.set(curr, key - k0); + break; + case kRed: + puzzle.set(curr, puzzle.next_number(curr)); + break; + case kGreen: + puzzle.toggle_mark(curr); + break; + case kYellow: + if (puzzle.next_free(curr) <= Pos::last()) + curr = puzzle.next_free(curr); + break; + case kBlue: + if (puzzle.untouched()) + puzzle.generate(setup.givens_count, setup.symmetric); + else + puzzle.reset(); + break; + default: + return osContinue; + } + } + if (puzzle.solved()) + { + new_puzzle_request = true; + infoText = tr("Congratulations!\nPress OK to start a new puzzle"); + } + paint(); + state = osContinue; + } + return state; +} + +/** Paint all pieces of the menu. */ +void Menu::paint() +{ + int trans = setup.transparency; + tColor fg, bg = TRANS(GRID_COLOR, trans); + int x1 = xPos, y1 = yPos; + int x2 = xPos + GRID_SIZE - 1, y2 = yPos + GRID_SIZE -1; + + // Save and restore palette to reduce flickering. + cPalette savePalette(*osd->GetBitmap(0)); + osd->DrawRectangle(x1, y1, x2, y2, bg); + osd->SetPalette(savePalette, 0); + + // Paint all cells. + for (Pos p = Pos::first(); p <= Pos::last(); p = p.next()) + { + fg = NUMBER_FG, bg = NUMBER_BG; + if (puzzle.given(p)) + fg = GIVEN_FG, bg = GIVEN_BG; + else if (puzzle.marked(p)) + fg = MARKED_FG, bg = MARKED_BG; + else if (setup.mark_errors && puzzle.error(p)) + fg = ERROR_FG, bg = ERROR_BG; + else if (setup.mark_ambiguous && puzzle.ambiguous(p)) + fg = AMBIG_FG, bg = AMBIG_BG; + fg = TRANS(fg, trans); + bg = TRANS(bg, trans); + + // Paint the background of the cell. + x1 = xPos + CELL_POS(p.col()), y1 = yPos + CELL_POS(p.row()); + x2 = x1 + CELL_SIZE - 1, y2 = y1 + CELL_SIZE - 1; + osd->DrawRectangle(x1, y1, x2, y2, bg); + + // Paint the content of the cell. + if (puzzle.get(p) != 0) + { + char txt[2] = { '0' + puzzle.get(p), 0 }; +#if VDRVERSNUM < 10307 + osd->SetFont(fontFix); + osd->Text(x1 + max((CELL_SIZE - osd->Width(txt)) / 2, 0), + y1 + max((CELL_SIZE - cOsd::LineHeight()) / 2, 0), + txt, fg, bg); +#else + const cFont* font = cFont::GetFont(fontFix); + osd->DrawText(x1, y1, txt, fg, bg, font, CELL_SIZE, CELL_SIZE, taCenter); +#endif + } + } + + // Paint the cursor. + bg = TRANS(CURSUR_COLOR, trans); + x1 = xPos + CELL_POS(curr.col()), y1 = yPos + CELL_POS(curr.row()); + x2 = x1 + CELL_SIZE - 1, y2 = y1 + CELL_SIZE - 1; + osd->DrawRectangle(x1 - 5, y1 - 5, x2, y1, bg); + osd->DrawRectangle(x1 - 5, y1, x1, y2 + 5, bg); + osd->DrawRectangle(x1, y2, x2 + 5, y2 + 5, bg); + osd->DrawRectangle(x2, y1 - 5, x2 + 5, y2, bg); + + // Paint info window. + if (infoText) + { + if (!info) + info = new Bitmap(GRID_SIZE - 20, 60); + info->text(infoText); + osd->DrawBitmap(xPos + 10, yPos + 10, *info); + infoText = NULL; + } + + osd->Flush(); +} @@ -0,0 +1,66 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: menu.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_MENU_H +#define VDR_SUDOKU_MENU_H + +#include "sudoku.h" +namespace SudokuPlugin { class SetupData; class Bitmap; } +namespace Sudoku { class Puzzle; class Pos; } +#include <vdr/config.h> +#include <vdr/osdbase.h> +#include <vdr/osd.h> + +// Compatibility to older vdr versions +#if VDRVERSNUM < 10307 + #define cOsd_ cOsdBase +#else + #define cOsd_ cOsd +#endif + + +namespace SudokuPlugin +{ + + //--- class SudokuPlugin::Menu ----------------------------------------------- + + /** Main menu of the plugin */ + class Menu : public cOsdObject + { + const SetupData& setup; + Sudoku::Puzzle& puzzle; + Sudoku::Pos& curr; + int xPos, yPos; + cOsd_* osd; + Bitmap* info; + const char* infoText; + bool new_puzzle_request; + + public: + + /** Constructor */ + Menu(const SetupData& setup, Sudoku::Puzzle& puzzle, Sudoku::Pos& curr); + + /** Destructor */ + virtual ~Menu(); + + /** Display the menu on the OSD. */ + virtual void Show(); + + /** Process user events. */ + virtual eOSState ProcessKey(eKeys key); + + private: + + /** Paint all pieces of the menu. */ + void paint(); + }; + +} // namespace SudokuPlugin + +#endif // VDR_SUDOKU_MENU_H diff --git a/puzzle.cpp b/puzzle.cpp new file mode 100644 index 0000000..803c130 --- /dev/null +++ b/puzzle.cpp @@ -0,0 +1,260 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: puzzle.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#include "puzzle.h" +#include "generator.h" +#include <assert.h> + +using namespace Sudoku; + + +//--- class Sudoku::Numbers ---------------------------------------------------- + +/** Constructor */ +Numbers::Numbers() +{ + reset(); +} + +/** Destructor */ +Numbers::~Numbers() +{ +} + +/** Remove all numbers. */ +void Numbers::reset() +{ + for (unsigned int i = 0; i < SDIM; ++i) + content[i] = 0; +} + +/** Set numbers from contents of sudoku if marked in marks. */ +void Numbers::set_contents(const Numbers& sudoku, const bool marks[SDIM]) +{ + for (unsigned int i = 0; i < SDIM; ++i) + if (marks[i]) + content[i] = sudoku.get(i); + else + content[i] = 0; +} + +/** Set the number into this cell. */ +void Numbers::set(Pos pos, unsigned int number) +{ + assert (pos <= Pos::last()); + assert (0 <= number && number <= DIM); + content[pos] = number; +} + +/** Get the number from this cell. */ +unsigned int Numbers::get(Pos pos) const +{ + assert (pos <= Pos::last()); + assert (0 <= content[pos] && content[pos] <= DIM); + return content[pos]; +} + + +//--- class Sudoku::Puzzle ----------------------------------------------------- + +/** Constructor */ +Puzzle::Puzzle(unsigned int givens_count, bool symmetric) +{ + if (givens_count == 0) + clear_givens(); + else + generate(givens_count, symmetric); +} + +/** Reset the puzzle. */ +void Puzzle::reset() +{ + unsigned int i; + + // Fill the puzzle with the givens. + for (i = 0; i < SDIM; ++i) + Numbers::set(i, givens.get(i)); + + // Compute possible numbers for all cells. + for (i = 0; i < SDIM; ++i) + compute_numbers(i); + + // Reset marked cells. + for (i = 0; i < SDIM; ++i) + marks[i] = false; +} + +/** Set the number into this cell. */ +void Puzzle::set(Pos pos, unsigned int number) +{ + assert (pos <= Pos::last()); + assert (0 <= number && number <= DIM); + + if (!given(pos) && get(pos) != number) + { + Numbers::set(pos, number); + + // Refresh possible numbers of all affected cells. + for (Pos p = Pos::first(); p <= Pos::last(); p = p.next()) + if (p.col() == pos.col() || p.row() == pos.row() || p.reg() == pos.reg()) + compute_numbers(p); + } +} + +/** Generate a new puzzle. */ +void Puzzle::generate(unsigned int givens_count, bool symmetric) +{ + // Search a random non-ambiguous puzzle. + for (bool found = false; !found;) + { + Generator generator(*this, givens_count, symmetric, symmetric ? 500 : 2000); + generator.find_next_solution(); + found = generator.solution_is_valid(); + } + reset(); +} + +/** Set givens from contents of sudoku if marked in given_marks. */ +void Puzzle::set_givens(const Numbers& sudoku, const bool given_marks[SDIM]) +{ + givens.set_contents(sudoku, given_marks); + reset(); +} + +/** Remove all givens. */ +void Puzzle::clear_givens() +{ + givens.reset(); + reset(); +} + +/** No cells set? */ +bool Puzzle::untouched() const +{ + unsigned int i; + + for (i = 0; i < SDIM; ++i) + if (get(i) != givens.get(i)) + return false; + + return true; +} + +/** Is the number in this cell given? */ +bool Puzzle::given(Pos pos) const +{ + assert (pos <= Pos::last()); + return givens.get(pos) != 0; +} + +/** Is there an error on this position? */ +bool Puzzle::error(Pos pos) const +{ + assert (pos <= Pos::last()); + return !correct(pos); +} + +/** Is the number in this cell ambiguous? */ +bool Puzzle::ambiguous(Pos pos) const +{ + assert (pos <= Pos::last()); + return get(pos) != 0 && count[pos] > 1; +} + +/** All cells set and no errors? */ +bool Puzzle::solved() const +{ + unsigned int i; + + for (i = 0; i < SDIM; ++i) + if (get(i) == 0 || !correct(i)) + return false; + + return true; +} + +/** Is this cell marked? */ +bool Puzzle::marked(Pos pos) const +{ + assert (pos <= Pos::last()); + return marks[pos]; +} + +/** Toggle the mark for this cell. */ +void Puzzle::toggle_mark(Pos pos) +{ + assert (pos < Pos::last()); + marks[pos] = !marks[pos]; +} + +/** Get the next free cell with minimal possible numbers. */ +Pos Puzzle::next_free(Pos pos) const +{ + unsigned int min_count = DIM+1, min_index = SDIM, i; + + for (pos = (pos+1)%SDIM, i = 0; i < SDIM; ++i, pos = (pos+1)%SDIM) + if (get(pos) == 0 && count[pos] < min_count) + min_count = count[pos], min_index = pos; + + return min_index; +} + +/** Get the next possible number for this cell. */ +unsigned int Puzzle::next_number(Pos pos) +{ + assert (pos <= Pos::last()); + unsigned int n = get(pos); + unsigned int i; + + if (!given(pos)) + for (n = (n+1)%(DIM+1), i = 0; i < DIM+1; ++i, n = (n+1)%(DIM+1)) + if (numbers[pos][n]) + break; + + return n; +} + +/** Get the count of possible numbers for this cell. */ +unsigned int Puzzle::numbers_count(Pos pos) +{ + assert (pos <= Pos::last()); + return count[pos]; +} + +/** Compute all possible numbers for this cell. */ +void Puzzle::compute_numbers(Pos pos) +{ + assert(pos <= Pos::last()); + unsigned int i; + + // Fill list with all numbers. + for (i = 1; i <= DIM; ++i) + numbers[pos][i] = true; + + // Disable numbers found in row, column or region. + for (Pos p = Pos::first(); p <= Pos::last(); p = p.next()) + if (p != pos && + (p.col() == pos.col() || p.row() == pos.row() || p.reg() == pos.reg())) + numbers[pos][get(p)] = false; + + // Count the possible numbers. + count[pos] = 0; + for (i = 1; i <= DIM; ++i) + if (numbers[pos][i]) + ++count[pos]; + + // 0 is always possible. + numbers[pos][0] = true; +} + +/** Is the number in this cell a possible number? */ +bool Puzzle::correct(Pos pos) const +{ + assert(pos <= Pos::last()); + return count[pos] != 0 && numbers[pos][get(pos)]; +} diff --git a/puzzle.h b/puzzle.h new file mode 100644 index 0000000..4083350 --- /dev/null +++ b/puzzle.h @@ -0,0 +1,163 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: puzzle.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_PUZZLE_H +#define VDR_SUDOKU_PUZZLE_H + +#include "sudoku.h" + + +/** Sudoku puzzle + * + * A Sudoku puzzle consists of 9 x 9 cells subdivided into 9 regions with 3 x 3 + * cells. The rules are simple. There have to be the numbers from 1 to 9 in + * every row, column and region. + */ +namespace Sudoku +{ + + /** Regions, rows/columns and square dimension of the puzzle */ + enum + { + /** Regions dimension. Width and height of a region */ + RDIM = 3, + + /** Dimension. Number of cells in a row, column or region */ + DIM = RDIM * RDIM, + + /** Square dimension. Number of cells in the whole puzzle */ + SDIM = DIM * DIM + }; + + + //--- class Sudoku::Pos ------------------------------------------------------ + + /** Position in a Sudoku */ + class Pos + { + unsigned int pos; + public: + Pos(unsigned int col, unsigned int row) : pos(col + row * DIM) {} + Pos(unsigned int pos = 0) : pos(pos) {} + operator unsigned int() const { return pos; } + static Pos first() { return 0; } + static Pos last() { return SDIM-1; } + Pos next() const { return pos + 1; } + unsigned int col() const { return pos % DIM; } + unsigned int row() const { return pos / DIM; } + unsigned int reg() const { return (col() / RDIM) + RDIM * (row() / RDIM); } + static Pos center() { return SDIM / 2; } + Pos symmetric() const { return SDIM - 1 - pos; } + Pos prev_col() const { return col() > 0 ? pos - 1 : pos; } + Pos next_col() const { return col() < DIM-1 ? pos + 1 : pos; } + Pos prev_row() const { return row() > 0 ? pos - DIM : pos; } + Pos next_row() const { return row() < DIM-1 ? pos + DIM : pos; } + }; + + + //--- class Sudoku::Numbers -------------------------------------------------- + + /** Numbers of a Sudoku */ + class Numbers + { + unsigned int content[SDIM]; + + public: + + /** Constructor */ + Numbers(); + + /** Destructor */ + virtual ~Numbers(); + + /** Remove all numbers. */ + virtual void reset(); + + /** Set numbers from contents of sudoku if marked in marks. */ + virtual void set_contents(const Numbers& sudoku, const bool marks[SDIM]); + + /** Set the number into this cell. */ + virtual void set(Pos pos, unsigned int number); + + /** Get the number from this cell. */ + virtual unsigned int get(Pos pos) const; + }; + + + //--- class Sudoku::Puzzle --------------------------------------------------- + + /** Sudoku puzzle */ + class Puzzle : public Numbers + { + Numbers givens; + bool marks[SDIM]; + bool numbers[SDIM][DIM+1]; + unsigned int count[SDIM]; + + public: + + /** Constructor */ + Puzzle(unsigned int givens_count = 0, bool symmetric = true); + + /** Reset the puzzle. */ + virtual void reset(); + + /** Set the number into this cell. */ + virtual void set(Pos pos, unsigned int number); + + /** Generate a new puzzle. */ + void generate(unsigned int givens_count, bool symmetric = true); + + /** Set givens from contents of sudoku if marked in given_marks. */ + void set_givens(const Numbers& sudoku, const bool given_marks[SDIM]); + + /** Remove all givens. */ + void clear_givens(); + + /** No cells set? */ + bool untouched() const; + + /** Is the number in this cell given? */ + bool given(Pos pos) const; + + /** Is there an error on this position? */ + bool error(Pos pos) const; + + /** Is the number in this cell ambiguous? */ + bool ambiguous(Pos pos) const; + + /** All cells set and no errors? */ + bool solved() const; + + /** Is this cell marked? */ + bool marked(Pos pos) const; + + /** Toggle the mark for this cell. */ + void toggle_mark(Pos pos); + + /** Get the next free cell with minimal possible numbers. */ + Pos next_free(Pos pos = Pos::last()) const; + + /** Get the next possible number for this cell. */ + unsigned int next_number(Pos pos); + + /** Get the count of possible numbers for this cell. */ + unsigned int numbers_count(Pos pos); + +private: + + /** Compute all possible numbers for this cell. */ + void compute_numbers(Pos pos); + + /** Is the number in this cell a possible number? */ + bool correct(Pos pos) const; + }; + +} // namespace Sudoku + +#endif // VDR_SUDOKU_PUZZLE_H diff --git a/setup.cpp b/setup.cpp new file mode 100644 index 0000000..eb1ad80 --- /dev/null +++ b/setup.cpp @@ -0,0 +1,80 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: setup.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#include "setup.h" +#include "i18n.h" +#include <strings.h> + +using namespace SudokuPlugin; + + +//--- class SudokuPlugin::SetupData -------------------------------------------- + +/** Constructor + * + * Initialize the parameters of the plugin with standard values. + */ +SetupData::SetupData() +{ + givens_count = 36; + symmetric = 1; + mark_errors = 1; + mark_ambiguous = 1; + transparency = 50; +} + +/** Parse the parameters of the plugin. + * + * This method is called for each parameter the plugin has previously + * stored in the global setup data. + */ +bool SetupData::parse(const char* name, const char* value) +{ + if (!strcasecmp(name, "GivensCount")) + givens_count = atoi(value); + else if (!strcasecmp(name, "Symmetric")) + symmetric = atoi(value); + else if (!strcasecmp(name, "MarkErrors")) + mark_errors = atoi(value); + else if (!strcasecmp(name, "MarkAmbiguous")) + mark_ambiguous = atoi(value); + else if (!strcasecmp(name, "Transparency")) + transparency = atoi(value); + else + return false; + return true; +} + + +//--- class SudokuPlugin::SetupPage -------------------------------------------- + +/** Constructor */ +SetupPage::SetupPage(SetupData& setup) : + setup(setup), data(setup) +{ + Add(new cMenuEditIntItem(tr("Givens count"), &data.givens_count, 26, 81)); + Add(new cMenuEditBoolItem(tr("Symmetric givens"), &data.symmetric)); + Add(new cMenuEditBoolItem(tr("Mark errors"), &data.mark_errors)); + Add(new cMenuEditBoolItem(tr("Mark ambiguous numbers"), + &data.mark_ambiguous)); + Add(new cMenuEditIntItem(tr("Transparency (%)"), &data.transparency, 0, 100)); +} + +/** Store the parameters of the plugin. + * + * The parameters of the plugin are stored into the global setup data file. + */ +void SetupPage::Store() +{ + setup = data; + SetupStore("GivensCount", setup.givens_count); + SetupStore("Symmetric", setup.symmetric); + SetupStore("MarkErrors", setup.mark_errors); + SetupStore("MarkAmbiguous", setup.mark_ambiguous); + SetupStore("Transparency", setup.transparency); +} @@ -0,0 +1,60 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: setup.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_SETUP_H +#define VDR_SUDOKU_SETUP_H + +#include "sudoku.h" +#include <vdr/menuitems.h> + + +namespace SudokuPlugin +{ + + //--- class SudokuPlugin::SetupData ------------------------------------------ + + /** Setup parameters of the plugin */ + class SetupData + { + public: + int givens_count; + int symmetric; + int mark_errors; + int mark_ambiguous; + int transparency; + + /** Constructor */ + SetupData(); + + /** Parse the parameters of the plugin. */ + bool parse(const char* name, const char* value); + }; + + + //--- class SudokuPlugin::SetupPage ------------------------------------------ + + /** Setup menu page to adjust the parameters of the plugin */ + class SetupPage : public cMenuSetupPage + { + SetupData& setup; + SetupData data; + + public: + + /** Constructor */ + SetupPage(SetupData& setup); + + protected: + + /** Store the parameters of the plugin. */ + virtual void Store(); + }; + +} // namespace SudokuPlugin + +#endif // VDR_SUDOKU_SETUP_H diff --git a/solver.cpp b/solver.cpp new file mode 100644 index 0000000..9355d33 --- /dev/null +++ b/solver.cpp @@ -0,0 +1,95 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: solver.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#define USE_RAND +#include "solver.h" +#include "backtrack.h" +#include "puzzle.h" +#include <assert.h> + +using namespace Sudoku; +using namespace BackTrack; + + +//--- class Sudoku::Solver ----------------------------------------------------- + +/** Constructor */ +Solver::Solver(Puzzle& puzzle, bool random_init, unsigned int max_iter) : + Algorithm(*this, max_iter), puzzle(puzzle), random_init(random_init) +{ + free_count = 0; + for (Pos p = Pos::first(); p <= Pos::last(); p = p.next()) + if (!puzzle.given(p)) + ++free_count; +} + +/** Set the element to the first sibling. */ +void Solver::set_first_at(unsigned int level) +{ + assert(level < free_count); + const Pos p = puzzle.next_free(); + assert (p <= Pos::last()); + + free_list[level] = p; + puzzle.set(p, 0); + + if (level == 0) + random = random_init; + + unsigned int i, count = puzzle.numbers_count(p); + if (count != 0) + { + puzzle.set(p, puzzle.next_number(p)); + + if (random) + for (count = rand(count), i = 0; i < count; ++i) + puzzle.set(p, puzzle.next_number(p)); + } + else + puzzle.set(p, 1); +} + +/** Set the element to the next sibling. */ +void Solver::set_next_at(unsigned int level) +{ + assert(level < free_count); + Pos p = free_list[level]; + unsigned int n = puzzle.next_number(p); + if (n != 0) + puzzle.set(p, n); +} + +/** Reset the element. */ +void Solver::reset_at(unsigned int level) +{ + assert(level < free_count); + puzzle.set(free_list[level], 0); + random = false; +} + +/** Check if the element is set to the last sibling. */ +bool Solver::is_last_at(unsigned int level) const +{ + assert(level < free_count); + return puzzle.next_number(free_list[level]) == 0; +} + +/** Check if the element is valid (following elements ignored). */ +bool Solver::is_valid_at(int level) const +{ + assert(level < int(free_count)); + if (level < 0) + return puzzle.solved(); + return !puzzle.error(free_list[level]); +} + +/** Check if the level is the last possible level. */ +bool Solver::is_last_level(int level) const +{ + return level >= int(free_count) - 1; +} diff --git a/solver.h b/solver.h new file mode 100644 index 0000000..65cf87e --- /dev/null +++ b/solver.h @@ -0,0 +1,104 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: solver.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_SOLVER_H +#define VDR_SUDOKU_SOLVER_H + +#include "sudoku.h" +#include "backtrack.h" +#include "puzzle.h" + + +namespace Sudoku +{ + + //--- class Sudoku::Solver --------------------------------------------------- + + /** Implementation of a backtracking algorithm to solve Sudoku puzzles + * + * The algorithm tries to set numbers in all free cells of the puzzle + * sticking to the rules of Sudoku puzzles. + * + * There are three ways to use this class: + * + * 1. Solve a Sudoku puzzle with some numbers given: + * + * \code + * Puzzle puzzle(36); // Generate a random puzzle with 36 givens. + * Solver solver(puzzle); + * solver.find_next_solution(); + * if (solver.solution_is_valid()) + * { + * // Do something with the puzzle. + * ... + * } + * solver.find_next_solution(); + * bool more_than_one_solution = solver.solution_is_valid(); + * \endcode + * + * 2. Search a random Sudoku solution: + * + * \code + * Puzzle puzzle; // Generate an empty puzzle without givens. + * Solver solver(puzzle, true); + * solver.find_next_solution(); + * if (solver.solution_is_valid()) + * { + * // Do something with the puzzle. + * ... + * } + * \endcode + * + * 3. Search all Sudoku solutions: + * + * \code + * Puzzle puzzle; // Generate an empty puzzle without givens. + * Solver solver(puzzle); + * solver.find_next_solution(true); + * while (solver.solution_is_valid()) + * { + * // Do something with the puzzle. + * ... + * solver.find_next_solution(true); + * } + * \endcode + */ + class Solver : public BackTrack::Algorithm, public BackTrack::Solution + { + Puzzle& puzzle; + Pos free_list[SDIM]; + unsigned int free_count; + bool random_init, random; + + public: + + /** Constructor */ + Solver(Puzzle& puzzle, bool random_init = false, unsigned int max_iter = 0); + + /** Set the element to the first sibling. */ + virtual void set_first_at(unsigned int level); + + /** Set the element to the next sibling. */ + virtual void set_next_at(unsigned int level); + + /** Reset the element. */ + virtual void reset_at(unsigned int level); + + /** Check if the element is set to the last sibling. */ + virtual bool is_last_at(unsigned int level) const; + + /** Check if the element is valid (following elements ignored). */ + virtual bool is_valid_at(int level) const; + + /** Check if the level is the last possible level. */ + virtual bool is_last_level(int level) const; + }; + +} // namespace Sudoku + +#endif // VDR_SUDOKU_SOLVER_H diff --git a/sudoku.cpp b/sudoku.cpp new file mode 100644 index 0000000..1c9ab86 --- /dev/null +++ b/sudoku.cpp @@ -0,0 +1,114 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: sudoku.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#include "sudoku.h" +#include "puzzle.h" +#include "menu.h" +#include "setup.h" +#include "i18n.h" +#include <vdr/plugin.h> + + +/** 'Sudoku' is a VDR plugin to generate and solve Number Place puzzles. */ +namespace SudokuPlugin +{ + + /** Version number of the plugin */ + static const char* VERSION = "0.1.0"; + + /** Short description of the plugin's purpose */ + static const char* DESCRIPTION = + "Sudoku - generate and solve Number Place puzzles"; + + /** Name of the entry in VDR's main menu */ + static const char* MAINMENUENTRY = "Sudoku"; + + + //--- class SudokuPlugin::Plugin --------------------------------------------- + + /** Main class of the VDR plugin 'Sudoku' */ + class Plugin : public cPlugin + { + SetupData setup; + Sudoku::Puzzle puzzle; + Sudoku::Pos curr; + + public: + + /** Version number of the plugin */ + virtual const char* Version() { return VERSION; } + + /** Localized short description of the plugin's purpose */ + virtual const char* Description() { return tr(DESCRIPTION); } + + /** Perform the startup actions of the plugin. */ + virtual bool Start(); + + /** Localized name of the entry in VDR's main menu */ + virtual const char* MainMenuEntry() { return tr(MAINMENUENTRY); } + + /** OSD object that shows the plugin's main menu */ + virtual cOsdObject* MainMenuAction(); + + /** Setup menu page to adjust the parameters of the plugin */ + virtual cMenuSetupPage* SetupMenu(); + + /** Parse the parameters of the plugin. */ + virtual bool SetupParse(const char* name, const char* value); + }; + +} // namespace SudokuPlugin + + +using namespace SudokuPlugin; + + +//--- class SudokuPlugin::Plugin ----------------------------------------------- + +/** Perform the startup actions of the plugin. + * + * This method is called once at VDR's startup. + */ +bool Plugin::Start() +{ + RegisterI18n(Phrases); + puzzle.generate(setup.givens_count, setup.symmetric); + curr = curr.center(); + return true; +} + +/** OSD object that shows the plugin's main menu + * + * This method is called every time the plugin's main menu entry is selected. + */ +cOsdObject* Plugin::MainMenuAction() +{ + return new Menu(setup, puzzle, curr); +} + +/** Setup menu page to adjust the parameters of the plugin + * + * This method is called every time the plugin's setup menu entry is selected. + */ +cMenuSetupPage* Plugin::SetupMenu() +{ + return new SetupPage(setup); +} + +/** Parse the parameters of the plugin. + * + * This method is called for each parameter the plugin has previously + * stored in the global setup data. + */ +bool Plugin::SetupParse(const char* name, const char* value) +{ + return setup.parse(name, value); +} + +/** "Magic" hook that allows VDR to load the plugin into its memory */ +VDRPLUGINCREATOR(Plugin); // Don't touch this! diff --git a/sudoku.h b/sudoku.h new file mode 100644 index 0000000..a7309d2 --- /dev/null +++ b/sudoku.h @@ -0,0 +1,24 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: sudoku.h 11 2005-10-28 01:00:01Z tom $ + */ + +#ifndef VDR_SUDOKU_H +#define VDR_SUDOKU_H + + +#ifdef USE_RAND +#include <stdlib.h> +#include <time.h> +/** Random number 0 .. max-1 */ +static unsigned int rand(unsigned int max) +{ + static unsigned int seed = time(NULL); + return (unsigned int)((double)max * rand_r(&seed) / (RAND_MAX + 1.0)); +} +#endif // USE_RAND + +#endif // VDR_SUDOKU_H diff --git a/tools/Makefile b/tools/Makefile new file mode 100644 index 0000000..cd02cfb --- /dev/null +++ b/tools/Makefile @@ -0,0 +1,41 @@ +# +# Sudoku: A plugin for the Video Disk Recorder +# +# See the README file for copyright information and how to reach the author. +# +# $Id: Makefile 11 2005-10-28 01:00:01Z tom $ + +# Define STATIC_LINK=1 to force static linking +#STATIC_LINK = 1 + +# Define WITH_TEST=1 to include test procedures +#WITH_TEST = 1 + +PROGRAM = sudoku_generator + +SRCS = ../puzzle.cpp ../generator.cpp ../solver.cpp ../backtrack.cpp + +VERSION = $(shell grep 'static const char\* VERSION *=' ../sudoku.cpp | \ + awk '{ print $$6 }' | sed -e 's/[";]//g') + +CXX ?= g++ +CXXFLAGS ?= -O2 -Wall -Woverloaded-virtual +DEFINES += -D_GNU_SOURCE -DVERSION=\"$(VERSION)\" + +ifdef STATIC_LINK + CXXFLAGS += -static +endif + +ifdef WITH_TEST + DEFINES += -DWITH_TEST +endif + +### Targets: + +all: $(PROGRAM) + +$(PROGRAM): $(PROGRAM).cpp $(SRCS) $(SRCS:%.cpp=%.h) + $(CXX) $(CXXFLAGS) $(DEFINES) $(INCLUDES) -o $@ $(PROGRAM).cpp $(SRCS) + +clean: + @-rm -f $(PROGRAM) core* *~ diff --git a/tools/sudoku_generator.cpp b/tools/sudoku_generator.cpp new file mode 100644 index 0000000..a0d3e4b --- /dev/null +++ b/tools/sudoku_generator.cpp @@ -0,0 +1,378 @@ +/* + * Sudoku: A plugin for the Video Disk Recorder + * + * See the README file for copyright information and how to reach the author. + * + * $Id: sudoku_generator.cpp 11 2005-10-28 01:00:01Z tom $ + */ + +#include "../puzzle.h" +#include "../solver.h" +#include "../generator.h" +#include <stdio.h> +#include <string.h> +#include <getopt.h> + +using namespace Sudoku; + + +void print_copyleft(unsigned int givens_count) +{ + printf("Sudoku with %d givens generated by sudoku_generator %s\n" + " Copyright (C) 2005, Thomas Günther <tom@toms-cafe.de>\n" + " This puzzle can be used without any limitations.\n" + "\n", givens_count, VERSION); +} + +void print_usage() +{ + printf("Usage: sudoku_generator [-n|--non-sym] [-d|--dump] [<givens_count>]\n" + " Generate a Sudoku puzzle.\n" + " givens_count Number of givens (<= 81). Default is 36.\n" + " Less than 26 givens takes very long.\n" + " -n, --non-sym Generate a non-symmetric Sudoku puzzle.\n" + " -d, --dump Dump the generated Sudoku (don't print).\n" + "\n" + " sudoku_generator -s|--solve <sudoku_dump>\n" + " Solve a Sudoku puzzle.\n" + " sudoku_dump String with 81 * 1-9 or _ (+ ignored).\n" + "\n" + " sudoku_generator -p|--print <sudoku_dump>\n" + " Print a Sudoku puzzle.\n" + " sudoku_dump String with 81 * 1-9 or _ (+ ignored).\n" + "\n" +#ifdef WITH_TEST + " sudoku_generator -t|--test\n" + " Perform some test procedures.\n" + "\n" +#endif + " sudoku_generator -h|--help\n" + " Print this help.\n" + "\n"); +} + +void print_sudoku(const Numbers* sudoku_list[], unsigned int count, + unsigned int givens_count = 0) +{ + printf("\n"); + for (unsigned int row = 0; row <= DIM; ++row) + { + if (row % RDIM == 0) + { + for (unsigned int idx = 0; idx < count; ++idx) + { + printf(" "); + for (unsigned int col = 0; col < DIM; ++col) + { + if (col % RDIM == 0) + printf(" "); + printf("- "); + } + printf(" "); + } + printf("\n"); + } + if (row < DIM) + { + for (unsigned int idx = 0; idx < count; ++idx) + { + printf(" "); + for (unsigned int col = 0; col < DIM; ++col) + { + if (col % RDIM == 0) + printf("| "); + unsigned int n = sudoku_list[idx]->get(Pos(col, row)); + if (n) + printf("%d ", n); + else + printf(" "); + } + printf("| "); + } + printf("\n"); + } + } + printf("\n"); + if (givens_count != 0) + print_copyleft(givens_count); +} + +void print_sudoku(const Numbers& sudoku, unsigned int givens_count = 0) +{ + const Numbers* sudoku_list[] = { &sudoku }; + print_sudoku(sudoku_list, 1, givens_count); +} + +void print_sudoku(const Numbers& sudoku1, const Numbers& sudoku2, + unsigned int givens_count = 0) +{ + const Numbers* sudoku_list[] = { &sudoku1, &sudoku2 }; + print_sudoku(sudoku_list, 2, givens_count); +} + +void dump_sudoku(const Numbers& sudoku) +{ + for (unsigned int row = 0; row < DIM; ++row) + { + for (unsigned int col = 0; col < DIM; ++col) + { + unsigned int n = sudoku.get(Pos(col, row)); + if (n) + printf("%d", n); + else + printf("_"); + } + if (row < DIM-1) + printf("+"); + } + printf("\n"); +} + +int generate_puzzle(unsigned int givens_count, bool non_sym, bool dump) +{ + Puzzle puzzle; + Generator generator(puzzle, givens_count, !non_sym); + generator.find_next_solution(); + if (!generator.solution_is_valid()) + return 1; + if (dump) + dump_sudoku(puzzle); + else + print_sudoku(puzzle, givens_count); + return 0; +} + +Numbers dump_to_numbers(const char *dump) +{ + Numbers numbers; + for (Pos p = Pos::first(); *dump && p <= Pos::last(); ++dump) + { + if (*dump != '+') + { + if (*dump > '0' && *dump - '0' <= DIM) + numbers.set(p, *dump - '0'); + p = p.next(); + } + } + return numbers; +} + +int solve_puzzle(const char *dump) +{ + Numbers numbers(dump_to_numbers(dump)); + bool given_marks[SDIM]; + for (Pos p = Pos::first(); p <= Pos::last(); p = p.next()) + given_marks[p] = numbers.get(p) != 0; + Puzzle puzzle; + puzzle.set_givens(numbers, given_marks); + Solver solver(puzzle); + solver.find_next_solution(); + if (!solver.solution_is_valid()) + return 1; + print_sudoku(numbers, puzzle); + solver.find_next_solution(); + if (!solver.solution_is_valid()) + return 0; + printf("Error: Sudoku has more than one solution!\n"); + return 1; +} + +int print_puzzle(const char *dump) +{ + Numbers numbers(dump_to_numbers(dump)); + print_sudoku(numbers); + return 0; +} + +#ifdef WITH_TEST +bool test_search_first() +{ + bool correct = true; + printf("Search the first Sudoku!\n"); + Puzzle puzzle; + Solver solver(puzzle); + solver.find_next_solution(); + if (solver.solution_is_valid()) + print_sudoku(puzzle); + else + correct = false, printf("Error: Sudoku is invalid!\n"); + printf("Search the second Sudoku!\n"); + solver.find_next_solution(); + if (solver.solution_is_valid()) + print_sudoku(puzzle); + else + correct = false, printf("Error: Sudoku is invalid!\n"); + return correct; +} + +bool test_search_random() +{ + bool correct = true; + printf("Search a random Sudoku!\n"); + Puzzle puzzle; + Solver solver(puzzle, true); + solver.find_next_solution(); + if (solver.solution_is_valid()) + print_sudoku(puzzle); + else + correct = false, printf("Error: Sudoku is invalid!\n"); + printf("Search another random Sudoku!\n"); + solver.reset(); + solver.find_next_solution(); + if (solver.solution_is_valid()) + print_sudoku(puzzle); + else + correct = false, printf("Error: Sudoku is invalid!\n"); + return correct; +} + +bool test_generate_symmetric() +{ + bool correct = true; + printf("Generate a random Sudoku with 36 symmetric givens!\n"); + Puzzle puzzle; + Generator generator(puzzle, 36); + generator.find_next_solution(); + if (generator.solution_is_valid()) + print_sudoku(puzzle); + else + correct = false, printf("Error: Sudoku is invalid!\n"); + printf("Solve the generated Sudoku!\n"); + Solver solver(puzzle); + solver.find_next_solution(); + if (solver.solution_is_valid()) + print_sudoku(puzzle); + else + correct = false, printf("Error: Sudoku is invalid!\n"); + solver.find_next_solution(); + if (solver.solution_is_valid()) + correct = false, print_sudoku(puzzle), + printf("Error: Sudoku has more than one solution!\n"); + else + printf("Sudoku has only one solution!\n"); + printf("\n"); + return correct; +} + +bool test_generate_non_symmetric() +{ + bool correct = true; + printf("Generate a random Sudoku with 26 non-symmetric givens!\n"); + Puzzle puzzle; + Generator generator(puzzle, 26, false); + generator.find_next_solution(); + if (generator.solution_is_valid()) + print_sudoku(puzzle); + else + correct = false, printf("Error: Sudoku is invalid!\n"); + printf("Solve the generated Sudoku!\n"); + Solver solver(puzzle); + solver.find_next_solution(); + if (solver.solution_is_valid()) + print_sudoku(puzzle); + else + correct = false, printf("Error: Sudoku is invalid!\n"); + solver.find_next_solution(); + if (solver.solution_is_valid()) + correct = false, print_sudoku(puzzle), + printf("Error: Sudoku has more than one solution!\n"); + else + printf("Sudoku has only one solution!\n"); + printf("\n"); + return correct; +} + +int test_sudoku() +{ + unsigned int count = 0; + unsigned int error = 0; + ++count; + if (!test_search_first()) + ++error; + ++count; + if (!test_search_random()) + ++error; + ++count; + if (!test_generate_symmetric()) + ++error; + ++count; + if (!test_generate_non_symmetric()) + ++error; + if (error > 0) + printf("%d errors in %d tests\n", error, count); + else + printf("All %d tests correct\n", count); + if (error > 0) + return 1; + return 0; +} +#endif // WITH_TEST + +int main(int argc, char* argv[]) +{ + static const struct option long_options[] = + { + { "non-sym", no_argument, NULL, 'n' }, + { "dump", no_argument, NULL, 'd' }, + { "solve", no_argument, NULL, 's' }, + { "print", no_argument, NULL, 'p' }, +#ifdef WITH_TEST + { "test", no_argument, NULL, 't' }, +#endif + { "help", no_argument, NULL, 'h' }, + { NULL } + }; +#ifdef WITH_TEST + static const char* options = "ndspth"; +#else + static const char* options = "ndsph"; +#endif + bool non_sym = false; + bool dump = false; + bool solve = false; + bool print = false; + bool test = false; + bool help = false; + bool error = false; + int c; + while ((c = getopt_long(argc, argv, options, long_options, NULL)) != -1) + { + switch (c) + { + case 'n': non_sym = true; break; + case 'd': dump = true; break; + case 's': solve = true; break; + case 'p': print = true; break; +#ifdef WITH_TEST + case 't': test = true; break; +#endif + case 'h': help = true; break; + default: error = true; + } + } + int arg_count = argc - optind; + + unsigned int givens_count = 36; + if ((arg_count == 0 || + (arg_count == 1 && sscanf(argv[optind], "%u", &givens_count) == 1)) && + givens_count > 0 && givens_count <= SDIM && + !solve && !print && !test && !help && !error) + return generate_puzzle(givens_count, non_sym, dump); + + if (solve && arg_count == 1 && strlen(argv[optind]) >= SDIM && + !non_sym && !dump && !test && !help && !error) + return solve_puzzle(argv[optind]); + + if (print && arg_count == 1 && strlen(argv[optind]) >= SDIM && + !non_sym && !dump && !test && !help && !error) + return print_puzzle(argv[optind]); + +#ifdef WITH_TEST + if (test && arg_count == 0 && + !non_sym && !dump && !print && !help && !error) + return test_sudoku(); +#endif + + print_usage(); + return 2; +} |