h a l f b a k e r yBaker Street Irregulars
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
browse anonymously,
or get an account
and write.
register,
|
|
|
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.
Negative Sudoku Dot System
http://jeffyepstein.com/docs/other/sudoku
The 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/Sudoku
The first puzzle on this page has the same solution as my example puzzle [imaginality, Apr 15 2008]
[link]
|
| |
So long as every wrong digit appears only once in each row, cell and column this should not cause me any problems. |
|
| |
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 "&". |
|
| |
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. |
|
| |
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? |
|
| |
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? |
|
| |
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? |
|
| |
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. |
|
| |
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. |
|
| |
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). |
|
| |
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? |
|
| |
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. |
|
| |
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? |
|
| |
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. |
|
| |
//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? |
|
| |
I still say the poster ought to post an
example. |
|
| |
Somebody page me when there's an example. I'm intrigued by this and want to see how it works. Or doesn't. |
|
| |
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 |
|
| |
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? |
|
| |
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? |
|
| |
//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....... |
|
| |
//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. |
|
| |
//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. |
|
| |
Actually, if you can solve it by reason
alone, then the second problem is not an
issue (there must be only one solution). |
|
| |
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. |
|
| |
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. |
|
| |
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. |
|
| |
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? |
|
| |
Would it make you guys feel better if I wrote a computerized solver for it? |
|
| |
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. |
|
| |
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] That is a very elegant proof. |
|
| |
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. |
|
| |