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.

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.

Wnt-3a and Wnt-3 differently stimulate proliferation and neurogenesis of spinal neural precursors and promote neurite outgrowth by canonical signaling

Wnt factors regulate neural stem cell development and neuronal connectivity. Here we investigated whether Wnt-3a and Wnt-3, expressed in the developing spinal cord, regulate proliferation and the neuronal differentiation of spinal cord neural precursors (SCNP). Wnt-3a promoted a sustained increase of SCNP proliferation, whereas Wnt-3 enhanced SCNP proliferation transiently and increased neurogenesis through β-catenin signaling. Consistent with this, Wnt-3a and Wnt-3 differently regulate the expression of Cyclin-dependent kinase inhibitors. Furthermore, Wnt-3a and Wnt-3 stimulated neurite outgrowth in SCNP-derived neurons through ß-catenin and TCF4-dependent transcription. GSK-3ß inhibitors mimicked Wnt signaling and promoted neurite outgrowth in established cultures. We conclude that Wnt-3a and Wnt-3 signal through the canonical Wnt/β-catenin pathway to regulate different aspects of SCNP development. These findings may be of therapeutic interest for the treatment of neurodegenerative diseases and nerve injury.

Signalling by neurotrophins and hepatocyte growth factor regulates axon morphogenesis by differential β-catenin phosphorylation

Tyrosine phosphorylation of ß-catenin, a component of adhesion complexes and the Wnt pathway, affects cell adhesion, migration and gene transcription. By reducing ßcatenin availability using shRNA-mediated gene silencing or expression of intracellular N-cadherin, we show that ß-catenin is required for axon growth downstream of Brain Derived Neurotrophic Factor (BDNF) and Hepatocyte Growth Factor (HGF) signalling. We demonstrate that receptor tyrosine kinases (RTK) Trk and Met interact with and phosphorylate ß-catenin. Neurotrophins (NT) stimulation of Trk receptors results in phosphorylation of ß-catenin at residue Y654 and increased axon growth and branching. Conversely, pharmacological inhibition of Trk or a Y654F mutant blocks these effects. ß-catenin phospho(P)-Y654 colocalizes with the cytoskeleton at growth cones. However, HGF that also increases axon growth and branching, induces ß-catenin phosphorylation at Y142 and a nuclear localization. Interestingly, dominant negative ΔN-TCF4 abolishes the effects of HGF in axon growth and branching, but not of NT. We conclude that NT and HGF signalling differentially phosphorylate ß-catenin, targeting ß-catenin to distinct compartments to regulate axon morphogenesis by TCF4-transcription-dependent and independent mechanisms. These results place ß-catenin downstream of growth factor/RTK signalling in axon differentiation.

Chemokines induce axon outgrowth downstream of Hepatocyte Growth Factor and TCF/β-catenin signaling

Axon morphogenesis is a complex process regulated by a variety of secreted molecules, including morphogens and growth factors, resulting in the establishment of the neuronal circuitry. Our previous work demonstrated that growth factors [Neurotrophins (NT) and Hepatocyte Growth Factor (HGF)] signal through β-catenin during axon morphogenesis. HGF signaling promotes axon outgrowth and branching by inducing β-catenin phosphorylation at Y142 and transcriptional regulation of T-Cell Factor (TCF) target genes. Here, we asked which genes are regulated by HGF signaling during axon morphogenesis. An array screening indicated that HGF signaling elevates the expression of chemokines of the CC and CXC families. In line with this, CCL7, CCL20, and CXCL2 significantly increase axon outgrowth in hippocampal neurons. Experiments using blocking antibodies and chemokine receptor antagonists demonstrate that chemokines act downstream of HGF signaling during axon morphogenesis. In addition, qPCR data demonstrates that CXCL2 and CCL5 expression is stimulated by HGF through Met/b-catenin/TCF pathway. These results identify CC family members and CXCL2 chemokines as novel regulators of axon morphogenesis downstream of HGF signaling.

Task-induced deactivation from rest extends beyond the default mode brain network

Activity decreases, or deactivations, of midline and parietal cortical brain regions are routinely observed in human functional neuroimaging studies that compare periods of task-based cognitive performance with passive states, such as rest. It is now widely held that such task-induced deactivations index a highly organized"default-mode network" (DMN): a large-scale brain system whose discovery has had broad implications in the study of human brain function and behavior. In this work, we show that common task-induced deactivations from rest also occur outside of the DMN as a function of increased task demand. Fifty healthy adult subjects performed two distinct functional magnetic resonance imaging tasks that were designed to reliably map deactivations from a resting baseline. As primary findings, increases in task demand consistently modulated the regional anatomy of DMN deactivation. At high levels of task demand, robust deactivation was observed in non-DMN regions, most notably, the posterior insular cortex. Deactivation of this region was directly implicated in a performance-based analysis of experienced task difficulty. Together, these findings suggest that task-induced deactivations from rest are not limited to the DMN and extend to brain regions typically associated with integrative sensory and interoceptive processes.

