The Action Plugin and Action Addon Framework
The Sudoku Action Addon
The Plugin Sudoku allows to store, in an advanced way, a sudoku and to perform operations on it. Allows to enter in each cell the "correct" value and also values "not candidate" (ie, the values that the cell can not take). The Sudoku Action Addon provides a single atom #sudoku. It takes four inputs where former is the action name and the others are the options related to action:
The Atom Action #sudoku allows to enter numbers in the sudoku, to
print it on standard output or on a text file, to enter values for "not candidate"
and to print it on standard output with all the values that each cell can take.
The Action setDimension allows to specify the size of the grid; every time
this action is executed, if the specified size are different from the current one,
the grid is destroyed and then recreated; the parameters AO1 and AO2 specify respectively
the number of rows and the number columns.
The Action insertNumber allows to enter a value in a certain position of
the grid; the AO1 parameter indicates the row in which to insert the number, the
parameter AO2 indicates the column in which to insert the number, AO3 parameter
indicates the number to be inserted.
The Action print allows to print to standard output the sudoku; the parameters
are not used.
The Action writeToFile allows to print the sudoku file, the file is written
in "append" mode in order to analyze what were the steps that led to the
solution; AO1 parameter is used to specify the name of the file to write to, the
parameters AO2 and AO3 are not used.
The Action insertNumberNotCandidate allows to enter a value "not candidate"
in a certain position of the grid; the AO1 parameter indicates the row in which
to insert the number, the parameter AO2 indicates the column in which to insert
the number, AO3 parameter indicates the number to be inserted.
The Action printWithThePossibilities allows to print to standard output
the sudoku with all the values that each cell can take; the parameters are not
used.
The Sudoku Action Addon provides some External Atoms:
You can check it out its source here.
For other action addons return to the section Action Addons of The Action Plugin and Action Addon Framework.
Some experimental results
This addon allowed us to experiment with the incremental application of Sudoku inference rules as described in [1]. Large Sudoku tables cannot be solved by pure guess & check strategies, due to the huge underlying search space: on the other hand, ActHEX allows to iterate over partially complete tables, and to repeatedly apply a number of deterministic inference strategies depending on the current resolution progress. Our ActHEX-based iterative player allows to solve Sudoku tables as large as 81 X 81, which are far out of the performance reach of an ASP-based system using a pure guess & check strategy.
| ActHEX | NonDetdlv | NonDetg+c | |
|---|---|---|---|
| 16x16 SuperEasy | 8.14 | 1.99 | 2.03 |
| 16x16 VeryEasy | 11.85 | 10.75 | 1.64 |
| 16x16 Easy | 13.48 | 8.58 | 2.40 |
| 25x25 SuperEasy | 37.11 | 11.36 | 9.72 |
| 25x25 VeryEasy | 124.33 | 3070.48 (2/3) | 10.19 |
| 25x25 Easy (2) | 116.24 | TO | 75.15 |
| 36x36 SuperEasy | 154.92 | 62.24 | 38.01 |
| 36x36 VeryEasy | 678.04 | TO | 824.14 |
| 36x36 Easy | 806.35 | TO | 9342.62 |
| 49x49 SuperEasy | 625.01 | 75.20 | 247.83 |
| 49x49 VeryEasy | 2381.84 | 75.97 (1/3) | 138.93 (1/3) |
| 49x49 Easy | 3337.10 | TO | TO |
| 64x64 SuperEasy | 1421.13 | OOM | OOM |
| 81x81 SuperEasy | 31720.29 | OOM | OOM |
Legend: OOM = Out Of Memory, TO = Timed Out. All times are given in seconds. The timeout is 32000 seconds. Each line corresponds to an instance family of 3 instances (unless differently speficied). Times are the average over the instance family; whenever present, data in parentheses account for finished instances out of the total available in a given category.
The above table shows our experiments on a selected number of Sudoku Tables (Source), of increasing size, ranging from 16 X 16 (sub-blocks of size 4) to 81 X 81 (sub-blocks of size 9). The SuperEasy and the VeryEasy instances are executed with the deterministic strategy Det[0], the Easy instances with the deterministic strategy Det[1].
Det[0] implements the so called hidden and naked single rules [2], known in the Sudoku literature as basic deterministic inference rules useful for completing Sudoku tables (download encoding).
Det[1] enriches hidden and naked single rules with interaction rules [2], another known family of Sudoku inference rules (download encoding).
The columns NonDetdlv and NonDet(g+c) show the performance of a single nondeterministic ASP encoding run respectively with DLV release 2012-12-17 and Gringo 3.0.5 coupled with Clasp 2.1.1 (64bit version for both systems). (DLV encoding, Gringo encoding).
Both Det[0] and Det[1] work on a iterative basis by maintaining a partially completed Sudoku table. At each iteration, candidate values can be excluded from the current table, depending on whether some deterministic inference rule triggers or not. The iterative process terminates when the Sudoku table is complete, or no further inference can be performed.
The purpose of the experiment was to assess whether and to what extent applying known deterministic inferences could help in reducing an expectedly large search space. Outcomes show that the implementation of deterministic inferences comes at a performance overhead which is worth its price when Sudoku tables reach a fairly large size.
[1] Calimeri, F., Ianni, G., Perri, S., Zangari, J.: The eternal battle between determinism and nondeterminism: preliminary studies in the sudoku domain. Accepted for publication at the 20th RCRA International Workshop on "Experimental Evaluation of Algorithms for solving problems with combinatorial explosion".
[2] D. Berthier. The Hidden Logic of Sudoku (Second Edition). December 2007. ISBN 9781847534729
Last edited 2013-04-23
General
dlvhex source code @ github.com
Description-Of-A-Project
Popular Plugins
Action Plugin
DecisionDiagrams Plugin
Description Logics Plugin
Description Logics Lite Plugin
MELD: Belief Merging Plugin
Nested HEX Plugin
MCSIE Plugin
String Plugin
dlvhex-semweb Project
Documentation
User Guide
README
doxygen
Writing Plugins in C++
Writing Plugins in Python