简短规则摘要（Google搜索可能会更好）：
如果无法放置数字，则表示创建的数独板无效，将存在一个不能放置数字的正方形。例如。需要填充的正方形在其行中的编号为1至3，在其列中的编号为4至6，在其网格中的编号为7至9，但仍为空。
至此，我知道我需要实现一个递归的回溯算法
问题：我认为这种回溯算法并不是真正的回溯，但最终会陷入一个循环，在该循环中，它至少总是找到与删除前相同的解决方案。因此，已删除的解决方案需要以某种方式进行存储，如果在需要删除之前清空解决方案，则再次存储其值...这似乎真的很and肿，并且不必要。
如果有人对我如何在代码中实现简单的回溯算法提出建议，我将不胜感激！
相关代码在SolveSudoku（）中的此代码段的底部。
using System;
using System.Collections.Generic;
static class GenericFunctions
{
public static void Shuffle<T>(this IList<T> list, System.Random rng)
{
int n = list.Count;
while (n > 1)
{
n--;
int k = rng.Next(n + 1);
T value = list[k];
list[k] = list[n];
list[n] = value;
}
}
}
class Functions
{
private int[,] gameboard = new int[9, 9]; //is only read/edited by Get/SetBoardValue
//row from 1 to 9
//column from 1 to 9
//square from 1 to 9
//gameboard from [0-8,0-8]
private bool PlaceOnBoard(int row, int column, int number, int[,] board)
{
if (NotInRCS(row, column, number, board))
{
SetBoardValue(row, column, number, board);
return true;
}
else return false;
}
private int GetBoardValue(int row, int column, int[,] board) //translates between 1-9 and 0-8 declarations
{
if (row < 1 || row > 9) Console.WriteLine("Error. row="+row);
if (column < 1 || column > 9) Console.WriteLine("Error. column="+column);
return board[row - 1, column - 1];
}
private void SetBoardValue(int row, int column, int number, int[,] board) //translates between 1-9 and 0-8 declarations
{
board[row - 1, column - 1] = number;
}
private bool NotInRCS(int row, int column, int number, int[,] board)
{
if (NotPlaced(row, column, board) && NotInRow(row, column, number, board) && NotInColumn(row, column, number, board) && NotInSquare(row, column, number, board)) return true;
else return false;
}
private bool NotPlaced(int row, int column, int[,] board)
{
if (GetBoardValue(row, column, board) == 0) return true;
return false;
}
private bool NotInRow(int row, int column, int number, int[,] board)
{
for (int i = 1; i < 10; i++) if (GetBoardValue(i, column, board) == number) return false;
return true;
}
private bool NotInColumn(int row, int column, int number, int[,] board)
{
for (int i = 1; i < 10; i++) if (GetBoardValue(row, i, board) == number) return false;
return true;
}
private bool NotInSquare(int row, int column, int number, int[,] board)
{
int square = GetSquare(row, column);
int st_row = GetStartRow(square);
int st_column = GetStartColumn(square);
for (int startrow = st_row; startrow < st_row + 3; startrow++)
{
for (int startcolumn = st_column; startcolumn < st_column + 3; startcolumn++)
{
if (GetBoardValue(startrow, startcolumn, board) == number) return false;
}
}
return true;
}
private int GetStartRow(int square)
{
if (square > 0 && square < 4) return 1;
if (square > 3 && square < 7) return 4;
else return 7;
}
private int GetStartColumn(int square)
{
if ((square % 3) - 1 == 0) return 1;
if ((square % 3) - 2 == 0) return 4;
else return 7;
}
private int GetSquare(int row, int column) //takes row/coloumn 1-9 as input and outputs the associated square 1(tl)-9(br)
{
int square = 1;
for (int rou = 1; rou < 4; rou++) if ((3 * rou) - 3 < row && row < (3 * rou) + 1) square += (rou * 3) - 3;
for (int col = 1; col < 4; col++) if ((3 * col) - 3 < column && column < (3 * col) + 1) square += (col - 1);
return (square);
}
private List<int> CreateRandomIntList(System.Random rnd, int maxnumber, int iterations)
{
int calc = maxnumber * iterations;
var numbers = new List<int>();
int counter = 0;
for (int i = 1; i < maxnumber + 1; i++)
{
for (int j = 1; j < iterations + 1; j++)
{
numbers.Add(i);
counter++;
}
}
numbers.Shuffle(rnd);
return numbers;
}
private int PosToRow(int position)
{
return 1 + ((position - 1) / 9);
}
private int PosToCol(int position)
{
if (position % 9 == 0) return 9;
else return position % 9;
}
private void PrintBoard(int[,] board, int change = 0)
{
if (change == 0) Console.WriteLine("____Sudoku Board____");
else Console.WriteLine("____Solution Board____");
for (int row = 1; row < 10; row++)
{
string helpstring = "";
for (int col = 1; col < 10; col++)
{
helpstring = String.Concat(helpstring, String.Format("{0},", GetBoardValue(row, col, board)));
}
Console.WriteLine(helpstring);
}
Console.WriteLine("____________________");
}
private int PossibleSolutions(int row, int col, int[,] board)
{
int count = 0;
for (int num = 1; num < 10; num++)
{
if (NotInRCS(row, col, num, board)) count++;
}
return count;
}
private int[,] SolutionMatrix(int[,] board)
{
int[,] solutions = new int[9, 9];
for (int pos = 1; pos < 82; pos++)
{
int row = PosToRow(pos);
int col = PosToCol(pos);
solutions[row - 1, col - 1] = PossibleSolutions(row, col, board);
}
return solutions;
}
private void SolveSudoku(System.Random rnd, int placed = 0)
{
//Create SolutionMatrix for current board: stores the # of possible solutions for each square
int[,] solutionmatrix = SolutionMatrix(gameboard);
//Search SolutionMatrix for lowest entry
int value = 10; // # solutions
int valuerow = 10; //
int valuecol = 10;
for (int pos = 1; pos < 82; pos++)
{
int row = PosToRow(pos);
int col = PosToCol(pos);
//if no viable cell is found valuerow & valuecol remain 10 here
//following System.IndexOutOfRangeException in gameboard[valuerow-1, valuecol-1] in GetBoardValue
if (solutionmatrix[row - 1, col - 1] < value && solutionmatrix[row - 1, col - 1] != 0)
{
value = solutionmatrix[row-1, col-1];
valuerow = row;
valuecol = col;
}
}
//Short-term 'fix'
if (valuerow == 10 || valuecol == 10)
{
Console.WriteLine("Sudoku cannot be solved. No solutions left.");
return;
}
//Try to place number in lowest entry pos
List<int> numbers = CreateRandomIntList(rnd, 9, 1); //return {1,...,9} shuffled
for (int it = 0; it < 9; it++)
{
if (PlaceOnBoard(valuerow, valuecol, numbers[it], gameboard)) //exception triggers if valuerow/col == 10
{
placed++;
if (placed == 81)
{
PrintBoard(gameboard);
}
else
{
SolveSudoku(rnd, placed);
}
break;
}
else if (it == 8) Console.WriteLine("Cannot Solve Sudoku");
}
}
static void Main()
{
Functions eff = new Functions();
System.Random rng = new System.Random();
eff.SolveSudoku(rng);
}
}
我目前正在研究一种算法，以创建有效的填充数独板，并且需要实现回溯算法。这个问题已经发布了数百次，但是我找不到...