*Теория*(VB.NET || C#.net ) Нужен алгоритм для мини - игры
 

Добрый день!
Игра: есть поле 8 х 8 ячеек(изначально серого цвета), игрок имеет право ходить только буквой "Г" и только в ещё не пройденный квадрат(пройденный квадрат меняет цвет на красный).
Допустим игрок сделал n ходов, надо сделать так ,что бы при нажатии на кнопку рядом с игровым полем, компьютер заполнял оставшееся поле с учетом выше перечисленных правил(ходы компьютера сохраняются в файле) или ,если заполнить поле нет возможности, выдавал сообщение об этом.
Нужен алгоритм позволяющий заполнять поле после n>=0 ходов игрока.. Может кто нить знает где его можно взять или есть идеи как построить алгоритм?...
Заранее благодарю.

Т.е. компьютер должен сам сходить "буквой Г"?
Ну и чего сложного? Массив 8х8, "непохоженное" поле - 0, похоженное - "1". Из текущего положения капм пытается сходить буквой Г, если там единичка - то пытается сходить по-другому, если больше вариантов хода для него нет - то все...

ну это то понятно)) только у него в каждом случае от 1 до 8 вариантов ходов(допустим игрок сделал один ход, это ж сколько переборов сделать надо), а надо что бы он закрасил все поле.. если сделать такой перебор, то это имхо извращение..
думаю существует какое то математическое решение..

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

CyberDaemon
DedAlex
ок.. прийду домой попробую написать.. но возникает такой вопрос:
Изначально я создаю массив кнопок 8 на 8( поле).. попутно создал массив 8 на 8 типа boolean(true - пройденная ячейка, false - непройденное ячейка).. так вот, как быстрее будет работать программа: если работать с массивом булеан или лучше создать целочисленный массив или вообще использовать свойство уже существующего массива кнопок .tab(mas(i,j) - массив кнопок, mas(i,j).tag=1 - пройденная кнопка-ячейка, mas(i,j).tag=0 - непройденная) ?

ssdm
Полагаю, от одного до восьми на каждый ход. При условии, что они с игроком по очереди ходят.

Или игрок должен начать, а компьютер после этого "ходом коня пройти все поле, не попадая дважды в одну и ту-же клетку"? Тогда простор для фантазии в самом деле огромный, и перебором _это_ решать...

именно так )

при маленьком количестве закрашеных клеток комп решение будет быстро находить(потому что куда ни плюнь везде пусто:)


А при занятых количестве клеток больше допустим 3/4. Можно сделать так:
Взять оставшиеся пустые клетки и проверять можно ли туды ходить.А если заняты все клетки то gane over and happy end.
Я думаю,если использовать такой вариант алгоритма , его работа существенно ускорится т.к. иначе при большом количестве занятых клеток комп будет впустую проверять варианты ходов.




Кстати можно вопрос. Комп просто показует все ходы которые возможно или вы играете с ним. Если идет игра с ним то придется делать еще оценку позицииь. В этом случае перебор вглубь на первых ходах будет ужасно медленным.И почему вы расматриваете только ходы коня, есть же еще много фигур(или это не шахматы)

bezumes
это не шахматы..
играю я один.. а комп это что то вроде подсказки..
мало просто сходить, надо сходиь так, что бы закрасить все поле..

Придется строить дерево.
Получается количество ходов=63(8*8-1),и количество уровней дерева.Количество вариантов которые придется перебирать мне и представить сложно
Допустим все клетки свободные .фигура находится где то посредине.
Смотрим что за ходы у нас есть(8 ходов, если фигура находится с краю поля то меньше).Прросматриваем первый ход.Вновь строим все возможные ходы и так поднимаемся по "дереву" пока или не достигним того что все заполним(кстати все эти текущие ходы надо запоминать)и выведем то что снизу это первые сверху последнии.Если ходы заканчиваются а свободные клетки остаются на уровень вниз и расчет оставшихся ходов.

Можно еще сделать чтобы при переходе по дереву на уровень вверх просматривалась ветвь на которой больше всего ходов, т.к. там вероятность того что идем туда выше.

Еще можно прикрутить оценку позиции. В центре оценка будет больше, т.к ходов больше, по краям меньше.

Певые ходы(2-3) можно сделать случайными(или нельзя?), скорость возрастет на несколько порядков.



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

Значит задачу надо пытаться свести к решению более мелких задач, типа заполнения полей 4х4 так, чтобы можно было из них "собрать" 8х8

думаю нет.. так как если рассмотревать 4 отдельных квадрата 4х4, то выподают ходы из одного квадрата в другой..