http://norvig.com/sudoku.html
http://www.dos486.com/sudoku/index.shtml
Sudoku Generator
http://www.dos486.com/sudoku/index.shtml
http://www.codeproject.com/Articles/23206/Sudoku-Algorithm-Generates-a-Valid-Sudoku-in
Others:
http://johannesbrodwall.com/2010/04/06/why-tdd-makes-a-lot-of-sense-for-sudoko/
https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html
Solving a Sudoku Puzzle
Rules:
http://en.algoritmy.net/article/42521/Sudoku ===> Java implementation: HumanizedSudokuSolver
http://hodoku.sourceforge.net/en/tech_singles.php
http://planetsudoku.com/how-to/how-do-you-sudoku.html
https://potatocodes.wordpress.com/2014/09/07/solving-a-sudoku-puzzle/
https://github.com/JunJi-T/SudokuBackTrack/blob/master/SudokuBackTrack.java
Full House/Last Digit
http://www.sadmansoftware.com/sudoku/hiddensingle.htm
Naked Single (Singleton, Sole Candidate)
Whilst solving Sudoku puzzles, it is often the case that a cell can only possibly take a single value, when the contents of the other cells in the same row, column and block are considered. This is when, between them, the row, column and block use eight different digits, leaving only a single digit available for the cell.
Hidden Single (Unique Candidate)
If a cell is the only one in a row, column or block that can take a particular value, then it must have that value. All rows, columns and blocks, must contain each of the digits 1 to 9, so if there is only one cell that can hold a particular value, then it must hold that value.
For example, in the partial Sudoku puzzle below, the marked cell is the only one in block five that can hold a 2, and so it must hold a 2.
Backtracking | Set 7 (Sudoku) | GeeksforGeeks
http://massivealgorithms.blogspot.com/2014/07/backtracking-set-7-sudoku-geeksforgeeks.html
LeetCode - Valid Sudoku | Darren's Blog
http://massivealgorithms.blogspot.com/2014/06/leetcode-valid-sudoku-darrens-blog.html
http://bangbingsyb.blogspot.com/2014/11/leetcode-valid-sudoku-sudoku-solver.html
http://www.geeksforgeeks.org/program-sudoku-generator/
http://www.dos486.com/sudoku/index.shtml
Sudoku Generator
http://www.dos486.com/sudoku/index.shtml
- Randomly choose a cell with more than one candidate
- Populate that cell with a random value from among its candidates
- Try solving the puzzle
- If no solutions exist, reject this placement and try again
- If exactly one solution exists, we are done
- If multiple solutions exist, keep this placement and return to step one.
http://www.codeproject.com/Articles/23206/Sudoku-Algorithm-Generates-a-Valid-Sudoku-in
Others:
http://johannesbrodwall.com/2010/04/06/why-tdd-makes-a-lot-of-sense-for-sudoko/
https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html
Solving a Sudoku Puzzle
Rules:
http://en.algoritmy.net/article/42521/Sudoku ===> Java implementation: HumanizedSudokuSolver
http://hodoku.sourceforge.net/en/tech_singles.php
http://planetsudoku.com/how-to/how-do-you-sudoku.html
https://potatocodes.wordpress.com/2014/09/07/solving-a-sudoku-puzzle/
https://github.com/JunJi-T/SudokuBackTrack/blob/master/SudokuBackTrack.java
Full House/Last Digit
http://www.sadmansoftware.com/sudoku/hiddensingle.htm
Naked Single (Singleton, Sole Candidate)
Whilst solving Sudoku puzzles, it is often the case that a cell can only possibly take a single value, when the contents of the other cells in the same row, column and block are considered. This is when, between them, the row, column and block use eight different digits, leaving only a single digit available for the cell.
Hidden Single (Unique Candidate)
If a cell is the only one in a row, column or block that can take a particular value, then it must have that value. All rows, columns and blocks, must contain each of the digits 1 to 9, so if there is only one cell that can hold a particular value, then it must hold that value.
For example, in the partial Sudoku puzzle below, the marked cell is the only one in block five that can hold a 2, and so it must hold a 2.
Naked Pair, Triplet, Quad (Naked Subset, Disjoint Subset)
This technique is known as "naked pair" if two candidates are involved, "naked triplet" if three, or "naked quad" if four.
If two cells in the same row, column or block have only the same two candidates, then those candidates can be removed from the candidates of the other cells in that row, column or block. This is because one of the cells must hold one of the candidates, and the other cell must hold the other candidate - so neither can go in any of the other cells.
This technique can be applied to more than two cells at once, but in all cases, the number of cells must be the same as the number of different candidates. Each cell doesn't need to have every member of the subset as candidates, but no cell can have any candidates outside the subset.
https://gigaom.com/2012/10/12/meet-the-algorithm-thats-way-better-than-you-at-sudoku/
A difficult puzzle will provide a minimal amount of information, just a few seemingly random spaces filled in, but the rules regarding each space, row, column and 3-by-3 region mean there’s only one correct way to complete the whole puzzle. Applying such an algorithm to systems with similar rules in place could mean even faster prediction of how those systems will evolve or what shape they’ll ultimately take.
http://www.nature.com/srep/2012/121011/srep00725/full/srep00725.html
http://blog.forret.com/2006/08/a-sudoku-challenge-generator/
STEP 2: SHUFFLE THE GRID AROUND
There are a couple of transformations that we can apply on a Sudoku grid while still keeping it in a valid state. They are:
swapping two rows in same group: when you swap 2 rows within the same ‘group’ (within the 3×3 borders), the Sudoku requirements remain fulfilled
swapping two columns in same group: the vertical version of the previous one.
swapping two groups of rows: when you swap two 9×3 groups of cells, that keeps the grid valid too.
swapping two groups of columns: vertical version of the previous one
transposing the whole grid (the columns become the rows and vice versa)
STEP 3: ERASE A NUMBER OF CELLS
number of cells to erase: this is one of the most important factors that define the difficulty level of a Sudoku puzzle.
http://ssjs.chinajournal.net.cn/EditorA/WebPublication/paperDigest.aspx?paperID=SSJS200921000&isCnki=ck01
设计一个算法用以生成各种难度等级的数独题,通过对游戏规则的分析,首先从以下三个方面定义难度等级:已知格总数、已知格的分布和穷举搜索复杂度.本算法采用"挖洞"思想,经过以下两步生成数独题:1)运用拉斯维加斯随机算法生成一个终盘;2)采用以下五个操作"抹去"一部分数字来生成数独题:①根据所需要的难度等级选取一种挖洞顺序;②制定两个约束来控制已知格的分布;③通过深度优先搜索来求解,从而保证"挖去"一个数字后该数独题仍有唯一解;④引入剪枝技术来避免无效的"挖洞"尝试;⑤对"挖"好"洞"的数独题进行等效对称变换,以增加题目的多样性.可以生成游戏者所需要的任意5种难度的数独题.经过对算法时间和空间复杂度的分析,论证了本算法的有效性.对"挖洞法"的研究成果可总结为以下三个方面:1)通过对"挖洞"顺序的大量试探,找到了可生成高难度数独题的"挖洞"顺序;2)采用反证法来判断一个数独题解的唯一性;3)通过避免"回溯"和"重填"来降低算法的运行时间.
https://github.com/cokecoffe/sudoku/tree/master/Resource
整个生成数独题的算法分为两步执行：先随机生成一个填满数字且符合游戏约束的终
盘。而后根据所需求的难度等级“抹去”一些数字。每“抹去”一个数字就验证一次解的唯一
性．如此往复直至满足所需的难度要求为止．最后通过适当的等价对称变换后输出该题．
1)生成一个终盘；2)在终盘上“挖洞”；3)对“挖”好的题进行等效变换．
变换1互换任意两种数字的位置(例如将格盘中所有的“1”和所有的“9”互换位置)．
变换2整体互换任意两个小九宫格行或小九宫格列(例如行1、行2和行3组成一个小
九宫格行整体)
变换3在同一个小九宫格行(列)中重排(互换)行(列)．
变换4全盘行、列互换，即矩阵转置．
A difficult puzzle will provide a minimal amount of information, just a few seemingly random spaces filled in, but the rules regarding each space, row, column and 3-by-3 region mean there’s only one correct way to complete the whole puzzle. Applying such an algorithm to systems with similar rules in place could mean even faster prediction of how those systems will evolve or what shape they’ll ultimately take.
http://www.nature.com/srep/2012/121011/srep00725/full/srep00725.html
http://blog.forret.com/2006/08/a-sudoku-challenge-generator/
STEP 2: SHUFFLE THE GRID AROUND
There are a couple of transformations that we can apply on a Sudoku grid while still keeping it in a valid state. They are:
swapping two rows in same group: when you swap 2 rows within the same ‘group’ (within the 3×3 borders), the Sudoku requirements remain fulfilled
swapping two columns in same group: the vertical version of the previous one.
swapping two groups of rows: when you swap two 9×3 groups of cells, that keeps the grid valid too.
swapping two groups of columns: vertical version of the previous one
transposing the whole grid (the columns become the rows and vice versa)
STEP 3: ERASE A NUMBER OF CELLS
number of cells to erase: this is one of the most important factors that define the difficulty level of a Sudoku puzzle.
http://ssjs.chinajournal.net.cn/EditorA/WebPublication/paperDigest.aspx?paperID=SSJS200921000&isCnki=ck01
设计一个算法用以生成各种难度等级的数独题,通过对游戏规则的分析,首先从以下三个方面定义难度等级:已知格总数、已知格的分布和穷举搜索复杂度.本算法采用"挖洞"思想,经过以下两步生成数独题:1)运用拉斯维加斯随机算法生成一个终盘;2)采用以下五个操作"抹去"一部分数字来生成数独题:①根据所需要的难度等级选取一种挖洞顺序;②制定两个约束来控制已知格的分布;③通过深度优先搜索来求解,从而保证"挖去"一个数字后该数独题仍有唯一解;④引入剪枝技术来避免无效的"挖洞"尝试;⑤对"挖"好"洞"的数独题进行等效对称变换,以增加题目的多样性.可以生成游戏者所需要的任意5种难度的数独题.经过对算法时间和空间复杂度的分析,论证了本算法的有效性.对"挖洞法"的研究成果可总结为以下三个方面:1)通过对"挖洞"顺序的大量试探,找到了可生成高难度数独题的"挖洞"顺序;2)采用反证法来判断一个数独题解的唯一性;3)通过避免"回溯"和"重填"来降低算法的运行时间.
https://github.com/cokecoffe/sudoku/tree/master/Resource
整个生成数独题的算法分为两步执行：先随机生成一个填满数字且符合游戏约束的终
盘。而后根据所需求的难度等级“抹去”一些数字。每“抹去”一个数字就验证一次解的唯一
性．如此往复直至满足所需的难度要求为止．最后通过适当的等价对称变换后输出该题．
1)生成一个终盘；2)在终盘上“挖洞”；3)对“挖”好的题进行等效变换．
变换1互换任意两种数字的位置(例如将格盘中所有的“1”和所有的“9”互换位置)．
变换2整体互换任意两个小九宫格行或小九宫格列(例如行1、行2和行3组成一个小
九宫格行整体)
变换3在同一个小九宫格行(列)中重排(互换)行(列)．
变换4全盘行、列互换，即矩阵转置．
http://massivealgorithms.blogspot.com/2014/07/backtracking-set-7-sudoku-geeksforgeeks.html
/* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */bool SolveSudoku(int grid[N][N]){ int row, col; // If there is no unassigned location, we are done if (!FindUnassignedLocation(grid, row, col)) return true; // success! // consider digits 1 to 9 for (int num = 1; num <= 9; num++) { // if looks promising if (isSafe(grid, row, col, num)) { // make tentative assignment grid[row][col] = num; // return, if success, yay! if (SolveSudoku(grid)) return true; // failure, unmake & try again grid[row][col] = UNASSIGNED; } } return false; // this triggers backtracking}http://massivealgorithms.blogspot.com/2014/06/leetcode-valid-sudoku-darrens-blog.html
http://bangbingsyb.blogspot.com/2014/11/leetcode-valid-sudoku-sudoku-solver.html
http://www.geeksforgeeks.org/program-sudoku-generator/
- In all 9 sub matrices 3×3 the elements should be 1-9, without repetition.
- In all rows there should be elements between 1-9 , without repetition.
- In all columns there should be elements between 1-9 , without repetition.
A simple naive solution can be.
- Randomly take any number 1-9.
- Check if it is safe to put in the cell.(row , column and box)
- If safe, place it and increment to next location and go to step 1.
- If not safe, then without incrementing go to step 1.
- Once matrix is fully filled, remove k no. of elements randomly to complete game.
Improved Solution : We can improve the solution, if we understand a pattern in this game. We can observe that all 3 x 3 matrices, which are diagonally present are independent of other 3 x 3 adjacent matrices initially, as others are empty.
3 8 5 0 0 0 0 0 0 9 2 1 0 0 0 0 0 0 6 4 7 0 0 0 0 0 0 0 0 0 1 2 3 0 0 0 0 0 0 7 8 4 0 0 0 0 0 0 6 9 5 0 0 0 0 0 0 0 0 0 8 7 3 0 0 0 0 0 0 9 6 2 0 0 0 0 0 0 1 4 5
(We can observe that in above matrix, the diagonal matrices are independent of other empty matrices initially). So if we fill them first, then we will only have to do box check and thus column/row check not required.
Secondly, while we fill rest of the non-diagonal elements, we will not have to use random generator, but we can fill recursively by checking 1 to 9.
Following is the improved logic for the problem. 1. Fill all the diagonal 3x3 matrices. 2. Fill recursively rest of the non-diagonal matrices. For every cell to be filled, we try all numbers until we find a safe number to be placed. 3. Once matrix is fully filled, remove K elements randomly to complete game.
int[] mat[]; int N; // number of columns/rows. int SRN; // square root of N int K; // No. Of missing digits // Constructor Sudoku(int N, int K) { this.N = N; this.K = K; // Compute square root of N Double SRNd = Math.sqrt(N); SRN = SRNd.intValue(); mat = new int[N][N]; } // Sudoku Generator public void fillValues() { // Fill the diagonal of SRN x SRN matrices fillDiagonal(); // Fill remaining blocks fillRemaining(0, SRN); // Remove Randomly K digits to make game removeKDigits(); } // Fill the diagonal SRN number of SRN x SRN matrices void fillDiagonal() { for (int i = 0; i<N; i=i+SRN) // for diagonal box, start coordinates->i==j fillBox(i, i); } // Returns false if given 3 x 3 block contains num. boolean unUsedInBox(int rowStart, int colStart, int num) { for (int i = 0; i<SRN; i++) for (int j = 0; j<SRN; j++) if (mat[rowStart+i][colStart+j]==num) return false; return true; } // Fill a 3 x 3 matrix. void fillBox(int row,int col) { int num; for (int i=0; i<SRN; i++) { for (int j=0; j<SRN; j++) { do { num = randomGenerator(N); } while (!unUsedInBox(row, col, num)); mat[row+i][col+j] = num; } } } // Random generator int randomGenerator(int num) { return (int) Math.floor((Math.random()*num+1)); } // Check if safe to put in cell boolean CheckIfSafe(int i,int j,int num) { return (unUsedInRow(i, num) && unUsedInCol(j, num) && unUsedInBox(i-i%SRN, j-j%SRN, num)); } // check in the row for existence boolean unUsedInRow(int i,int num) { for (int j = 0; j<N; j++) if (mat[i][j] == num) return false; return true; } // check in the row for existence boolean unUsedInCol(int j,int num) { for (int i = 0; i<N; i++) if (mat[i][j] == num) return false; return true; } // A recursive function to fill remaining // matrix boolean fillRemaining(int i, int j) { // System.out.println(i+" "+j); if (j>=N && i<N-1) { i = i + 1; j = 0; } if (i>=N && j>=N) return true; if (i < SRN) { if (j < SRN) j = SRN; } else if (i < N-SRN) { if (j==(int)(i/SRN)*SRN) j = j + SRN; } else { if (j == N-SRN) { i = i + 1; j = 0; if (i>=N) return true; } } for (int num = 1; num<=N; num++) { if (CheckIfSafe(i, j, num)) { mat[i][j] = num; if (fillRemaining(i, j+1)) return true; mat[i][j] = 0; } } return false; } // Remove the K no. of digits to // complete game public void removeKDigits() { int count = K; while (count != 0) { int cellId = randomGenerator(N*N); // System.out.println(cellId); // extract coordinates i and j int i = (cellId/N); int j = cellId%9; if (j != 0) j = j - 1; // System.out.println(i+" "+j); if (mat[i][j] != 0) { count--; mat[i][j] = 0; } } }