Effects of Different Salinities on Juvenile Growth of Gammarus aequicauda (Malacostraca: Amphipoda)

Gammarus aequicauda is a euryhaline amphipod that is a common inhabitant of brackish environments of theMediterranean Sea. In the Ebro delta, the population density of G. aequicauda is highly variable throughout the year. The main objective of this study is to investigate the effect of salinity on the growth of G. aequicauda juveniles. G. aequicauda embryos and juveniles can survive and grow in the laboratory between 2 psu and 40 psu salinity, depending on the previous acclimation period for the reproductive individuals. Adults acclimated at 34 psu produced embryos and juveniles that survived and developed at salinities between 9 psu and 40 psu; adults acclimated at 9 psu produced embryos and juveniles that could develop in oligohaline conditions. The lower growth rate values were 10.9 μmd−1 and 13.5 μmd−1 at 40 psu and 2 psu, respectively, with the higher values of 18.0 μmd−1 and 18.5 μmd−1 at 19 and 34 psu, respectively.

Salivary cotinine concentrations in daily smokers in Barcelona, Spain: a cross-sectional study

Background: Characterizing and comparing the determinant of cotinine concentrations in different populations should facilitate a better understanding of smoking patterns and addiction. This study describes and characterizes determinants of salivary cotinine concentration in a sample of Spanish adult daily smoker men and women. Methods: A cross-sectional study was carried out between March 2004 and December 2005 in a representative sample of 1245 people from the general population of Barcelona, Spain. A standard questionnaire was used to gather information on active tobacco smoking and passive exposure, and a saliva specimen was obtained to determine salivary cotinine concentration. Two hundred and eleven adult smokers (>16 years old) with complete data were included in the analysis. Determinants of cotinine concentrations were assessed using linear regression models. Results: Salivary cotinine concentration was associated with the reported number of cigarettes smoked in the previous 24 hours (R2 = 0.339; p < 0.05). The inclusion of a quadratic component for number of cigarettes smoked in the regression analyses resulted in an improvement of the fit (R2 = 0.386; p < 0.05). Cotinine concentration differed significantly by sex, with men having higher levels. Conclusion: This study shows that salivary cotinine concentration is significantly associated with the number of cigarettes smoked and sex, but not with other smoking-related variables.

Juventud, políticas públicas y crisis en España: ¿Triángulo mágico o triángulo de las Bermudas?

In times of crisis, the youth policies are experiencing enormous cutbacks and transformations to the point that we are wondering whether they really exist as public policies with their own entity. The situation in which many young people find themselves in Spain leads them to wonder where the traditional protection networks are: The family, the NGO’s or the Welfare State, when they are really needed. Our objective in this article is to show and discuss the situation of the youth policies in Spain in the present context of social austerity and drastic cutbacks. We carry out this analysis from the parameters of the magical triangle that unite policies, research and social work with young people

The membrane-permeable calmodulin inhibitors (W-7/W-13) bind to membranes changing the electrostatic surface potential. Dual effect of W-13 on EGFR activation

Membrane-permeable calmodulin inhibitors, such as the napthalenesulfonamide derivatives W-7/W-13, trifluoperazine, and calmidazolium, are used widely to investigate the role of calcium/calmodulin (Ca2+/CaM) in living cells. If two chemically different inhibitors (e.g. W-7 and trifluoperazine) produce similar effects, investigators often assume the effects are due to CaM inhibition. Zeta potential measurements, however, show that these amphipathic weak bases bind to phospholipid vesicles at the same concentrations as they inhibit Ca 2 /CaM; this suggests that they also bind to the inner leaflet of the plasma membrane, reducing its negative electrostatic surface potential. This change will cause electrostatically bound clusters of basic residues on peripheral (e.g. Src and K-Ras4B) and integral (e.g. epidermal growth factor receptor (EGFR)) proteins to translocate from the membrane to the cytoplasm. We measured inhibitor-mediated translocation of a simple basic peptide corresponding to the calmodulin-binding juxtamembrane region of the EGFR on model membranes; W-7/W-13 causes translocation of this peptide from membrane to solution, suggesting that caution must be exercised when interpreting the results obtained with these inhibitors in living cells. We present evidence that they exert dual effects on autophosphorylation of EGFR;W-13 inhibits epidermal growth factordependent EGFR autophosphorylation under different experimental conditions, but in the absence of epidermal growth factor, W-13 stimulates autophosphorylation of the receptor in four different cell types. Our interpretation is that the former effect is due toW-13inhibition of Ca 2 /CaM, but thelatter results could be due to binding of W-13 to the plasma membrane.