{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:22Z","timestamp":1740109282033,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,10,5]],"date-time":"2016-10-05T00:00:00Z","timestamp":1475625600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0223-y","type":"journal-article","created":{"date-parts":[[2016,10,5]],"date-time":"2016-10-05T14:42:28Z","timestamp":1475678548000},"page":"742-762","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Exact Sampling Algorithms for Latin Squares and Sudoku Matrices via Probabilistic Divide-and-Conquer"],"prefix":"10.1007","volume":"79","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0093-4674","authenticated-orcid":false,"given":"Stephen","family":"DeSalvo","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,5]]},"reference":[{"key":"223_CR1","unstructured":"Arratia, R., DeSalvo, S.: Poisson and independent process approximation for random combinatorial structures with a given number of components, and near-universal behavior for low rank assemblies. arXiv preprint arXiv:1606.04642 (2016)"},{"issue":"3","key":"223_CR2","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1017\/S0963548315000358","volume":"25","author":"R Arratia","year":"2016","unstructured":"Arratia, R., DeSalvo, S.: Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example. Comb. Probab. Comput. 25(3), 324\u2013351 (2016)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"223_CR3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(84)90075-1","volume":"8","author":"CJ Colbourn","year":"1984","unstructured":"Colbourn, C.J.: The complexity of completing partial latin squares. Discrete Appl. Math. 8(1), 25\u201330 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"8","key":"223_CR4","doi-asserted-by":"crossref","first-page":"2457","DOI":"10.1016\/j.laa.2008.12.023","volume":"430","author":"G Dahl","year":"2009","unstructured":"Dahl, G.: Permutation matrices related to sudoku. Linear Algebra Appl. 430(8), 2457\u20132463 (2009)","journal-title":"Linear Algebra Appl."},{"key":"223_CR5","unstructured":"DeSalvo, S.: Probabilistic divide-and-conquer: deterministic second half. arXiv preprint arXiv:1411.6698 (2014)"},{"key":"223_CR6","doi-asserted-by":"crossref","unstructured":"DeSalvo, S.: Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method. arXiv preprint arXiv:1608.07922 (2016)","DOI":"10.1016\/j.endm.2017.05.006"},{"key":"223_CR7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0927-0507(06)13004-2","volume":"13","author":"L Devroye","year":"2006","unstructured":"Devroye, L.: Nonuniform random variate generation. Handb. Oper. Res Manag. Sci. 13, 83\u2013121 (2006)","journal-title":"Handb. Oper. Res Manag. Sci."},{"issue":"1","key":"223_CR8","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1214\/aos\/1030563990","volume":"26","author":"P Diaconis","year":"1998","unstructured":"Diaconis, P., Sturmfels, B., et al.: Algebraic algorithms for sampling from conditional distributions. Ann. Stat. 26(1), 363\u2013397 (1998)","journal-title":"Ann. Stat."},{"issue":"4\u20135","key":"223_CR9","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1017\/S0963548304006315","volume":"13","author":"P Duchon","year":"2004","unstructured":"Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G.: Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput. 13(4\u20135), 577\u2013625 (2004)","journal-title":"Combin. Probab. Comput."},{"issue":"1","key":"223_CR10","first-page":"15","volume":"39","author":"B Felgenhauer","year":"2006","unstructured":"Felgenhauer, B., Jarvis, F.: Mathematics of sudoku i. Math. Spectr. 39(1), 15\u201322 (2006)","journal-title":"Math. Spectr."},{"key":"223_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)"},{"issue":"12","key":"223_CR12","doi-asserted-by":"crossref","first-page":"3697","DOI":"10.1016\/j.jspi.2011.06.001","volume":"141","author":"R Fontana","year":"2011","unstructured":"Fontana, R.: Fractions of permutations. an application to sudoku. J. Stat. Plan. Inference 141(12), 3697\u20133704 (2011)","journal-title":"J. Stat. Plan. Inference"},{"key":"223_CR13","doi-asserted-by":"crossref","unstructured":"Fontana, R.: Random latin squares and sudoku designs generation. arXiv preprint arXiv:1305.3697 (2013)","DOI":"10.1214\/14-EJS913"},{"key":"223_CR14","doi-asserted-by":"crossref","unstructured":"Fontana, R., Rapallo, F., Rogantin, M.P.: Markov bases for sudoku grids. In: Advanced Statistical Methods for the Analysis of Large Data-Sets, pages 305\u2013315. Springer, (2012)","DOI":"10.1007\/978-3-642-21037-2_28"},{"issue":"1","key":"223_CR15","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0095-8956(90)90128-M","volume":"48","author":"CD Godsil","year":"1990","unstructured":"Godsil, C.D., McKay, B.D.: Asymptotic enumeration of latin rectangles. J. Comb. Theory Ser. B 48(1), 19\u201344 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"223_CR16","unstructured":"Huber, M.L.: Perfect Simulation. Chapman & Hall\/CRC Monographs on Statistics & Applied Probability. Taylor & Francis, (2015)"},{"issue":"6","key":"223_CR17","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1002\/(SICI)1520-6610(1996)4:6<405::AID-JCD3>3.0.CO;2-J","volume":"4","author":"MT Jacobson","year":"1996","unstructured":"Jacobson, M.T., Matthews, P.: Generating uniformly distributed random latin squares. J. Comb. Des. 4(6), 405\u2013437 (1996)","journal-title":"J. Comb. Des."},{"key":"223_CR18","unstructured":"Jarvis, F..: Website of Frazer Jarvis. http:\/\/www.afjarvis.staff.shef.ac.uk\/sudoku\/bertram.html (2005)"},{"issue":"4","key":"223_CR19","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/1008731.1008738","volume":"51","author":"M Jerrum","year":"2004","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4), 671\u2013697 (2004). (electronic)","journal-title":"J. ACM"},{"key":"223_CR20","volume-title":"Markov Chains and Mixing Times","author":"DA Levin","year":"2009","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Soc, Providence (2009)"},{"key":"223_CR21","doi-asserted-by":"crossref","unstructured":"Newton, P.K., DeSalvo, S.A.: The shannon entropy of sudoku matrices. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, page rspa20090522. The Royal Society (2010)","DOI":"10.1098\/rspa.2009.0522"},{"key":"223_CR22","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0097-3165(75)90013-8","volume":"18","author":"A Nijenhuis","year":"1975","unstructured":"Nijenhuis, A., Wilf, H.S.: A method and two algorithms on the theory of partitions. J. Comb. Theory Ser. A 18, 219\u2013222 (1975)","journal-title":"J. Comb. Theory Ser. A"},{"key":"223_CR23","unstructured":"Nijenhuis, A., Wilf, H.S.: Combinatorial algorithms. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, second edition, 1978. For computers and calculators, Computer Science and Applied Mathematics (1978)"},{"key":"223_CR24","doi-asserted-by":"crossref","unstructured":"Random Struct. Algor. Exact sampling with coupled markov chains and applications to statistical mechanics. 9(1\u20132), 223\u2013252 (1996)","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<223::AID-RSA14>3.0.CO;2-O"},{"key":"223_CR25","unstructured":"Ridder, A.: Counting the number of sudoku\u2019s by importance sampling simulation (2013)"},{"issue":"2","key":"223_CR26","first-page":"54","volume":"39","author":"E Russell","year":"2006","unstructured":"Russell, E., Jarvis, F.: Mathematics of sudoku II. Math. Spectr. 39(2), 54\u201358 (2006)","journal-title":"Math. Spectr."},{"key":"223_CR27","unstructured":"Sloane, N.J.A.: Online Encyclopedia of Integer Sequences. Published electronically at http:\/\/www.oeis.org\/"},{"issue":"1","key":"223_CR28","doi-asserted-by":"crossref","first-page":"Article 1 46","DOI":"10.37236\/418","volume":"17","author":"DS Stones","year":"2010","unstructured":"Stones, D.S.: The many formulae for the number of Latin rectangles. Electron. J. Comb. 17(1), Article 1 46 (2010)","journal-title":"Electron. J. Comb."},{"key":"223_CR29","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511987045","volume-title":"A Course in Combinatorics","author":"JH Lint van","year":"2001","unstructured":"van Lint, J.H., Wilson, R.M.: A Course in Combinatorics, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"issue":"36\u201338","key":"223_CR30","first-page":"1","volume":"12","author":"J Neumann Von","year":"1951","unstructured":"Von Neumann, J.: Various techniques used in connection with random digits. Appl. Math Ser. 12(36\u201338), 1 (1951)","journal-title":"Appl. Math Ser."},{"issue":"18","key":"223_CR31","doi-asserted-by":"crossref","first-page":"3072","DOI":"10.1016\/j.dam.2013.06.007","volume":"161","author":"K Yordzhev","year":"2013","unstructured":"Yordzhev, K.: On the number of disjoint pairs of s-permutation matrices. Discrete Appl. Math. 161(18), 3072\u20133079 (2013)","journal-title":"Discrete Appl. Math."},{"key":"223_CR32","unstructured":"Yordzhev, K.: Random permutations, random sudoku matrices and randomized algorithms. arXiv preprint arXiv:1312.0192 , (2013)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0223-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0223-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0223-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,9]],"date-time":"2022-07-09T20:02:03Z","timestamp":1657396923000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0223-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,5]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["223"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0223-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,10,5]]}}}