============================ Distributed Sudoku Generator

=========== Team: FUXIA

Andrei Grigorean
Sonia Stan
Mihnea Giurgea

=============== Install and Run

Install

1) Install picloud http://docs.picloud.com/quickstart.html
    sudo pip install cloud

2) Configure picloud 
    picloud setup
        email: s.kipy3@gmail.com
        password: hackathon

Run

$ ./generate difficulty_level [--simulate] - difficulty_level can be [1,2,3,4,5] - without the simulate flag, the program will not simulate picloud on the localhost and will try to connect to the site.

Running Tests

• test files are in the test/ folder and can be run using nosetests:

  $ nosetests test/ -v

• there are several input boards we use for testing, each with a different difficulty level. All can be found in the subfolder: fixtures/

==================== Project Description:

The Distributed Sudoku Generator Project generates Sudoku games having different levels of difficulty. Traditionaly the Sudoku games are divided into five categories, according to human perceived difficulty. We have decided to keep the same five levels in our implementation of the generator:

• extremely easy
• easy
• medium
• difficult
• evil

"Generating Sudoku puzzles is easy. Generating evil Sudoku puzzles is... EVIL."

Four factors affecting the difficulty level are taken into consideration in this metrics respectively as follows:

• the total amount of given cells,
• the lower bound of given cells in each row and column,
• applicable techniques by human logic thinking, and
• enumerating search times by computer.

======================= Project Implementation:

Solution's Building Blocks

There are three fundamental entities used in our implementation:

• Solver
  • input: an incomplete Sudoku board
  • output:
    • None: there is no solution for solving the board
    • solution: if there exists at least one posssible solution, it returns the completed Sudoku board
  • explanation:
    • simple baktracking using few optimizations. At each step: we compute all the possible values for each cell, select the cell with the fewest possibilites and then expand it.
• Las Vegas
  • output: a complete Sudoku board
  • explanation:
    • this is a well known algorithm for generating complete Sudoku boards.
    • we generate a few random cells and then use the Solver to find a possible solution.
• Digger:
  • input: a complete Sudoku board (generated by Las Vegas)
  • output: incomplete Sudoku board with a unique solution (the starting board for the human player)
  • explanation:
    • we try "digging out" cells such that the remaining board has only one solution.
    • the way we implement the "dig out" operations determines the difficulty of the game.

The Digging Strategy

Two variables are used that set restrictions on the digging operations: the first one tells us the maximum total number of digged cells and the second one tells us the maximum number of digged cells on a row or an a column.

The Digging Orders:

• Left to Right then Top to Bottom
• Wandering along “S”
• Jumping one cell
• Randomizing globally

Conclusions

Q: How far are we from the optimal solution for generating an evil puzzle?

A: It has been proven that it is necessary to have at least 17 completed cells in a starting board. Our algorithm can generate an evil puzzle with 22 completed cells! Of course, there are other algorithms with better results than ours, but their implementation requires a much greater effort than can be achieved in 24hours.