В принципе у меня есть сетка 3 x 3, которая заполняется двумя цифрами 00 - 99. Некоторые цифры указаны в качестве входных данных, остальные неизвестны. Каковы некоторые предложения о том, как решить такую проблему с помощью грубой силы в C?Макросы квадратов силы магии
EDIT: Извините, я забыл часть проблемы. Каждая строка, столбец и диагональ должны содержать один и тот же номер. Я не хочу, чтобы какой-нибудь код начинал с каких-либо алгоритмов.
Существует простое рекурсивное решение вашей проблемы, которое является примером типа грубой силы, называемой backtracking (google that).
Рекурсивная функция (скажем, fill_next) находит следующую ячейку с неизвестным значением. Если такой ячейки нет, она проверяет квадрат, чтобы увидеть, соответствует ли он требованиям (суммы правильны), и если это так печатает квадрат в качестве решения; он возвращается. Если есть ячейка с неизвестным значением, она зацикливается, пробуя каждое из значений от 0 до 99, в свою очередь, для этой ячейки, а затем вызывает себя рекурсивно, чтобы заполнить следующую неизвестную ячейку.
Как добраться до следующей ячейки с неизвестным значением: вы можете просто перейти к find_next номер следующей ячейки, чтобы начать смотреть; вы можете начать все это, вызвав fill_next (0). Число клеток от 0 до 8, так как у вас есть 9 ячеек. Если вы храните квадрат в 2D-массиве, просто используйте num% 3 и num/3 в качестве индексов.
Это было бы намного проще описать, просто предоставив вам несколько строк кода, которые требуется, но вы сказали, что не хотите этого.
В чем проблема? Вы пытаетесь выяснить, что такое каждый номер? являются ли они любыми критериями, которые должны соответствовать цифрам? Если да, просто угадайте каждый возможный номер в каждом? пока комбинация не будет соответствовать критериям.
Извините, я забыл часть проблемы. Каждая строка, столбец и диагональ должны содержать один и тот же номер. – foo
Как я понимаю, «просто угадайте каждое возможное число в каждом?» Это проблема, которую ОП требует решения. Проверка того, является ли полученный квадрат магическим квадратом, более очевидна. –
3x3 сетка звучит как 2d-массив.
Некоторые примеры код в JS:
var a=[
[ 11, 12, 13 ],
[ 21, 22, 23 ],
[ 31, 32, 33 ]
];
for(var r=0; r<a.length; r++)
for(var c=0; c<a[r].length; c++)
console.log(r+','+c+' = '+a[r]+','+a[r][c]);
а - массив 3х3 сетки (массив массивов) г - текущая строка итерации с - текущий столбец итерации
Необязательно a.length и a[r].length может оба являются константами 3 (в вашем случае).
Это печатает сетку, но это не запрос OP. –
@ Jim - Это «грубая форсировка» сетки, именно то, что хотел OP, с той разницей, что OP не сказал, что он хотел с ней сделать, поэтому я решил распечатать ее. – Christian
@ Христиан Нет, это не совсем то, что хотел OP; то, что хотел OP, - это знать, как решать магические квадраты, где известны некоторые из значений, а некоторые неизвестны. –
Проблема грубой силы для магического квадрата довольно проста.
Если сумма не совпадают с первой суммой вы вычислить в любой момент, то вы «Сделано. Если все суммы равны, то вы нашли магический квадрат.
Это определяет, является ли заполненный квадрат магическим квадратом, но ОП спрашивает, как заполнить квадрат, чтобы найти все решения. –
О да! Ну, грубой силой было бы попробовать каждую комбинацию чисел в пропавших местах. Если было 3 недостающих ячейки, попробуйте 0-0-0, и запустите алгоритм, описанный выше. Затем попробуйте 0-0-1 и снова запустите алгоритм и т. Д. И т. Д. До 99-99-99. Это предполагает, что магическое число неизвестно. –
Когда вы говорите «попробуйте 0-0-0 ... затем попробуйте 0-0-1 и т. Д.», вы просто повторяете вопрос, а не отвечаете на него. См. Мой ответ выше, который предоставляет алгоритм для этого. –
Магические квадраты - это действительно система (простых) одновременных уравнений. Вы решаете это путем преобразования в матрицу и используя Gaussian elimination, который является грубой силой, но достаточно изящной в то же время.Если решение не уникально, вы, по крайней мере, уменьшите набор ограничений на решение, которое должно сделать решение намного проще.
Это не «грубая сила», поскольку термин обычно (или даже необычно) понимается. Это, безусловно, более эффективный и эффективный способ решения проблемы, но это не то, о чем попросил ОП. –
@Jim: Вы не хотите применять «истинную» грубую силу к магическим квадратам (т. Е. Просматривать все возможности и видеть один за другим, если они являются решением), поскольку пространство поиска составляет 100^9 (== 10^18, многие многие годы процессора с нынешней технологией) и поэтому совершенно непрактично большие. –
Чтобы расширить «много процессорных лет», один современный процессор не может искать одну комбинацию в 1ns. Вам нужен кластер, возможно, большой, чтобы получить такую скорость поиска, и даже тогда вы ожидаете, что время решения составит около 16 лет. (Верхняя граница - 1Gs - чуть меньше 32 лет, ожидаемое время поиска примерно в два раза меньше, при условии, что решение уникально.) –
решить, какую проблему? –
Это проблема магического квадрата? – John
Как здорово это сделать вопрос, не зная, как это происходит? – stacker