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