Программа нахождения решения Судоку. Только начинающий. Жду конструктивной критики! - 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, если совпадений не было }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д