psotirov

Sudoku solver

Feb 4th, 2013
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.87 KB | None | 0 0
  1. using System;
  2.  
  3. class Sudoku
  4. {
  5.     static int[,] board = new int[9,9];
  6.  
  7.     static void Main()
  8.     {
  9.         int firstRow = 9;
  10.         int firstCol = 9;
  11.         for (int row = 0; row < 9; row++)
  12.         {
  13.             string line = Console.ReadLine();
  14.             for (int col = 0; col < 9; col++)
  15.             {
  16.                 int num = line[col] - (int)'0'; // takes the digit
  17.                 if (num > 0 && num < 10) board[row, col] = num; // if is digit place it into the board
  18.                 else // we have empty cell
  19.                 {
  20.                     if (firstRow >= row && firstCol > col) // looking for the first empty cell (upper-left)
  21.                     {
  22.                         firstRow = row;
  23.                         firstCol = col;
  24.                     }
  25.                 }
  26.             }
  27.         }
  28.  
  29.         PlaySudoku(firstRow, firstCol);
  30.  
  31.         for (int row = 0; row < 9; row++)
  32.         {
  33.             for (int col = 0; col < 9; col++)
  34.             {
  35.                 Console.Write(board[row, col]);
  36.             }
  37.             Console.WriteLine();
  38.         }
  39.     }
  40.  
  41.     static bool PlaySudoku(int feRow, int feCol)
  42.     {
  43.         bool[] usedDigits = new bool[9]; // for each digit that is used in the current line we set its digit to true
  44.         for (int c = 0; c < 9; c++)
  45.         {
  46.             if (board[feRow, c] > 0) // extract already used row numbers
  47.             {
  48.                 usedDigits[board[feRow, c]-1] = true;
  49.             }
  50.             if (board[c, feCol] > 0) // extract already used column numbers
  51.             {
  52.                 usedDigits[board[c, feCol] - 1] = true;
  53.             }
  54.             if (board[(feRow/3)*3 + c/3,(feCol/3)*3 + c%3] > 0) // extract already used subgrid numbers
  55.             {
  56.                 usedDigits[board[(feRow / 3) * 3 + c / 3, (feCol / 3) * 3 + c % 3] - 1] = true;
  57.             }
  58.         }
  59.  
  60.         for (int digit = 1; digit < 10; digit++)
  61.         {
  62.             if (!usedDigits[digit-1]) // this digit is free to use
  63.             {
  64.                 // try to solve with this digit
  65.                 board[feRow, feCol] = digit; // put the digit into current cell
  66.                 int newRow = feRow;
  67.                 int newCol = feCol;
  68.                 while (newRow < 9 && board[newRow, newCol] > 0) // looking for next empty cell
  69.                 {
  70.                     if (++newCol > 8)
  71.                     {
  72.                         newCol = 0;
  73.                         newRow++;
  74.                     }
  75.                 }
  76.  
  77.                 if (newRow == 9) return true; // GREAT! We have fully filled Sudoku solution
  78.                 if (PlaySudoku(newRow, newCol)) return true; // here is the final exit path from recursion
  79.             }
  80.         }
  81.         board[feRow, feCol] = 0; // restore empty current cell
  82.         return false; // if we are here we don't have a solution -> go upstairs
  83.     }
  84. }
Advertisement
Add Comment
Please, Sign In to add comment