用于创建数独板的暴力算法
我正在开发的是，最初整个数独板都是空的。 其中一个随机单元（81个中）填充了随机值（1-9）。
现在我想用蛮力方法填充所有剩余的细胞。
从我在谷歌搜索后得知的是，我们应该从第一个单元格开始并用1填充它（如果它有效），然后用2填充第二个单元格（如果它有效，我们将开始检查大于最后填充的单元格，在这种情况下为1，一旦达到9，我们将其重置为1）。
问题是它不能正常工作！
任何人都可以将我链接到确切的算法。
我最近在我的博客中做了一个关于在C＃中创建数独求解器的系列文章; 您可以根据您的目的调整我提供的简单回溯算法。
http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/
以下是回溯方法的实现：
import java.util.Random; public class Sudoku { public static void main(String[] args) { Random rand = new Random(); int r = rand.nextInt(9); int c = rand.nextInt(9); int value = rand.nextInt(9) + 1; Board board = new Board(); board.set(r, c, value); System.out.println(board); solve(board, 0); System.out.println(board); } private static boolean solve(Board board, int at) { if (at == 9*9) return true; int r = at / 9; int c = at % 9; if (board.isSet(r, c)) return solve(board, at + 1); for (int value = 1; value <= 9; value++) { if (board.canSet(r, c, value)) { board.set(r, c, value); if (solve(board, at + 1)) return true; board.unSet(r, c); } } return false; } static class Board { private int[][] board = new int[9][9]; private boolean[][] rs = new boolean[9][10]; private boolean[][] cs = new boolean[9][10]; private boolean[][][] bs = new boolean[3][3][10]; public Board() {} public boolean canSet(int r, int c, int value) { return !isSet(r, c) && !rs[r][value] && !cs[c][value] && !bs[r/3][c/3][value]; } public boolean isSet(int r, int c) { return board[r][c] != 0; } public void set(int r, int c, int value) { if (!canSet(r, c, value)) throw new IllegalArgumentException(); board[r][c] = value; rs[r][value] = cs[c][value] = bs[r/3][c/3][value] = true; } public void unSet(int r, int c) { if (isSet(r, c)) { int value = board[r][c]; board[r][c] = 0; rs[r][value] = cs[c][value] = bs[r/3][c/3][value] = false; } } public String toString() { StringBuilder ret = new StringBuilder(); for (int r = 0; r < 9; r++) { for (int c = 0; c < 9; c++) ret.append(board[r][c]); ret.append("\n"); } return ret.toString(); } } } 在数学的Algorithmics上列出了一些算法。 你所描述的听起来像一个回溯的方法。
看看下面的内容。 请注意，我没有运行它，所以我不能保证它的声明：
http://www.codeproject.com/KB/game/SudokuGen.aspx
代码在VB.NET中，但算法在C＃中是相同的。
这里有一个C＃版本：
http://www.codeproject.com/KB/game/sudokuincsharp.aspx
@Bill the Lizard提供的链接很好地解释了一些事情，而不是我上面提供的实现链接。
我使用了一种没有回溯的方法，尽管while循环可能就是这样。 引用算法书我读过“递归中没有任何东西不能使用迭代重复”。
我一直用我的眼睛检查这个，因为我无法绕过递归方法，即使相对理解递归：
这个方法，我有点指导，在网格检查器中有一个错误，当我发现它时，它似乎现在正在工作。 我正在定位它，因为很难找到完整且正常工作的代码。 IOS SDK。
#define WIDTH 9 #define HEIGHT 9 @interface ViewController () //- (BOOL) numberConflicts:(int)testNum; - (BOOL) number:(int)n conflictsWithRow:(int)r; - (BOOL) number:(int)n conflictsWithColumn:(int)c; - (BOOL) number:(int)n conflictsWithSquareInPointX:(int)x andPointY:(int)y; - (BOOL) number:(int)n conflictsAtGridPointX:(int)xPoint andPointY:(int)yPoint; - (int) incrementSudokuValue:(int)v; @end static int sudoku[WIDTH][HEIGHT]; @implementation ViewController - (void)viewDidLoad { [super viewDidLoad]; /// Initialize it for (int x = 0; x < WIDTH; x++) { for (int y = 0; y < HEIGHT; y++) { sudoku[x][y] = 0; } } /// int tries = 0; for (int j = 0; j < HEIGHT; j++) { for (int i = 0; i < WIDTH; i++) { int num = arc4random()%9 + 1; while ([self number:num conflictsAtGridPointX:i andPointY:j]) { num = [self incrementSudokuValue:num]; tries++; if (tries > 10) { //restart the column tries = 0; for(int count = 0; count < WIDTH; count++) { sudoku[count][j] = 0; } i = 0; } } if(sudoku[i][j] == 0) sudoku[i][j] = num; tries = 0; for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { printf("%i ", sudoku[x][y]); } printf("\n"); } printf("\n"); } } for (int x = 0; x < WIDTH; x++) { for (int y = 0; y < HEIGHT; y++) { printf("%i ", sudoku[y][x]); } printf("\n"); //newline } // Do any additional setup after loading the view, typically from a nib. } - (void)didReceiveMemoryWarning { [super didReceiveMemoryWarning]; // Dispose of any resources that can be recreated. } - (BOOL) number:(int)n conflictsWithRow:(int)r; { for (int y = 0; y < HEIGHT; y++) { if (sudoku[y][r] == n) { return YES; } } return NO; } - (BOOL) number:(int)n conflictsWithColumn:(int)c; { for (int x = 0; x < WIDTH; x++) { if (sudoku[c][x] == n) { return YES; } } return NO; } - (BOOL) number:(int)n conflictsAtGridPointX:(int)xPoint andPointY:(int)yPoint; { if ([self number:n conflictsWithRow:yPoint]) { return YES; } if ([self number:n conflictsWithColumn:xPoint]) { return YES; } if ([self number:n conflictsWithSquareInPointX:xPoint andPointY:yPoint]) { return YES; } return NO; } - (BOOL) number:(int)n conflictsWithSquareInPointX:(int)x andPointY:(int)y; { int leftX = x - (x % 3); //used to use int division // leftX *= 3; int topY = y - (y % 3); // topY *= 3; int rightX = leftX + 2; int bottomY = topY + 2; for(int subY = topY; subY <= bottomY; subY++) //bug was here, used < instead of less N equal to... { for ( int subX = leftX; subX <= rightX; subX++) { if (sudoku[subX][subY] == n) { return YES; } } } NSLog(@"Testing grid at %i, %i", x/3, y/3); NSLog(@"LeftX: %i TopY: %i", leftX, topY); return NO; } - (int) incrementSudokuValue:(int)v; { if (v < 9) { v++; return v; } return 1; }
注意：头文件为空，如果需要，可将其粘贴到iOS单一View应用程序中。
注意：可能无限循环（以上有时会，但非常快），可能需要另一个更全局的“尝试”变量，并重新启动算法作为安全，或给它一个种子/同时做两个
编辑：如果源网格是可解的（或不存在），下面应该是无限循环的安全
#define WIDTH 9 #define HEIGHT 9 @interface ViewController () //- (BOOL) numberConflicts:(int)testNum; - (BOOL) number:(int)n conflictsWithRow:(int)r; - (BOOL) number:(int)n conflictsWithColumn:(int)c; - (BOOL) number:(int)n conflictsWithSquareInPointX:(int)x andPointY:(int)y; - (BOOL) number:(int)n conflictsAtGridPointX:(int)xPoint andPointY:(int)yPoint; - (int) incrementSudokuValue:(int)v; @end static int sudoku[WIDTH][HEIGHT]; @implementation ViewController - (BOOL) fillGridWithNext:(int)next; { for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { if (sudoku[x][y] != 0) { if (x == 8 && y == 8) { return YES; } continue; } for (int count = 0; count < (HEIGHT-1); count++) { if ([self number:next conflictsAtGridPointX:x andPointY:y]) { next = [self incrementSudokuValue:next]; } else { sudoku[x][y] = next; if( [self fillGridWithNext:arc4random()%9+1]) { return YES; } } } sudoku[x][y] = 0; return NO; } } return NO; } - (void)viewDidLoad { [super viewDidLoad]; /// Initialize it for (int x = 0; x < WIDTH; x++) { for (int y = 0; y < HEIGHT; y++) { sudoku[x][y] = 0; } } sudoku[0][0]=9; int next; next = (arc4random()%9)+1; if( [self fillGridWithNext:next]) //seeded { NSLog(@"Solved"); } else { NSLog(@"No solution"); } for (int x = 0; x < WIDTH; x++) { for (int y = 0; y < HEIGHT; y++) { printf("%i ", sudoku[y][x]); } printf("\n"); //newline } // Do any additional setup after loading the view, typically from a nib. } - (void)didReceiveMemoryWarning { [super didReceiveMemoryWarning]; // Dispose of any resources that can be recreated. } - (BOOL) number:(int)n conflictsWithRow:(int)r; { for (int y = 0; y < HEIGHT; y++) { if (sudoku[y][r] == n) { return YES; } } return NO; } - (BOOL) number:(int)n conflictsWithColumn:(int)c; { for (int x = 0; x < WIDTH; x++) { if (sudoku[c][x] == n) { return YES; } } return NO; } - (BOOL) number:(int)n conflictsAtGridPointX:(int)xPoint andPointY:(int)yPoint; { if ([self number:n conflictsWithRow:yPoint]) { return YES; } if ([self number:n conflictsWithColumn:xPoint]) { return YES; } if ([self number:n conflictsWithSquareInPointX:xPoint andPointY:yPoint]) { return YES; } return NO; } - (BOOL) number:(int)n conflictsWithSquareInPointX:(int)x andPointY:(int)y; { int leftX = x - (x % 3); //used to use int division // leftX *= 3; int topY = y - (y % 3); // topY *= 3; int rightX = leftX + 2; int bottomY = topY + 2; for(int subY = topY; subY <= bottomY; subY++) //bug was here, used < instead of less N equal to... { for ( int subX = leftX; subX <= rightX; subX++) { if (sudoku[subX][subY] == n) { return YES; } } } NSLog(@"Testing grid at %i, %i", x/3, y/3); NSLog(@"LeftX: %i TopY: %i", leftX, topY); return NO; } - (int) incrementSudokuValue:(int)v; { if (v < 9) { v++; return v; } return 1; } @end
简介：第一个版本存在缺陷，但（大部分）完成了工作。 它随机生成每一行，如果该行无效，则擦除并重新开始。 这将消除源网格，并且可以永远消失，但大部分时间都可以工作。
较低的代码使用递归。 我不认为它适当地回溯，但它在我的测试中解决了空和半种子网格。 我想我需要保存一个“状态”网格来回溯，但我不是这样做的。 我发帖都是因为他们都回答“蛮力”...我自己，我应该研究递归，我无法解释为什么较低的一个有效，我个人可以帮助做到这一点。
注意：第一个完成后会在眨眼时完成...如果速度意味着比应用程序更可靠（在这种情况下有点反直觉，无限循环，呵呵）。
这种简单的随机游走算法也应该有效（ 但效率低 – 使用风险自负!!! ）：
编辑： – 为无法解决的解决方案添加了修复程序。
对于网格中的每个空单元格
array = Get_Legal_Numbers_for_cell（row，col）;
如果（数组为空）{
Clear_All_cells（）
} else {
number = Random_number_from（array）;
Put_Number_in_Cell（数）;
}
编辑2
如果有人对此感兴趣，则描述使用基于随机的搜索来解决数独的方法 。