User:Robbiemuffin/Sudoku

The objective of Sudoku is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.

5	3
6
	9	8

	7
1	9	5



	6

8
4
7

	6
8		3
	2

		3
		1
		6

	6


4	1	9
	8

2	8
		5
	7	9

→

5	3	4
6	7	2
1	9	8

6	7	8
1	9	5
3	4	2

9	1	2
3	4	8
5	6	7

8	5	9
4	2	6
7	1	3

7	6	1
8	5	3
9	2	4

4	2	3
7	9	1
8	5	6

9	6	1
2	8	7
3	4	5

5	3	7
4	1	9
2	8	6

2	8	4
6	3	5
1	7	9

Notation

Each board is divided into regions labelled A through I, and likewise each region's cels are labelled 1 through nine:

A	B	C
D	E	F
G	H	I

i	ii	iii
iv	v	vi
vii	viii	ix

(top)
(mid)
(bot)

(left)	(midc)	(right)

Such that you can denote the following:

A location

Aii — the ii cel at region A

A mark in a region

H2 — the 2 marked in region H

Segments

E(top) — the top row in region E
B(mid) — the middle row in region B
D(right) — the right column in region D
I(midc) — the middle column in region I

	Aii


	B(mid)


		D(right)

	E(top)



	2


	I(midc)

Basics

Because the rules constrain only rows, columns, and regions, the different plays tend to fit nicely in rows, columns and regions.

Necessitation

Some moves are just required. I bet you can guess how to complete this region:

2	1	9
8	3
6	5	4

Likewise with rows and columms:

	2

1	9	3



2		8



5	6	7

	7
	3
	1

	4
	8
	6

Exclusion

Use numbers across regions to collaboratively narrow down choices:

Region
based exclusion

	2


	5

5

		5

Row/Column
based exclusion



9	1	4



6	3	8

5

		5

Implication

Implication is the first generative move. That is to say, it requires that you generate an in-between state. You can roughly think of generative moves as following a series of component-moves such that the first (and possibly successive) one requires any of a set of outcomes, but cannot specify those outcomes, while the last move takes these into account and thereby produces a specific outcome.

So, even without being able to pin down a number, if you can place it at a row or column within a region, this can place a number elsewhere:

Region
based implication

	2

6	7	8

2	3	4

5

		5

Row/Column
based implication

3
	8



9	1	4



6

5

		5

Implication can get quite cumbersome:

3
	8



9	1	4



6

5



		5

8	2
1	3
9

1	7
9	6

This move reads something like a recipe.

Looking at 5 in context of the ABC row

Region A's 3 and 8 require those numbers for the row to be in B or C
the row in region B is full
therefore there is a 3-8 pair in C
so the row's 5 is in A
D5 blocks the left column
And we can pin 5 to the right column in G because:
1. F5 locks the 5 to the bottom row in I
2. so the entire bottom row is blocked for 5
3. Leaving only right column spaces for 5 in G
therefore G5 blocks the right column
so A5 is in viii

Moves

Outside of easy puzzles, most puzzles cannot be solved without more advanced techniques. However, between any two of these moves, one should generally ensure that all the basic moves have satisified any uncertainties (as they are the easiest to perform, and commonly as you solve a puzzle, each solution changes the puzzle).

The Pidgeonhole Principle

I'm naming this after the Pigeonhole principle because it is a nice, near approximate and I dont know any particular name for the technique. It is perhaps a bit different than you might expect: The technique counts each possible position for each number in a region. If a particular cel in the region is left with only one number, then that number must be in that cel.

