Назад к вопросам
Лига Цифровой Экономики
Junior — Middle
66
Каким образом вы реализуете систему для автоматической проверки решений судоку?
Компании, где спрашивали
Ответ от нейросети
sobes.tech AI
Для автоматической проверки решений судоку можно реализовать алгоритм, который проверяет три основных условия:
- В каждой строке все цифры от 1 до 9 встречаются не более одного раза.
- В каждом столбце все цифры от 1 до 9 встречаются не более одного раза.
- В каждом из девяти 3x3 блоков все цифры от 1 до 9 встречаются не более одного раза.
Примерный подход:
- Представить судоку в виде двумерного массива int[9][9].
- Для каждой строки, столбца и блока создать структуру (например, boolean[] или Set<Integer>) для отслеживания уже встреченных цифр.
- Пройтись по всем ячейкам и проверять, не нарушается ли правило уникальности.
Пример кода на Java:
public boolean isValidSudoku(int[][] board) {
for (int i = 0; i < 9; i++) {
boolean[] rowCheck = new boolean[9];
boolean[] colCheck = new boolean[9];
boolean[] boxCheck = new boolean[9];
for (int j = 0; j < 9; j++) {
// Проверка строки
if (board[i][j] != 0) {
if (rowCheck[board[i][j] - 1]) return false;
rowCheck[board[i][j] - 1] = true;
}
// Проверка столбца
if (board[j][i] != 0) {
if (colCheck[board[j][i] - 1]) return false;
colCheck[board[j][i] - 1] = true;
}
// Проверка блока
int rowIndex = 3 * (i / 3) + j / 3;
int colIndex = 3 * (i % 3) + j % 3;
if (board[rowIndex][colIndex] != 0) {
if (boxCheck[board[rowIndex][colIndex] - 1]) return false;
boxCheck[board[rowIndex][colIndex] - 1] = true;
}
}
}
return true;
}
Этот метод проверяет, что текущая доска судоку корректна. Для проверки решения нужно убедиться, что все ячейки заполнены и метод возвращает true.