Sudoku Documentation

Introduction:

This Sudoku game was started as a personal project to bring me back on track with web development after spending months traveling and not using a computer all this time. I thought I forgot most, but it seems getting back to business took less time than I thought, and was also fun process.

I wanted to build a Sudoku game in pure JS, after playing lots of Sudoku on my iPhone. At the beginning the game was simple, I managed to create a board with random numbers which followed the rules of the game:

1. No number can repeat itself in the same 3x3 square
2. No number can repeat itself on the same 9 cells column or row.
3. Every empty cell should have a "mirror" empty cell (for example cells [0,7] & [8,1] OR [3,3] & [5,5]) ps. when Cells and 3x3 Cox index starts from '0' ,left to right, top to bottom.
4. Each game should have one and only solution to be considered a valid Sudoku game.

Technologies:

• HTML5
• Javascript (partially based on latest ES.5)
• Spiced with some CSS3 (selectors, transitions, media queries, etc.)
• web-workers
• localStorage
• woff pre-formatted font

Browser support:

• IE9+ (without the web-workers support)
• FF4+
• Chrome

Program flow:

1. HTML table markup is generated for the board
2. there are many pre-generated games for each difficulty level. A random one is picked from the default 'easy' grade, from the 'board.games' object. This is done because it takes time (~400ms) to generate a valid Sudoku game, so for sake of user experience the program first loads a pre-made game.
3. Meanwhile, the program creates (spawns) 6 new games on 6 different CPU threads via web-workers and runs all necessary calculations to make sure they are valid games. there are a couple of good reasons to use web-workers in this situation:
   1. The workers run on different threads, which makes sure the browser doesn't "hang up" when intense JS calculations are done, and the UX is kept smooth.
   2. In some rare cases the where calculations becomes too intense for a specific game, it can crush the browser, so by utilizing the web-workers, this situation will no longer happen
   3. Performance. creating many boards at the same time and sort them by difficultly while the person is actually interacting with the program in the background is pretty neat :)
4. Every time a user choose to play a new game, the program picks one of the games that was generated when the program first loaded, so the user will have a unique board never played before. every board the program generates is unique for the user and probably universally unique by the laws of probability.
5. The program spawns up to 15 new unique games into the 'board.games' object for each level of difficulty, so the user will never have to wait for a game to be calculated and generated, because this already happened in the background.

Program options:

• Difficulty User can select between multiple difficuly levels:
  Very easy, Easy, Medium, Tough, Very touch, Extreme
• Save game to localStorage
• Load game load a previously saved from from the localStorage
• New game play a new game from the same difficulty level picked
• Restart game play the same game from a state before any move was first made
• Import user can input a string of numbers which represent a board. it's common among sudoku programs
• Export exports the current game as a string of numbers
• Share gives the user a link to the current played game
• All notes for every empty cell, show all possible numbers which could reside in it
• Notes toggle Notes mode. when user clicks a cell to pick a number, it will we shown as a "note". A mere possibility
• Clear notes clear all notes from all the cells

How a Sudoku game is generated:

1. For every spawned board there is an array which represent it, and which is being 'populated' with numbers according to the laws of sudoku, until all the board is full and complete.
2. After the board is made, the program starts to remove numbers from random cells and their "mirror" cells, and checks after each pair removal if there is a solution and it's a single one. this is the the process which takes the longest time in the creation process and it's pure math, which is done by the "Dancing Links" algorithm (written by professor Donald Knuth), and this was the initial reason I choose to use web-workers. This algorithm is very complex math which solves problems, and probably 99% of Sudoku programs in the world use this, in one implementation of the other.
3. Cells keep being removed. if more than 1 solution is found, or none, then the last cells that were removed are returned, and another position to be removed is picked randomly. this is done until a certain point that the program finds it hard to remove more.
4. Now is the trickiest part, which is the most important; grading the generated game. This was done after excessive research for weeks, and eventually learning a number of methods to solve sudoku games, from basic methods to more advanced ones, and building functions that mimic the that line of thinking and try to solve the game like a human would. The grading system is an excellent one, tested on many games and fine-tuned for more than 2 weeks, to make sure games are rated as honestly as possible. I have designed a sudoku Solver which can solves most games and if not, there are complex calculations to determine the grade anyhow. the grader was designed to be standalone so others could integrate it in their games as well, because I haven't found anything like this in Javascript on the Internet.
5. After the game has been given a grade, it is added to the array of already created games, sorted by its rating.

