Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
У вас в описании задачи про китайские шашки не написано, чего получить то надо:) По тексту статьи понял, что должна остаться только 1 фишка, правильно?
Ага, сейчас допишу. Спасибо
Странно, что это китайские, а не шотландские :)
Вроде, китайские все-таки — http://fitnessbrain.ru/flash/igryi-golovolomki/shinese-checkers-kitayskie-shashki
прошу прощения, если что-то упустил, а какой это язык?
А что такое idx и что значат условия типа
?
if idx in [2,9,14,15,16,17,18,21,22,23,24,25,28,29,30,31,32,37,44]:
?
Это значит, что на клетку, индекс которой в квадрате 7*7 равен idx, можно пойти. В данном случае, справа (на клетку 2 — прыжком с клетки 4 через клетку 3).
как-то не вполне ясно — откуда эти числа взялись и почему они повторяются в разных условиях?
В разные клетки можно попасть с разных сторон. В клетку 2 — справа и снизу (с 4 через 3 и с 16 через 9 соответственно), в клетку 3 — только снизу (с 17 через 10), в клетки центрального квадрата — со всех четырёх сторон. Поэтому в разных массивах находится разный набор клеток, но некоторые встречаются в нескольких массивах. Откуда взялись? Вероятно, получены методом пристального взгляда на игровое поле :)
рисуешь в екселе табличку 7х7 клеток, нумеруешь их, думаешь как можно попасть в клетку, сделав валидный ход.
>>> Откуда взялись? Вероятно, получены методом пристального взгляда на игровое поле :)
во-во
>>> Откуда взялись? Вероятно, получены методом пристального взгляда на игровое поле :)
во-во
Решение на C++ с кодировкой состяний битовой строкой (младшие 33 бита из int64) решает «китайские шашки» за 40 секунд. Безо всяких отсечений. Количество комбинаций, которые пришлось перебрать — около 110 миллионов.
Заменил поиск в ширину на рекурсию — решила за секунду. Программа сократилась на треть.
А можно исходники куда-нибудь выложить?
Пожалуйста.
Единственная проблема — что при выводе хода она первые две клетки выводит в случайном порядке.
Кстати, как выкладывать, чтбы оно было с вертикальным скроллбаром?
Единственная проблема — что при выводе хода она первые две клетки выводит в случайном порядке.
#include<stdio.h>
#include<memory.h>
#include<time.h>
int *Arr; // 2^30 bytes, 2^28 ints
int L=1<<28;
long long Sit0=0x1fffeffffLL;
int fld[49]={-1,-1,0,1,2,-1,-1, -1,-1,3,4,5,-1,-1, 6,7,8,9,10,11,12, 13,14,15,16,17,18,19, 20,21,22,23,24,25,26, -1,-1,27,28,29,-1,-1, -1,-1,30,31,32,-1,-1};
int nsteps=0;
long long Steps[80][2];
void AddStep(int a,int b,int c){
if(a<0 || b<0 || c<0) return;
Steps[nsteps][0]=(1LL<<a)+(1LL<<b);
Steps[nsteps][1]=(1LL<<c);
Steps[nsteps+1][0]=(1LL<<c)+(1LL<<b);
Steps[nsteps+1][1]=(1LL<<a);
nsteps+=2;
}
void InitSteps(){
for(int i=0;i<49;i++){
if((i%7)<5) AddStep(fld[i],fld[i+1],fld[i+2]);
if(i<35) AddStep(fld[i],fld[i+7],fld[i+14]);
}
}
int Solution[33];
int LS=0;
bool Solve(long long s){
Arr[(int)(s>>5)]|=1<<((int)s&31);
if((s&(s-1))==0) return true;
for(int k=0;k<nsteps;k++){
long long u=Steps[k][0],v=Steps[k][1];
if((u&~s)==0 && (v&s)==0){
long long s1=(s&~u)|v;
if((Arr[(int)(s1>>5)]&1<<((int)s1&31))==0){
if(Solve(s1)){
Solution[LS++]=k;
return true;
}
}
}
}
return false;
}
void main(){
long c=clock();
InitSteps();
Arr=new int[L];
memset(Arr,0,L*4);
if(Solve(Sit0)){
for(int m=LS;--m>=0;){
int k=Solution[m];
long long u=Steps[k][0],v=Steps[k][1];
for(int i=0;i<33;i++) if(u&1LL<<i) printf("%d ",i);
for(int i=0;i<33;i++) if(v&1LL<<i) printf("-> %d\n",i);
}
}
printf("Time=%ld\n",clock()-c);
}
Кстати, как выкладывать, чтбы оно было с вертикальным скроллбаром?
Уж простите, но код, решающий китайские шашки — как китайская грамота выглядит :) Расскажите народу, пожалуйста, что к чему.
Что ж. Если вы не любите разгадывать головоломки…
На поле 33 клетки. Нумеруем их от 0 до 32 в любом порядке. После этого каждую позицию можно представить в виде 33-битного двоичного числа (1 в k-м разряде означает, что на k-м поле есть фишка). Поскольку в int 33-битное число не укладывается, приходится использовать long long.
Создаём массив возможных ходов. Каждый ход описывается двумя масками: в первой — 2 ненулевых бита, указывающие, на каких полях должны были находиться фишки до хода, во второй — 1 бит, указывающий, где будет фишка после хода. Если первая маска равна U, вторая V, а текущая позиция F, то ход возможен, если выполняется условие (U&~F)==0 && (V&F)==0, а после хода мы окажемся в позиции (F&~U)|V. Можно было бы проще, если вместо W взять 3-битную маску U|V, тогда ход возможен, если ((F^U)&W)==0, а новая позиция F1=F^W. Но уж как написал, так написал.
Для инициализации ходов берём карту поля (fld), просматриваем на ней все отрезки длины 3. Пусть отрезок состоит из клеток a,b,c. Если все клетки принадлежат игровому полю (номера неотрицательны), то такой отрезок даёт два хода. Для первого маска U=(1<<a)|(1<<b), V=1<<c, а для второго — U=(1<<b)|(1<<c), V=1<<a.
Заводим массив, в котором каждой возможной позиции соответствует 1 бит. Позиций у нас 2^33, и такой массив займёт 1 гигабайт, для которого найдётся место даже в 32-битном режиме. Этот массив нам понадобится, чтобы помечать уже обработанные позиции.
Выписываем маску Sit0, соответствующую стартовой позиции, и начинаем решение.
Решение рекурсивно, функции Solve передаётся единственный параметр — маска s позиции.
Сразу помечаем в битовом массиве, что решением этой позиции мы уже озабочены.
Проверяем, не осталась ли на поле ровно одна фишка. Это делается проверкой условия (s&(s-1))==0 — оно выполняется только для s=0 и для степеней двойки. Если фишка одна, возвращаем true — позиция имеет решение.
Если фишек больше одной, то перебираем все ходы, и для каждого смотрим, возможен ли он (проверяя условие (U&~s)==0 && (V&s)==0). Если ход возможен, вызываем Solve для позиции, возникшей после этого хода, и смотрим результат. Если true — мы нашли решение, сохраняем наш ход в стеке Solution, и сами возвращаем true. Если же ни один из ходов не привел к результату, значит, позиция тупиковая — возвращаем false.
После того, как функция Solve(Sit0) вычислилась (и вернула true), в стеке Solution оказалась в точности та последовательность ходов, которая привела к решению. Осталось её распечатать.
Если бы на поле было хотя бы на одну клетку больше, дела (в 32-битной системе) были бы намного хуже — пришлось бы заводить hash-таблицу с масками просмотренных позиций и надеяться, что мы успеем закончить поиск до того, как таблица переполнится.
На поле 33 клетки. Нумеруем их от 0 до 32 в любом порядке. После этого каждую позицию можно представить в виде 33-битного двоичного числа (1 в k-м разряде означает, что на k-м поле есть фишка). Поскольку в int 33-битное число не укладывается, приходится использовать long long.
Создаём массив возможных ходов. Каждый ход описывается двумя масками: в первой — 2 ненулевых бита, указывающие, на каких полях должны были находиться фишки до хода, во второй — 1 бит, указывающий, где будет фишка после хода. Если первая маска равна U, вторая V, а текущая позиция F, то ход возможен, если выполняется условие (U&~F)==0 && (V&F)==0, а после хода мы окажемся в позиции (F&~U)|V. Можно было бы проще, если вместо W взять 3-битную маску U|V, тогда ход возможен, если ((F^U)&W)==0, а новая позиция F1=F^W. Но уж как написал, так написал.
Для инициализации ходов берём карту поля (fld), просматриваем на ней все отрезки длины 3. Пусть отрезок состоит из клеток a,b,c. Если все клетки принадлежат игровому полю (номера неотрицательны), то такой отрезок даёт два хода. Для первого маска U=(1<<a)|(1<<b), V=1<<c, а для второго — U=(1<<b)|(1<<c), V=1<<a.
Заводим массив, в котором каждой возможной позиции соответствует 1 бит. Позиций у нас 2^33, и такой массив займёт 1 гигабайт, для которого найдётся место даже в 32-битном режиме. Этот массив нам понадобится, чтобы помечать уже обработанные позиции.
Выписываем маску Sit0, соответствующую стартовой позиции, и начинаем решение.
Решение рекурсивно, функции Solve передаётся единственный параметр — маска s позиции.
Сразу помечаем в битовом массиве, что решением этой позиции мы уже озабочены.
Проверяем, не осталась ли на поле ровно одна фишка. Это делается проверкой условия (s&(s-1))==0 — оно выполняется только для s=0 и для степеней двойки. Если фишка одна, возвращаем true — позиция имеет решение.
Если фишек больше одной, то перебираем все ходы, и для каждого смотрим, возможен ли он (проверяя условие (U&~s)==0 && (V&s)==0). Если ход возможен, вызываем Solve для позиции, возникшей после этого хода, и смотрим результат. Если true — мы нашли решение, сохраняем наш ход в стеке Solution, и сами возвращаем true. Если же ни один из ходов не привел к результату, значит, позиция тупиковая — возвращаем false.
После того, как функция Solve(Sit0) вычислилась (и вернула true), в стеке Solution оказалась в точности та последовательность ходов, которая привела к решению. Осталось её распечатать.
Если бы на поле было хотя бы на одну клетку больше, дела (в 32-битной системе) были бы намного хуже — пришлось бы заводить hash-таблицу с масками просмотренных позиций и надеяться, что мы успеем закончить поиск до того, как таблица переполнится.
Фразу "… если вместо W взять 3-битную маску U|V..." следует читать, как "… если вместо V взять 3-битную маску W=U|V.."
Я не «не люблю». Не умею, скорее. Возможно, для всех ваш код предельно ясен, но я попытался понять, но не смог. Спасибо за пояснения :)
Можно пару вопросов:
«Если первая маска равна U, вторая V, а текущая позиция F, то ход возможен, если выполняется условие (U&~F)==0 && (V&F)==0»
поясните, как (разберем, например, 0, 1, 2 как a,b,c) 11 (в двоичной) соотносится с «на каких полях находятся фишки до хода» и как прийти к проверке на возможность хода?
«Проверяем, не осталась ли на поле ровно одна фишка. Это делается проверкой условия (s&(s-1))==0 — оно выполняется только для s=0 и для степеней двойки.»
Ну а если на поле, скажем, осталось как раз 2^n фишек?
Можно пару вопросов:
«Если первая маска равна U, вторая V, а текущая позиция F, то ход возможен, если выполняется условие (U&~F)==0 && (V&F)==0»
поясните, как (разберем, например, 0, 1, 2 как a,b,c) 11 (в двоичной) соотносится с «на каких полях находятся фишки до хода» и как прийти к проверке на возможность хода?
«Проверяем, не осталась ли на поле ровно одна фишка. Это делается проверкой условия (s&(s-1))==0 — оно выполняется только для s=0 и для степеней двойки.»
Ну а если на поле, скажем, осталось как раз 2^n фишек?
F=3=00011 в двоичной записи значит, что фишки находятся на клетках 0 и 1, а на остальных клетках фишек нет. Если a=0, b=1, c=2, то для одного из ходов будет U1=00011, V1=00100 (прыжок из клетки 0 через 1 на клетку 2), а для другого — U2=00110, V2=00001 (прыжок из 2 через 1 на клетку 0).
В первом случае U1&~F = 00011&11100 = 00000, V1&F = 00100&00011 = 00000 — ход возможен. После хода мы перейдем в ситуацию (F&~U1)|V1 = (00011&11100)|00100 = 00100 — на поле стоит одна фишка, на клетке 2.
Во втором случае U2&~F = 00110&11100 = 00100 != 0 — ход невозможен: на клетке 2 нет фишки.
Число s задано так, что каждый бит 1 в его двоичной записи показывает, что на данной клетке есть фишка. Если на поле 2^n фишек, где n>0, то в двоичной записи соответствующего числа s будет более одной единицы, а значит, само s не будет степенью двойки. И s&(s-1) не будет равно нулю.
В первом случае U1&~F = 00011&11100 = 00000, V1&F = 00100&00011 = 00000 — ход возможен. После хода мы перейдем в ситуацию (F&~U1)|V1 = (00011&11100)|00100 = 00100 — на поле стоит одна фишка, на клетке 2.
Во втором случае U2&~F = 00110&11100 = 00100 != 0 — ход невозможен: на клетке 2 нет фишки.
Число s задано так, что каждый бит 1 в его двоичной записи показывает, что на данной клетке есть фишка. Если на поле 2^n фишек, где n>0, то в двоичной записи соответствующего числа s будет более одной единицы, а значит, само s не будет степенью двойки. И s&(s-1) не будет равно нулю.
Да, я вижу, что битовые операции дают верные результаты, но меня интересует, так сказать, как вы пришли к этому инварианту — откуда следует, что создав именно такие маски, для любого подходящего хода выражения будут верны?
Ох… я просто прикинул, что хочу получить, и написал.
Сравнивать с нулём проще, чем с маской из единиц, поэтому 1 в маске результата должно означать, что «что-то не так». Что у нас может быть не так?
— в маске U стоит 1, а в F — 0 (фишки, нужной для хода, нет в наличии)
— в маске V стоит 1 и в F тоже 1.
Нам нужно написать выражение, которое при выполнении любого из этих условий для какого-то бита запишет в этот бит 1, а если оба условия не выполняются — оставит там 0.
Глядя на формулировку, видим, что итоговая формула имеет вид A|B, где A=«в маске U стоит 1, а в F — 0», а B=«в маске V стоит 1 и в F тоже 1».
Формулу B записать проще: в ней явно видна формулировка операции «и»: B=(F&V). Формула A — это тоже «и», но вместо F надо взять ~F (чтобы 0 превратился в 1). Получаем условие
((U&~F)|(V&F))==0. Можно было бы с ним еще поиграться (и довести до ((U|V)&(F^U))==0), но это непросто и незачем.
Сравнивать с нулём проще, чем с маской из единиц, поэтому 1 в маске результата должно означать, что «что-то не так». Что у нас может быть не так?
— в маске U стоит 1, а в F — 0 (фишки, нужной для хода, нет в наличии)
— в маске V стоит 1 и в F тоже 1.
Нам нужно написать выражение, которое при выполнении любого из этих условий для какого-то бита запишет в этот бит 1, а если оба условия не выполняются — оставит там 0.
Глядя на формулировку, видим, что итоговая формула имеет вид A|B, где A=«в маске U стоит 1, а в F — 0», а B=«в маске V стоит 1 и в F тоже 1».
Формулу B записать проще: в ней явно видна формулировка операции «и»: B=(F&V). Формула A — это тоже «и», но вместо F надо взять ~F (чтобы 0 превратился в 1). Получаем условие
((U&~F)|(V&F))==0. Можно было бы с ним еще поиграться (и довести до ((U|V)&(F^U))==0), но это непросто и незачем.
Я тут используя ваши идеи тоже написал код, он получился в чуть более «С++» стиле.
Находит решение за 1.3 сек и 1.0 GB с использованием
Находит решение за 1.3 сек и 1.0 GB с использованием
vector<bool> и за 1.7 сек и несколько MB с использованием std::unordered_set.эээээ
логично же блин
:-(
не программист я
логично же блин
:-(
не программист я
стоп
рекурсия — это тоже поиск
только более эффективный
рекурсия — это тоже поиск
только более эффективный
Мне так кажется, что код на Python тоже будет работать быстрее например на pypy.
Хм, алгоритм пришел в голову меньше чем за пол минуты, со 2 попытки. Или это программа для того, чтоб была программа?
Ты программировал на чем-нибудь до прохождения этого курса?
Я чувствую себя таким глупым, потому что решал все эти головоломки без помощи программирования. :(
А с ходом коня — на шамхматном поле оставалась 1 клетка. Польностью заполнить так и не получилось, но пробовал это дело ещё в 9 или 10 классе, потом как-то забылось и перестал пробовать.
Пользуясь случаем, посоветуйте литературу по Python и C++, собираюсь в ближайшем будущем заняться (до этого немного программировал на Pascal и Delphi). Спасибо.
А с ходом коня — на шамхматном поле оставалась 1 клетка. Польностью заполнить так и не получилось, но пробовал это дело ещё в 9 или 10 классе, потом как-то забылось и перестал пробовать.
Пользуясь случаем, посоветуйте литературу по Python и C++, собираюсь в ближайшем будущем заняться (до этого немного программировал на Pascal и Delphi). Спасибо.
Я с радостью тебе помогу:
Специально для habrahabr, накидал мою реализацию алгоритма на C#, забирать тут:
github.com/hack2root/checkersolver.git
Из особенностей:
1) вывод дерева решения,
2) возможность задания произвольной формы доски (т.к. есть матрица смежности)
3) полностью реализация в объектно-ориентированном стиле
4) возможность проигрывания решения (undo/redo)
5) статистика использования ветвлений при поиска решения в пространстве решений
Специально для habrahabr, накидал мою реализацию алгоритма на C#, забирать тут:
github.com/hack2root/checkersolver.git
Из особенностей:
1) вывод дерева решения,
2) возможность задания произвольной формы доски (т.к. есть матрица смежности)
3) полностью реализация в объектно-ориентированном стиле
4) возможность проигрывания решения (undo/redo)
5) статистика использования ветвлений при поиска решения в пространстве решений
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Применяем на практике знания, полученные на курсе MIT 6.00x (edx.org)