{"_id":"@brunoccc/sudokujs","_rev":"1-f370b7e0de5bb3ef64618694da971466","name":"@brunoccc/sudokujs","dist-tags":{"latest":"1.0.9"},"versions":{"1.0.9":{"name":"@brunoccc/sudokujs","version":"1.0.9","description":"Yet Another Sudoku Solver","main":"dist/index.js","types":"dist/index.d.ts","scripts":{"build":"tsc","test":"jest","prepublish":"npm run lint && npm run test && npm run build","lint":"tslint --project ."},"author":{"name":"Bruno Cicciarello"},"license":"MIT","devDependencies":{"@types/jest":"^24.0.22","@types/node":"^12.12.7","jest":"^24.9.0","ts-jest":"^24.1.0","tslint":"^5.20.1","typescript":"^3.7.2"},"repository":{"type":"git","url":"git+https://github.com/brunoccc/sudokujs.git"},"gitHead":"2bbf442f302d64e54d6966bcd8b352b4b562461a","bugs":{"url":"https://github.com/brunoccc/sudokujs/issues"},"homepage":"https://github.com/brunoccc/sudokujs#readme","_id":"@brunoccc/sudokujs@1.0.9","_nodeVersion":"12.3.0","_npmVersion":"6.9.0","dist":{"integrity":"sha512-0p0cS9mIZXFak44W3XjA8of/nfAohlCzQA2JSmLI4WhW/SaPZ9/OgtPD99mQ5Yik/drWa8Kcl1jnkMJ5/OmAjQ==","shasum":"1a929a0357889ba649e63c87396ed1cd3d69e724","tarball":"https://registry.npmjs.org/@brunoccc/sudokujs/-/sudokujs-1.0.9.tgz","fileCount":15,"unpackedSize":34742,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJdyYyWCRA9TVsSAnZWagAAlbYP/jOEby0uqpDCwEI/CWl5\nn0L2mVKTurGpSSr4hZ2Cgr56JpbIpl6h2pfEDjmVKc1UuiYglSVZewfaecwx\nZ/1FM+pLExbMQVj9MywgP4i7HnC1K3ILvClfqlsyfJdLj3Fix6BmLDTEA6VE\nDkPDYKhRDEE4UbVrDi+wi5TzoZKonCmu/d+paCUWI2T12Rg8nE3k6eTBi7Im\n5wwepY+h1dszbc9jTeYFY/BiayU8vctJjesYtIOxPhgkW1ztSz+57rjEtkgB\nOWUJA3mHUvWPMWYy1gzUKgYx+DbkOwjTZUPDolzlrMSkxaxWe8O+x/uxEcCL\nj1UPwBg2N6Sfyg/Iq6lCSIox7VIY/Aijned4zGjy5s/PgdK6AX9TAaHvsQPj\nAtWDZXxhkTVVn8mq9a8+53rTJmn5WAUICxTjgxP7VwRegou5krya3lKJHnUT\np3Or2hsx04DIJnfkn9U1HJBZqvVZmkaTp7hfVTERVDvX1NQPtAEvE9pgnNMe\nEA303+wx7qTp/+EGV4ZVS02URgejUqJjD1tD3hvDXa5hPyx+BeWwqNuR9vMd\niofVxqKGd4qECCriAYxhO7GcihhivA8ldTTaHo1QOx9IyOTP+M8WmX/gEP9D\nDQW2SXsAW1ZepO0Xl7+UELOHOvOEri/seKx5G4PVvngYB05sGWZ0nckh5l70\nQk+6\r\n=UBgG\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIHPDAIPo7odQfBQn+v0BVkNU0Ltm+p5vIlyOWm1pSU1UAiEAhL+e5NMfFrmVa6I3cnOBubxMNnd4fCf1Pn8oiN9AUIQ="}]},"maintainers":[{"name":"brunoccc","email":"bruno.cicciarello.uk@gmail.com"}],"_npmUser":{"name":"brunoccc","email":"bruno.cicciarello.uk@gmail.com"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/sudokujs_1.0.9_1573489813980_0.6545000930334861"},"_hasShrinkwrap":false}},"time":{"created":"2019-11-11T16:30:13.748Z","1.0.9":"2019-11-11T16:30:14.085Z","modified":"2022-04-04T20:49:22.066Z"},"maintainers":[{"name":"brunoccc","email":"bruno.cicciarello.uk@gmail.com"}],"description":"Yet Another Sudoku Solver","homepage":"https://github.com/brunoccc/sudokujs#readme","repository":{"type":"git","url":"git+https://github.com/brunoccc/sudokujs.git"},"author":{"name":"Bruno Cicciarello"},"bugs":{"url":"https://github.com/brunoccc/sudokujs/issues"},"license":"MIT","readme":"[![Build Status](https://travis-ci.com/brunoccc/sudokujs.svg?branch=master)](https://travis-ci.com/brunoccc/sudokujs)\n[![npm version](https://badge.fury.io/js/%40brunoccc%2Fsudokujs.svg)](https://badge.fury.io/js/%40brunoccc%2Fsudokujs)\n\n# YET ANOTHER SUDOKU SOLVER\n\nYes! How exciting? And this is a porting of my original Java code: https://github.com/brunoccc/sudoku\n\nWell, this is ~~probably~~ not the most efficient algorithm out there, but nevertheless I thought it could be interesting to share it as an open source project.\n\n### HOW DOES IT WORK\n\nIt's basically a simple recursive algorithm that:\n\n* Finds the empty cell with less possible alternatives\n* Writes the first possible value\n* Calls itself and sees if it solves the puzzle\n* If not, tries with the next possible value\n* If no more values, then it's an impossible task\n\nCompared to a normal _brute-force_ algorithm (which tries all the possible combinations until a solution has been found), this code performs better because of two reasons:\n\n* It tracks the possible alternatives for each cell (see below how)\n* It always selects the cell with less possible alternatives. Ideally, if the Sudoku has been designed for a human solver, this means that some cells will have a very limited number of possibilities, and the backtracking will not be used often\n\nI think that the tracking of which values are possible is quite interesting. Essentially it keeps a bitmask for each row, column, or block. Each bit set to 1 represents a possible value.  \nWhen we write a value in a cell, we set to 0 the corresponding bit for the bitmasks of that row, that column and that block (i.e. \"this value is no longer available\").  \nWhen we need to know the possible values for a cell, we simply combine the bitmasks of that row, column and block using a logical `AND`.\n\n![Alternative values and bitmasks](doc/brunoccc-sudoku-1.png?raw=true \"Bitmasks\")\n\n### HOW TO USE IT\n\nThe easiest way is to use the NPM package. Import the project into your `node_modules`:\n\n```\nnpm install --save @brunoccc/sudokujs\n```\n\nAnd simply use it:\n\n```\nconst { Sudoku } = require('@brunoccc/sudokujs');\n\nconst grid = [\n    [ 0, 0, 0,   0, 0, 0,    0, 0, 0 ],\n    [ 0, 0, 0,   0, 0, 3,    0, 8, 5 ],\n    [ 0, 0, 1,   0, 2, 0,    0, 0, 0 ],\n\n    [ 0, 0, 0,   5, 0, 7,    0, 0, 0 ],\n    [ 0, 0, 4,   0, 0, 0,    1, 0, 0 ],\n    [ 0, 9, 0,   0, 0, 0,    0, 0, 0 ],\n\n    [ 5, 0, 0,   0, 0, 0,    0, 7, 3 ],\n    [ 0, 0, 2,   0, 1, 0,    0, 0, 0 ],\n    [ 0, 0, 0,   0, 4, 0,    0, 0, 9 ],\n];\n\nconst sudoku = new Sudoku(grid);\n\nif (sudoku.solve()) {\n    console.log(\"Solved!\");\n    console.log(sudoku.toString());\n} else {\n    console.log(\"Impossible!\");\n}\n\n```\n\n\n\n\n","readmeFilename":"README.md"}