public class Board {
private static String charpieces = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
- public int difficulty=1; // 1=Hard ... N=Easy
- public boolean gravity=true;
- public int [] boardSize;
- public char[][] board;
- public LinkedList<Move> history;
-
- // ----------------------
- // Public methods
- // ----------------------
-
- public Board() {
- }
-
- // The board always has a 1-square width free rectangle that has
- // to be taken into account when specifying the size
- public void initialize(int sizeI, int sizeJ) {
- boardSize = new int[2];
- boardSize[0]=sizeI;
- boardSize[1]=sizeJ;
- board = new char[boardSize[0]][boardSize[1]];
- for (int i=0;i<boardSize[0];i++)
- for (int j=0;j<boardSize[1];j++)
- board[i][j]=0;
- history=new LinkedList<Move>();
- }
-
- public static String pieceToString(char piece) {
- return charpieces.substring(piece,1);
- }
-
- public static char StringToPiece(String piece) {
- char upiece;
- long charpiecesLen=charpieces.length();
- for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
- if (upiece<charpiecesLen) return upiece;
- else return 0;
- }
-
- public String toString() {
- String result=" ";
- for (int j=0;j<boardSize[1];j++) {
- if (j>0) result+=" ";
- result+=""+(j%10);
- }
- result+="\n "+StringRepeat("--",boardSize[1]);
- for (int i=0;i<boardSize[0];i++) {
- result+="\n"+(i%10)+"|";
- for (int j=0;j<boardSize[1];j++) {
- if (j>0) result+=" ";
+ public int difficulty=1; // 1=Hard ... N=Easy
+ public boolean gravity=true;
+ public int [] boardSize;
+ public char[][] board;
+ public LinkedList<Move> history;
+
+ // ----------------------
+ // Public methods
+ // ----------------------
+
+ public Board() {
+ }
+
+ // The board always has a 1-square width free rectangle that has
+ // to be taken into account when specifying the size
+ public void initialize(int sizeI, int sizeJ) {
+ boardSize = new int[2];
+ boardSize[0]=sizeI;
+ boardSize[1]=sizeJ;
+ board = new char[boardSize[0]][boardSize[1]];
+ for (int i=0;i<boardSize[0];i++)
+ for (int j=0;j<boardSize[1];j++)
+ board[i][j]=0;
+ history=new LinkedList<Move>();
+ }
+
+ public static String pieceToString(char piece) {
+ return charpieces.substring(piece,1);
+ }
+
+ public static char StringToPiece(String piece) {
+ char upiece;
+ long charpiecesLen=charpieces.length();
+ for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
+ if (upiece<charpiecesLen) return upiece;
+ else return 0;
+ }
+
+ public String toString() {
+ String result=" ";
+ for (int j=0;j<boardSize[1];j++) {
+ if (j>0) result+=" ";
+ result+=""+(j%10);
+ }
+ result+="\n "+StringRepeat("--",boardSize[1]);
+ for (int i=0;i<boardSize[0];i++) {
+ result+="\n"+(i%10)+"|";
+ for (int j=0;j<boardSize[1];j++) {
+ if (j>0) result+=" ";
result+=charpieces.substring(board[i][j],board[i][j]+1);
- }
- result+=" |\n";
- if (i<boardSize[0]-1)
- result+=" |"+StringRepeat(" ",boardSize[1])+"|";
- }
- result+=" "+StringRepeat("--",boardSize[1])+"\n";
- return result;
- }
+ }
+ result+=" |\n";
+ if (i<boardSize[0]-1)
+ result+=" |"+StringRepeat(" ",boardSize[1])+"|";
+ }
+ result+=" "+StringRepeat("--",boardSize[1])+"\n";
+ return result;
+ }
public void buildRandomBoard(int sizeI, int sizeJ, int difficulty, boolean gravity) {
- initialize(sizeI,sizeJ);
- this.difficulty=difficulty;
- this.gravity=gravity;
-
- int numDifferentPieces=((boardSize[0]-2)*(boardSize[1]-2)/((difficulty+1)*2))+1;
- for (int n=0;n<((difficulty+1)*2);n++) {
- for (int k=0;k<numDifferentPieces;k++) {
- int i,j;
- do {
- j=(myrand() % (boardSize[1]-2))+1;
- i=findFreeRow(j);
- } while (i<1);
+ initialize(sizeI,sizeJ);
+ this.difficulty=difficulty;
+ this.gravity=gravity;
+
+ int numDifferentPieces=((boardSize[0]-2)*(boardSize[1]-2)/((difficulty+1)*2))+1;
+ for (int n=0;n<((difficulty+1)*2);n++) {
+ for (int k=0;k<numDifferentPieces;k++) {
+ int i,j;
+ do {
+ j=(myrand() % (boardSize[1]-2))+1;
+ i=findFreeRow(j);
+ } while (i<1);
// ShisenSho.log("numDifferentPieces="+numDifferentPieces+", n="+n+", k="+(int)k+", i="+i+", j="+j);
// ShisenSho.log(toString());
board[i][j]=(char)k;
- }
- }
- }
+ }
+ }
+ }
- /*
- ALGORITHM TO COMPUTE CONNECTION PATH BETWEEN PIECES A (IA,JA) AND B (IB,JB)
+ /*
+ ALGORITHM TO COMPUTE CONNECTION PATH BETWEEN PIECES A (IA,JA) AND B (IB,JB)
- - Delete A and B from the board (consider them as blank spaces)
- - Calculate the set H of possible horizontal lines in the board (lines through blank spaces)
- - Calculate the set V of possible vertical lines in the board
- - Find HA, VA, HB, VB in the sets
- - If HA=HB, result is a straight horizontal line A-B
- - If VA=VB, result is a straight vertical line A-B
- - If HA cuts VB, the result is an L line A-(IA,JB)-B
- - If VA cuts HB, the result is an L line A-(IB,JA)-B
- - If exists an V line that cuts HA and HB, the result is a Z line A-(IA,JV)-(IB-JV)-B
- - If exists an H line that cuts VA and VB, the result is a Z line A-(IV,JA)-(IV,JB)-B
+ - Delete A and B from the board (consider them as blank spaces)
+ - Calculate the set H of possible horizontal lines in the board (lines through blank spaces)
+ - Calculate the set V of possible vertical lines in the board
+ - Find HA, VA, HB, VB in the sets
+ - If HA=HB, result is a straight horizontal line A-B
+ - If VA=VB, result is a straight vertical line A-B
+ - If HA cuts VB, the result is an L line A-(IA,JB)-B
+ - If VA cuts HB, the result is an L line A-(IB,JA)-B
+ - If exists an V line that cuts HA and HB, the result is a Z line A-(IA,JV)-(IB-JV)-B
+ - If exists an H line that cuts VA and VB, the result is a Z line A-(IV,JA)-(IV,JB)-B
- The following data types are defined:
+ The following data types are defined:
- - Board
- - Point(int i, int j)
- - Line(Point a, Point b)
- - LineSet(Line l1, ..., Line lN)
+ - Board
+ - Point(int i, int j)
+ - Line(Point a, Point b)
+ - LineSet(Line l1, ..., Line lN)
- The following operations are defined
+ The following operations are defined
- LineSet getHorizontalLines(Board board, Point a, Point b) // a and b needed to consider them as blank
- - LineSet getVerticalLines(Board board, Point a, Point b)
- - boolean lineIsHorizontal(Line l)
- - boolean lineIsVertical(Line l)
- - boolean lineContainsPoint(Line l, Point p)
- - boolean lineEqualsLine(Line l1, Line l2)
- - boolean lineCutsLine(Line l1, Line l2)
- */
- public List<Point> getPath(Point a, Point b) {
- List<Point> result=new ArrayList<Point>();
-
- if (getPiece(a)!=getPiece(b)) return result;
-
- List<Line> h=getHorizontalLines(a,b);
- List<Line> v=getVerticalLines(a,b);
- Line ha=null, va=null, hb=null, vb=null;
-
- for (Line l : h) {
- if (l.contains(a)) ha=l;
- if (l.contains(b)) hb=l;
- if (ha!=null && hb!=null) break;
- }
-
- for (Line l : v) {
- if (l.contains(a)) va=l;
- if (l.contains(b)) vb=l;
- if (va!=null && vb!=null) break;
- }
+ - LineSet getVerticalLines(Board board, Point a, Point b)
+ - boolean lineIsHorizontal(Line l)
+ - boolean lineIsVertical(Line l)
+ - boolean lineContainsPoint(Line l, Point p)
+ - boolean lineEqualsLine(Line l1, Line l2)
+ - boolean lineCutsLine(Line l1, Line l2)
+ */
+ public List<Point> getPath(Point a, Point b) {
+ List<Point> result=new ArrayList<Point>();
+
+ if (getPiece(a)!=getPiece(b)) return result;
+
+ List<Line> h=getHorizontalLines(a,b);
+ List<Line> v=getVerticalLines(a,b);
+ Line ha=null, va=null, hb=null, vb=null;
+
+ for (Line l : h) {
+ if (l.contains(a)) ha=l;
+ if (l.contains(b)) hb=l;
+ if (ha!=null && hb!=null) break;
+ }
+
+ for (Line l : v) {
+ if (l.contains(a)) va=l;
+ if (l.contains(b)) vb=l;
+ if (va!=null && vb!=null) break;
+ }
// stdout.printf("va=%s, ha=%s, vb=%s, hb=%s\n",va.toString(),ha.toString(),vb.toString(),hb.toString());
- if ((ha==null && va==null) || (hb==null && vb==null))
- return result;
+ if ((ha==null && va==null) || (hb==null && vb==null))
+ return result;
- if (ha.equals(hb) || va.equals(vb)) {
- result.add(a);
- result.add(b);
- return result;
- }
+ if (ha.equals(hb) || va.equals(vb)) {
+ result.add(a);
+ result.add(b);
+ return result;
+ }
- Point ab;
+ Point ab;
- ab=ha.cuts(vb);
- // stdout.printf("(ha cuts vb) ab=%s\n",ab.toString());
+ ab=ha.cuts(vb);
+ // stdout.printf("(ha cuts vb) ab=%s\n",ab.toString());
- if (ab!=null) {
- result.add(a);
- result.add(ab);
- result.add(b);
- return result;
- }
+ if (ab!=null) {
+ result.add(a);
+ result.add(ab);
+ result.add(b);
+ return result;
+ }
- ab=va.cuts(hb);
- // stdout.printf("(va cuts hb) ab=%s\n",ab.toString());
+ ab=va.cuts(hb);
+ // stdout.printf("(va cuts hb) ab=%s\n",ab.toString());
if (ab!=null) {
result.add(a);
result.add(ab);
- result.add(b);
- return result;
- }
+ result.add(b);
+ return result;
+ }
for (Line l : v) {
- Point al=l.cuts(ha);
- Point bl=l.cuts(hb);
+ Point al=l.cuts(ha);
+ Point bl=l.cuts(hb);
// stdout.printf("(%s cuts ha) al=%s\n",l.toString(),al.toString());
// stdout.printf("(%s cuts hb) bl=%s\n",l.toString(),bl.toString());
- if (al!=null && bl!=null) {
- result.add(a);
- result.add(al);
- result.add(bl);
- result.add(b);
- return result;
- }
- }
+ if (al!=null && bl!=null) {
+ result.add(a);
+ result.add(al);
+ result.add(bl);
+ result.add(b);
+ return result;
+ }
+ }
- for (Line l : h) {
- Point al=l.cuts(va);
- Point bl=l.cuts(vb);
+ for (Line l : h) {
+ Point al=l.cuts(va);
+ Point bl=l.cuts(vb);
// stdout.printf("(%s cuts va) al=%s\n",l.toString(),al.toString());
// stdout.printf("(%s cuts vb) bl=%s\n",l.toString(),bl.toString());
if (al!=null && bl!=null) {
- result.add(a);
- result.add(al);
- result.add(bl);
- result.add(b);
- return result;
- }
- }
+ result.add(a);
+ result.add(al);
+ result.add(bl);
+ result.add(b);
+ return result;
+ }
+ }
- return result;
- }
+ return result;
+ }
public char getPiece(Point p) {
- return board[p.i][p.j];
- }
+ return board[p.i][p.j];
+ }
public void setPiece(Point p, char piece) {
- board[p.i][p.j]=piece;
- }
+ board[p.i][p.j]=piece;
+ }
- public String getStrPiece(Point p) {
- char piece=board[p.i][p.j];
- return charpieces.substring(piece,1);
- }
+ public String getStrPiece(Point p) {
+ char piece=board[p.i][p.j];
+ return charpieces.substring(piece,1);
+ }
public void setStrPiece(Point p, String piece) {
- char upiece;
- long charpiecesLen=charpieces.length();
+ char upiece;
+ long charpiecesLen=charpieces.length();
for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
- if (upiece<charpiecesLen) board[p.i][p.j]=upiece;
- }
-
- public void play(Point a0, Point b0) {
- // It's important to sink the upper piece first
- Point a=(a0.i<b0.i)?a0:b0;
- Point b=(a0.i<b0.i)?b0:a0;
- Move m=new Move(a,b,getPiece(a));
- history.add(0,m);
- setPiece(a,(char)0);
- processGravity(a);
- setPiece(b,(char)0);
- processGravity(b);
- }
-
- public boolean getCanUndo() {
- return !history.isEmpty();
- }
-
- public void undo() {
- if (!getCanUndo()) return;
- Move m=history.remove(0);
- undoGravity(m.b);
- setPiece(m.b,m.piece);
- undoGravity(m.a);
- setPiece(m.a,m.piece);
- }
-
- public List<Line> getPairs(int maxResults) {
- List<Line> result=new ArrayList<Line>();
- List<Integer> pieces=new ArrayList<Integer>();
- List<List<Point>> piecePoints=new ArrayList<List<Point>>();
- for (int i=0;i<boardSize[0];i++)
- for (int j=0;j<boardSize[1];j++) {
- int piece=(int)board[i][j];
- if (piece==0) continue;
- int key=pieces.indexOf(piece);
- Point p=new Point(i,j);
- if (key==-1) {
- List<Point> points0=new ArrayList<Point>();
- points0.add(p);
- pieces.add(piece);
+ if (upiece<charpiecesLen) board[p.i][p.j]=upiece;
+ }
+
+ public void play(Point a0, Point b0) {
+ // It's important to sink the upper piece first
+ Point a=(a0.i<b0.i)?a0:b0;
+ Point b=(a0.i<b0.i)?b0:a0;
+ Move m=new Move(a,b,getPiece(a));
+ history.add(0,m);
+ setPiece(a,(char)0);
+ processGravity(a);
+ setPiece(b,(char)0);
+ processGravity(b);
+ }
+
+ public boolean getCanUndo() {
+ return !history.isEmpty();
+ }
+
+ public void undo() {
+ if (!getCanUndo()) return;
+ Move m=history.remove(0);
+ undoGravity(m.b);
+ setPiece(m.b,m.piece);
+ undoGravity(m.a);
+ setPiece(m.a,m.piece);
+ }
+
+ public List<Line> getPairs(int maxResults) {
+ List<Line> result=new ArrayList<Line>();
+ List<Integer> pieces=new ArrayList<Integer>();
+ List<List<Point>> piecePoints=new ArrayList<List<Point>>();
+ for (int i=0;i<boardSize[0];i++)
+ for (int j=0;j<boardSize[1];j++) {
+ int piece=(int)board[i][j];
+ if (piece==0) continue;
+ int key=pieces.indexOf(piece);
+ Point p=new Point(i,j);
+ if (key==-1) {
+ List<Point> points0=new ArrayList<Point>();
+ points0.add(p);
+ pieces.add(piece);
piecePoints.add(points0);
- key=pieces.indexOf(piece);
- piecePoints.get(key);
- } else {
- List<Point> points1=piecePoints.get(key);
- points1.add(p);
- }
- }
-
- int nresults=0;
- for (List<Point> points : piecePoints) {
- int n=(int)points.size();
- for (int i=0;i<n;i++) {
- Point a=points.get(i);
- for (int j=i+1;j<n;j++) {
- Point b=points.get(j);
- List<Point> path=getPath(a.copy(),b.copy());
- if (path!=null && path.size()>0) {
- result.add(new Line(a,b));
- if (nresults++==maxResults) break;
- }
- }
- if (nresults==maxResults) break;
- }
- if (nresults==maxResults) break;
- }
- return result;
- }
-
- public int getNumPieces() {
- int result=0;
- for (int j=0;j<boardSize[1];j++) {
- for (int i=0;i<boardSize[0];i++) {
- if (board[i][j]!=0) result++;
- }
- }
- return result;
- }
-
- // ----------------------
- // Private methods
- // ----------------------
-
- /* RAND_MAX assumed to be 32767 */
- private int myrand() {
+ key=pieces.indexOf(piece);
+ piecePoints.get(key);
+ } else {
+ List<Point> points1=piecePoints.get(key);
+ points1.add(p);
+ }
+ }
+
+ int nresults=0;
+ for (List<Point> points : piecePoints) {
+ int n=(int)points.size();
+ for (int i=0;i<n;i++) {
+ Point a=points.get(i);
+ for (int j=i+1;j<n;j++) {
+ Point b=points.get(j);
+ List<Point> path=getPath(a.copy(),b.copy());
+ if (path!=null && path.size()>0) {
+ result.add(new Line(a,b));
+ if (nresults++==maxResults) break;
+ }
+ }
+ if (nresults==maxResults) break;
+ }
+ if (nresults==maxResults) break;
+ }
+ return result;
+ }
+
+ public int getNumPieces() {
+ int result=0;
+ for (int j=0;j<boardSize[1];j++) {
+ for (int i=0;i<boardSize[0];i++) {
+ if (board[i][j]!=0) result++;
+ }
+ }
+ return result;
+ }
+
+ // ----------------------
+ // Private methods
+ // ----------------------
+
+ /* RAND_MAX assumed to be 32767 */
+ private int myrand() {
return (int)Math.floor(Math.random()*32768);
- }
-
- private String StringRepeat(String s, int n) {
- String result="";
- for (int i=0;i<n;i++)
- result+=s;
- return result;
- }
-
- private int findFreeRow(int j) {
- for (int i=1;i<boardSize[0]-1;i++) {
- if (board[i][j]!=0) return (i-1);
- }
- return (boardSize[0]-1-1);
- }
-
- private List<Line> getHorizontalLines(Point excludeA, Point excludeB) {
- List<Line> result=new ArrayList<Line>();
- for (int i=0;i<boardSize[0];i++) {
- int j0=-1;
- boolean empty;
- for (int j=0;j<boardSize[1];j++) {
- empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
- || (i==excludeB.i && j==excludeB.j));
- if (j0==-1 && empty) {
- j0=j;
- } else if (j0!=-1 && !empty) {
- result.add(new Line(new Point(i,j0), new Point(i,j-1)));
- j0=-1;
- }
- }
- if (j0!=-1) result.add(new Line(new Point(i,j0), new Point(i,boardSize[1]-1)));
- }
+ }
+
+ private String StringRepeat(String s, int n) {
+ String result="";
+ for (int i=0;i<n;i++)
+ result+=s;
+ return result;
+ }
+
+ private int findFreeRow(int j) {
+ for (int i=1;i<boardSize[0]-1;i++) {
+ if (board[i][j]!=0) return (i-1);
+ }
+ return (boardSize[0]-1-1);
+ }
+
+ private List<Line> getHorizontalLines(Point excludeA, Point excludeB) {
+ List<Line> result=new ArrayList<Line>();
+ for (int i=0;i<boardSize[0];i++) {
+ int j0=-1;
+ boolean empty;
+ for (int j=0;j<boardSize[1];j++) {
+ empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
+ || (i==excludeB.i && j==excludeB.j));
+ if (j0==-1 && empty) {
+ j0=j;
+ } else if (j0!=-1 && !empty) {
+ result.add(new Line(new Point(i,j0), new Point(i,j-1)));
+ j0=-1;
+ }
+ }
+ if (j0!=-1) result.add(new Line(new Point(i,j0), new Point(i,boardSize[1]-1)));
+ }
// stdout.printf("\ngetHorizontalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
- // for (Line line : result) stdout.printf("%s ",line.toString());
- // stdout.printf("\n");
+ // for (Line line : result) stdout.printf("%s ",line.toString());
+ // stdout.printf("\n");
- return result;
- }
+ return result;
+ }
private List<Line> getVerticalLines(Point excludeA, Point excludeB) {
List<Line> result=new ArrayList<Line>();
projects / FreeShisen / commitdiff