Poteze skakača/Java

Iz MaFiRaWiki

Izvorna koda

  1. import java.util.List;
  2. import java.util.Vector;
  3.  
  4. public class Skakac {
  5. int n; // velikost sahovnice
  6. int[][] polje; // tabela polj na sahovnici
  7. static final int PRAZNO = 0;
  8. int k; // stevec potez
  9. public Skakac(int n) {
  10. this.n = n;
  11. k = 0;
  12. polje = new int[n][n];
  13. }
  14. // vrne true, ce je sahovnica polna
  15. public boolean jePolna() { return k == n*n; }
  16. // izpisi sahovnico
  17. public void izpisi(){
  18. for (int[] vrstica : polje){
  19. for (int j : vrstica) {
  20. System.out.print(j + "\t");
  21. }
  22. System.out.println();
  23. }
  24. }
  25. // Poisce resitev glede na trenutno stanje, zacni v (x,y).
  26. // Vrne true, ce je nasel resitev.
  27. public boolean resi(int x, int y) {
  28. narediPotezo(x,y);
  29. if (jePolna()) {
  30. return true;
  31. }
  32. else {
  33. for (Koordinata p : moznePoteze(x,y)){
  34. if (resi(p.x, p.y)) { return true; }
  35. }
  36. odstraniPotezo(x,y);
  37. return false;
  38. }
  39. }
  40.  
  41. // poteze, ki so mozne iz polja (x,y)
  42. public List<Koordinata> moznePoteze(int x, int y) {
  43. List<Koordinata> s = new Vector<Koordinata>();
  44. final int[] dx = { 2, 1, -1, -2, -2, -1, 1, 2};
  45. final int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1};
  46. for (int i = 0; i < dx.length; i++){
  47. if (veljavnaPoteza(x+dx[i],y+dy[i])) { s.add(new Koordinata(x+dx[i],y+dy[i])); }
  48. }
  49. return s;
  50. }
  51.  
  52. private boolean veljavnaPoteza(int x, int y) {
  53. return 0 <= x && x < n && 0 <= y && y < n && polje[x][y] == PRAZNO;
  54. }
  55.  
  56. public void odstraniPotezo(int x, int y) {
  57. k--;
  58. polje[x][y] = PRAZNO;
  59. }
  60.  
  61. public void narediPotezo(int x, int y) {
  62. k++;
  63. polje[x][y] = k;
  64. }
  65. }

  1. public class Koordinata {
  2. public int x, y;
  3. public Koordinata(int u, int v) { x = u; y = v; }
  4. public String toString() {
  5. return "(" + x + "," + y + ")";
  6. }
  7. }

Primer uporabe

> s = new Skakac(8);
> s.resi(0,0)
true
> s.izpisi()
1	60	39	34	31	18	9	64
38	35	32	61	10	63	30	17
59	2	37	40	33	28	19	8
36	49	42	27	62	11	16	29
43	58	3	50	41	24	7	20
48	51	46	55	26	21	12	15
57	44	53	4	23	14	25	6
52	47	56	45	54	5	22	13
Osebna orodja