Sudoku

[999_Springs]

This should be interesting to hear. I'm trying to test my hypothesis that the proportion of teenagers who do sudoku nowadays (I mean, compared to a few years ago) is decreasing.

[Riobe]

Yeah, but I can only go up to a certain difficulty.

[29403]

No, because I prefer Kakuro, and it's better anyway.

[T3chno]

I prefer Peggle.

[Tunco]

I prefer Sudoku to all of them, I can do it up to "hard" difficulty. "Very hard" ones are very hard.

[George]

There's always Sudoku in the newspaper, but I never do it. The word puzzles are better.

[Titanium]

I got bored of Sudoku a long time ago, I prefer crosswords.

[999_Springs]

The problem with puzzle ratings is that you only ever seem to find these in newspapers and they are REALLY over-rated. To a solver like me, newspaper puzzle ratings are pretty much irrelevant. I find all newspaper puzzles easy, and that is because they are supposed to be easy.

What I mean is: suppose you took a sudoku creator program and started clicking randomly on the grid with your mouse until you get a valid puzzle. There is a reasonable chance that this puzzle may be beyond the level of difficulty of all newspaper puzzles. People who create sudokus for newspapers tend to discard these, publishing only the easy ones.

Here's a little puzzle. I would be interested to see how hard you find it. It should be really easy.

Code: Select all

...|...|...
123|...|...
...|456|...
---+---+---
...|...|417
...|...|...
865|...|...
---+---+---
...|198|...
...|...|526
...|...|...

And, by the way, if anyone can do the 9.0 puzzle in my loading signature WITHOUT guessing, they'll get a prize. I warned you: it's ridiculously hard.

Code: Select all

.62|.78|.95
8.9|3.5|6.7
57.|69.|.8.
---+---+---
.95|784|.6.
7.6|..9|85.
.8.|5.6|7.9
---+---+---
.57|96.|..8
9.8|..7|5.6
6..|85.|97. WARNING: RIDICULOUSLY HARD!!!

[Pixon]

Yep. I love Sudoku. It takes me a while to do the harder ones, though.

[PsychoSnail]

I sometimes do Sudoku. I usually stick to the easier ones, though.

[smartalco]

I used to do quite a few and got pretty good at them, I'll try yours later 999.

[TribulatioN]

I Sudoku. If I'm not drop dead tired, or reading a book, I'd probably end up finding myself completing a puzzle before bed. I do them all, as long it takes.

[scythe]

999_Springs,
Suck it.
362|178|495
819|345|627
574|692|183
---+---+---
195|784|362
746|239|851
283|516|749
---+---+---
457|961|238
938|427|516
621|853|974

Solving time: 2h34m

Oh, and no, I don't play sudoku regularly. It's too much goddamned work.

[Seneschal]

I don't.
But my mum's an addict for all things sudoku, especially "killer".

[999_Springs]

So, it looks like my hypothesis was wrong...

scythe33: I'm trying to make sense of your attachment, but I can't understand what is going on. WHAT IS IT!!!??!? It sort of looks like some bizarre computer solver output. And I don't know where you got the 2f and 2h from.

[scythe]

It's a method I devised to find a solution. Here's how it works:

First, we number the large squares 1 - 9 like so:
1|2|3
-+-+-
4|5|6
-+-+-
7|8|9

then row 1 is 1 2 and 3, row 2 is 4, 5, and 6, column 1 is 1, 4, and 7, column 2 is 2, 5, and 8.

The idea is to list the possible cases for each square, then list the possible cases for each row and column in terms of the possible cases for each square. Now, if the cases are letters, let's say row 1 has possibilities as follows:

r1A = 1A2A3B
r1B = 1A2A3C
r1C = 1B2C3D

and column 1 has possibilities as follows:

c1A = 1A4C7C
c1B = 1C4A7A

then the left 'r' shape has two possiblities:

lrA = c1A * r1A = 1A2A3B4C7C
lrB = c1A * r1B = 1A2A3C4C7C

and we can then plug in the case numbers and see what happens to the puzzle. It's likely that many of the cases will lead immediately to contradictions, and one might even lead to a solution. Alternatively, we can enumerate column 2 and compare it with lrA and lrB, but this is usually slower.

I got the 2f and 2h after enumerating cases and eliminating impossible ones. It's worth mentioning that they were only incidental to solving the puzzle; the real work happened at the bottom.

So let's analyze the solution. Step 1:

Code: Select all

democrat:
dA: b = 1, o = 2, ; = 4
dB: b = 4, o = 1, ; = 2
dC: b = 4, o = 2, ; = 1

independent:
iA: e = 1, / = 4, pt = 23
iB: e = 2, / = 4, pt = 13
iC: e = 4, / = 2, pt = 13
iD: e = 4, / = 1, pt = 23

