You're logic is fine - but you're using regular iterative logic, for a recursive function.Originally Posted by ridilla
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.
how's that?Code:int counter(count) { if(count = 1) { return; } else { count++; counter(count); } }
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:
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:Code:| 1 ? 3 | 4 ? 6 | 7 ? 9 |
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.
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?
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.
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).
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.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; }
Have you posted up ALL the requirements for your program, yet? If not, do it ASAP.
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
His notes on it are these:Code:int validate(int puzzle[PSIZE][PSIZE]);
"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:
It seems like you could write the validate function without using the checkValue function, but for some reason, he requires us to use it.Code:int checkValue(int puzzle[PSIZE][PSIZE], int value, int row, int col);
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
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.Code:void setSingles(int puzzle[PSIZE][PSIZE]);
-- 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:
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[][]Code:void copy(int from[PSIZE][PSIZE], int to[PSIZE][PSIZE]);
-- The stats structure is initialized
-- This is where I'm stuck. The brute force part. This is the next part of the main:Code:stats.failedAttempts = 0; stats.backtracks = 0;
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.Code:stats = solve(puzzle, original, stats);
Here's the protoype
and the notes:Code:Stats solve(int puzzle[PSIZE][PSIZE], int original[PSIZE][PSIZE], Stats stats);
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.
You noticed that, already? Brilliant!Your solutions use 1D arrays, but it seems I'm working with 2D arrays.
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!
