I am trying to write a program to solve 9x9 sudoku by forced digits technique.forced digits technique ....finding spot that are empty , that can only be filled by one particular digit. I need help or an idea how to begin ....any help will be greatly appreciated.
sudoku3_bare.pdf sudoku3_forced.pdf
like in first file ...after applying forced technique produces the second file.
Last edited by code_lover; 09-15-2011 at 01:55 AM.
How do you know when you're doing Sudoku by hand if only number can go there?
Quzah.
Hope is the first step on the road to disappointment.
the forced digits is going to check for the only place a value can go and force that value the....I don,t know if my explanation is making sense.
In the first file ....Row 2 Col 4 , value 1 was forced there because that is the only place it can be.
Last edited by code_lover; 09-15-2011 at 02:00 AM.
No, I want to know in your words how you know if only a single number can fit in one spot. Have you ever played Sudoku? If not, you need to go play a couple dozen games. Then, answer that question. How is it you know that only one number fits in one spot? If you can't put that into words, you can't do this problem.
Quzah.
Hope is the first step on the road to disappointment.
I have played a sudoku but this is different ...I am trying to find and reduce the empty boxes ...please try and open the files and go through it and spot the difference
See I don't actually care if you get the answer to this question. Giving you the answer does nothing for me. I just don't care enough. Giving a choice, I would however like it if you actually understood how to get the answer, or failing that, how to think it through for yourself. Luckily for me, I do have a choice in this, and since I don't care to hand you an answer, I'm not going to. Have fun.
Quzah.
Hope is the first step on the road to disappointment.
Well, write down in words how you play sudoku. Step by step. Then try this steps in a actual sudoku. Can you solve it with the steps, write the code for every step. Nothing more, nothing less.
How do you want to set up your program to solve Sudoku?
Generally, there are two ways to do it:
1) your program will solve the puzzle by brute force, efficiently trying all possible values, and when they fail, backtrack and try again. Lots of game playing require backtracking, so this is a great programming skill to learn.
For solving Sudoku, it's also WAY easier than the second way, using logic only, with very few if any guesses:
2) the "human" way. Humans aren't good at working out the possible permutations of an 81 number puzzle, so we use other methods. These methods vary from the ridiculously obvious, to the insanely subtle. These are challenging, and much larger, programs.
Either way, your program should first, handle "naked singles", because they are the most basic, and simple solution to match a number with the cell correctly. Whether the singularity of a number for a cell comes from checking the row it's on, the column it's in, or the 9 cell "house" it shares, doesn't matter. All three parts of the puzzle must conform to Sudoku's ONE RULE.
A lot of programs will explore a few human type techniques, but if they fail to solve the puzzle, then revert to a brute force function to handle the rest of the solving. That is a great compromise position to aim for.
There are several great resources for Sudoku solving on the web. You should bookmark a couple of them, and work through their solving techniques until you fully understand all the ways to work with forced or naked singles.
I don't believe a Sodoku solver would need to be as advanced as Adak say, creating a solver for level 1 to level 3 should be pretty straight forward and not that much of a challenge with the basic stuff you learn in the first few chapters of most books. This does not take into account that someone trying this out would be able to do so by reading a few chapters from a book/tutorial since there is more then simple page reading when it comes to programming. Creating an array for each line/row and 3x3 space should be enough and then simply 'linking' these together with a smart function should provide a fast and fairly basic code to do this. The adding a function to add the single cells (where only one number is possible) and an exclusion function that works with the arrays should be enough. Pointers could probably be avoided but would speed up the program a lot if they are used.
But this thread sound a bit like homework or project works I have read about in other languages so I won't help that much with it. Brute forcing a sudoku sound like wasting a lot of time and processing power, although I do believe this is what OP is supposed to use for this problem as part of the assignment.
EDIT: A few 'storage' arrays will probably be helpful and save some time when getting data for the functions.
Last edited by Newbi2C; 09-16-2011 at 08:56 AM.
A brute force Sudoku solver, can be fairly simple.
A human-style solver which does NO brute force guessing, can be incredibly difficult to code up. Several such program use thousands of line of code, just for the solving portion of the program.
Here's a list of the techniques that are involved for a human style (non trial and error), solver:
A good compromise, is to have a few of the most common functions added to your solver program, and should that fail to solve the puzzle, then have the program call a brute force solving function to finish off the unsolved portion of the puzzle.Basics:
Naked Single
Hidden Single
Naked Pair
Naked Triple
Locked Candidate (1)
Locked Candidate (2)
Naked Quad
Hidden Pair
Hidden Triple
Hidden Quad
Basic/unfinned Fish:
Code:
X-Wing
Swordfish
Jellyfish
Advanced Basics:
Code:
BUG+1
XY-Wing
XYZ-Wing
Uniqueness Tests: Type 1-6
Code:
Unique Rectangle Type 1
Unique Rectangle Type 2 (variant of Type 5)
Unique Rectangle Type 3
Unique Rectangle Type 4 (variant of Type 6)
Unique Rectangle Type 5 (variant of Type 2)
Unique Rectangle Type 6 (variant of Type 4)
Advanced: level 1
Code:
Remote Pairs
2-String Kite, Empty Rectangle, Skyscraper
Colors and Multiple Colors
Fish:
Code:
finned/Sashimi X-Wing
finned/Sashimi Swordfish
finned/Sashimi Jellyfish
Fish -- Franken and mutant
Uniqueness Tests: restricted candidates
Code:
Strong Links on UR candidates (w/o or w/ Naked_Single extension)
Advanced:
Code:
XY-Chain, XY-Loop
Chain, Loop
Forcing Network -- SIN
Etc:
Code:
Templates
This list of techniques will solve nearly all Sudoku puzzles, however.
Sudoku Programming Hierarchy of Techniques:
- Naked Single
- Hidden Single
- Naked Pair
- Locked Candidate 1
- Locked Candidate 2
- Naked Triple
- Naked Quad
- Hidden Pair
- X-Wing
- Swordfish
- Colors
- Multi-Colors
- Hidden Triple
- XY-Wing
- Hidden Quad
Note that most puzzles you see in the newspaper are fairly easy, but there are puzzles out there that will curl your hair. These more difficult puzzles require very subtle logic, if you want to solve the puzzle without using brute force.
Try this one, for instance:
Code:002 | 090 | 107 038 | 600 | 000 400 | 000 | 000 ----+-----+---- 000 | 005 | 000 009 | 010 | 300 000 | 400 | 000 ----+-----+---- 000 | 000 | 004 000 | 007 | 920 806 | 030 | 700
