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.

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.

Diffraction grating couplers milled in Si3N4 rib waveguides with a focused ion beam

Focused ion beam milling is a processing technology which allows flexible direct writing of nanometer scale features efficiently substituting electron beam lithography. No mask need results in ability for patterns writing even on fragile micromechanical devices. In this work we studied the abilities of the tool for fabrication of diffraction grating couplers in silicon nitride waveguides. The gratings were fabricated on a chip with extra fragile cantilevers of sub micron thickness. Optical characterization of the couplers was done using excitation of the waveguides in visible range by focused Gaussian beams of different waist sizes. Influence of Ga+ implantation on the device performance was studied.

1.48 and 1.84 µm thulium emissions in monoclinic KGd(WO4)2 single crystals

By exciting at 788 nm, we have characterized the near infrared emissions of trivalent thulium ions in monoclinic KGd(WO4)2 single crystals at 1.48 and 1.84 mm as a function of dopant concentration from 0.1% to 10% and temperature from 10 K to room temperature. We used the reciprocity method to calculate the maximum emission cross-section of 3.0310220 cm2 at 1.838 mm for the polarization parallel to the Nm principal optical direction. These results agrees well with the experimental data. Experimental decay times of the 3H4!3F4 and 3F4!3H6 transitions have been measured as a function of thulium concentration.

Readout schemes for low noise single-photon avalanche diodes fabricated in conventional HV-CMOS technologies

Three different pixels based on single-photon avalanche diodes for triggered applications, such as fluorescence lifetime measurements and high energy physics experiments, are presented. Each pixel consists of a 20µm x 100µm (width x length) single photon avalanche diode and a monolithically integrated readout circuit. The sensors are operated in the gated mode of acquisition to reduce the probability to detect noise counts interferring with real radiation events. Each pixel includes a different readout circuit that allows to use low reverse bias overvoltages. Experimental results demonstrate that the three pixels present a similar behaviour. The pixels get rid of afterpulses and present a reduced dark count probability by applying the gated operation. Noise figures are further improved by using low reverse bias overvoltages. The detectors exhibit an input dynamic range of 13.35 bits with short gated"on" periods of 10ns and a reverse bias overvoltage of 0.5V. The three pixels have been fabricated in a standard HV-CMOS process.

Progress in single junction microcrystalline silicon solar cells deposited by Hot-Wire CVD

Hot-Wire Chemical Vapor Deposition has led to microcrystalline silicon solar cell efficiencies similar to those obtained with Plasma Enhanced CVD. The light-induced degradation behavior of microcrystalline silicon solar cells critically depends on the properties of their active layer. In the regime close to the transition to amorphous growth (around 60% of amorphous volume fraction), cells incorporating an intrinsic layer with slightly higher crystalline fraction and [220] preferential orientation are stable after more than 7000 h of AM1.5 light soaking. On the contrary, solar cells whose intrinsic layer has a slightly lower crystalline fraction and random or [111] preferential orientation exhibit clear light-induced degradation effects. A revision of the efficiencies of Hot-Wire deposited microcrystalline silicon solar cells is presented and the potential efficiency of this technology is also evaluated.

Tailoring the surface density of silicon nanocrystals embedded in SiOx single layers

In this article, we explore the possibility of modifying the silicon nanocrystal areal density in SiOx single layers, while keeping constant their size. For this purpose, a set of SiOx monolayers with controlled thickness between two thick SiO2 layers has been fabricated, for four different compositions (x=1, 1.25, 1.5, or 1.75). The structural properties of the SiO x single layers have been analyzed by transmission electron microscopy (TEM) in planar view geometry. Energy-filtered TEM images revealed an almost constant Si-cluster size and a slight increase in the cluster areal density as the silicon content increases in the layers, while high resolution TEM images show that the size of the Si crystalline precipitates largely decreases as the SiO x stoichiometry approaches that of SiO2. The crystalline fraction was evaluated by combining the results from both techniques, finding a crystallinity reduction from 75% to 40%, for x = 1 and 1.75, respectively. Complementary photoluminescence measurements corroborate the precipitation of Si-nanocrystals with excellent emission properties for layers with the largest amount of excess silicon. The integrated emission from the nanoaggregates perfectly scales with their crystalline state, with no detectable emission for crystalline fractions below 40%. The combination of the structural and luminescence observations suggests that small Si precipitates are submitted to a higher compressive local stress applied by the SiO2 matrix that could inhibit the phase separation and, in turn, promotes the creation of nonradiative paths.

Spatial mapping of exciton lifetimes in single ZnO nanowires

