Я использовал метод без обратной трассировки, хотя цикл 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 Single View, если хотите.
Внимание: может выполняться бесконечно (и иногда выше, ноочень быстро), может потребоваться другая, более глобальная переменная «try», и перезапустить алгоритм в качестве меры безопасности или дать ему начальное значение / выполнить оба действия
edit: нижеприведенное должно быть защищено от бесконечных циклов, если источникрешетка решаема (или не существует)
#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
Резюме: первая версия имеет недостатки, но (в основном) выполняет свою работу.Он генерирует каждую строку случайным образом, если строка недействительна, он стирает и начинает заново.Это уничтожит исходные сетки и может работать вечно, но работает большую часть времени.
Нижний код использует рекурсию.Я не думаю, что он корректно возвращается, но он решил пустые и полусеменные сетки на моих тестах.Я думаю, что мне нужно сохранить сетку "State" для возврата, но я этого не делаю.Я публикую оба, так как они оба отвечают на "грубую силу" ... самостоятельно, я должен изучить рекурсию, я не могу объяснить, почему работает нижняя, лично я мог бы помочь с этим.
Примечание: первый заканчивается за мгновение или около того, когда он заканчивается ... если скорость означает больше, чем надежность для вашего приложения (несколько нелогично в этом случае с бесконечным циклом, хе).