## This is a SuDoku generator in progress

This jar file is an executable.  In windows, where you have Java installed, download the file, then just click on it with the mouse to run it. Or to run it in place, right click and choose to open the file where it is.

### I AM STILL WORKING ON DEBUGGING SOLVE TECHNIQUES AND THIS IS NOT FINISHED. Solve is debugged up to Swordfish. Still no difficulty metric.

At this point, all puzzles can be solved using a brute force technique. The technique used is to guess a number for a cell from all available numbers for the cell then see if it is correct. If it is not, try another until all available numbers are guessed. If no available number works, back up to the previous box and try another number.

SuDoku

Work remaining: code in difficulty metrics - this means that all solve techniques must be added and debugged. The approach is to create puzzles then solve them using various techniques that have varying levels of difficulty. The user is then presented with a puzzle that uses techniques that match the selected difficulty level.

I started this project by trying to randomly populate the board. That did not work.

After some preliminary research I got a backtrack algorithm (see below) to work but it does not generate unique boards. Unique boards are needed to determine difficulty.

I finally implemented an algorithm that seeds the first 3x3 board with random numbers then uses matrix multiplication to generate permutations. I avoided doing the matrix multiplication by looking at the final result and hard coding the transformations into the source. See Math Space treatment of Sudoku problem.

```       // permutate the seed into the 8 other cells.
/*

__________________________________________
SEED	Permutation1 Permutation2
| 0,0 0,1 0,2 | 1,0 1,1 1,2 | 2,0 2,1 2,2 |
0,0 0,1 0,2   0,3 0,4 0,5   0,6 0,7 0,8
| 1,0 1,1 1,2 | 2,0 2,1 2,2 | 0,0 0,1 0,2 |
1,0 1,1 1,2   1,3 1,4 1,5   1,6 1,7 1,8
| 2,0 2,1 2,2 | 0,0 0,1 0,2 | 1,0 1,1 1,2 |
2,0 2,1 2,2   2,3 2,4 2,5   2,6 2,7 2,8
__________________________________________
Permutation3  Permutation4  Permutation5
| 0,1 0,2 0,0 | 1,1 1,2 1,0 | 2,1 2,2 2,0 |
3,0 3,1 3,2   3,3 3,4 3,5   3,6 3,7 3,8
| 1,1 1,2 1,0 | 2,1 2,2 2,0 | 0,1 0,2 0,0 |
4,0 4,1 4,2   4,3 4,4 4,5   4,6 4,7 4,8
| 2,1 2,2 2,0 | 0,1 0,2 0,0 | 1,1 1,2 1,0 |
5,0 5,1 5,2   5,3 5,4 5,5   5,6 5,7 5,8
__________________________________________
Permutation6  Permutation7  Permutation8
| 0,2 0,0 0,1 | 1,2 1,0 1,1 | 2,2 2,0 2,1 |
6,0 6,1 6,2   6,3 6,4 6,5   6,6 6,7 6,8
| 1,2 1,0 1,1 | 2,2 2,0 2,1 | 0,2 0,0 0,1 |
7,0 7,1 7,2   7,3 7,4 7,5   7,6 7,7 7,8
| 2,2 2,0 2,1 | 0,2 0,0 0,1 | 1,2 1,0 1,1 |
8,0 8,1 8,2   8,3 8,4 8,5   8,6 8,7 8,8
__________________________________________
*/
String s="";

s = cells[2][2].getText();
cells[1][5].setText(s); cells[0][8].setText(s);
cells[5][1].setText(s); cells[4][4].setText(s); cells[3][7].setText(s);
cells[8][0].setText(s); cells[7][3].setText(s); cells[6][6].setText(s);
s = cells[1][2].getText();
cells[0][5].setText(s); cells[2][8].setText(s);
cells[4][1].setText(s); cells[3][4].setText(s); cells[5][7].setText(s);
cells[7][0].setText(s); cells[6][3].setText(s); cells[8][6].setText(s);
s = cells[0][2].getText();
cells[2][5].setText(s); cells[1][8].setText(s);
cells[3][1].setText(s); cells[5][4].setText(s); cells[4][7].setText(s);
cells[6][0].setText(s); cells[8][3].setText(s); cells[7][6].setText(s);
s = cells[2][1].getText();
cells[1][4].setText(s); cells[0][7].setText(s);
cells[5][0].setText(s); cells[4][3].setText(s); cells[3][6].setText(s);
cells[8][2].setText(s); cells[7][5].setText(s); cells[6][8].setText(s);
s = cells[1][1].getText();
cells[0][4].setText(s); cells[2][7].setText(s);
cells[4][0].setText(s); cells[3][3].setText(s); cells[5][6].setText(s);
cells[7][2].setText(s); cells[6][5].setText(s); cells[8][8].setText(s);
s = cells[0][1].getText();
cells[2][4].setText(s); cells[1][7].setText(s);
cells[3][0].setText(s); cells[5][3].setText(s); cells[4][6].setText(s);
cells[6][2].setText(s); cells[8][5].setText(s); cells[7][8].setText(s);
s = cells[2][0].getText();
cells[1][3].setText(s); cells[0][6].setText(s);
cells[5][2].setText(s); cells[4][5].setText(s); cells[3][8].setText(s);
cells[8][1].setText(s); cells[7][4].setText(s); cells[6][7].setText(s);
s = cells[1][0].getText();
cells[0][3].setText(s); cells[2][6].setText(s);
cells[4][2].setText(s); cells[3][5].setText(s); cells[5][8].setText(s);
cells[7][1].setText(s); cells[6][4].setText(s); cells[8][7].setText(s);
s = cells[0][0].getText();
cells[2][3].setText(s); cells[1][6].setText(s);
cells[3][2].setText(s); cells[5][5].setText(s); cells[4][8].setText(s);
cells[6][1].setText(s); cells[8][4].setText(s); cells[7][7].setText(s);

```

According to the link above a board is unique if:

```
If cell[r][c] = cell[m][n] for some r != m and c != n
then cell[r][n] != cell[m][c]
```

I wrote code to check for uniqueness and the backtrack did not give a unique board but the permutation algorithm always (every time I checked) does.

Here is the backtrack algorithm - It does NOT generate unique boards but can be used for a brute force solution.

```/**
* @(#)SuDoku.java
*
* SuDoku application
*
* @author Kenneth L Moore
* @version 1.00 2011/5/8
*
*  After trying a simple random assignment algorithm I came up with and
*  failing,  I did some research and found:
*
*  Algorithm for generation of board from codeproject.com by The ANZAC
*
*  English Language description of the algorithm:
*
*  Use a backtracking algorithm.  Each square starts with 9 random numbers.
*  Randomly assign numbers until a mistake is made.  If a mistake is made,
*  back up and reassign the previous square.
*
*  Flow:
*
*  Start
*
*   if out of numbers, restore numbers go back 1 and start over
*   get a number for the square
*   if it violates sudoku rules go to start
*   else use it and remove from list
*   go to next square
*
*  Pseudo Code:
*
*  //Make a list of row column assignments for each of the 81 squares on the board
*  rowColList
*  //Assign a shuffled list of 1 through 9 to each of the 81 squares on the board.
*  availableNums
*
*  iterate through the boxes
*  place = 0;
*  while(place < 81)
*      if(no number available){
*         listForPlace = new list()
*         place--
*      }
*      else{
*         num = first availableNum
*         if(num does not violate)
*            assign num
*         remove num from list
*         place++
*      }
*
*
*/
```