Пишем шахматную программу (Играем в Чапаева)

Здравствуйте дорогие друзья

Предыдущая публикация

Мы с Беней решили поскакать на коне по шахматной доске

Условие задачи

Среди математических развлечений давно известна задача обхода шахматной фигурой коня всех клеток шахматной доски

Она заключается в нахождении маршрута коня на шахматной доске.

В 1823 году Варнсдорф в брошюре “Простейшее и наиболее общее решение задачи о ходе коня” предложил следующее правило обхода доски размером 8x8.

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

На практике это правило легко позволяет строить обходы доски, хотя долгое время не было известно, справедливо ли оно. Опровержение правила Варнсдорфа было найденос помощью ЭВМ “Проминь- 2” , где для любого исходного поля доски указаны контрпримеры. Иными словами, с какого бы поля конь ни начал движение, следуя правилу Варнсдорфа, его можно завести в тупик до полного обхода доски.

Но для нас это не важно и мы пойдем по пути Варнсдорфа.

MainActivity.java

public float[] points = new float[4];
public Bitmap imgMoveKnight;
public Canvas canvasKnight;

public void onBackPressed()

...

number2=0x8000000000000000L;
SwitchFromTo=0;

points[0]=0f;
points[1]=0f;
points[2]=0f;
points[3]=0f;

...

public DrawView

canvasBmp3 = new Canvas(bitmap3);

canvasBmp3.drawBitmap(bitmap1, 0, 0, null);

imgMoveKnight = Bitmap.createBitmap(bitmap1.getWidth(), bitmap1.getHeight(), bitmap1.getConfig());
canvasKnight = new Canvas(imgMoveKnight);
canvasBmp3.drawBitmap(bitmap1, 0, 0, null);
canvasBmp3.drawBitmap(imgMoveKnight, 0, 0, null);

protected void onDraw(Canvas canvas)

...

if ((number1&(0x8000000000000000L>>>i))!=0)
{
canvasBmp3.drawBitmap(bitmap4, dx + (i % 8)*h, dy + (i / 8)*h, null);
}

//PrintLine();
Start=System.currentTimeMillis ();
if (desc.WPiece[4]!=0)
{
desc.WPiece[4]=Long.highestOneBit(desc.WPiece[4]);
Chapaev(Long.numberOfLeadingZeros(desc.WPiece[4]),-1L,1);
canvas.drawBitmap(bitmap3, 0, 0, paint);
printDesc(canvas);
desc.WPiece[4]=0;
}
Stop=System.currentTimeMillis ();
time_count = TimeCount(Stop-Start);
showAlert(sInstance, " РІСЂР µ РјСЏ ", time_count);
...

public boolean onTouchEvent

...

number2=0x8000000000000000L>>>NumPol;

points[0]=0f;
points[1]=0f;
points[2]=0f;
points[3]=0f;

try

...

if (desc.returnPiece(NumPol)<6

...

if ((To&number1)!=0)
{
MoveGenerator.moveFromTo(desc,desc,From,To);
setPoints( From,To);
}

public void PrintLine()
{
paint.setColor(Color.RED);
paint.setStrokeWidth(10);
canvasKnight.drawLines(points,paint);
canvasKnight.drawCircle(points[2], points[3], 10, paint);
paint.setStrokeWidth(0);
paint.setColor(Color.BLACK);
canvasBmp3.drawBitmap(imgMoveKnight, 0, 0, paint);
}
public void setPoints(long F,long T)
{
points[0]=dx + Long.numberOfLeadingZeros(F) % 8 * h+h/2;
points[1]=dy + Long.numberOfLeadingZeros(F) / 8 * h+h/2;
points[2]=dx + Long.numberOfLeadingZeros(T) % 8 * h+h/2;
points[3]=dy + Long.numberOfLeadingZeros(T) / 8 * h+h/2;
}
public void Chapaev(int N,long l,int depth)
{
long m2=0;
int best=0;
int temp=10;
long bestmove=0;
long m1 = MascBit.MaskOneBit[N];
if (Long.bitCount(l)==64)
{
l^=m1;
}
long m = MascBit.KnightAttak[N]&l;
int k = Long.bitCount(m);
for (int i = 0; i < k; i++)
{
m2 = Long.highestOneBit(m);
//MoveGenerator.moveFromTo(desc,dsc,m1,m2);
best=Long.bitCount(MascBit.KnightAttak[Long.numberOfLeadingZeros(m2)]&l);
if (best<=temp)
{
temp=best;
bestmove=m2;
}
m^=m2;
}//for
if (m2==0){return;} MoveGenerator.moveFromTo(desc,desc,m1,bestmove);
setPoints(m1,bestmove);
PrintLine(); Chapaev(Long.numberOfLeadingZeros(bestmove),l^bestmove,1);
}

MoveGenerator.java

public static Desc newPos(String str)
{
dsc = new Desc(MainActivity.StrFen str );
return dsc;
}

До встречиvoid Desc moveFromTo(Desc dfrom,Desc dto, long from, long to)
{
for (int i=1;i<6;i++)
{
dto.WPiece[i]=dfrom.WPiece[i];
dto.BPiece[i]=dfrom.BPiece[i];
}
//С „ РёРіСѓСЂР ° РЅР ° from
int f = MainActivity.desc dto .returnPiece(Long.numberOfLeadingZeros(from));
if ((f==-1)|(from==to)){return;}
MainActivity.desc dfrom;}
dto .removePiece(from);
MainActivity.desc dto .removePiece(to);
MainActivity.desc dto .addPiece(f,to);
return dto;
}

До встречи

PS