We investigate the spatial dependence of the exciton lifetimes in single ZnO nanowires. We have found that the free exciton and bound exciton lifetimes exhibit a maximum at the center of nanowires, while they decrease by 30% towards the tips. This dependence is explained by considering the cavity-like properties of the nanowires in combination with the Purcell effect. We show that the lifetime of the bound-excitons scales with the localization energy to the power of 3/2, which validates the model of Rashba and Gurgenishvili at the nanoscale.

Effect of pressure on La2(WO4)3 with a modulated scheelite-type structure

We have studied the effect of pressure on the structural and vibrational properties of lanthanum tritungstate La2(WO4)3. This compound crystallizes under ambient conditions in the modulated scheelite-type structure known as the α phase. We have performed x-ray diffraction and Raman scattering measurements up to a pressure of 20 GPa, as well as ab initio calculations within the framework of the density functional theory. Up to 5 GPa, the three methods provide a similar picture of the evolution under pressure of α-La2(WO4)3. At 5 GPa, we begin to observe some structural changes, and above 6 GPa we find that the x-ray patterns cannot be indexed as a single phase. However, we find that a mixture of two phases with C2/c symmetry accounts for all diffraction peaks. Our ab initio study confirms the existence of several C2/c structures, which are very close in energy in this compression range. According to our measurements, a state with medium-range order appears at pressures above 9 and 11 GPa, from x-ray diffraction and Raman experiments, respectively. Based upon our theoretical calculations we propose several high-pressure candidates with high cationic coordinations at these pressures. The compound evolves into a partially amorphous phase at pressures above 20 GPa.

Improving Pitch Tracking Performance in Hard Noise Conditions by a Preprocessing Based on Mathematical Morphology

In this paper we show how a nonlinear preprocessing of speech signal -with high noise- based on morphological filters improves the performance of robust algorithms for pitch tracking (RAPT). This result happens for a very simple morphological filter. More sophisticated ones could even improve such results. Mathematical morphology is widely used in image processing and has a great amount of applications. Almost all its formulations derived in the two-dimensional framework are easily reformulated to be adapted to one-dimensional context

Regression-based techniques for statistical decision making in single-case designs

The present study evaluates the performance of four methods for estimating regression coefficients used to make statistical decisions regarding intervention effectiveness in single-case designs. Ordinary least squares estimation is compared to two correction techniques dealing with general trend and one eliminating autocorrelation whenever it is present. Type I error rates and statistical power are studied for experimental conditions defined by the presence or absence of treatment effect (change in level or in slope), general trend, and serial dependence. The results show that empirical Type I error rates do not approximate the nominal ones in presence of autocorrelation or general trend when ordinary and generalized least squares are applied. The techniques controlling trend show lower false alarm rates, but prove to be insufficiently sensitive to existing treatment effects. Consequently, the use of the statistical significance of the regression coefficients for detecting treatment effects is not recommended for short data series.

Particle shape and orientation in laser diffraction and static image analysis size distribution analysis of micrometer sized rectangular particles

Laser diffraction (LD) and static image analysis (SIA) of rectangular particles [United States Pharmacopeia, USP30-NF25, General Chapter <776>, Optical Miroscopy.] have been systematically studied. To rule out sample dispersion and particle orientation as the root cause of differences in size distribution profiles, we immobilize powder samples on a glass plate by means of a dry disperser. For a defined region of the glass plate, we measure the diffraction pattern as induced by the dispersed particles, and the 2D dimensions of the individual particles using LD and optical microscopy, respectively. We demonstrate a correlation between LD and SIA, with the scattering intensity of the individual particles as the dominant factor. In theory, the scattering intensity is related to the square of the projected area of both spherical and rectangular particles. In traditional LD the size distribution profile is dominated by the maximum projected area of the particles (A). The diffraction diameters of a rectangular particle with length L and breadth B as measured by the LD instrument approximately correspond to spheres of diameter ØL and ØB respectively. Differences in the scattering intensity between spherical and rectangular particles suggest that the contribution made to the overall LD volume probability distribution by each rectangular particle is proportional to A2/L and A2/B. Accordingly, for rectangular particles the scattering intensity weighted diffraction diameter (SIWDD) explains an overestimation of their shortest dimension and an underestimation of their longest dimension. This study analyzes various samples of particles whose length ranges from approximately 10 to 1000 μm. The correlation we demonstrate between LD and SIA can be used to improve validation of LD methods based on SIA data for a variety of pharmaceutical powders all with a different rectangular particle size and shape.