HackerPapers

arXiv:1111.4083cs.AI

Unbiased Statistics of a CSP - A Controlled-Bias Generator

Denis Berthier

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

We show that estimating the complexity (mean and distribution) of the instances of a fixed size Constraint Satisfaction Problem (CSP) can be very hard. We deal with the main two aspects of the problem: defining a measure of complexity and generating random unbiased instances. For the first problem, we rely on a general framework and a measure of complexity we presented at CISSE08. For the generation problem, we restrict our analysis to the Sudoku example and we provide a solution that also explains why it is so difficult.

arXiv comments
Journal reference
Innovations in Computing Sciences and Software Engineering, (2010) 165-170
DOI
doi:10.1007/978-90-481-3660-5_28
Subjects
cs.AIArtificial Intelligence

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Oct 2022 to Oct 2022.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Will We Ever Run Out of Sudoku Puzzles? 1 comment

    • > A more reasonable question would be, how many partially completed sudoku grids are there which have a unique solution. We don't know the answer to that. The number of minimal Sudoku puzzles is estimated (with 0.065% relative error) to be 3.1055e+37 (or 2.5477e+25 for…

      53x15View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.