Here in DC, we recently had an unexpected snow day. By the word unexpected, I don’t mean that the snow wasn’t forecast – it was definitely forecast. It just never came. However due to the forecast I decided to avoid traffic just in case the predictions were correct. So while staying at home, I began thinking about some things that I’ve been wanting to update on the site and one thing that came up was an update to my Sudoku program. Previously, it contained about 10000 sample puzzles of varying difficulty. However, I told myself that I would return to the idea of generating my own Sudoku puzzles. I decided to tackle that task last week. The question was how would I do this. The Sudoku solver itself works through the dancing links algorithm which uses backtracking, so this was the approach that figured as most likely to get me a profitable result in generating new puzzles (I have also seen alternative approaches discussed where people start with an initial Sudoku and swap rows and columns to generate a new puzzle). The next question was how to actually implement this method. Here is an overview of the algorithm. I went from cell to cell (left to right, and top to bottom starting in the top left corner) attempting to place a random value in that cell. If that value can be a part of a valid Sudoku (meaning that there exists a solution with the current cells filled in as is), then we continue and fill in the next cell. Otherwise, we will try to place a different value in the current cell. This process is continued until all cells are filled in. The next step was to create a puzzle out of a filled in Sudoku. The tricky about this step is that if too many cells are removed then we wind up generating a puzzle that has multiple solutions. If too few cells are removed though, then the puzzle will be too easy to solve. Initially, I went repeatedly removed cells from the locations that were considered the most beneficial. This generally results in a puzzle with about 35-40 values remaining. To remove additional cells, I considered each of the remaining values and questioned whether hiding the cell would result in the puzzle having multiple solutions. If this was the case, then the cell value was not removed. Otherwise it was. As a result I now have a program that generates Sudoku puzzles that generally have around 25 hints. You should give it a try.
A friend described this puzzle to me and I enjoyed it so much that I just had to write a script so that I could play it more. The rules of this puzzle are simple. Cells can be in one of three states: An UNSHADED (white) cell means that you have not considered this cell yet. A DARK GREY SHADED cell means that the sum of the dark grey shaded cells in that row and column must equal the number in that cell. A LIGHT GREY SHADED cell means that the sum of the dark grey shaded cells in all the connected cells must equal the number in that cell. I Hope you Enjoy
Earlier this week, I was able to write a script that solves the popular Sudoku game. It was a fun experience because along the way I learned about a new way to implement the backtracking algorithm on exact cover problems. Say we have a set of items. They could be practically anything, but for the sake of understanding lets think of something specific, like school supplies. In particular lets say that school is starting back and you have a checklist of things you need to buy:
- a pencil
- a pen
- a notebook
- a spiral tablet
- a ruler
- a calculator
- a lamp
- a bookbag (or knapsack as I just learned people call them)
- and some paper
- a pencil, a notebook and a ruler
- a pen, a calculator and a bookbag
- a spiral tablet a lamp and some paper
- Each cell in the grid must receive a value
- a value can only appear once in each row
- a value can only appear once in each column
- a value can only appear once in each pre-defined 3 by 3 subgrid.
- If a cell (i, j) in the grid receives the value v, then we also need to note that row i, column j, and the pre-defined subgrid have also received its proper value.
- The first 81 (81 = 9*9) columns in the table will answer the question of does row i, column j have anything in that position. This will tell us whether the cell is empty or not, but will not tell us the value in the cell.
- The next 81 columns in the table will answer the question of does row i (of the Sudoku grid) have the value v in it yet.
- The next 81 columns in the table will answer the question of does column j (of the Sudoku grid) have the value v in it yet.
- The final 81 columns in the table will answer the question of does the (3×3) subgrid containing (i, j) have the value v in it yet.
- row[i*9+j] = 1 (this says that cell (i, j) is nonempty)
- row[81+i*9+v] = 1 (this says that cell row i has value v)
- row[81*2+j*9+v] = 1 (this says that column j has value v)
- row[81*3+(Math.floor(i/3)*3+Math.floor(j/3))*9+v] = 1 (this says that the 3 x 3 subgrid of (i, j) has value v)