Program structure:

There are a couple of globals functions/objects:

• texts (stores all the texts rendered by the UI)
• options (logic for all the buttons/actions the user can interact with)
• utility (utility functions such as generating a random number, custom program alerts, and different Array transformations)
• board (the heart of the program, which creates sudoku games, and handles all the game logic)
• solver (Grades the board by trying to solve it with different human-logic approaches)
• analyzer (algorithms for different human-like solving methods)
• timer (a stopwatch method to time the user. can't can paused and continued by clicking the timer itself) in the first versions the timer automatically paused when user has switched the focus of the current window, but I have found ways to abuse this feature so it was canceled it.

Deeper explaining some of the main methods:

• board (object)

  First board.init() is called, which creates an empty table using .generateMainTable(). Then checks if there is a game that should be loaded from the window.location.search, and if not, load a random game from the pre-rendered games board.games object, and spawn in the background new 6 games, using board.spawnBoards(), which is a complicated process by itself, which involves the board.populate() function, which creates a complete Sudoku game by filling all the cells with random numbers and checking after each insertion if the game is valid or not using the board.checkNumber() function. then comes the cells removal part, which is explained more thoroughly in the "How a Sudoku game is made" section of this file. after a game was created, analyzed, and given a grade, the program binds the user events, like mouse click, and keyboard support. this is done by calling the board.bindUserEvents() in board.init(). (keyboard is supported when user hovers a cell with the mouse and then click a number in the keypad, or hit the delete key). After that, the board.selectBox().init() it called to initialize the box which pops up when user clicks a cell that can be changed. Then, the options.bind_buttons() is called to initialize all buttons like "new", "restart", "save" etc.. The most important object, which is the actual array that represents the game is "board.arr". after it is totally ready, it is manifested inside the table element itself using the board.load() function, and a copy of the game is saved in board.arr_original. After everything was initialized, the program injects the table element (board.mainBoard) to the DOM.

• solver

  Utilize the analyzer object and determine after every move made how much points to give the game, up to the final calculated grade. After each analyzer pass, the solver determine how to continue. if singles were found (numbers that can only occur in a specific cell) then pass all the solving methods once more from start.

• analyzer

  Currently support 5 solving methods, from easy to more advanced:

  • possibilities (object) Keys: box and cell number, Values: array of all position's possibilities
  • evaluatePosib() check all possibilities for every cell, and if found a single one for a cell, then use it.
  • singleInBox() find all possibilities for every 3x3 box and send result to the hiddenSingles() function
  • singleInRowCol() same as above just for rows and columns
  • hiddenSingles() finds numbers which are unique in a certain set of arrays. ex. [1,2,3],[1,2,4],[3,2] then '4' is unique
  • findNakedPairs() for a set of arrays, find pair of numbers which follow this pattern: [1,3,6,9],[1,5],[3,6,9],[1,5],[1,6] so in array 2 and 4 there are the same numbers: 1 & 5, which are only in those 2 arrays, therefore can be removed from the other arrays → [3,6,9],[1,5],[3,6,9],[1,5],[6]
  • findNakedTriples() for a set of arrays, find if 3 arrays share the same and ONLY numbers [1,5,7,8],[5,6,9],[5,6,9],[2,5],[1,5,8,9],[5,6,9],[2,7]
    ⇓
    [1,7,8],[5,6,9],[5,6,9],[2],[1,8],[5,6,9],[2,7]
  • findHiddenPairsTriples() for a set of arrays, find if a 2 or 3 arrays share the same numbers, even if there are other numbers inside them which are not shared among them. ex. for a hidden pair: [4,9],[4,6,9],[6,9],[3,9],[3,7],[3,7,8],[1,3,5,8],[1,3,5,7,8]
    ⇓
    [4,9],[4,6,9],[6,9],[3,9],[3,7],[3,7,8],[1,5],[1,5]