Where do Sudoku boards come from?

How do we generate random Sudoku boards?  There are several possible approaches.  A simple one is outlined below in pseudo-code:

Board create() {
  construct an empty board
  addToBoard(board, 0);
  return board;
}

void addToBoard(Board board, int cell) {
  if (level == 81) return;

  for each digit in permute(1,2,...,9) {
    place digit in cell
    if no constraint is violated
      if (addToBoard(board, cell + 1) return true;

  place 0 in cell
  return false;
}

What's happening here? First off, we've organized the board into an array of 81 cells; each cell contains a number from 1 to 9, or 0 to indicate a blank cell. We start placing numbers in the first cell and gradually make our way through the board. For each cell, we try each number in some random order, and try to fill in the rest of the board recursively for each choice. If we make an impossible choice, eventually we will be backed into a corner where no choice is possible for a particular cell. When that happens, addToBoard will empty the cell and return false.  Another value will be tried for the previous cell.  If we ever reach 81 levels of recursion, we‘re done.

The clause "no constraint is violated" is easy to implement. I generate a series of tables, one for each cell, that provide the indices of all cells that are in the same row, column, or box as the cell. There are 8 other cells in the same row, 8 in the same column, and 4 cells that are in the same box but not in the same row or columns, for a total of 20 cells related to a given cell.

Because we fill the cells in a particular order every time, there might be some bias. Some boards may be generated more frequently than others. One way to make things more random would be to generate a random permutation table, and to fill in the cells in the order given by the table.

Once we have a random grid, we need to decide on a set of clues. Here we need a way of solving a board from a set of clues. Actually, the routine that generates the boards is almost a solver in itself. If it is modified to skip over cells that already have been assigned a value, it will find a solution for any board where a solution is possible. This is the backtracking solution, aka the "total guess." A more interesting approach is to mimic human solution techniques, in order to only accept boards that have logical solutions. My solver implements the techniques that I have discussed previously, as well as some others that I will be writing about soon.

Given a solver, a set of clues is easy to generate. Create an empty board, and copy as many values from the solved board as you like. If you want a symmetrical board, copy cells in symmetrical pairs. If you want a board that spells out someone‘s initials, that‘s also possible. Now run the solver on the clue board. If it comes up with a solution, great. If not, you can either reveal more squares, reveal a different set of squares, or start again from square one by generating a new board.

Once you have a clued board, you‘ll want to be sure it has a unique solution. If your solver is based on logic, this will be guaranteed automatically. Every move that the solver makes is forced, so whatever solution it arrives it must be the only one possible. If you are using a backtracking solver, it can be modified to continue generating solutions after finding the first one. Keep a counter of how many solutions have been found; when the counter reaches 2, quit the solution process.

The folks at Sky TV neglected this step, leading to the world's largest Sudoku blunder !

An additional bit of finesse (which I haven't yet implemented) would be to ensure that all of the clues are necessary. Remove a clue (or a pair of clues if you are enforcing symmetry) and see if the gird still has a unique solution. If not, put the clue or pair of clues back and try removing another. Eventually you must reach a set of clues where no clue can be removed. This may not be the smallest set of clues that work for the board, but it will be minimal in the sense that no clue can be derived from the rest of the clues.

Some Sudoku generators skip the step of generating a board altogether. It's enough to place some random numbers in the board and see if it has a solution. For a backtracking solver, which can solve puzzles very quickly, the time wasted analyzing impossible sets of clues will be minor. For a human-style solver, it seems reasonable to exclude the possibility of self-contradictory clues by first generating a consistent underlying board. But, I haven't experimented with this possibility.

You can start with a full board, and remove values until you no longer have a unique solution, or you can start with an empty board and add values until you do. Which way you go is a matter of taste.

Comments

[Add]

My friend, you are an absolute hero.

Thank you for this entry!

Rgds,

Add

[Nexika]

Who Else Wants To Know The Secrets To Solving Sudoku Puzzles?"

Click here! NOW!

http://nexika.robhenry.hop.clickbank.net

[ugvtwx izlndvr]

teum tahedryn rqei tpufv rntks eoxdi sqrdnz

[The Sudoku Times Player]

Hey nice article. I would like you to know the new interactive online sudoku puzzle at http://www.thesudokutimes.com.

[Arun]

4 1 8
7 6 2 9 4
8 5 3 2 7 9
6 4 1
4 2 8 7
9 5 2
7 1 9 2 8 3
4 3 9 6 5
9 6 2

[Sudoku Tips]

usually use an online solver like at http://sudokusolver.info
but now maybe I don't have to

[Sudoku Fanatic]

Nice sudoku news website...

http://www.thesudokutimes.com