• Welcome to Overclockers Forums! Join us to reply in threads, receive reduced ads, and to customize your site experience!

Help with part of sudoku puzzle

Overclockers is supported by our readers. When you click a link to make a purchase, we may earn a commission. Learn More.
MustangX

MustangX

Registered
​
Joined
Jun 18, 2006
Location
Southern Pa
I'm creating a sudoku puzzle that solves itself. I started on the first row to see if I could get it to work. The problem I'm having is that all of the 9 numbers aren't showing up at the same time and sometimes there are multiple instances of a number. Is there any other way of doing this besides If statements that would make the operation much faster? Here's the code:

Code: 
Dim row1(9) As Integer
Dim x As Integer
Function Randomizer()
    Randomize
        For x = 1 To 9
            row1(x) = Int(Rnd * 9) + 1
        Next x
End Function

Private Sub cmd_exit_Click()
    End
End Sub

Private Sub cmd_solve_Click()
    Call Randomizer
    If row1(1) <> row1(2) And row1(1) <> row1(3) And row1(1) <> row1(4) And row1(1) <> row1(5) And row1(1) <> row1(6) And row1(1) <> row1(7) And row1(1) <> row1(8) And row1(1) <> row1(9) Then
        lbl_r1_1 = row1(1)
    End If
    
    If row1(2) <> row1(1) And row1(2) <> row1(3) And row1(2) <> row1(4) And row1(2) <> row1(5) And row1(2) <> row1(6) And row1(2) <> row1(7) And row1(2) <> row1(8) And row1(2) <> row1(9) Then
        lbl_r1_2 = row1(2)
    End If
    
    If row1(3) <> row1(1) And row1(3) <> row1(2) And row1(3) <> row1(4) And row1(3) <> row1(5) And row1(3) <> row1(6) And row1(3) <> row1(7) And row1(3) <> row1(8) And row1(3) <> row1(9) Then
        lbl_r1_3 = row1(3)
    End If
    
    If row1(4) <> row1(1) And row1(4) <> row1(2) And row1(4) <> row1(3) And row1(4) <> row1(5) And row1(4) <> row1(6) And row1(4) <> row1(7) And row1(4) <> row1(8) And row1(4) <> row1(9) Then
        lbl_r1_4 = row1(4)
    End If
    
    If row1(5) <> row1(1) And row1(5) <> row1(2) And row1(5) <> row1(3) And row1(5) <> row1(4) And row1(5) <> row1(6) And row1(5) <> row1(7) And row1(5) <> row1(8) And row1(5) <> row1(9) Then
        lbl_r1_5 = row1(5)
    End If
    
     If row1(6) <> row1(1) And row1(6) <> row1(2) And row1(6) <> row1(3) And row1(6) <> row1(4) And row1(6) <> row1(5) And row1(6) <> row1(7) And row1(6) <> row1(8) And row1(6) <> row1(9) Then
        lbl_r1_6 = row1(6)
    End If
    
     If row1(7) <> row1(1) And row1(7) <> row1(2) And row1(7) <> row1(3) And row1(7) <> row1(4) And row1(7) <> row1(5) And row1(7) <> row1(6) And row1(7) <> row1(8) And row1(7) <> row1(9) Then
        lbl_r1_7 = row1(7)
    End If
    
    If row1(8) <> row1(1) And row1(8) <> row1(2) And row1(8) <> row1(3) And row1(8) <> row1(4) And row1(8) <> row1(5) And row1(8) <> row1(6) And row1(8) <> row1(7) And row1(8) <> row1(9) Then
        lbl_r1_8 = row1(8)
    End If
    
     If row1(9) <> row1(1) And row1(9) <> row1(2) And row1(9) <> row1(3) And row1(9) <> row1(4) And row1(9) <> row1(5) And row1(9) <> row1(6) And row1(9) <> row1(7) And row1(9) <> row1(8) Then
        lbl_r1_9 = row1(9)
    End If
    
    If row1(1) + row1(2) + row1(3) + row1(4) + row1(5) + row1(6) + row1(7) + row1(8) + row1(9) <> 45 Then
        For x = 1 To 9
            row1(x) = 0
        Next x
    End If

End Sub
 
MustangX said:
I'm creating a sudoku puzzle that solves itself. I started on the first row to see if I could get it to work. The problem I'm having is that all of the 9 numbers aren't showing up at the same time and sometimes there are multiple instances of a number. Is there any other way of doing this besides If statements that would make the operation much faster? Here's the code:

Code: 
Dim row1(9) As Integer
Dim x As Integer
Function Randomizer()
    Randomize
        For x = 1 To 9
            row1(x) = Int(Rnd * 9) + 1
        Next x
