Задача такая:
Нужно заполнить квадратную матрицу (9х9, а может и другой размерности) числами от 1 до 9 (или до числа размерности) так, чтобы в строках и в столбцах числа не повторялись.
Кто знает алгоритм, напишите его, буду признателен!

Добавлено через 6 минут и 36 секунд
Модераторам:
Можно продублировать эту тему в форумах Программирование игр, графики и иск. интл., Алгоритмы

решалку для судоку делаеш? 

говорю сразу, если важно время - перебором ни в коем случае не делай.

ответ на плюс:
самый оптимальный способ - RANDOM.
т.е. есть массив решений, в принципе полуается кубическая матрица.
есть функция валидации - которая проваеряет на корректность сгенерированное значение матрицы (строки, столбца)
после каждой генерации матрицы - проверяеш, если не совпало - заново генериш.

самый большой недостаток:
вероятность, что при наличит решения рандом - алгоритм не попадет за заданное кол-во итераций (200 неапример)
в решение.

Да решалку.
То что нужно прверять корректность значений это ерунда.
Нужно найти правильное расположение цифр, чтобы все было по условию. Вот, допустим, заполнилась почти вся матрица, кроме последней ячейки, а в эту ячейку ни одно число не подходит, и что тогда? Нужно возвращаться назад, вот с этим то и проблемма

наверное там ей и место, тебя ведь алгоритм интересует. перенести? а дублировать не надо.

stab, да. Спасибо!

emmanuil, 
Вот посмотри самый простой вариант заполнения:
заполняем с лева на право, с верху в низ;
каждая следующая строка начинается со следуещего числа.
Размер роли не играет 9х9, 10х10,13х13 ...

1  2  3  4  5  6  7  8  9 
2  3  4  5  6  7  8  9  1
3  4  5  6  7  8  9  1  2
4  5  6  7  8  9  1  2  3
5  6  7  8  9  1  2  3  4
6  7  8  9  1  2  3  4  5
7  8  9  1  2  3  4  5  6
8  9  1  2  3  4  5  6  7
9  1  2  3  4  5  6  7  8

Это в любом случае начальный вариант, его можно заполнить нячиная с каждого их 4-х углов.
В приведенном выше примере каждая строка и колонка уникальна.
Что бы не нарушать уникальности строк или колонок, мне думается, можно перемещать либо только колонки, либо только строки. (т.е. менять местами, например - 1 с 4, 2 с 5, 3 с 6, 7 с 9, а 8-я на месте)
(от перемены мест слогаемых, сумма не изменяется)

1  2  3  4  5  6  7  8  9      
3  4  5  6  7  8  9  1  2
2  3  4  5  6  7  8  9  1
5  6  7  8  9  1  2  3  4
4  5  6  7  8  9  1  2  3
7  8  9  1  2  3  4  5  6
9  1  2  3  4  5  6  7  8
8  9  1  2  3  4  5  6  7

Получается что заполнив начальный вариант из какого-то угла, мы можем получить другие варианты, только при помощи перемены порядка расположения либо строк, либо колонок. Все.   

Рандом здесь не уместен. Только алгоритм заполнения. 

Удачи.   




Это сообщение отредактировал(а) thomas - 4.7.2007, 09:35

thomas, спасибо!
Но как быть если некоторые ячейки матрицы уже заполнены и их перемещать нельзя. это игра "судоку", слышал про такую?

emmanuil, 
Не, не слышал.   

Но по логике вещей, заполнить матрицу можно только так, как я написал выше. Для каждого размера есть определенное кол-во комбинацый. Ни больше ни меньше.
Значит, уже имеемые позиции отвечают той или иной комбинации. 
Вопрос только в том как определить какая комбинация нужна?

Да можешь привести пример какого либо начального расположения известных цыфр.
Я может на досуге покумекаю над этим.

ЗЫ А кто знает адрес хоста куда можно картинки заливать, что бы на форум можно было выкладывать?   

Это сообщение отредактировал(а) thomas - 4.7.2007, 09:44

предлагаю тупейший хардкор способ.

Делаеш ПОЛНЫЙ ПЕРЕБОР.
записываеш все варианты на диск (несколько гигов )
затем остается лишь найти подходящий 
)))))

 *-----------*
 |4.5|1..|..7|
 |..1|..6|..4|
 |.8.|2..|...|
 |---+---+---|
 |...|.7.|56.|
 |7..|.2.|..8|
 |.94|.3.|...|
 |---+---+---|
 |...|..2|.8.|
 |6..|8..|4..|
 |8..|..9|7.6|
 *-----------*

Вот например. И еще нужно чтобы в квадратах 3х3 тоже числа не повторялись

Вот весь код, но при некоторых комбинациях прога виснет, из рекурсии не выходит, мож кто увидит в чем дело?
(алг-м нашел гдето в сети, точно не помню где, был на C++, перевел на C#, кое-что переделал)
метод SudokuSolve стартует все.

Ну что ж, раз больше нет предложений, то благодарю всех за участие!
Но вопрос остался не решенным!

если это еще актуально - могу попробовать написать программу