Generating highly balanced sudoku problems as hard problems

Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in [8, 44, 39, 9]. On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of m rows and n columns with m = n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables – variables with the same value in all the solutions of an instance– and hardness of GSP.

Automated monitoring of medical protocols: a secure and distributed architecture

The control of the right application of medical protocols is a key issue in hospital environments. For the automated monitoring of medical protocols, we need a domain-independent language for their representation and a fully, or semi, autonomous system that understands the protocols and supervises their application. In this paper we describe a specification language and a multi-agent system architecture for monitoring medical protocols. We model medical services in hospital environments as specialized domain agents and interpret a medical protocol as a negotiation process between agents. A medical service can be involved in multiple medical protocols, and so specialized domain agents are independent of negotiation processes and autonomous system agents perform monitoring tasks. We present the detailed architecture of the system agents and of an important domain agent, the database broker agent, that is responsible of obtaining relevant information about the clinical history of patients. We also describe how we tackle the problems of privacy, integrity and authentication during the process of exchanging information between agents.

The impact of balancing on problem hardness in a highly structured domain

Random problem distributions have played a key role in the study and design of algorithms for constraint satisfaction and Boolean satisfiability, as well as in ourunderstanding of problem hardness, beyond standard worst-case complexity. We consider random problem distributions from a highly structured problem domain that generalizes the Quasigroup Completion problem (QCP) and Quasigroup with Holes (QWH), a widely used domain that captures the structure underlying a range of real-world applications. Our problem domain is also a generalization of the well-known Sudoku puz- zle: we consider Sudoku instances of arbitrary order, with the additional generalization that the block regions can have rectangular shape, in addition to the standard square shape. We evaluate the computational hardness of Generalized Sudoku instances, for different parameter settings. Our experimental hardness results show that we can generate instances that are considerably harder than QCP/QWH instances of the same size. More interestingly, we show the impact of different balancing strategies on problem hardness. We also provide insights into backbone variables in Generalized Sudoku instances and how they correlate to problem hardness.

On balanced CSPs with high treewidth

Tractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose methods to increase their hardness by increasing the balance of both the constraint language and the constraint graph. The balance of a constraint is increased by maximizing the number of domain elements with the same number of occurrences. The balance of the graph is defined using the classical definition from graph the- ory. In this sense we present two graph models; a first graph model that increases the balance of a graph maximizing the number of vertices with the same degree, and a second one that additionally increases the girth of the graph, because a high girth implies a high treewidth, an important parameter for binary CSPs hardness. Our results show that our more balanced graph models and constraints result in harder instances when compared to typical random binary CSP instances, by several orders of magnitude. Also we detect, at least for sparse constraint graphs, a higher treewidth for our graph models.

Statistical modelling of CSP solving algorithms performance

The goal of this work is to try to create a statistical model, based only on easily computable parameters from the CSP problem to predict runtime behaviour of the solving algorithms, and let us choose the best algorithm to solve the problem. Although it seems that the obvious choice should be MAC, experimental results obtained so far show, that with big numbers of variables, other algorithms perfom much better, specially for hard problems in the transition phase.

Generating hard SAT/CSP instances using expander graphs

In this paper we provide a new method to generate hard k-SAT instances. We incrementally construct a high girth bipartite incidence graph of the k-SAT instance. Having high girth assures high expansion for the graph, and high expansion implies high resolution width. We have extended this approach to generate hard n-ary CSP instances and we have also adapted this idea to increase the expansion of the system of linear equations used to generate XORSAT instances, being able to produce harder satisfiable instances than former generators.

How hard is a commercial puzzle: the eternity II challenge

Recently, edge matching puzzles, an NP-complete problem, have received, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

Edge matching puzzles as hard SAT/CSP benchmarks

Recently, edge matching puzzles, an NP-complete problem, have rececived, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

Llave electrónica basada en patrones de movimiento

Sistema embebido capaz de almacenar y posteriormente reconocer patrones de movimiento realizados con él y avisar de la detección de un patrón reconocido a otro sistema mediante una conexión TCP/IP vía Wi-Fi.

Aplicación Catalunya Cultura

Aplicación para dispositivos móviles de la plataforma Android que permite buscar y consultar las ofertas y propuestas de carácter cultural (teatro, conciertos, fiestas tradicionales, etc.) que se realizan en todos los pueblos y ciudades de Cataluña.

Nuevos datos sobre los yacimientos wurmienses del litoral catalán

We present a new bed of cold Malacological fauna of the Wrm in the Catalan littoral, one af its species is dated for the first time iii the hlediterranean (Sipho curtus). We point out the predorninance of Gasteropoda as regards Bivalves in comparison with the other cold beds known.

Applications of optically active metallacycles: new useful materials for the determination of the enantiomeric excess of Lewis bases and as resolving agents for monodentate phosphines

Es descriu la síntesi de nous compostos ciclopal·ladats derivats d'imines i amines primàries, òpticament actius, així com les seves aplicacions per a la determinació de l'excés enantiomèric i per a la resolució de bases de Lewis. També es comenta la síntesi i resolució de noves fosfines P-quirals, així com la seva aplicació a processos de catàlisi asimètrica. A més, es descriu la preparació d'algunes fosfines secundàries quirals i s'estudia la seva estabilitat configuracional.

Progress in a-Si:H/c-Si heterojunction emitters obtained by Hot-Wire CVD at 200°C

In this work, we investigate heterojunction emitters deposited by Hot-Wire CVD on p-type crystalline silicon. The emitter structure consists of an n-doped film (20 nm) combined with a thin intrinsic hydrogenated amorphous silicon buffer layer (5 nm). The microstructure of these films has been studied by spectroscopic ellipsometry in the UV-visible range. These measurements reveal that the microstructure of the n-doped film is strongly influenced by the amorphous silicon buffer. The Quasy-Steady-State Photoconductance (QSS-PC) technique allows us to estimate implicit open-circuit voltages near 700 mV for heterojunction emitters on p-type (0.8 Ω·cm) FZ silicon wafers. Finally, 1 cm 2 heterojunction solar cells with 15.4% conversion efficiencies (total area) have been fabricated on flat p-type (14 Ω·cm) CZ silicon wafers with aluminum back-surface-field contact.

Repercusiones de la anorexia y la bulimia en la salud oral, prevención y tratamiento

El presente artículo trata de aportar una puesta al día de los problemas que presentan los pacientes afectados de anorexia y de bulimia nerviosa. Se expone la información que el odontólogo debe tener en cuenta respecto al conocimiento de la enfermedad, sus manifestaciones orales, los criterios diagnósticos y los enfoques preventivos y terapéuticos necesarios.

El volcanismo jurásico del sector valenciano de la Cordillera Ibérica. Distribución y trama estructural

En el sector valenciano de la Cordillera Iberica se desarrolla durante el Jurásico un volcanismo fundamentalmente piroclastico, con emisiones basalticas y traquibasalticas en el Pliensbachiense, Toarciense y Bajociense. La cartografia de los afloramientos permite definir dos alineaciones NW-SE (franja de Caudiel, alineación piroclástica de Alcublas), asi como un rea ms amplia de traza general NE-SW en las sierras de Javalambre y Camarena. Tal disposicion regional sugiere que las manifesiaciones volcaiiicas ocurren segun dosdirecciones principales de fracturacion tardihercinica~(NW-SEy NK-SW) y an posiblemente a favor de los puntos de interseccin de ambos sistemas estructurales. La direccin NW-SE ejerce el maximo control de la actividad volcnica jursica, al igual que previamente durante el Triasico superior (linea ofitica de Altura).