Sudoku Brute Force Algorithm Help (recursion?)

This is a discussion on Sudoku Brute Force Algorithm Help (recursion?) within the C Programming forums, part of the General Programming Boards category; Originally Posted by ridilla the loops seem necessary to me, here's my reasoning. hopefully you can tell me why they're ...

  1. #16
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by ridilla View Post
    the loops seem necessary to me, here's my reasoning. hopefully you can tell me why they're not necessary.

    the first loop is necessary to progress through the row, provided both sub-levels turn out to be valid. The second loop increments the value each time a non-valid entry is tried. I suppose you could also use row[i]++, but then how would the machine know to stop at 9? Would you have to write an out for that?
    You're logic is fine - but you're using regular iterative logic, for a recursive function.

    do this, write a function to count from 1 to 10, using ONLY recursion. No loops allowed!

    That will help get you into recursive thinking.

  2. #17
    Registered User
    Join Date
    May 2010
    Posts
    11
    Code:
    int
    counter(count)
    {
    
       if(count = 1)
       {
          return;
       }
       else
       {
       count++;
       counter(count);
       } 
    }
    how's that?

  3. #18
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    That's more like it. You don't need a bunch of loops because the function itself will be doing the looping.

    So the search() function will need:

    the board[][N] and the square that is being searched for possible's that are valid.

    If the search finds a valid digit, it goes to the next unsolved square and goes down one level of recursion.

    If it finds no valid digit exits, it returns one level up. Now the "square" variable will be the OLD square, not the former one from the deeper level, (no bookkeeping needed), and the search continues for a higher valid digit, for THAT OLD square.

    So, take your recursive skeletal function, and adapt it to work on just this one row:


    Code:
    | 1 ? 3 | 4 ? 6 | 7 ? 9 |
    And for this example, let's assume we could get no other info on what the possible digits for the ? squares, could be, except the obvious:

    The answer lies in this search set:
    258
    285
    528 << Thiis is the answer (we arbitrarily decide).
    582
    825
    852

    If you need other functions to support your recursion, that's fine. But no loops in the recursive function except one for the value of that one square.

    It can be done with none, but one loop is fine - reasonable even, imo.

    And no mass of parameters for the recursive function! NO original board, especially. You can show it on your display if you want, but it has no place, in this function.

    That will give you a real feel for solving this recursively.

  4. #19
    Registered User
    Join Date
    May 2010
    Posts
    11
    Are you sure that the square variable will go back to what it was? I know that would be true for a variable, but arrays aren't copied when they're passed from function to function, the actual array is passed. So if an array is passed one level down, and values are inputted but none end up working, when it's passed back up, those values will still be in the array, won't they?

  5. #20
    Registered User
    Join Date
    May 2010
    Posts
    11
    Also, the parameters for my function are hard and fast - i have to pass in two arrays and the initialized stats data. The function doesn't check just one cell, it has to check them all in one call. I'm still very confused as to how to make that work without (or with) loops. eeeek.

  6. #21
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by ridilla View Post
    Are you sure that the square variable will go back to what it was? I know that would be true for a variable, but arrays aren't copied when they're passed from function to function, the actual array is passed. So if an array is passed one level down, and values are inputted but none end up working, when it's passed back up, those values will still be in the array, won't they?
    Well--- Not exactly!

    Anyway, I'm not aware of the requirements for your parameters when I wrote this up tonight, but it should give you an idea. You can code your program either recursively or iteratively. This example actually does both, so it uses just one row[9]. (just a bit of programmer's trickery in that).

    Code:
    /* shows both an iterative and recursive function example on a Sudoku row solver
    Only one row is used. The answer is arbitrarily set as 1 5 3 4 2 6 7 8 9. 
    
    Adak, May 6, 2010
    
    Status: ok, but untested
    */
    
    #include <stdio.h>
    
    int isSolved(int row[9], int); 
    int isValid(int row[], int, int);
    void seek(int row[], int);
    int set(int row[]);
    
    int main() {
      int i, solved ; 
      int row[9] = {1,0,3,4,0,6,7,0,9};
      
      printf("\n1 0 3 4 0 6 7 0 9 << Original Puzzle \n");
      printf("\n1 5 3 4 2 6 7 8 9 << The (arbitrary) Solution");
      set(row);
      solved = isSolved(row, 9);
      putchar('\n');
      for(i = 0; i < 9; i++)
        printf("%d ", row[i]);
      if(solved) 
        printf("<< the puzzle is solved ");
      else
        printf("<< the puzzle is still not solved");
    
      printf("\n\n\t\t\t     press enter when ready");
      i = getchar(); 
      return 0;
    }
    
    /* This is the iterative part of the solution. No recursion in here */
    int set(int row[9]) {
      int i, ng;  //ng = "no good", and is a bit of trickery
      for(i = 0, ng = 0; i < 9; i++) {
        if((row[i] == 0) || (ng))
          if(ng)   {
            seek(row, --i);
            ng = 0;
          }
          else
            seek(row, i);
        if(!isSolved(row, i+1)) {
          ng = i;
        }
      }
      return 0;
    }
    /* This is the recursive function. No iterative logic in here */
    void seek(int row[9], int sqr) {
      row[sqr]++ ;
      if(isValid(row, sqr, row[sqr]))
        return;
      else
        seek(row, sqr);
    }
    int isValid(int row[9], int sqr, int n) {
      int gud = 1;
      int i;
      
      for(i = 0; i < 9; i++)
        if((row[i] != 0) && (i != sqr)) {
          if(row[i] == n)
            break;
      }
      if(i < 9)
        gud = 0;
      return gud;
    }
    int isSolved(int row[9], int sqr) {
      int i;
      int ans[9] = { 1,5,3,4,2,6,7,8,9 };
      for(i = 0; i < sqr; i++) {
        if(ans[i] != row[i])
          return 0;
      }
      return 1;
    }
    Nevertheless, YOU might want to have a truly recursive "backtracker". This is just another way to do it, using a bit of both iteration and recursion.

    Have you posted up ALL the requirements for your program, yet? If not, do it ASAP.

  7. #22
    Registered User
    Join Date
    May 2010
    Posts
    11
    Here are the specifications of the project:

    We're given a main function, which we cannot edit in any way. It does the following, in this order.
    -- Initializes three variables, int puzzle[PSIZE][PSIZE], int original[PSIZE][PSIZE] and Stats stats, which is a data structure that contains stats.backtracks and stats.failed attempts. PSIZE = 9.

    -- Calls the "get(puzzle)" function, which our professor has written and we are not to edit. It's a void function that passes in the puzzle[][] array, populates it with values inputted by the user and exits.

    -- Calls the "display(puzzle)" function, another one we're not to edit. Does exactly what it says.

    -- Does an if test with the "validate" function, the first function we have to write. While those first two functions were locally prototyped, all the others (the ones i have to write) are in another file. If the validate function returns a 0 (invalid), the program quits, and if not, it continues.

    The validate function has to be written to match his provided prototype, which is this

    Code:
    int validate(int puzzle[PSIZE][PSIZE]);
    His notes on it are these:

    "This function determines if a puzzle conforms to the rules of a
    well-formed sudoku puzzle. This means all values must be between
    0 and the size of the puzzle and all non-zero values must be
    unique on their row, column, and local square.

    NOTE: Ideally, this function will make use of your checkValue function.

    Parameters
    puzzle: The puzzle to validate.

    Returns
    This function returns true (a non-zero value) if the puzzle is
    well-formed, otherwise false (zero)."

    The prototype for the checkValue function mentioned looks like this:

    Code:
    int checkValue(int puzzle[PSIZE][PSIZE], int value, int row, int col);
    It seems like you could write the validate function without using the checkValue function, but for some reason, he requires us to use it.

    I've written both these functions and they seem to work. The puzzle is sent to the validate function, where loops are used to move through the function, and find every non-zero value. When it does, it sends the value, along with the column and row where it occurs, and puzzle[][] to the validate function. If that value can go in the cell it's in, the value is returned to the validate function by the checkValue function. If not, 0 is returned. The validate function returns the same things, an integer (the last integer found in the puzzle) if puzzle[][] is valid, a zero if not. Keep in mind that at this time, these values are only being returned to the if test in the main, to see if the user inputted puzzle is valid. Okay, back to main.

    -- Next comes the setSingles function, which we write. The prototype looks like this

    Code:
    void setSingles(int puzzle[PSIZE][PSIZE]);
    I've written this function also, it works. It scans through the puzzle, stops at every zero value and checks to see if it's the only zero in the row, col or box. If it is, it goes through the row, col or box, sums up the value of the integers present and subtracts that from 45 (the sum from one to nine) to find the value that should go in the box with the zero. It then repeats the whole process until it's unable to find any more single-solution-cells.

    -- Main then displays this newly-updated puzzle[][], again using the display(puzzle) function

    -- Next it copies the puzzle[][] array to another array called original[][], using the copy function that we write. The prototype looks like this:

    Code:
    void copy(int from[PSIZE][PSIZE], int to[PSIZE][PSIZE]);
    this function is pretty simple, it just uses two looops to go through puzzle[][] and for every index, assigns the value present to the same index in original[][]

    -- The stats structure is initialized
    Code:
    stats.failedAttempts = 0;
    stats.backtracks = 0;
    -- This is where I'm stuck. The brute force part. This is the next part of the main:
    Code:
    stats = solve(puzzle, original, stats);
    note the parameters for the solve function -- two 2D arrays and the stats variables. Puzzle[][] isn't returned, because again, arrays aren't passed as copies, if my array from main is passed to that function and edited inside it, it will also be changed in main.

    Here's the protoype
    Code:
    Stats solve(int puzzle[PSIZE][PSIZE], int original[PSIZE][PSIZE], Stats stats);
    and the notes:

    This function solves the sudoku puzzle using the specified brute-force
    method described in the assigment. It also updates the statistics of
    the solution for later reporting as follows:

    1. Count every time you try a value (1-9) in a cell and it does not
    work by incrementing the failedAttempts variable in the Stats
    structure by one.
    2. Count every cell you backtrack to by incrementing the backtracks
    variable in the Stats structure by one. Only count cells that you
    have set using this algorithm (not cells set in the original puzzle
    or set by the Single-Solution-Cell Algorithm) and count every time
    you do it, i.e., you may backtrack over the same cell more than once!

    Parameters
    puzzle: The puzzle to solve.
    original: The original unsolved puzzle with single-solution cells set.
    stats: The structure to update with failed attempts and backtracks.

    Return
    The updated Stats struct and the solved puzzle.

    and here are some more notes on the B.F.M.

    Starting at row-zero column-zero and going from top-left to bottom right a row at a time find the lowest value (1-9) that works in each unset cell (a cell containing a zero). If you encounter a cell that has no value (1-9) that works you must back-track to the cell most recently set by this algorithm (not one originally set in the puzzle or set by the Single-Solution-Cell algorithm) and find the next highest value that works in that cell. If no value works in the cell, set it to zero and continue back-tracking to the first cell that does allow a change. Once you find a cell that allows a change then continue forward from that changed cell until you have set all of the cells in the puzzle.

    -- Next, the main uses the display function to display puzzle[][] (now solved), and also prints the statistics.


    Those are my requirements. I'm allowed to write more functions to be called by any of the ones I've written, but I can't change the main at all. Your solutions use 1D arrays, but it seems I'm working with 2D arrays. As for testing, we're provided with test input and expected output files, we have to diff-test them with an executable my teacher has written (how our program should look and act)

    Thanks for the help! Sorry for the length!!
    Last edited by ridilla; 05-07-2010 at 01:46 PM.

  8. #23
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your solutions use 1D arrays, but it seems I'm working with 2D arrays.
    You noticed that, already? Brilliant!

    I thank Gawd Ah'mighty, every day, that there is NO relationship between a row of 9 squares, and other rows of 9 squares, or columns of 9 squares, or 3 X 3 boxes of 9 squares, which all have to be tested for the same constraints.

    And here I thought you had to solve one row, or column or box, before you could solve the next one, and thus work your way up to solving the whole puzzle!

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Running a Brute Force Attack Simulation...
    By Junior89 in forum C++ Programming
    Replies: 31
    Last Post: 02-13-2011, 07:52 PM
  2. 2d array Brute force test
    By grimuth in forum C++ Programming
    Replies: 5
    Last Post: 04-08-2010, 10:01 AM
  3. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 01:41 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21