I’m horrible at keeping things short. So if you don’t want to read the rest, all I want to know is, what’s the next number you’d fill in to solve this puzzle? How did you figure out the next step (what was your technique)?
Okay, now for the longer version. I’ve been working on an online sudoku application on my homepage off and on for the past few months. I’ve got a week off after 1st semester exams before I go back for second semester (don’t ask–my school insists on doing everything its own way), and so I’ve been working on it a bit recently.
One of the features I recently added was a hint feature that would help you out if you get stuck. Even though it technically knows which numbers go in which spaces, the hint algorithm works by ignoring that and solving the puzzle just like you do. The theory is that that way it can offer hints that you could have figured out yourself based on the information currently in the puzzle; it doesn’t just divine an answer.
That’s cool, but it means that the solver algorithm can get stuck just like you. I’m in the process of adding more sub-techniques that it can use so it will get stuck less often. What I’ve been doing is running the solver on the advanced puzzles until it gets stuck. Then, I solve the next step by myself, see what technique I used, and then code that technique into the algorithm. Maybe I’m just worn out, maybe it’s just that it’s late. But I cannot for the life of me figure out the next step in solving this puzzle. I hope it doesn’t come down to any technique involving branching.
Also, I’m aware that there are a number of great resources online that list detailed descriptions of various solving techniques. Now, I’ve gotten so frustrated that it’s become a personal quest to solve this puzzle.
As a final note, the site is still under active development and it hasn’t seen much traffic. If you notice any bugs or have any suggestions, I’d absolutely love to hear them. The link I provided up at the top of the (now very long) post goes directly to the saved puzzle that’s giving me so many problems. If you want to bookmark the page, this link will take you to the normal start page: Online Sudoku (it’s just the link above without the stuff after the question mark).
Look at the second row from the top. One cell has possible values (2,6), another has (6,7), another has (2,7). That’s three possibilities shared across three cells. (Be careful programming that. The shared cells must all be in an exclusive group of nine.) Those digits must go in those three cells, we just don’t know which is which yet. But it means that you can eliminate those as possible values for any other cells in that row. That gets rid of two options for the cell on the far right.
(Another way to look at it is that only two cells in that row have 3 and 8 as possible values. One of them must be a 3, the other an 8.)
You’re right. The exclusive triples technique was going to be what I coded next, but I wasn’t sure if it was going to be useful enough. It looks like it will at least be useful in culling some options.
Of course, it looks like another technique will be necessary to actually figure out the next number, but any progress is good.
There’s another exclusive triple, and then I’ve found one more move after that. Haven’t solved it yet.
I have occasionally seen sudokus where I’ve had to guess to solve them. Assuming the puzzle is properly formed (only one possible solution from the initial state), just follow the consequences of the guess until it solves the puzzle or leads to a paradox. But I’ve often wondered if a sufficiently thorough analysis (probably using methods we haven’t even discussed yet) would detect the correct move without guessing.
Just out of curiousity, where “outside of Boston” are you?
I’m hoping it doesn’t end up requiring branching, because that algorithm will require some big changes. I know at some point it’s going to be unavoidable, though. If you’ve used exclusive triples twice already, it probably makes sense to start coding that one up.
I’m normally in Cambridge, MA, but for the next few days I’m at home outside of D.C. (Northern Virginia).
Last night I implemented the exclusive triples algorithm. Indeed, it only finds those three additional bits of information that Bippy just posted. Although the hint algorithm is now working harder and using an additional technique, it’ll still behaves outwardly just like it did before–it says it can’t solve it.
For convenience, here’s a link to a version of the puzzle after the exclusive triples algorithm has been applied: Updated Puzzle
Incidentally, the hints system keeps its own hidden set of penciled-in marks that result after all the various techniques are applied. If you ever want to replace your marks with the hint system’s, first, hit the hint button to ensure that its marks are up to date, then enter the following into your URL bar and hit enter:
javascript:mainGrid.workingListsToMarks();
This is more of a hidden, debug feature. That’s why it doesn’t have any UI representation.
After slaving over this puzzle for a long time (and I’m sure many of you have, too), I’ve come to the conclusion that the puzzle can’t be solved without branching (that is, guessing for one space and seeing if that assumption leads to a conclusion or contradiction). Of course if anyone can still demonstrate that there is a way to solve it without branching, that’d be great too.
Branching is pretty hard to implement in a solver because it essentially requires you to look into the future, so I’ll leave that in my long-term to-do list. Instead, I made a compromise: I just added a feature that should make branching a little less tedious. Basically, when you branch, the puzzle remembers the state it was in. Any changes you make in branch mode will be remembered and visibly marked with a little dot. If your assumption leads to a conclusion, that’s great. If it leads to a contradiction, however, then you can turn branch mode off, which will reset your puzzle to exactly what it was at the branch point (the timer will have kept running, of course). In addition, when in branch mode, the hint giver is on the lookout for contradictions–spaces that have no valid solutions–and will point them out if you ask for a hint. Branch mode is an advanced feature for advanced users, and as such its button is hidden in the more options area at the bottom of the application (hit the options button to slide the drawer out). Hitting the ‘b’ key will also toggle branch mode.
Sorry to use the thread to essentially just announce a new feature–I just wanted to give some sort of closure to this frustrating puzzle. Thanks for all of your help, everyone!
There are four 7s left to be placed. Placing a 7 in e2 would fix two more 7s, at i3 and d7; these two placements would then make a 7 placement in the lower-right square impossible. So the 7 must go in d3. (Solution from there is straightforward.)
Schematically, the possible positions of the 7s in the four remaining 3x3 squares look like this: (abcdefghij where a 7 can go, . where it can’t; rows and columns with 7s already placed have been deleted):
. a | c .
b . | . d
----+----
e f | h i
. g | . j
a=7 implies e=7 implies j=7 implies c=7, inconsistent; so b=7 and c=7.
I had similar thoughts to those of Omphaloskeptic. Namely, you can try to tie together cells that are same/different and see if there is a contradiction. I suppose in the end that works out to branching (“If this is a 7, then…”) so it might not help at all.
I assume you’ve coded the technique of looking at not only what is possible in a cell, but what is possible for a given number? I’ve often found cases where it is possible for a given cell to have multiple values, but 1 of those values can go in that spot only. A rather contrived example:
If that is all you start with, there is only 1 spot left for the 4 in the top row, but at first glance it looks like 4,6,7,8 or 9 is possible with 4 having two possibilities in that same group of cells (upper right).