Судоку - это головоломка с расстановкой чисел. Цель состоит в том, чтобы заполнить сетку
9 × 9
числами таким образом, чтобы каждый столбец, каждая строка и каждая из девяти3 × 3
sub-сеток, составляющих сетку все, содержали все номеров от1
до9
один раз.
Реализуйте алгоритм, который будет проверять, представляют ли заданные
grid
чисел действительную головоломку Судоку в соответствии с правилами компоновки, описанными выше. Обратите внимание, что головоломка, обозначеннаяgrid
, не обязательно должна быть решаемой. - от CodeFights
Теперь у меня есть небольшая настройка тестовой среды, поэтому я смог очень быстро приступить к работе (локально). В наши дни настройка среды разработки значительно упростилась! Все доступные инструменты напомнили мне, что пробовать новые языки / фреймворки / стеки и т. Д. - это весело. когда ты можешь сразу же прыгнуть!
Мне нравится играть в судоку; Написание этого простого валидатора оказалось интересным и быстрым испытанием. Моя основная идея заключалась в проверке строк, столбцов, затем квадратов. Строки и столбцы - это просто, но квадраты ... Я знал, что должен быть сложный способ достичь 9 слотов для каждого квадрата, и мне действительно пришлось заставить себя не зацикливаться на этом - просто решите его и затем оптимизируйте позже. Мне приходилось несколько раз устранять проблему из-за перебоев, а также просто для того, чтобы перефокусировать внимание и напомнить себе, чтобы не расстраивались, когда я не вижу сразу хитрого решения ...
function sudoku2(grid) { var collapsed = [[], [], []]; //Guaranteed to be 9x9. Guaranteed to have '.' or 1-9 for(var x = 0; x < grid.length; x++) { //Check row //grid[x][0-8] for(var i = 1; i <= 9; i++) { if(!isValid(i, grid[x].join(""))) { return false; } } //Check column //grid[0-8][x] var column = []; for(var y = 0; y < grid.length; y++) { column.push(grid[y][x]); collapsed[(x % 3)].push(grid[x][y]); } for(var i = 1; i <= 9; i++) { if(!isValid(i, column.join(""))) { return false; } } } //Check squares // grid[0-2][0-2], grid[0-2][3-5], grid[0-2][6-8] var squares = [[], [], [], [], [], [], [], [], []]; var k = 0; while(k < 9) { for(var j = 0; j < 3; j++) { squares[k].push(collapsed[j].shift()); squares[k].push(collapsed[j].shift()); squares[k].push(collapsed[j].shift()); } for(var i = 1; i <= 9; i++) { if(!isValid(i, squares[k].join(""))) { return false; } } k++; } return true; } function isValid(i, a) { // No number is repeated var first = a.indexOf(i); if(first >= 0) { if(a.indexOf(i, first + 1) >= 0) { return false; } } return true; }
Я проследил и проверил пару локальных тестов, которые у меня были, и протолкнул его через CodeFights ... он прошел, и я двигаюсь дальше! У меня есть повторяющийся код, я думаю, что мог бы сделать его быстрее, это некрасиво, но ... я хочу быстрее собрать первое решение, это то, что я пытаюсь отработать на собеседовании. Я также работаю над тем, чтобы говорить о проблемах, вспоминать терминологию, вычислять Big O ... и поэтому я пишу здесь слова! Big O (n) - худший случай для моего решения - вы проверяете каждый элемент 3 раза (как столбец, строку и квадрат) плюс работа по созданию столбцов и квадратов, но сетка всегда 9x9.
Я хотел бы оптимизировать это решение, но не думаю, что зацикливаться на нем полезно - я хочу тратить свое время на решение множества проблем. Но я держу это в глубине души! На GitHub.
После того, как мое решение пройдет тесты, я хотел бы взглянуть на другие решения. Я был удивлен, что CodeFights поддерживает стрелки, но был разочарован, увидев это в лучшем решении:
Это абсолютно объективно, профессионально и действительно необходимо. Поднимите, пожалуйста, этому парню еще раз большой палец вверх… Вы чувствуете себя хорошо из-за грубости с незнакомцами? Это та культура и отношение, которых я бы хотел избежать. Как интервьюер, я задаю простые вопросы, чтобы помочь мне оценить ваше общее отношение и социальные навыки, потому что эти вещи на самом деле тоже важны. 👍