End Function

Private Sub cmd_exit_Click()
    End
End Sub

Private Sub cmd_solve_Click()
    Call Randomizer
    If row1(1) <> row1(2) And row1(1) <> row1(3) And row1(1) <> row1(4) And row1(1) <> row1(5) And row1(1) <> row1(6) And row1(1) <> row1(7) And row1(1) <> row1(8) And row1(1) <> row1(9) Then
        lbl_r1_1 = row1(1)
    End If
    
    If row1(2) <> row1(1) And row1(2) <> row1(3) And row1(2) <> row1(4) And row1(2) <> row1(5) And row1(2) <> row1(6) And row1(2) <> row1(7) And row1(2) <> row1(8) And row1(2) <> row1(9) Then
        lbl_r1_2 = row1(2)
    End If
    
    If row1(3) <> row1(1) And row1(3) <> row1(2) And row1(3) <> row1(4) And row1(3) <> row1(5) And row1(3) <> row1(6) And row1(3) <> row1(7) And row1(3) <> row1(8) And row1(3) <> row1(9) Then
        lbl_r1_3 = row1(3)
    End If
    
    If row1(4) <> row1(1) And row1(4) <> row1(2) And row1(4) <> row1(3) And row1(4) <> row1(5) And row1(4) <> row1(6) And row1(4) <> row1(7) And row1(4) <> row1(8) And row1(4) <> row1(9) Then
        lbl_r1_4 = row1(4)
    End If
    
    If row1(5) <> row1(1) And row1(5) <> row1(2) And row1(5) <> row1(3) And row1(5) <> row1(4) And row1(5) <> row1(6) And row1(5) <> row1(7) And row1(5) <> row1(8) And row1(5) <> row1(9) Then
        lbl_r1_5 = row1(5)
    End If
    
     If row1(6) <> row1(1) And row1(6) <> row1(2) And row1(6) <> row1(3) And row1(6) <> row1(4) And row1(6) <> row1(5) And row1(6) <> row1(7) And row1(6) <> row1(8) And row1(6) <> row1(9) Then
        lbl_r1_6 = row1(6)
    End If
    
     If row1(7) <> row1(1) And row1(7) <> row1(2) And row1(7) <> row1(3) And row1(7) <> row1(4) And row1(7) <> row1(5) And row1(7) <> row1(6) And row1(7) <> row1(8) And row1(7) <> row1(9) Then
        lbl_r1_7 = row1(7)
    End If
    
    If row1(8) <> row1(1) And row1(8) <> row1(2) And row1(8) <> row1(3) And row1(8) <> row1(4) And row1(8) <> row1(5) And row1(8) <> row1(6) And row1(8) <> row1(7) And row1(8) <> row1(9) Then
        lbl_r1_8 = row1(8)
    End If
    
     If row1(9) <> row1(1) And row1(9) <> row1(2) And row1(9) <> row1(3) And row1(9) <> row1(4) And row1(9) <> row1(5) And row1(9) <> row1(6) And row1(9) <> row1(7) And row1(9) <> row1(8) Then
        lbl_r1_9 = row1(9)
    End If
    
    If row1(1) + row1(2) + row1(3) + row1(4) + row1(5) + row1(6) + row1(7) + row1(8) + row1(9) <> 45 Then
        For x = 1 To 9
            row1(x) = 0
        Next x
    End If

End Sub
Click to expand...

A random number might be great for the first one or two numbers on the first row. After that, you don't want random numbers, imo.

You have a search space to go through. It just makes sense to start at the small side of that search space, and keep working toward it's highest number. Coincidentally, this is how most programs work,

There are three tests that each possible number for a square must pass:
1) Is it unique on that row
2) Is it unique on that col
3) Is it unique on it's box of 9 squares

