Программа нахождения решения Судоку. Только начинающий. Жду конструктивной критики! - C#
Формулировка задачи:
Пожалуйста, оцените, и укажите на ошибки: оформления программы, составления комментариев!
using System;
using System.Collections.Generic;
namespace Sudoku_Solver
{
class Program
{
static void Main(string[] args)
{
int index = 0;
int[] sudoku = new int[81] {0,1,0, 7,5,0, 0,6,0, // Вводим судоку
0,2,7, 0,4,3, 5,0,0, // ячейка - один символ
4,0,8, 6,0,0, 0,0,7, // строка - 9 символов по горизонтали
// столбец - 9 символов по вертикали
0,8,0, 0,6,9, 0,0,0, // сегмент - группа из 9 символов
0,0,0, 8,0,0, 6,7,5,
2,0,0, 0,3,7, 0,4,0,
0,7,9, 0,8,0, 0,2,0,
8,0,0, 1,0,6, 0,0,3,
1,3,0, 0,0,5, 0,8,4};
//Вывод судоку на экран
Console.WriteLine("Судоку");
Writeln(sudoku);
if (CheckSudoku(sudoku)) //Условие проверяет в методе правильность судоку
{
//Если судоку правильное, то ищется решение
if (Solver(index, ref sudoku)) //Условие проверяет есть ли решение,
{ //если есть, метод возвращает true и по ref ссылке первое найденное решение
Console.WriteLine("Первое найденное решение Судоку");
Writeln(sudoku);
}
else Console.WriteLine("Нет решений");
}
else Console.WriteLine("Судоку составлен с ошибками");
Console.ReadKey();
}
//Метод проверки судоку на правильность составления
static bool CheckSudoku(int[] sudoku) // метод возвращает true, если судоку составлен правильно
{
for (int index = 0; index < 81; index++)
{
if (9 < sudoku[index] || sudoku[index] < 0) //Проверка значений ячеек в диапазоне 1 до 9
return false;
if (sudoku[index] != 0) //Проверяем на совпадение только ненулевые ячейки
{
//проверяем ячейку на совпадение значения с другими ячейками в строке, столбце, сегменте
if (CheckPossibleValue(sudoku[index], index, sudoku) == false)
return false;
}
}
return true;
}
//Метод поиска решения судоку
static bool Solver(int index, ref int[] sudoku)
{
if ((index < 81) && (sudoku[index] == 0)) //Проверяем ячейки подряд, кроме заполненных и запрещаем выход за пределы массива судоку
{
Stack<int> stackPossibleValues = new Stack<int>(); //инициализируем стек для возможных значений ячейки
for (int possibleValue = 1; possibleValue < 10; possibleValue++) //последовательно проверяем значение от 1 до 9 и записываем в стек
{
if (CheckPossibleValue(possibleValue, index, sudoku)) //если нет совпадений в столбце строке и сегменте
stackPossibleValues.Push(possibleValue); //записываем значение в стек
}
while (stackPossibleValues.Count > 0) //проверяем значения из стека для ячейки, пока стек не опустеет
{
sudoku[index] = stackPossibleValues.Pop(); //присваеваем ячейке значение из стека
if (Solver(index + 1, ref sudoku)) //Метод вызывает сам себя с увеличением индекса массива судоку
return true; //Условие if вернет true, только если достигли конца судоку, т.е. все ячейки заполнены
}
sudoku[index] = 0; //если все значения стека проверены, и из вложенных методов возвращалось false,
return false; //то обнуляем ячейку с номером index, возвращаем предыдущему методу false
}
else if (index < 81) //заполненные ячейки пропускаем.
{
if (Solver(index + 1, ref sudoku) == false)
return false;
}
return true; //возврат true будет при index = 81, т.е. все ячейки заполнены,
//произойдет последовательный выход из всех вложенных методов, т.к. все методы будут возвращать true
}
//Метод проверяее значение на совпадение с другими ячейками в строке, столбце, сегменте
//в метод поступает: проверяемое значение, индекс ячейки, где проверяется это значение, и массив судоку
static bool CheckPossibleValue(int value, int index, int[] sudoku)
{
//проверяем по строке и столбцу
for (int j = 0; j < 9; j++)
{
if (value == sudoku[(index / 9) * 9 + j] //находим первый элемент строки (index / 9) * 9
& index != (index / 9) * 9 + j) //условие чтобы ячейка не сравнивала себя с собой
{
return false; //возвращаем false, если было совпадение значения с ячейками в строке
}
if (value == sudoku[(index % 9) + 9 * j] //находим первый элемент столбца (index % 9) + 9
& index != (index % 9) + 9 * j)
{
return false; //возвращаем false, если было совпадение значения с ячейками в столбце
}
}
//проверяем по сегменту
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 3; k++)
{ //находим первый элемент сегмента ((index / 27 * 27) + (index % 9) / 3 * 3)
if (value == sudoku[(index / 27 * 27) + ((index % 9) / 3 * 3) + (9 * j) + k]
& index != ((index / 27 * 27) + (index % 9) / 3 * 3 + (9 * j) + k))
{
return false; //возвращаем false, если было совпадение значения с ячейками в сегменте
}
}
}
return true; //возвращаем true, если совпадений не было
}
//Просто метод вывода на экран судоку в удобоваримом виде
static void Writeln(int[] sudoku)
{
Console.WriteLine(new string('-', 21));
for (int i = 0; i < 81; i++)
{
Console.Write("{0} ", sudoku[i]);
if (((i + 1) % 3 == 0) & ((i + 1) % 9 != 0))
Console.Write("| ");
if ((i + 1) % 9 == 0)
Console.WriteLine();
if ((i + 1) % 27 == 0)
Console.WriteLine(new string('-', 21));
}
}
}
}Решение задачи: «Программа нахождения решения Судоку. Только начинающий. Жду конструктивной критики!»
textual
Листинг программы
//Метод проверяее значение на совпадение с другими ячейками в строке, столбце, сегменте
//в метод поступает: проверяемое значение, индекс ячейки, где проверяется это значение, и массив судоку
static bool CheckPossibleValue(int value, int index, int[] sudoku)
{
const int lineSize = 9; // кол-во ячеек в строке
const int blockSize = 27; // кол-во ячеек в блоке - три сегмента по горизонтали(три строки)
const int lineSegmentSize = 3; // кол-во строк в сегменте
const int colomnSegmentSize =3; // кол-во столбцов в сегменте
//проверяем по строке и столбцу
for (int j = 0; j < lineSize; j++)
{
if (value == sudoku[(index / lineSize) * lineSize + j] //находим первый элемент строки (index / 9) * 9
&& index != (index / lineSize) * lineSize + j) //условие чтобы ячейка не сравнивала себя с собой
{
return false; //возвращаем false, если было совпадение значения с ячейками в строке
}
if (value == sudoku[(index % lineSize) + lineSize * j] //находим первый элемент столбца (index % 9) + 9
&& index != (index % lineSize) + lineSize * j)
{
return false; //возвращаем false, если было совпадение значения с ячейками в столбце
}
}
//проверяем по сегменту
for (int j = 0; j < lineSegmentSize; j++)
{
for (int k = 0; k < colomnSegmentSize; k++)
{ //находим первый элемент сегмента ((index / 27 * 27) + (index % 9) / 3 * 3)
if (value == sudoku[(index / blockSize * blockSize)
+ ((index % lineSize) / lineSegmentSize * lineSegmentSize) + (lineSize * j) + k]
&& index != ((index / blockSize * blockSize)
+ (index % lineSize) / lineSegmentSize * lineSegmentSize + (lineSize * j) + k))
{
return false; //возвращаем false, если было совпадение значения с ячейками в сегменте
}
}
}
return true; //возвращаем true, если совпадений не было
}