스도쿠 솔버의 알고리즘 [,] 모든

Question

좋은 하루,

나는 C# 스도쿠 솔버 응용 프로그램에서 일한지하지만 난 진심으로 스도쿠를 해결하기 위해 알고리즘의 어려움을 과소 평가. 내가 구현할 수있는 알고리즘에 대한 웹 검색을 해왔지만, 나는 내 머리를 얻을 수있는 쉬운 알고리즘을 찾는 행운이 없었다.

내 응용 프로그램에서 작동 할 수있는 알고리즘을 찾았지만,이 사람은 일차원 배열을 사용하여 작동합니다. 다차원 배열과 함께 작동하도록 변경하려고했지만 제대로 작동하지 않습니다.

아무도 내게 조언을 주거나 다차원 배열 (int [,])과 함께 작동하도록 코드를 어떻게 바꿀 수 있는지 보여 줄 수 있습니까? 나는 혼자서 찾지 못하고있다. 이 코드는 여기에서 찾을 수 있습니다 : http://blah.winsmarts.com/2007-1-sudoku_solver_in_c-.aspx

int [,]와 함께 작동하는 다른 알고리즘이 있다면 물론 멋지기도합니다.

오랜 시간 동안 검색을해온 덕분에 크게 도움이 될 것입니다. 미리 감사드립니다.

Answer 1

링크 된 코드는 이미 논리적으로 2D 배열을 사용하며 단지 1D 배열을 뒷면으로 사용합니다. 이 변경 :

private int[] vals = new int[81]; 
public int this[int row, int column] 
{ 
    get { return vals[FindIndex(row, column)]; } 
    set 
    { 
     vals[FindIndex(row, column)] = value; 
    } 
} 

private int FindIndex(int row, int column) 
{ 
    return (((column - 1) * 9) + row - 1); 
} 

사람 :

private int[,] vals = new int[9,9]; 
public int this[int row, int column] 
{ 
    get { return vals[row - 1, column - 1]; } 
    set 
    { 
     vals[row - 1, column - 1] = value; 
    } 
} 

Answer 2

재귀합니다 (- 1 's이 (가) 현재 코드의 나머지 부분과 필요한 row 및 column 시작 1 0 대신에 있기 때문에) 역 추적, 무차별 대항력, 알고리즘

public class SudokoSolver 
{ 
    private readonly Grid _grid; 

    public SudokoSolver(Grid grid) 
    { 
     _grid = grid; 
     _grid.Validate(); 
    } 

    public int?[,] SolvePuzzle() 
    { 
     Solve(); 
     Console.WriteLine(_grid.Assigns + " tries total."); 
     return _grid.Data; 
    } 

    private bool Solve() 
    { 
     int row, col; 
     if (!_grid.FindUnassignedLoc(out row, out col)) 
     { 
      return true; 
     } 

     for (int num = 1; num <= 9; num++) 
     { 
      if (_grid.NoConflicts(row, col, num)) 
      { 
       _grid.Assign(row, col, num); 

       if (Solve()) 
       { 
        return true; 
       } 
       _grid.Unassign(row, col); 
      } 
     } 

     return false; 
    } 

    public int?[,] Data 
    { 
     get { return _grid.Data; } 
    } 
} 

public class Grid 
{ 
    public int?[,] Data { get; private set; } 
    private int _curC = 0; 
    private int _curR = 0; 
    private int _assigns = 0; 

    public Grid(int?[,] data) 
    { 
     Data = data ?? new int?[9,9]; 
    } 
    public bool FindUnassignedLoc(out int row, out int col) 
    { 
     while (Data[_curR, _curC].HasValue) 
     { 
      _curC++; 

      if (_curC == 9) 
      { 
       _curR++; 
       _curC = 0; 
      } 

      if (_curR == 9) 
      { 
       row = -1; 
       col = -1; 
       return false; 
      } 
     } 

     row = _curR; 
     col = _curC; 

     return true; 
    } 

    public bool NoConflicts(int row, int col, int num) 
    { 
     for (int r = 0; r < 9; ++r) 
     { 
      if (Data[r, col] == num) 
      { 
       return false; 
      } 
     } 

     for (int c = 0; c < 9; c++) 
     { 
      if (Data[row, c] == num) 
      { 
       return false; 
      } 
     } 

     int fromC = 3 * (col/3); 
     int fromR = 3 * (row/3); 

     for (int c = fromC; c < fromC + 3; c++) 
     { 
      for (int r = fromR; r < fromR + 3; r++) 
      { 
       if (Data[r, c] == num) 
       { 
        return false; 
       } 
      } 
     } 

     return true; 
    } 

    public void Assign(int row, int col, int num) 
    { 
     _assigns++; 
     Data[row, col] = num; 
    } 

    public void Unassign(int row, int col) 
    { 
     Data[row, col] = null; 
     _curC = col; 
     _curR = row; 
    } 

    public int Assigns 
    { 
     get { return _assigns; } 
    } 

    public void Validate() 
    { 
     if (Data.Length != 81) 
     { 
      throw new Exception("Invalid dimentions!"); 
     } 

     if (!IsLegal()) 
     { 
      throw new Exception("Illigal numbers populated!"); 
     } 
    } 

    public bool IsLegal() 
    { 
     var container = new HashSet<int>(); 
     //vertical check 
     for (int c = 0; c < 9; ++c) 
     { 
      container.Clear(); 
      for (int r = 0; r < 9; ++r) 
      { 
       if (Data[r, c].HasValue) 
       { 
        if (container.Contains(Data[r, c].Value)) 
        { 
         return false; 
        } 
        container.Add(Data[r, c].Value); 
       } 
      } 
     } 
     // horizontal check 
     for (int r = 0; r < 9; ++r) 
     { 
      container.Clear(); 
      for (int c = 0; c < 9; ++c) 
      { 
       if (Data[r, c].HasValue) 
       { 
        if (container.Contains(Data[r, c].Value)) 
        { 
         return false; 
        } 
        container.Add(Data[r, c].Value); 
       } 
      } 
     } 

     // square check 
     var topLeftCorners = new List<Tuple<int, int>> 
     { 
      new Tuple<int, int>(0,0), 
      new Tuple<int, int>(0,3), 
      new Tuple<int, int>(0,6), 
      new Tuple<int, int>(3,0), 
      new Tuple<int, int>(3,3), 
      new Tuple<int, int>(3,6), 
      new Tuple<int, int>(6,0), 
      new Tuple<int, int>(6,3), 
      new Tuple<int, int>(6,6) 
     }; 

     foreach (var topLeftCorner in topLeftCorners) 
     { 
      int fromC = topLeftCorner.Item2; 
      int fromR = topLeftCorner.Item1; 

      container.Clear(); 

      for (int c = fromC; c < fromC + 3; c++) 
      { 
       for (int r = fromR; r < fromR + 3; r++) 
       { 
        if (Data[r, c].HasValue) 
        { 
         if (container.Contains(Data[r, c].Value)) 
         { 
          return false; 
         } 
         container.Add(Data[r, c].Value); 
        } 
       } 
      } 
     } 

     return true; 
    } 
}