duplicacy problems while creating a sudoku puzzle

Question

I am trying to create my own normal 9x9 sudoku puzzle.

I divided the problem into two parts -

1. creating a fully filled sudoku, and
2. removing unnecessary numbers from the grid

Right now, I am stuck with the first part.

---

This is the algorithm I use in brief:

a) first of all I choose a number (say 1), generate a random cell position, and place it there if

• the cell is not already occupied, and
• if the row does not already have the number, and
• if the column does not already have the number, and
• if the 3x3 box does not already have the number

b) now I check for a situation in which in a row, or a column or a box, only one place is empty and I fill that

c) I check that if there is a number that in not present in a box but is present in the boxes in the same row and the same column (i am talking about 3x3 boxes here), the number's place is fixed and I fill it.

d) I repeat the above steps until every number appears nine times on the grid.

---

The problem I am facing is that, more than often I am getting an intermediate situation like this:

 0  1  0 | 0  0  3 | 0[4/2]0 
 0 [2] 0 | 0 [4] 1 | 3  0  0 
 3  0 [4]|[2] 0  0 | 0  0  1 
---------+---------+---------
 2  0  3 | 0  5  4 | 0  1  0 
 0  0  1 | 3  0  2 |[4] 0  0 
 0  4  0 | 0  1  0 |[2] 3  0 
---------+---------+---------
 1  0  2 | 0  3  0 | 0  0 [4] 
 4  3  0 | 1  0  0 | 0  0 [2] 
 5  0  0 | 4  2  0 | 1  0  3

See the place with [4/2] written? that is the place of 2 as well as 4 because of the boxes marked [].

What can I do to avoid getting in this situation (because this situation is a deadlock - I cannot move further)

Answer 1

If you've reached a contradictory state where a cell if both 2 and 4 some of your other 2s and 4s must be placed wrongly. You need to rollback and try some different solutions.

Sounds like you might have an algorithm problem? Some good stuff here.

Answer 2

There's another way to generate sudoku puzzles: Start with a known good grid - any one will do - then randomly 'shuffle' it by applying operations that don't destroy the invariants. Valid operations include:

• Swapping rows within a block
• Swapping columns within a block
• Swapping entire rows of blocks (eg, first 3, middle 3, last 3 rows)
• Swapping entire columns of blocks
• Swapping all instances of one number with another
• Reflecting the board
• Rotating the board

With these operations, you can generate a very large range of possible boards. You need to be careful about how you apply the operations, however - much like the naive shuffle, it's easy to write an algorithm that makes some boards more likely than others. A technique similar to the Knuth shuffle may help here.

Edit: It has been pointed out in the comments that these operations alone aren't sufficient to create every possible grid.

Answer 3

You will always get that situation. You need a recursive backtracking search to solve it.

Basically, the only way to determine whether a particular digit really is valid for a cell is to continue the search and see what happens.

Backtracking searches are normally done using recursive calls. Each call will iterate through the (possibly) still valid options for one cell, recursing to evaluate all the options for the next cell. When you can't continue, backtracking means returning from the current call - erasing any digit you tested out for that cell first, of course.

When you find a valid solution, either save it and backtrack to continue (ie find alternatives), or break out of all the recursive calls to finish. Success in a recursive backtracking search is a special case where throwing an exception for success is IMO a good idea - it is exceptional for a particular call to succeed, and the code will be clearer.

If generating a random board, iterate the options in a particular recursive call (for a particular cell) in random order.

The same basic algorithm also applies for a partly completed board (ie to solve existing sodoku) - when evaluating a cell that already has a digit, well, that's the only option for that cell so recurse for the next cell.

Here's the backtracking search from a solver I wrote once - a lot is abstracted out, but hopefully that just makes the principle clearer...

size_t Board::Rec_Search (size_t p_Pos)
{
  size_t l_Count = 0;

  if (p_Pos == 81)  //  Found a solution
  {
    l_Count++;

    std::cout << "------------------------" << std::endl;
    Draw ();
    std::cout << "------------------------" << std::endl;
  }
  else
  {
    if (m_Board [p_Pos] == 0)  //  Need to search here
    {
      size_t l_Valid_Set = Valid_Set (p_Pos);

      if (l_Valid_Set != 0)  //  Can only continue if there are possible digits
      {
        size_t  l_Bit = 1;  //  Scan position for valid set

        for (size_t i = 1; i <= 9; i++)
        {
          if (l_Valid_Set & l_Bit)
          {
            Set_Digit  (p_Pos, i);
            l_Count += Rec_Search (p_Pos + 1);
          }

          l_Bit <<= 1;
        }

        Clr_Digit (p_Pos);  //  Ensure cleared properly for backtracking
      }
    }
    else  //  Already filled in - skip
    {
      l_Count += Rec_Search (p_Pos + 1);
    }
  }

  return l_Count;
}