C#学习教程:用于创建数独板的暴力算法分享


用于创建数独板的暴力算法

我正在开发的是,最初整个数独板都是空的。 其中一个随机单元(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

如果有人对此感兴趣,则描述使用基于随机的搜索来解决数独的方法 。

上述就是C#学习教程:用于创建数独板的暴力算法分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注---猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/ckf/1031993.html

发表评论

邮箱地址不会被公开。 必填项已用*标注