republican:
rA: h = 1, w[ = 23
rB: h = 2, w[ = 13

We're starting with the middle column. It's not hard to see that it'll be the easiest one.

democrat is the fourth column; it's so named because it's on the left side. independent is the fifth column, and republican is the sixth. dA, dB, and dC are all the ways democrat can look. iA, iB, iC, and iD are all the ways independent can look. We don't care which of p and t is which, since they're in the same square -- so when we enumerate square cases, it won't help us eliminate p and t combinations.

So let's enumerate square cases:

Code: Select all

square 2:				dA	dB	dC	iA	iB	iC	iD	rA	rB
2A: b = 1, h = 2, e = 4		*					*	*		*
2B: b = 4, h = 1, e = 2			*	*		*			*
2C: b = 4, h = 2, e = 1			*	*	*					*
											
square 5:											
5A: o = 1, p = 2, t = 3			*		*			*	*	*
5B: o = 1, p = 3, t = 2			*		*			*	*	*
5C: o = 2, p = 1, t = 3		*		*		*	*		*	*
5D: o = 2, p = 3, t = 1		*		*		*	*		*	*
												
square 8:											
8A: ; = 1, / = 4, w = 2, [ = 3			*	*	*			*
8B: ; = 1, / = 4, w = 3, [ = 2			*	*	*			*
8C: ; = 2, / = 4, w = 1, [ = 3		*		*	*				*
8D: ; = 2, / = 4, w = 3, [ = 1		*		*	*				*
8E: ; = 4, / = 1, w = 2, [ = 3	*						*	*	
8F: ; = 4, / = 1, w = 3, [ = 2	*						*	*
8G: ; = 4, / = 2, w = 1, [ = 3	*					*			*
8H: ; = 4, / = 2, w = 3, [ = 1	*					*			*

Now, each case has three associated sets of column cases: they correspond to possibilities for democrat, independent, and republican for the square case. For two cases to occur together in a case for the whole of column 2, they must share a democrat case, an independent case, and a republican case. So, for example, 2A can't occur with 5B since they don't share any democrat cases. We've effectively reduced an exclusive problem, finding sets that don't intersect, to an inclusive one -- finding sets that do. The layout of the stars is a visual aid that makes it easier to tell which combinations are possible and which ones aren't. After combining cases, we're left with just eight possibilities for column 2.

Code: Select all

column 2:
c2A:	2A5C8G	dAiCrB
c2B:	2A5C8H	dAiCrB
c2C:	2A5D8G	dAiCrB
c2D:	2A5D8H	dAiCrB
c2E:	2C5A8C	dBiArB
c2F:	2C5A8D	dBiArB
c2G:	2C5B8C	dBiArB
c2H:	2C5B8D	dBiArB

We're actually going to be solving row 1 in a similar manner. I'm going to ignore the details and just give you the cases, of which there are twelve.

Code: Select all

row1:
r1A: 1A2B3E	tAmDlB
r1B: 1A2B3F	tAmDlB
r1C: 1A2C3G	tAmClC
r1D: 1A2C3H	tAmClC
r1E: 1B2A3M	tAmBlE
r1F: 1B2A3N	tAmBlE
r1G: 1B2B3C	tCmAlD
r1H: 1B2B3D	tCmAlD
r1I: 1C2C3A	tCmClA
r1J: 1C2C3B	tCmClA
r1K: 1D2A3G	tDmBlC
r1L: 1D2A3H	tDmBlC

Now that we've got a row and a column, we can try to combine them. Since square 2 can only have one case at a time, the 2-case from the row case must match the 2-case from the column case. However, this will give us a ridiculous number of cases to enumerate -- 32 to be exact. It's time for us to cheat, and remember that pt, w[, and ij are interchangeable -- at least for now, which means that 5C is equivalent to 5D, 3A is equivalent to 3B, 8G = 8H, and so on, reducing the number of cases for the rows and columns:

Code: Select all

column 2:
c2A:	2A 5(C, D) 8(G, H)
c2B: 2C 5(A, B) 8(G, H)

row 1:
r1A: 1A2B3(E, F)	
r1C: 1A2C3(G, H)	
r1E: 1B2A3(M, N)
r1G: 1B2B3(C, D)
r1I: 1C2C3(A, B)
r1K: 1D2A3(G, H)

so combining cases, we find just four cases for the middle 't' shape:

Code: Select all

middle 'T':
mtA:	1A 	2C 	3(G, H)	5(A, B)	8(C, D)
a = 1, b = 4, c = 3, d = 4, e = 1, f = 2, g = 3, h = 2, o = 1, ; = 2, / = 4, ij = 14, pt = 23, w[ = 13
1	6	2	|	4	7	8	|	3	9	5      
8	4	9	|	3	1	5	|	6	2	7       

5	7	3	|	6	9	2	|	4	8	1       
-	-	-	+	-	-	-	+	-	-	-   
3	9	5	|	7	8	4	|	1	6	23   

7	2	6	|	1	3	9	|	8	5	4   

4	8	1	|	5	2	6	|	7	3	9      

-	-	-	+	-	-	-	+	-	-	-      

2	5	7	|	9	6	1	|	3	4	8

9	3	8	|	2	4	7	|	5	1	6

6	1	4	|	8	5	3	|	9	7	23
mtB:	1B	2A	3(M, N) 5(C, D) 8(G, H)
a = 3, b = 1, c = 4, d = 1, e = 4, f = 2, g = 4, h = 2, o = 2, ; = 4, / = 2, ij = 13, pt = 13, w[ = 13
3	6	2	|	1	7	8	|	4	9	5      
8	1	9	|	3	4	5	|	6	2	7       

5	7	4	|	6	9	2	|	1	8	3       
-	-	-	+	-	-	-	+	-	-	-   
1	9	5	|	7	8	4	|	3	6	2   

7	4	6	|	2	3	9	|	8	5	1   

2	8	3	|	5	1	6	|	7	4	9      

-	-	-	+	-	-	-	+	-	-	-      

4	5	7	|	9	6	1	|	2	3	8

9	3	8	|	4	2	7	|	5	1	6

6	2	1	|	8	5	3	|	9	7	4
mtC:	1C	2C	3(A, B) 5(A, B) 8(C, D)
a = 3, b = 4, c = 1, d = 4, e = 1, f = 2, g = 1, h = 2, o = 1, ; = 2, / = 4, ij = 34, pt = 23, w[ = 13
134a	6	2	|	14b	7	8	|	134c	9	5      
8	14d	9	|	3	14e	5	|	6	2f	7       

5	7	134g	|	6	9	2h	|	134i	8	134j       
-	-	-	+	-	-	-	+	-	-	-   
123k	9	5	|	7	8	4	|	123l	6	123m   

7	1234n	6	|	12o	123p	9	|	8	5	1234q   

1234r	8	134s	|	5	123t	6	|	7	134u	9      

-	-	-	+	-	-	-	+	-	-	-      

1234v	5	7	|	9	6	13w	|	1234x	134y	8

9	13z	8	|	24;	24/	7	|	5	13,	6

6	1234.	134'	|	8	5	13[	|	9	7	1234]
mtD:	1D	2A	3(G, H)	5(C, D) 8(G, H)
a = 4, b = 1, c = 3, d = 1, e = 4, f = 2, g = 3, h = 2, o = 2, ; = 4, / = 2, ij = 14, pt = 13, w[ = 13
134a	6	2	|	14b	7	8	|	134c	9	5      
8	14d	9	|	3	14e	5	|	6	2f	7       

5	7	134g	|	6	9	2h	|	134i	8	134j       
-	-	-	+	-	-	-	+	-	-	-   
123k	9	5	|	7	8	4	|	123l	6	123m   

7	1234n	6	|	12o	123p	9	|	8	5	1234q   

1234r	8	134s	|	5	123t	6	|	7	134u	9      

-	-	-	+	-	-	-	+	-	-	-      

1234v	5	7	|	9	6	13w	|	1234x	134y	8

9	13z	8	|	24;	24/	7	|	5	13,	6

6	1234.	134'	|	8	5	13[	|	9	7	1234]

For each case, we enumerate variables (using the square cases as guides), then plug them in and simplify. mtA is an obvious combination, and, lo and behold, mtB solves the puzzle.

Also, I can totally use the royal 'we', because I'm the King of England.

[smartalco]

holy damn Scythe, I just stared at that puzzle for awhile, and found that I couldn't get a single damn number

999: do you have a simpler method?

[Clicker]

999: do you have a simpler method?

There are easier methods( believe me , a loteasier than this) for solving sudoku's.

And I can solve Sudoku's but not the hard ones, 999: it's very hard.

[smartalco]

There are easier methods( believe me , a loteasier than this) for solving sudoku's.

I know, as I have said, I have done a lot of puzzles and I am generally pretty good at them, I can't even find the first number in this one though...

[scythe]

According to Wikipedia, the proper way to solve sudoku is via exact covers. If I'm interpreting the article correctly, reducing sudoku to exact cover essentially trivializes the solution, so that anyone could solve it with enough time and paper (and a computer can do it in milliseconds).

Figures.

[Pheidippides]

I used to do Sudoku, and was decent on a medium difficulty level, but after reading that article that scythe posted, there's no way I'll ever be more than a casual, every-so-often Sudoku-er. That is some freaking hardcore math. I'll stick to word games. o,o

[EdoI]

I do Sudoku, and when I'm doing it I'm doing all levels. However, I'm doing it rarely.

[Donfuy]

I don't play Sudoku.

It's boring, both physically and mentally.
I mean, it can be interesting, for like 10 mins, then I get tired of it =/


I don't like other "Newspaper Games" either.

[Nexx]

I used to do Sudoku, and was decent on a medium difficulty level, but after reading that article that scythe posted, there's no way I'll ever be more than a casual, every-so-often Sudoku-er. That is some freaking hardcore math. I'll stick to word games. o,o

You don't need to know that math. You don't even really need to know math - it's logic. And yeah, the harder methods use more complicated logic, but it's doable.

And therein lies the trouble with sudoku for me. It's doable (for the most part), it just takes time. So it's been pretty much trivialized. However, writing a computer program to solve sudokus using purely logic - count me in!

[scythe]

What's my damn prize?