Rather than filling some of the Sudoku cells with correct numbers, I propose a Sudoku puzzle where every cell is filled with numbers that are not in that cell. From the perspective of programmers (who are usually already tracking cells as having 9 possible choices), this makes no difference whatsoever to the puzzle. From the perspective of humans, it has several interestic aspects:
1. Increases need for human solver to seek out groups of matched cells. Looking at only one cell will be less common.
2. Increased puzzle granularity. You can give solvers less information when the information is more granulated.
Below is an example anti-sudoku puzzle. "a" indicates that no information about that cell is provided:
6,68,26,a,23,59,a,2,3,
67,a,67,67,3,7,47,47,79,
68,a,26,89,23,9,a,4,a,
8,148,a,48,248,48,148,148,148,
2,123,136,a,238,38,13,13,13,
a,23,69,238,a,78,13,a,13,
a,48,2,a,a,56,568,a,a,
9,a,a,a,235,5,9,a,39,
9,48,24,25,235,57,8,a,289,
Thus, we know that the upper leftmost corner of the puzzle is not a 6 from the puzzle. To get started, notice where 8 must be according to row 4. This puzzle is solveable using only logic. Backtracking and guessing is unneeded.-- aguydude, Apr 11 2008 Negative Sudoku Dot System http://jeffyepstein.com/docs/other/sudokuThe widely used notation for temporary state in Sudoku. You could read this idea as a suggestion to only provide those dots. [jutta, Apr 11 2008, last modified Dec 10 2009] Example solution http://en.wikipedia.org/wiki/SudokuThe first puzzle on this page has the same solution as my example puzzle [imaginality, Apr 15 2008] So long as every wrong digit appears only once in each row, cell and column this should not cause me any problems.-- james_what, Apr 11 2008 You lost me. Are you saying that you start a puzzle and some of the information given is incorrect? Or a puzzle that just includes some jibberish, so instead of 123456789 it would be an "&".-- MisterQED, Apr 11 2008 But it might be difficult to make sure there is a unique solution - some of the wrong numbers might introduce alternative solutions where they are correct and the original numbers wrong.-- DrCurry, Apr 11 2008 Somehow I feel like there has to be a problem with every cell being filled with an incorrect digit, but this early in the morning I can't quite bring it to light.
Edit: DrCurry, your anno wasn't up until after I hit OK. But that's what I was trying to come up with. With all the squares being filled, but incorrectly, isn't there a huge number of possible solutions? Part of the way Sudoku works now is that there can be only one answer based on the digits already present, right?-- Noexit, Apr 11 2008 The way I understand the post, the numbers in the cells aren't wrong (in the sense of misleading), they just all mean the opposite of what they mean in a traditional sudoku. The finished grid would have eight numbers in each cell.
I think I understand the proposal, but I don't see the first conclusion - why does that require seeking out groups of matched cells in a way that regular sudoku doesn't?-- jutta, Apr 11 2008 I don't understand the proposal. When you say "every cell is filled with numbers that are not in that cell", what exactly do you mean? Is it already filled with these numbers that are not in it, or is it to be filled with numbers that are not in it?
And, as [jutta] points out, there is still the same logical interrelationship between cells, only 'in negative' - so where's the advantage?-- MaxwellBuchanan, Apr 11 2008 I don't understand it -am I missing something? I've seen a few variations of Soduko, but prefer the merits of the original anyway.-- xenzag, Apr 11 2008 If this is intended as some way of keeping notes (ie, storing intermediate states), I don't like it. The best way to do a SuDoKu is without making any notes, other than to write in the final digits.-- MaxwellBuchanan, Apr 11 2008 The point is that normally, you're told that at some cell, "This cell is a 9." In this version of the puzzle, instead you would be told, "This cell is not 9 or 8." To state that the cell was a 9, such a puzzle would instead state, "This cell is not 12345678." This results in far more granulated information, since you can now state that a cell is not 0-8 other cells, whereas in standard sudoku you can only state a cell is not 0 other cells or state a cell is not 8 other cells.
In both this and regular Sudoku, you often must seek out matched cells. But in regular Sudoku you can initially discover quite a bit by just using simple candidate elimination (i.e. there is no 1 in this row, that row, that column, this column, so there's a 1 right there).-- aguydude, Apr 12 2008 Ah, OK, I get it. Can you post a link to such a puzzle (or even, with a bit of effort, represent it in an annotation) so that we can try it?-- MaxwellBuchanan, Apr 12 2008 I still don't get it, but I'm bored now. Try the Sunday Times (UK of course) "very hard" sudoku, if you find the rest of them too easy. It's usually takes me a good hour to solve. They may have on-line examples.-- xenzag, Apr 12 2008 I feel dense. Maybe I'm hung up on the word "every" in the idea. Each cell is going to tell you what the digit is *not*? Is this correct? Or do you mean that some cells are going to tell you what the digit is not, and the rest remain blank? I'm with MB, asking for a demo. Or are you saying that I, the solver, fill in every digit that is not in that cell?-- Noexit, Apr 14 2008 I think the idea is like this. In a regular SuDuKo, you're given a few digits to begin with (eg, a "7" in one cell). In this version, you would instead be told something like "This cell is not a 1,2,3,4 or 8", meaning that it could be a 7, or a 5, 6 or 9.
In other words, it makes it possible to give you "partial clues" which limit the possible numbers in a cell, but don't necessarily tell you which digit it is.
Definitely need a working example.-- MaxwellBuchanan, Apr 14 2008 //In this version, you would instead be told something like "This cell is not a 1,2,3,4 or 8", meaning that it could be a 7, or a 5, 6 or 9.//
That's how I read it, too, Max.
You don't even have to phrase it negatively, the idea is exactly the same as saying, "This cell is 1, this cell is 2 or 4, this cell is 1, 2, 3, 4, or 9," etc.
I like it. I wonder how difficult such a puzzle would be. My initial guess is that if a normal Sudoku puzzle of moderate difficulty has, say, 20 cells filled in, this type should have the equivalent in fractions, e.g. 40 cells saying "this cell is either 1 or 2", or 60 cells saying, "this cell is either 1, 2 or 3", or a mix thereof.
Since there are only 81 cells on a Sudoku board, if that intuition is correct, most puzzles of this type would be pretty hard.
On the other hand, the number of given cells in normal Sudoku is less relevant to the puzzle's difficulty than their placement and significance, so since this puzzle would have more cells with partial information, that would reduce the difficulty (i.e. having 40 cells with "either 1 or 2" is less difficult than having 20 cells with "1" since more of the cells are going to be in useful locations). Maybe this factor more than compensates for the other factor?-- imaginality, Apr 14 2008 I still say the poster ought to post an example.-- MaxwellBuchanan, Apr 14 2008 Somebody page me when there's an example. I'm intrigued by this and want to see how it works. Or doesn't.-- Noexit, Apr 15 2008 I've put up an example (see link).
One significant difference between my example and the idea as posted: in my example, the numbers in the cell are the values that the cell *could* be - i.e. this is more 'partial sudoku' rather than 'negative sudoku'. I did it this way because it was quicker to do and makes more intuitive sense.
So, for example, the solution for the top left cell in my example could be 1, 5 or 9. (The idea as posted would display 2, 3, 4, 6, 7, and 8 in this cell.)
I haven't tried solving it yet so I don't know how easy/hard it is. If you want to check your solution, it's the same solution as the first puzzle listed on wikipedia's sudoku page. That example gave 30 cells to start with. My example gives:
15 x 1-value cells (e.g. 1) 10 x 2-value cells (e.g. 2 or 3) 5 x 3-value cells (e.g. 4, 5 or 6) 5 x 4-value cells 5 x 5-value cells-- imaginality, Apr 15 2008 One question before I tackle the puzzle. Is it reason-able. In other words, does it permit a solution purely by logical deduction, like a SuDoKu, or can the solution only be arrived at by guessing and testing?-- MaxwellBuchanan, Apr 15 2008 This seems to me to be the equivalent of attempting to solve a crossword in which every word is intentionally misspelled. Am I missing the point?-- jaksplat, Apr 15 2008 //This seems to me to be the equivalent of attempting to solve a crossword in which every word is intentionally misspelled. Am I missing the point?// Ah! The old 'Enigmatic Variations' in the Sunday Telegraph!. I finished one once.......-- gnomethang, Apr 15 2008 //I haven't tried solving it yet// In this case, then, there's a very good chance that it's either (a) not soluble by reason (ie, you can't go through a series of logical deductions to complete the puzzle) or (b) multi-soluble (has many solutions).
You need to figure out a way to avoid both of these.-- MaxwellBuchanan, Apr 15 2008 //You need to figure out a way to avoid both of these.//
No I don't. I never said it was a *working* example. ;) It's more just a visual example of how such a puzzle would look. If it actually works, that's a bonus. Otherwise, I'll leave that tricky task up to the original poster, or until I have some major procastinating to do.
Edit: Which I do. So, working on making it a working one now.-- imaginality, Apr 15 2008 Actually, if you can solve it by reason alone, then the second problem is not an issue (there must be only one solution).-- MaxwellBuchanan, Apr 15 2008 Okay, I added a couple more partial-info squares, and now it's definitely solvable. I think it's not too tricky - easy to medium perhaps.-- imaginality, Apr 15 2008 Yes, but was it soluble in its first form? I got most of the way through, but I suspect I've hit a wall. However, it may just be me.-- MaxwellBuchanan, Apr 15 2008 No, I don't think it was, either. I worked through it and also got stuck midway. But it only took a couple of additions to the given information to make it solvable.-- imaginality, Apr 15 2008 Where's aguydude when you need him? We have now a kinda sorta working model. Is the only way to demonstrate this accurately going to be a complete bake-off?-- Noexit, Apr 16 2008 Would it make you guys feel better if I wrote a computerized solver for it?-- aguydude, Apr 24 2008 imaginality: Your puzzle is too easy. The simplest sodoku puzzles have 17 numbers, which is 153 bits of information. An ideal anti-Sudoku puzzle should probably offer less than 125 bits of information, and should seek to avoid giving more than 2-3 bits of information per cell.-- aguydude, Apr 24 2008 With respect, aguydude, the number of bits of information provided is much less significant to the difficulty of the puzzle than their value and location.
I agree that my example puzzle is easy - I said as much - but that's not due to there being too much information given. If you take away more than a few of the given cells, it becomes impossible to solve.
In fact, in negative sudoku, it's trivial to make a puzzle with at least 567 bits of given information that's still impossible to solve uniquely.
Proof: take the solutions to two sudoku puzzles. In each cell of the negative sudoku puzzle, give all the digits except the two digits that appear in that cell in the solutions. This puzzle will tell you at least seven numbers that aren't in each cell, sometimes eight (where the two solutions have the same value for a cell), giving you at least 81 x 7 bits of information, but you can't solve the puzzle uniquely, since both of the solutions would fit with the given information.-- imaginality, Apr 30 2008 [Imaginality] That is a very elegant proof.-- MaxwellBuchanan, Apr 30 2008 The fact that taking away a couple bits of information makes imaginality's puzzle impossible to solve says nothing about its difficulty (proof: see proof by imaginality, extend to show that many puzzles can be trivially made unsolveable).
The difference between impossible to solve and possible to solve but difficult is huge, so comparing the two is meaningless.
However, I do admit that my claim that more or less information makes a puzzle tougher or easier is not really very accurate. My main issue with your puzzle was that it gives only slightly fewer 1-valued cells than a standard Sudoku puzzle would have given, making it too similar to a standard Sudoku puzzle.-- aguydude, May 05 2008 random, halfbakery