Sudoku Generator Initial thoughts (Incomplete)

Sudoku is a great distraction during a busy day. I somehow manage to stay away from this section at a cozy corner of the sports section on "the Hindu".

What if we were to design a sudoku generator which generates a fully formed sudoku template and simply plucks some numbers away depending on the difficulty level?

There are different ways in which we can generate a filled template. I'm thinking about one such (possibly) brute force way here. Comments are welcome!

1) Start from a random first line

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

You can do this in 9! - 9 factorial - ways. (Sigh!)

2)

i)

Construct the next line in such a way that you pick the following 3 from the last 6 in the first row.

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

6P3 ways (6 permuted in 3 slots)

ii)

Repeat the same for the second and third slots

Note: When we are doing this, we have to look for repetitions and consistency.  

For example: 

4 7 5 | 3 2 8 | 6 9 1 ||
3 8 1 | 4 5 1 | -  -  - || (This is wrong!)

Picked 4 5 1 from 4 7 5 and 6 9 1. This is clearly wrong.

It's also possible that we go about doing this over and over. While doing this we need to do some cool swaps while doing the validations in the same row.

4 7 5 | 3 2 8 | 6 9 1 ||
3 8 1 | 4 5 9 | 7 2 6 ||  (This is wrong too!)

4 7 5 | 3 2 8 | 6 9 1 ||
3 8 1 | 4 6 9 | 7 2 5 ||  (This is OK. Upphhh! Let's see...)

3) Pick the next 3 in third row in each 3 x 3 square is pretty much decided. It's only a matter of moving them around. We choose any order. 3 x 3!  

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

With these 3 steps, we can generate the first 3 x 9 section. 

4) Try steps 1 - 3 vertically.

Pick the next 6 from 3 x 2 

7 5

8 1

6 9

Eg., 

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

5)  Pick the next 6 from 

4 5
3 1
2 9

now with validations, of course

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

6)  We're not left with many choices for the next 6. The remaining 3 of each 3 x 2 square can be permuted. 

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

7) It gets tricky from here on... 

In the second 3 x 3, vertically down, we need to pick 6 from

7 1 8

9 3 6

While placing the 6, we need to consider all the basic validations

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

8) 

While trying to arrange 

9 3 6 

1 5 4 

We run into this strange issue where we need to find a not-so-straight-forward swap for 6. 

4 7 5 | 3 2 8 | 6 9 1 ||
3 8 1 | 4 6 9 | 7 2 5 ||
2 6 9 | 1 5 7 | 3 8 4 ||
5 4 2 | 7 8 3 | 9 1 6 ||
7 1 8 | 5 9 4 | 2 3 6 ||  (This is wrong!)
9 3 6
1 5 4
8 2 7
6 9 3

6 cannot be in the 1 x 3 section  2 3 6 because in the section

9 1 6

2 3 6

We need to have 1 - 9 each only once!  

What do we swap 6 with? 4 in 5 9 4? 

Let's see...

4 7 5 | 3 2 8 | 6 9 1 ||
3 8 1 | 4 6 9 | 7 2 5 ||
2 6 9 | 1 5 7 | 3 8 4 ||
5 4 2 | 7 8 3 | 9 1 6 ||
7 1 8 | 5 9 6 | 2 3 4 ||  (This is wrong!)
9 3 6
1 5 4
8 2 7
6 9 3

Oops! How can 4 be there? The vertical

1

5

4

6

4

Has two 4's now. Strict no-no!

Swapping with 3, 

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

Good here!

9) 

Fill the next 3 in the 2 sections

7 8 3

5 7 9 

and

9 1 6

2 4 3

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

10) 

4 7 5 | 3 2 8 | 6 9 1 ||
3 8 1 | 4 6 9 | 7 2 5 ||
2 6 9 | 1 5 7 | 3 8 4 ||
5 4 2 | 7 8 3 | 9 1 6 ||
7 1 8 | 5 9 6 | 2 4 3 ||
9 3 6 | 2 1 4 | 5 7 8 ||
1 5 4 | 8 3 2 | 7 ----|| (This is a blunder again. 7 can't be here. So swap with 2? )
8 2 7
6 9 3

4 7 5 | 3 2 8 | 6 9 1 ||
3 8 1 | 4 6 9 | 7 2 5 ||
2 6 9 | 1 5 7 | 3 8 4 ||
5 4 2 | 7 8 3 | 9 1 6 ||
7 1 8 | 5 9 6 | 2 4 3 ||
9 3 6 | 2 1 4 | 5 7 8 ||
1 5 4 | 8 7 2 | 3-----|| (Swapped with 3. 3 also has the same problem. So do 6 9 3)
8 2 7
6 9 3

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

This is where we will have to do more smart swaps. Check-mate!

Time up. 

Will continue a little later.