(note: this puzzle is credited to RUBYLIPS here, found from this thread at a sudoku programmer's site: Hardness measure?)



	9	7

		3

5

	6
	1
	8


		8
		3

	9
	7
	6

2
4

	1
	4
	5

		2

1

8	9

The basics do not clear any spaces. So now, to apply the pidgeonhole principle, we now mark possible moves in each region. For this example, we will use region C.

Start at 1 and work up to 9. Any number that is in the region obviously won't get any marks.

Here is a detail of the process, how to find the cels to mark for the 2s of region C:



	9	7

		3

5

	6
	1
	8


		8
		3

	9
	7
	6

2
4

	1
	4
	5

		2

1

8	9

In the end you end up with marks like this:

57	6	24
35	1	24
3	8	24

* Since we are looking for a square that only has one mark in it, we stop marking the square once it has two. This is only for convenience. It is also convenient to mark these on a scratch grid you draw on the side, if you are working on paper (although it can be done in your head).

Now we have taken into account all possible moves in all cels in region C. If we have only one mark in a given cel, there is only one possibility in that cel, and thus a solution is found. Therefore, the number at vii is a solution via the pidgeonhole principle:



	9	7

		3

5

	6
	1
3	8


		8
		3

	9
	7
	6

2
4

	1
	4
	5

		2

1

8	9

Naked Subsets

Looking across the board at each row and column, scan for clusters of N cels that allow only N rows or columns. (Thus, in a row or column, any three cels that can only have any of 3 numbers, or fours cels and 4 numbers, etc.)

We will examin the board's middle row and mark cels through exclusion in much the same way as in the pidgeonhole principle:

6
5
	4

	5
	3
	6

		8
		4
		3


789	3789	345 6789


3456 789	89	2


3456 789	1	79

4	5
	6
3


	7
	4

		6

		5

Here 7,8,9 sit alone in 3 squares. There are amung the 3 squares only 3 options, and those numbers must fill one of the select squares. The other squares in the row, therefore, cannot contain those numbers. So we can eliminate those options. In this case, that even gives us D3:

6
5
	4

	5
	3
	6

		8
		4
		3


789	3	3456


3456	89	2


3456	1	79

4	5
	6
3


	7
	4

		6

		5

Even if you don't win a square directly with this method, it is often still useful in the restrictions it places on remaining board possibilities.

* As an aside, it is much easier to see these when you do not need to use them, because the same effect cak be achieved through other means, than when you do.

Hidden Subsets

Hidden subsets can be thought of as related to naked subsets by their mechanism of exclusion. They are also the Row/Column version of the pidgeonhole principle. Unlike with the naked subsets, you're less likely to gestalt these coincidentally while playing, which makes it especially worthwhile to review. The following example is derrived from Sudoku Assistant - Solving Techniques

379	69	8
5

569	1	2

379	4	569


	7
	3

3

7

	8

6

5
		3
6		7

You can see that the only place in the row that 7 and 3 appear are the two highlighted cels. Therefore, those two cels must contain those two numbers. That's two numbers for two cels, therefore we can remove any other numbers from those cels.

37	69	8
5

569	1	2

37	4	569


	7
	3

3

7

	8

6

5
		3
6		7

We will continue working with this puzzle from this point in the next section.

Contingent Exclusion

Contingent exclusion is another generative move. If you are familiar with the game Snake, performing this is a little like that game but the intent is to crash into the body of the snake at a point where it turns.

Preamble

Consider this board again:

37		8
5

	1	2

37	4


	7
	3

3

7

	8

6

5
		3
6		7

If you assumes Ci is 7, you reach a contradiction in F:

37		8
5

	1	2

37	4


	7
	3

3

7

	8

6

5
		3
6		7

Therefore, it must be a three. This resolves the problem in F:

7		8
5

	1	2

3	4


	7
	3

3

7

	8

6

5
		3
6		7

If you consider instead starting in region A (which sets region C), this progresses like the Snake game, setting possibilities along the way — just go from Ai to Ci to Fv. Contingent Exclusion works on the basis of chains of pairs, triplets, etc, which lead along in a path to a contradiction. This contradiction will require that the origin point must be a different option.

The Method

The example herein is from Sudoku sover, where it is credited to Mark Summerville. (Although, the name comes from a different site.)

Consider the board:

17	4	3
6
2

9	8	67
4	2
37		1

2	5

	9	4

9
3
4	1

13		4
6		8
2		9

	7

		3

8	2
17
5	3	4

5
17	4
8	9


		5
7	1

The left column has a 1,7-pair, the middle column has a 1,3,7-triplet. The B region can only have a 7 at vii or at iii, because E7 must be in the middle column. The bottom of the column pairs is also a 1,7-pair, since I7 is already played.

If we start at A and set the pair value there to 7, then G is 1. If G is 1, then H is 7. But if H is 7, then Bvii is 3. That sets Biii to 7 and we reach a contradiction:

17	4	3
6
2

9	8	67
4	2
37		1

2	5

	9	4

9
3
4	1

13		4
6		8
2		9

	7

		3

8	2
17
5	3	4

5
17	4
8	9


		5
7	1

Therefore, A is 1 instead. (Verifying the numbers in each cell is left as an exercise to the curious.)