Thread: Sudoku Creator (this could be a long one)

Ok, so in the past I attempted to create a Sudoku Creating program. My first step was to create a program that could solve Sudoku Puzzles. After alot of work, that eventually happened. So I then attempted to revise it to create Sudoku Puzzles, but that fails miserably due to logic errors. So I figure I will start from the drawing board again and attempt to do this in my spare time.

I am going to first start of making this as a static 3x3 Sudoku Creator. When I have it working well, I will modify it to be more dynamic and make larger puzzles.

I'm short on time right now (got to get to work), so here is my basic methods that come to mind. I have provided what their return types will probably be and I have not provided method variables.

boolean rowCheck()
bolean colCheck()
boolean boxCheck()
boolean swapBox()
boolean swapRow()
boolean swapCol()
void setNumber()
? getBox() -- Depends on how I do this



So, first off. What sort of collection should I use for this? The first time around I used a 2 Dimensional Array, but that proved to be problematic when I had to deal with each 3x3 box. So that is preferably not my choice. Alternatively, I considered using a 2 Dimensional Linked List of 2 Dimensional Arrays. Where each 2 Dimensional Array will contain a 3x3 box, and they are linked together in a 2 Dimensional Linked List. But that may make it complicated to check horizontally and vertically along lines. Alternatively again, I think I will create a Box class of sorts that contains each box. But I will have to communicate with the other boxes to get their rows/columns when necessary. which could be a problem.

I'll keep updating this as things come to mind. Any help is appreciated.

Ok, so I'm working on figuring out the last part of creating the Sudoku Puzzle. After running through several checks and whatnot, it gets to the point where I have a few blank spots due to logic errors. What I need to do now is swap and insert numbers to fix the current logic errors. By doing so, I will create more logic errors, but those will get solved aswell. I've proven (through doing it by hand) that it is possible to swap around until all the answers are fixed, but I cant seem to think of a way to turn that into an algorithm.

Here is what a puzzle looks like when it comes out (cant really format). 0s indicate a blank spot.

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

And here are two solutions I found doing it by hand

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

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

Can anyone help me work out an algorithm to do the logic swapping? So far, I figure solving via column and inserting based on least amount of collateral damage is best. This mean swapping mainly along column lines inside of boxes and sometimes row lines inside of boxes.

You can easily generate a sudoku by starting with a "base" solved puzzle, then only swap rows/columns that reside in the same row/column of boxes. If you swap the these randomly several times, then randomly remove a bunch of numbers, you'll end up with a sudoku. Note: This method is not guaranteed to generate a "unique solution" sudoku (one that only has one possible solution).

So, for example:

You can swap row 0 with row 2 because they reside in the first 3 rows, and thus the first row of boxes.
You can swap row 3 with row 4 because they reside in the second row of boxes.
You can't swap row 0 with row 4 because they are in different rows of boxes.

The same concept applies to columns.


To solve a sudoku, the simplest solution is to just brute-force it. Just keep putting number into a spot and make sure the puzzle is still solvable. If it isn't try a different number. If you've exhausted all possible numbers for that spot, trace back and try a different number for the previous number to selected. There's few enough combinations that it can be solved by modern computers within a few seconds or less.

There is a pattern to the following simple solution (for each row, shift the previous by 3: caveat: when you reach a boundary (eg row 4/7) shift the first row of the previous block by 1). You can create this pattern every time, or just have them saved in memory:

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

Now shuffle...randomly swap rows and columns that belong to the same 'block' (eg row 1 and 2, column 4 and 6, etc...I'm using 1-based integers here). Swap as many as you want to randomize. Each time you do this you are generating a pseudo random puzzle (and it holds true for other dimensions, just the block and shift size changes). You can also save this solved puzzle as a 'seed' to the next randomization. There is no necessity to backtrack or use brute force. Its actually, in my opinion, a bit elegant.