3x9 Sudoku Solver: Number Insertion Function Failure
The function I created to insert unused numbers into the puzzle fails. I know that the decrement operations in the function don’t occur; however, this may not be the only problem.
Program Description:
1. The puzzle is input.
2. The puzzle is printed.
3. Arrays to hold unused values in the rows and boxes of the puzzle are declared.
4. Counters holding the amount of available numbers for each array described in step 3 are declared.
5. Strings corresponding to both the array and its corresponding counter are declared.
6. The puzzle is scanned, and each number not equaling 0 in the puzzle is set to 0 in its corresponding availability array, and the corresponding counter is decremented. (This works.)
7. Afterwards, a block of nested control structures is called that calls a function that should insert numbers into the puzzle where 0s, that represent blank spaces, are. This immediately fails after the first innermost if statement.
Here's the code:
Comment: The above if statement corresponds to row 1, box1. Where puz, row1, and box1 are the addresses of the first elements of the puzzle, row 1 availability, and box 1 availability arrays. a and d are the counters that correspond to the row1 and box1 arrays. i and j are indices of the puzzle when the function is called.
Comment: After this if statement, the procedure is repeated for (row 1, box 2), (row 1, box 3), (row 2, box 1), etc.
Here's the function:
The puzzle I consistently tested throughout program development is:
1 2 0 0 4 0 0 8 7
0 3 0 5 8 0 6 0 4
7 0 6 0 1 0 3 2 0
Basically, if the function is called and there is a 0 at the element of the puzzle, it should scan through the availability arrays that were passed until it finds to short integers that are equal, but not 0. Then, it decrements the amount of available numbers for the two arrays, copies the value of either of the arrays into the puzzle, then sets both values in the availability arrays to 0.
Problem Symptoms:
1. The program compiles.
2. The program runs.
3. When the program gets to the block of nested control structures that should complete the puzzle, it infinite loops within the first innermost while statement, and the first innermost if statement is successfully executed; however, the function that is called fails to do its job.
Problem Environment:
The program is coded and run using CodeBlocks. The problem occurs midway through execution.
Problem Research:
This program/problem is an independent project I took an interest in for my programming class. My teacher has approved for me to gain assistance in solving this problem via online forums. I haven’t looked at any Sudoku algorithms, code, problems, etc. online because I wanted the program to be an original project, with me generating most of the code. Besides, this is for a 3x9 puzzle, in which each box and row must contain the digits 1 – 9. When this program is complete, I will proceed to a 9 * 3 puzzle, and lastly a 9 * 9 puzzle. So far, I’ve only completed a program that solves a 3 * 3.
Diagnostics:
I have coded several functions that print out the numbers in the availability arrays and their corresponding counters and strings. This is how I found out that there counters never decrement.
Conclusion/ What I Need Help With:
I would like for some individual(s) to point out what’s wrong with my numInsertion function and to point out if there’s something wrong with my nested control structure block that handles the responsibility of solving the puzzle. Specifically, why the decrement operations don’t occur, if the values in the availability array don’t change when the function is called, why, and how to make the program better. I would like suggestions on how to improve the program’s efficiency once it’s complete, or just guidance to a different, more efficient approach to solving the puzzle. Thank You!
I had difficulty describing the problem, as I didn't want to dump a huge lump of code into the post. Please make remarks on how I may improve my questions in the future. Thanks.
Program Description:
1. The puzzle is input.
2. The puzzle is printed.
3. Arrays to hold unused values in the rows and boxes of the puzzle are declared.
4. Counters holding the amount of available numbers for each array described in step 3 are declared.
5. Strings corresponding to both the array and its corresponding counter are declared.
6. The puzzle is scanned, and each number not equaling 0 in the puzzle is set to 0 in its corresponding availability array, and the corresponding counter is decremented. (This works.)
7. Afterwards, a block of nested control structures is called that calls a function that should insert numbers into the puzzle where 0s, that represent blank spaces, are. This immediately fails after the first innermost if statement.
Here's the code:
|
|
Comment: The above if statement corresponds to row 1, box1. Where puz, row1, and box1 are the addresses of the first elements of the puzzle, row 1 availability, and box 1 availability arrays. a and d are the counters that correspond to the row1 and box1 arrays. i and j are indices of the puzzle when the function is called.
Comment: After this if statement, the procedure is repeated for (row 1, box 2), (row 1, box 3), (row 2, box 1), etc.
Here's the function:
|
|
The puzzle I consistently tested throughout program development is:
1 2 0 0 4 0 0 8 7
0 3 0 5 8 0 6 0 4
7 0 6 0 1 0 3 2 0
Basically, if the function is called and there is a 0 at the element of the puzzle, it should scan through the availability arrays that were passed until it finds to short integers that are equal, but not 0. Then, it decrements the amount of available numbers for the two arrays, copies the value of either of the arrays into the puzzle, then sets both values in the availability arrays to 0.
Problem Symptoms:
1. The program compiles.
2. The program runs.
3. When the program gets to the block of nested control structures that should complete the puzzle, it infinite loops within the first innermost while statement, and the first innermost if statement is successfully executed; however, the function that is called fails to do its job.
Problem Environment:
The program is coded and run using CodeBlocks. The problem occurs midway through execution.
Problem Research:
This program/problem is an independent project I took an interest in for my programming class. My teacher has approved for me to gain assistance in solving this problem via online forums. I haven’t looked at any Sudoku algorithms, code, problems, etc. online because I wanted the program to be an original project, with me generating most of the code. Besides, this is for a 3x9 puzzle, in which each box and row must contain the digits 1 – 9. When this program is complete, I will proceed to a 9 * 3 puzzle, and lastly a 9 * 9 puzzle. So far, I’ve only completed a program that solves a 3 * 3.
Diagnostics:
I have coded several functions that print out the numbers in the availability arrays and their corresponding counters and strings. This is how I found out that there counters never decrement.
Conclusion/ What I Need Help With:
I would like for some individual(s) to point out what’s wrong with my numInsertion function and to point out if there’s something wrong with my nested control structure block that handles the responsibility of solving the puzzle. Specifically, why the decrement operations don’t occur, if the values in the availability array don’t change when the function is called, why, and how to make the program better. I would like suggestions on how to improve the program’s efficiency once it’s complete, or just guidance to a different, more efficient approach to solving the puzzle. Thank You!
I had difficulty describing the problem, as I didn't want to dump a huge lump of code into the post. Please make remarks on how I may improve my questions in the future. Thanks.
Last edited on
perhaps Line 5 is too restrictive?
in particular u[h] == v[h] requires that u and v are equal at exactly the same position h
is that what you really want?
in particular u[h] == v[h] requires that u and v are equal at exactly the same position h
is that what you really want?
Yes, for instance if h = 5, then u[h] & v[h] will equal either 6 or 0. If both are 6, then the function should proceed to insert 6 at the position in the puzzle under which it was called.
ok, I understand your code a bit better line - Line 5 effectively is the same as:
if ( u[h]>0 && v[h]>0 )
correct? I'm assuming that u[] and v[] are initialized to 1-9, in order, with 0's for numbers removed
a couple of questions:
1. you have listed your input, but what is your expected output and the output you get with the code you currently have?
2. what happens when you have inserted the "wrong numbers", in the sense that you have inserted legal moves, but won't satisfy the solution of the entire puzzle? how does your algorithm handle this case?
if ( u[h]>0 && v[h]>0 )
correct? I'm assuming that u[] and v[] are initialized to 1-9, in order, with 0's for numbers removed
a couple of questions:
1. you have listed your input, but what is your expected output and the output you get with the code you currently have?
2. what happens when you have inserted the "wrong numbers", in the sense that you have inserted legal moves, but won't satisfy the solution of the entire puzzle? how does your algorithm handle this case?
You're correct on both of your reasonings. I implemented your version of line 5.
In response to your first question, there isn't any output because the program infinite loops within the control structure.
Your first question has made me realize the puzzle cannot be solved, since box 1 is missing 4, 5, 8, 9, yet 4, 5, 8 cannot be placed in row 2, where there are two blank spaces.
In response to your second question, I haven't yet developed solutions to fix an incorrect puzzle or the insertion of illegal numbers. I was saving that for after I created a program that could actually complete a puzzle without using unavailable numbers.
My current move is to create a puzzle with multiple solutions. I tested the following puzzle, and the correct values were removed from their arrays, and their counters were decremented.
0 5 3 0 0 0 2 8 7
0 6 4 1 8 7 0 3 9
9 8 0 0 0 0 0 4 0
From all of my experimentations, I can isolate the problem to the function and/or the block of nested control structures that completes the puzzle. Here it is.
Remember:
Counter:Availability Array
a: row 1
b: row 2
c: row 3
d: box 1
e: box 2
f: box 3
Are there problems here, or in the function?
Also, on an unrelated note, how do I get my code to paste properly? The post tends to sometimes lose or misplace indentations when I paste code.
In response to your first question, there isn't any output because the program infinite loops within the control structure.
Your first question has made me realize the puzzle cannot be solved, since box 1 is missing 4, 5, 8, 9, yet 4, 5, 8 cannot be placed in row 2, where there are two blank spaces.
In response to your second question, I haven't yet developed solutions to fix an incorrect puzzle or the insertion of illegal numbers. I was saving that for after I created a program that could actually complete a puzzle without using unavailable numbers.
My current move is to create a puzzle with multiple solutions. I tested the following puzzle, and the correct values were removed from their arrays, and their counters were decremented.
0 5 3 0 0 0 2 8 7
0 6 4 1 8 7 0 3 9
9 8 0 0 0 0 0 4 0
From all of my experimentations, I can isolate the problem to the function and/or the block of nested control structures that completes the puzzle. Here it is.
|
|
Remember:
Counter:Availability Array
a: row 1
b: row 2
c: row 3
d: box 1
e: box 2
f: box 3
Are there problems here, or in the function?
Also, on an unrelated note, how do I get my code to paste properly? The post tends to sometimes lose or misplace indentations when I paste code.
if your program is not too long, you should try to post the entire thing - look at it from my perspective: without the posting, my eyeballs have to act as the debugger whereas if you post it, I can compile and let the debugger do the work! In fact, you may try stepping through the debugger first, to see if you can detect where the app is acting unexpectedly.
so I ask again, with input:
0 5 3 0 0 0 2 8 7
0 6 4 1 8 7 0 3 9
9 8 0 0 0 0 0 4 0
what was your actual output vs your expected output?
on another note, I have only been introduced to sudoku once, a few years back by my cousin so I am, by no means, an expert in this area
however, wrt 2., what I mean is, I take it that it's possible that my algorithm makes all legal moves to replace 0's with unused numbers and yet, when it looks at the very last 0 to replace, the algorithm is screwed because it has walked into a "dead end", where none of the available numbers can legally be placed into that last 0 - I was just wondering how you dealt with this case
I take it that some of the hardest sudoku puzzles must be of the variety where a great number of permutations are all legal, up until the last 0 or two and then you're screwed because you didn't replace the first n-1 or n-2 0's correctly (where n is the initial number of 0's)...
(not sure about the pasting - the 8 space tabs annoy me when I paste tabs, so I actually replace them with 2 actual spaces before posting here)
in terms of your second posting, there are too many magic constants in the code so I'm not sure what your intentions are - all those 2, 5, 6, 9's look curious - will they work if the input changes? will they still work if the input is not 3x9?
so I ask again, with input:
0 5 3 0 0 0 2 8 7
0 6 4 1 8 7 0 3 9
9 8 0 0 0 0 0 4 0
what was your actual output vs your expected output?
on another note, I have only been introduced to sudoku once, a few years back by my cousin so I am, by no means, an expert in this area
however, wrt 2., what I mean is, I take it that it's possible that my algorithm makes all legal moves to replace 0's with unused numbers and yet, when it looks at the very last 0 to replace, the algorithm is screwed because it has walked into a "dead end", where none of the available numbers can legally be placed into that last 0 - I was just wondering how you dealt with this case
I take it that some of the hardest sudoku puzzles must be of the variety where a great number of permutations are all legal, up until the last 0 or two and then you're screwed because you didn't replace the first n-1 or n-2 0's correctly (where n is the initial number of 0's)...
(not sure about the pasting - the 8 space tabs annoy me when I paste tabs, so I actually replace them with 2 actual spaces before posting here)
in terms of your second posting, there are too many magic constants in the code so I'm not sure what your intentions are - all those 2, 5, 6, 9's look curious - will they work if the input changes? will they still work if the input is not 3x9?
Last edited on
The "magic constants" are only for a 3 * 9 puzzle. When they are used in a condition, they indicate a row or a box. i represents a row, while a range in j represents a box.
I understand what you are saying in your 4th to last paragraph. I'm not sure I have measures in place to prevent errors like that that could occur; however, this is do mostly in part to the program being unable to complete the puzzle in the first place. However, you bring up a very interesting point. I'll look into it.
I'll provide the code that you need, which would exclude functions that check my program's functionality and their associated variables main. Those work, as I've used them all, and they've produced correct results.
Remember, the short integers a-f correspond with the 6 short integer arrays immediately following them.
I've never used a debugger, but I could look up how to use CodeBlocks'.
Thanks for your efforts so far. I'll take another look at this problem.
I understand what you are saying in your 4th to last paragraph. I'm not sure I have measures in place to prevent errors like that that could occur; however, this is do mostly in part to the program being unable to complete the puzzle in the first place. However, you bring up a very interesting point. I'll look into it.
I'll provide the code that you need, which would exclude functions that check my program's functionality and their associated variables main. Those work, as I've used them all, and they've produced correct results.
|
|
Remember, the short integers a-f correspond with the 6 short integer arrays immediately following them.
I've never used a debugger, but I could look up how to use CodeBlocks'.
Thanks for your efforts so far. I'll take another look at this problem.
ok - stepping through the debugger now, but I actually don't want to spend too much time with your current code, because I don't think it will work, even if corrected
here is why: looking at the first row, there are 4! combinations for the 4 zeros left, the second row has 2! combinations, while the third row has 6! combinations - I am simplifying somewhat, because as you select a specific cell to fill, you will lower the number of combinations left in the other two rows
in your current algorithm, you are always trying to fill the lowest row with the lowest number left what if the solution requires a high number like 6 at (0,0), but you've inserted a 1 because a 1 is also legal at position (0,0) and you are going filling from bottom to top with lowest available numbers first?
I will look at your current code some more, but consider the case I have listed - I don't want to spend time correcting your current code and then find that you have to chuck it because your general algorithm doesn't work
in fact, it may be a good exercise to describe first in words, the steps in your algorithm, so we can confirm that it will actually work!
edit: think carefully about what I said in regards to the combinations - you may be able to create a more tractable algorithm using possible combinations
here is why: looking at the first row, there are 4! combinations for the 4 zeros left, the second row has 2! combinations, while the third row has 6! combinations - I am simplifying somewhat, because as you select a specific cell to fill, you will lower the number of combinations left in the other two rows
in your current algorithm, you are always trying to fill the lowest row with the lowest number left what if the solution requires a high number like 6 at (0,0), but you've inserted a 1 because a 1 is also legal at position (0,0) and you are going filling from bottom to top with lowest available numbers first?
I will look at your current code some more, but consider the case I have listed - I don't want to spend time correcting your current code and then find that you have to chuck it because your general algorithm doesn't work
in fact, it may be a good exercise to describe first in words, the steps in your algorithm, so we can confirm that it will actually work!
edit: think carefully about what I said in regards to the combinations - you may be able to create a more tractable algorithm using possible combinations
Last edited on
0 5 3 0 0 0 2 8 7 0 6 4 1 8 7 0 3 9 9 8 0 0 0 0 0 4 0 |
ok I see this:
(gdb) p row1
$26 = {1, 0, 0, 4, 0, 6, 0, 0, 9}
(gdb) p row2
$27 = {0, 2, 0, 0, 5, 0, 0, 0, 0}
(gdb) p row3
$28 = {1, 2, 3, 0, 5, 6, 7, 0, 0}
(gdb) p box1
$29 = {1, 2, 0, 0, 0, 0, 7, 0, 0}
(gdb) p box2
$30 = {0, 2, 3, 4, 5, 6, 0, 0, 9}
(gdb) p box3
$31 = {1, 0, 0, 0, 5, 6, 0, 0, 0} |
tell me what your algorithm is supposed to do - what numbers will be inserted where, in what order?
edit: I find this debugging output to be extremely useful for finding a good algorithm - for example, 1 can go into:
1. row1, box1
2. row1, box3 (but not really since 2, 8, and 7 fill those spots)
3. row3, box1
4. row3, box3
so 1 has 3 possible positions
however, 3 can only go into row3 box2 - no degrees of freedom
3, 4, 7, and 9 are the easiest to insert
inserting 1, 2, 5, and 6 will impact the others that have not been inserted yet
edit: I am wrong with that last comment - impacting others or not doesn't depend on number of degrees of freedom. However, it's easier to insert the easy ones first - doing so may actually decrease the degrees of freedom in what's left.
See what happens when you insert 3 in row3, box2 - when you do so, only 2 zeros in row3, box2 - this is a good thing, as it makes smaller your possible solution space!
edit: added input matrix for easier reading
Last edited on
one other thing - do you know how to use stl vectors and maps?
those data structures may actually be quite useful for implementing a fast algorithm.
edit: OOP classes may also be useful here for writing readable code - have you covered them yet?
those data structures may actually be quite useful for implementing a fast algorithm.
edit: OOP classes may also be useful here for writing readable code - have you covered them yet?
Last edited on
Yes, I'm a little familiar with vectors, and I have used classes for several programming exercises. I I completed the book C++ Without Fear this semester and started the first few chapters of Thinking in C++.
My algorithm is likely to have kinks, but this is due to being perplexed at the thought of designing a Sudoku program. It was up to me to do all, if not most of the thinking, and I very rarely ever pseudocode, flowchart, design my programs etc. I always just jumped into them. Now is a time where I could use those skills. I pseudocoded, but not enough.
I basically wanted to tackle the problem of solving a 9 X 9 by building increasingly larger but similar problems, i.e. 3 x 3, 3 x 9, 9 x 3, to perhaps make the design and programming of a 9 x 9 easier. Once again, I've never really practiced design and critical thinking in programming. That is where I'm at a loss. :/ This will be good practice and a good lesson when I complete it.
My algorithm is likely to have kinks, but this is due to being perplexed at the thought of designing a Sudoku program. It was up to me to do all, if not most of the thinking, and I very rarely ever pseudocode, flowchart, design my programs etc. I always just jumped into them. Now is a time where I could use those skills. I pseudocoded, but not enough.
I basically wanted to tackle the problem of solving a 9 X 9 by building increasingly larger but similar problems, i.e. 3 x 3, 3 x 9, 9 x 3, to perhaps make the design and programming of a 9 x 9 easier. Once again, I've never really practiced design and critical thinking in programming. That is where I'm at a loss. :/ This will be good practice and a good lesson when I complete it.
I asked about your knowledge of data structures because keeping account of various features of the initial puzzle can make the search for a solution more effective and more efficient.
ignoring any C++ code for the moment, imagine how you would solve the puzzle:
now, it sounds boring to write out the steps in pseudo-code, but it will actually make your coding clearer and more bug-free: after you translate your pseudo-code into C++ code, you can easily verify if various parts are working correctly.
you already have some basic data structures - the rows and boxes are fine - start from there and describe your algorithm and what you expect it to do at each step: no need to go into extreme detail, but it must be clear enough that we can write out which numbers will be placed where, when following the pseudocode
I often put pseudocode in comments before I code C++ to make sure that I have clearly thought through the algorithm
I recommend that you do the same before you continue to code (fyi, in my last post, I have actually fleshed out 50% of an algorithm)
edit: btw, there is nothing magical about pseudo-coding - just imagine trying to explain to a programmer friend the steps to your algorithm - that's all
ignoring any C++ code for the moment, imagine how you would solve the puzzle:
0 5 3 0 0 0 2 8 7 0 6 4 1 8 7 0 3 9 9 8 0 0 0 0 0 4 0 |
now, it sounds boring to write out the steps in pseudo-code, but it will actually make your coding clearer and more bug-free: after you translate your pseudo-code into C++ code, you can easily verify if various parts are working correctly.
you already have some basic data structures - the rows and boxes are fine - start from there and describe your algorithm and what you expect it to do at each step: no need to go into extreme detail, but it must be clear enough that we can write out which numbers will be placed where, when following the pseudocode
I often put pseudocode in comments before I code C++ to make sure that I have clearly thought through the algorithm
I recommend that you do the same before you continue to code (fyi, in my last post, I have actually fleshed out 50% of an algorithm)
edit: btw, there is nothing magical about pseudo-coding - just imagine trying to explain to a programmer friend the steps to your algorithm - that's all
Last edited on
Topic archived. No new replies allowed.