My program in C has a small 10 integer array, where element 0 is not used at all. Elements 1 through nine are either 1 or 0, depending on whether the row (let's take that as the example), has a "firm" number, or not. 1 it has a number, 0 it does not.

I have a CheckRow function, much like this:
Code: 
CheckRow(int row, int col, int candidate)  {
   puzzle[row][col] = candidate;
   for sqr = 1; sqr <= candidate; sqr++)  {
      if (puzzle[row][sqr]
          Used[sqr] += 1;
      else 
          Used[sqr] = 0;
       if (Used[sqr]) > 1 {
          puzzle[row][sqr] = 0;  /* restore it to zero */
          return 1   /* candidate number was a failure */
   
       }  
   }
   return 0;  /* candidate number was a success */
}

That's from memory and may not be quite perfect C, but you get the idea. It's VERY fast. A nearly identical function checks columns, and boxes of 9 sqr's.

I don't know if this is a more or less standard approach to programming this puzzle up, but it works, and it works very fast.

Adak
 
Alright, I get what your saying. One question though, how are you generating numbers from 1-9?
 
Usually using a for loop. Sometimes a while loop. Simple increments, never a random number.

Code: 
for ( i = 1; 1 < 10; i++)  {

   if (CheckRow(row, col, i) == 0) {
      if (CheckCol(row, col, i) == 0) {
         if (CheckBox(row, col, i) == 0 
             break;
      }
   }
}

The code above is more for conceptual purposes - the actual code is optimized and not easy to understand. (It was originally coded in compiled BASIC, so I felt it should have all kinds of optimizations, right away. I'm currently trying to make it a more "non optimized, user friendly" version, in C.

But while and for loops are used heavily in this program, and the idea it follows is always to start guessing at 1, and do a first check on that number. If it fails, don't check that 1 in that sqr anymore, (unless a sqr "upstream" from it is changed), instead loop back and get a 2 and try it in CheckRow(), only if it passes that, does it get tried in CheckCol(), and then only if it passes that test, does it get tested in CheckBox(). (CheckBox() goes last because there is more code needed for that one.)

I had not done hardly any Sudoku puzzles before starting my program, so it follows what I do by hand (although MUCH faster!), pretty much, to solve it. It begins with making a list of all the possibles for each sqr, and then starts to logically whittle them down in number,

The logic alone will nearly instantly solve simple puzzle patterns. More difficult puzzles will need some guessing to be done on the remaining possibles, since the logic rules become more and more arcane and very difficult for me (at least), to find a way to program them.

The guessing involves taking the sqr's with the fewest remaining possibles, and choosing one of them (again, always the lowest first), and seeing if that leads to solving other sqr's, which in turn, solves the whole puzzle. That's my "fast" solver. Then I have a "slow" solver, which uses pure "odometer" logic, to search the entire remaining search space, to find the answer. On very difficult puzzles, this could run for anything from a few minutes, to several days!

The odometer logic was just for fun, really.

I've learned now of an even more difficult Sudoku puzzle, which only has 17 sqr's with a given number. For each of these, there is only ONE possible answer. My program doesn't solve most of them because I had read that every Sudoku puzzle has at least 21 or more, given numbers. That will be addressed in a later version.

Sounds like it would be good for you to check out some of the several Sudoku puzzle forums, and see what you can learn. It is a much more involved puzzle to solve quickly, with lots of logic wrinkles, as well, than I believe you realize.

Google and enjoy! It is a FUN puzzle - you have to appreciate the way one change to a sqr over on the right, may affect several other sqr's, scattered all over the board, or no other sqr's, at all. :D
 
Is "Used" a variable in your program or is it a function? If it's a variable, do you have it set as an array or what?
 
MustangX said:
Is "Used" a variable in your program or is it a function? If it's a variable, do you have it set as an array or what?
Click to expand...

It's an array of type int. If the puzzle row in question looked like this:
*1*2*4*8*9*6*3*5*_*

Then Used[] subscripts would look like this:
0 1 2 3 4 5 6 7 8 9
================
0 1 1 1 1 1 1 0 1 1

Used[0] is ignored, and in the function CheckRow(), the Used array shows that only the number 7 can be used in the one remaining sqr on the end of the row.

Other numbers are tried (again, in order from low to high), but they all fail very early, because they make a subscript of Used[] > 1.

Every full row that is correct, will show nothing but 1's in the Used[] array. Then I change the input, but use the Used[] array again to check the columns. Again, it does two things - it tells me when a proposed number is illegal, AND it also tells me when the entire row, column or box of 9 sqr's, is LEGAL.

It takes some doing to get the box of 9 sqr's set up for the Used[] array, but it's worth it.
 
From what I understand there is a right move for every step along a sodoku puzzle out there and no guess work is needed. There are already a few sodoku solvers that don't guess at all, for example, http://www.sudokusolver.co.uk/

Good luck!
 
TreeNode said:
From what I understand there is a right move for every step along a sodoku puzzle out there and no guess work is needed. There are already a few sodoku solvers that don't guess at all, for example, http://www.sudokusolver.co.uk/

Good luck!
Click to expand...

You understand wrong. There are a number of logic rules helpful for solving Sudoku, several are quite arcane and extremely subtle.

They will not solve all the puzzles, however. Also, most of them are tough to code up, depending on your choice of a programming language, and your skill in same.

I used three of them in my solver, and said "whew! That's enough!"

We call it "guessing" but it's more like "what if", and not such a clumsy or amateurish thing as "guessing" implies.

Spreadsheets do "what if" calculations, all day long, for businesses around the world. Why shouldn't a Sudoku program do a bit of the same?
 
Nope. I'm pretty sure that all possible sodoku puzzles ever can be solved by logic ONLY, its just that its so difficult to code that nobody really has created a sodoku solver that incorporates all of those logic solving methods.
 
I've been thinking of writing a sudoku solver for some time now. This thread got me inspired to give it a shot. The logic of mine follows Adak's with one optimization. I start out by building stats for the table, that tell me what numbers are used in each row, column and box.
Code: 
void SudokuStats::Update(const SudokuTable& table, int row, int col)
{
    int value = table[row][col];
    if (value > 0)
    {
        mNSolved++;
        mRow[row][value-1] = true;
        mCol[col][value-1] = true;
        mBox[row/3][col/3][value-1] = true;
    }
}

void SudokuStats::Calculate(const SudokuTable& table)
{
    Clear();

    for (int row = 0; row < 9; row++)
    {
        for (int col = 0; col < 9; col++)
        {
            Update(table, row, col);
        }
    }
}

With that information I can quickly check to see what numbers are available for a specific location.

Code: 
void GetPossibleValues(
    const SudokuStats& stats,
    int row,
    int col,
    vector<int>& values)
{
    const bool* rowValues = stats.mRow[row];
    const bool* colValues = stats.mCol[col];
    const bool* boxValues = stats.mBox[row/3][col/3];
    values.clear();

    for (int i = 0; i < 9; i++)
    {
        if (!rowValues[i] && !colValues[i] && !boxValues[i])
        {
            values.push_back(i+1);
        }
    }
}

I wrote a function that finds the next best position to fill. This is used both to find the next location that I can find an answer for, and later, to find best location to make a guess at.

Code: 
int GetMostConstrainedEmptyCell(
    const SudokuTable& table,
    const SudokuStats& stats,
    int& bestRow,
    int& bestCol)
{
    vector<int> values(9);
    int bestCount = 10;
    for (int row = 0; row < 9; row++)
    {
        for (int col = 0; col < 9; col++)
        {
            if (table[row][col] == 0)
            {
                GetPossibleValues(stats, row, col, values);
                int count = static_cast<int>(values.size());
                if (count < bestCount)
                {
                    bestCount = count;
                    bestRow = row;
                    bestCol = col;
                    if (count <= 1)
                    {
                        return count;
                    }
                }
            }
        }
    }

    return bestCount;
}

Finally, I have a solve function. This will fill in all the squares that are obvious. Then, if it makes guesses. These are done by making recursive calls to the solve function.

Code: 
bool Solve(SudokuTable& table)
{
    SudokuStats stats;
    int row = 0;
    int col = 0;
    vector<int> values(9);
    stats.Calculate(table);
    int nValues = GetMostConstrainedEmptyCell(table, stats, row, col);

    // Fill in all the easy squares.
    while (nValues == 1)
    {
        GetPossibleValues(stats, row, col, values);
        table[row][col] = values[0];

        stats.Update(table, row, col);
        nValues = GetMostConstrainedEmptyCell(table, stats, row, col);
    }

    if (stats.mNSolved == 81)
    {
        return true;
    }
    else if (nValues < 1)
    {
        return false;
    }

    // We need to make a guess.
    GetPossibleValues(stats, row, col, values);
    for (int i = 0; i < nValues; i++)
    {
        SudokuTable guess = table;
        guess[row][col] = values[i];

        if (Solve(guess))
        {
            table = guess;
            return true;
        }
    }

    // No guesses were solvable.
    return false;
}

I've found that it can solve any of the puzzles I've given it in under a second. I'm not sure if there are some puzzles that require making many guesses that will take a long time.
 
Congratulations on your Sudoku program!

I wrote mine in QuickBasic. It's solve times are perhaps quicker than yours (with the compiled version), my design is not as well thought out as yours, and the code is quite large.

The hardest puzzles I've found are the set of 17 (where 17 square's only have a given value).

I don't have the link handy, but here are a several puzzles, which have only one solution:
123456789123456789123456789123456789123456789123456789123456789123456789123456789
===========================================================
000000010400000000020000000000050407008000300001090000300400200050100000000806000
000000010400000000020000000000050604008000300001090000300400200050100000000807000
000000012000035000000600070700000300000400800100000000000120000080000040050000600
000000012003600000000007000410020000000500300700000600280000040000300500000000000
000000012008030000000000040120500000000004700060000000507000300000620000000100000
000000012040050000000009000070600400000100000000000050000087500601000300200000000
000000012050400000000000030700600400001000000000080000920000800000510700000003000
000000012300000060000040000900000500000001070020000000000350400001400800060000000
000000012400090000000000050070200000600000400000108000018000000000030700502000000
000000012500008000000700000600120000700000450000030000030000800000500700020000000
000000012700060000000000050080200000600000400000109000019000000000030800502000000
000000012800040000000000060090200000700000400000501000015000000000030900602000000
000000013000500070000802000000400900107000000000000200890000050040000600000010000
000000013000700060000508000000400800106000000000000200740000050020000400000010000
000000013000700060000509000000400900106000000000000200740000050080000400000010000
000000013000800070000502000000400900107000000000000200890000050040000600000010000
000000013020500000000000000103000070000802000004000000000340500670000200000010000
000000013040000080200060000609000400000800000000300000030100500000040706000000000
000000013040000080200060000906000400000800000000300000030100500000040706000000000
000000013040000090200070000607000400000300000000900000030100500000060807000000000
000000013040000090200070000706000400000300000000900000030100500000060807000000000
000000013200800000300000070000200600001000000040000000000401500680000200000070000
000000013400800000200000070000400900001000000060000000000501600380000200000070000
000000014000000203800050000000207000031000000000000650600000700000140000000300000
000000014000020000500000000010804000700000500000100000000050730004200000030000600
000000014008005000020000000000020705100000000000000800070000530600140000000200000
000000014008005000020000000000020805100000000000000700070000530600140000000200000
000000014008009000020000000000020805100000000000000700070000930600140000000200000
000000014700000000000500000090014000050000720000600000000900805600000900100000000
000000014790000000000200000000003605001000000000000200060000730200140000000800000
000000014970000000000200000000003605001000000000000200060000730200140000000800000
000000015000400070300060000800000200000104000400500000000023600010000000070000000
000000015000400070400000000609000300000100800000700000500030200000060040010000000
000000015000800070300000000408000300000100400000700000500040200000090060010000000
000000015000800070400000000609000300000100800000700000500030200000060040010000000
000000015000830000000000200023000800000001000080000000105040000000600720900000000
000000015000830000000000200026000800000001000080000000105040000000300720900000000
000000015000900070400000000608000300000100800000700000500030200000060040010000000
000000015000900070400000000609000300000100800000700000500030200000060040010000000
000000015000900080300000000704000300000100400000800000500040200000070060010000000
000000015000900080400000000704000300000100900000800000500030200000070060010000000
000000015020060000000000408003000900000100000000008000150400000000070300800000060
000000015040080000000000300000040260500107000900000000300500000080000400000900000
Click to expand...
Each row above, is one puzzle's starting board set-up position.

My program doesn't solve all of these because I was told a Sudoku puzzle had to have at least 21 squares with a given value, and my algorithm currently requires that, in many cases.

How does your program do with these toughies?

The forum has put a blank space after the 55th square (that wasn't in the original), but I added a header 'ruler', to see what was going on,
and it appears that nothing is being lost - just pushed over.
 
Last edited:
I added some timing code to my program. It solves all the above puzzles in under a second each. Total time for all 42 was close to 3 seconds. The worst one, the 26th, took 0.7 seconds. This were times for the release build. Surprisingly, the debug build took 4 minutes to solve the 42 puzzles.

By solving it, I mean the program finds a solution. If there are multiple solutions it doesn't report it, just finds one solution. For example, I can give a puzzle with no givens (all zeros) and it will find an answer.

I think reading a solution before I implemented mine helped to organize my thoughts.
 
All 42 in 3 seconds is an *EXCELLENT* time! Congrats!! :clap: :clap:

Since I had never done Sudoku puzzles before I started writing my program, (and using just QuickBasic), the idea of a sophisticated design was "whoooosh!", out the window. Not knowing what you're designing before you start building is a real drawback. :D

There is a list of 1,000 or so of these games on the net. Not sure of the link, but if you google "Sudoku 17" and scout around, you should find 'em.
 
You must log in or register to reply here.

Similar threads

TickleMyElmo
Which one?
Replies
5
Views
2K
EarthDog
EarthDog
mackerel
FEATURED Zen 4 APUs anyone?
Replies
19
Views
777
dejo
dejo
don256us
New week still #8.
2
Replies
20
Views
899
Holdolin
Holdolin
don256us
Happy holidays edition with a 30 billion milestone!
Replies
5
Views
493
Holdolin
Holdolin
don256us
#7 and 3 Billion. Let's see what we're up to this week.
2
Replies
24
Views
653
=XAF=AfterShock
=XAF=AfterShock
Back