TicTacToe - генерирующие решения - PullRequest
Новая
       9

TicTacToe - генерирующие решения

0 голосов
/ 13 марта 2012

Учитывая сетку из nxn квадратов, где у каждого квадрата есть идентификатор, первый (верхний левый) квадрат имеет идентификатор 0 (таким образом, у сетки 5x5 будут идентификаторы 0-24), как показано ниже: 

00 01 02 03 04

05 06 07 08 09

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

Мне нужно сгенерировать все диагональные решения длины Y. Так что, если Y равен 3, то некоторые из решений будут: 

0,6,12

и 

11,17,23

, но, очевидно, НЕ 

3,9,15 (because the 15 does not follow on diagonally)

Есть идеи, как можно сгенерировать эти решения?

Это то, что у меня есть (размерность = 5, inARow = 3): 

public ArrayList<int[]> getSolutions(int dimension, int inARow) {

    ArrayList<int[]> solutions = new ArrayList<int[]>();

    //create row solutions
    for(int i=0; i<dimension*dimension; i = i+dimension) {
        for(int j=i; j<=i+dimension - inARow; j++){            
            int[] row = new int[inARow];
            int counter = 0;
            for(int k=j; k<j+inARow; k++){
                row[counter++] = k;
            }
            solutions.add(row);
        }
    }

    //create column solutions        
    for(int i=0;i<dimension;i++){
        for(int j=i; j<(dimension*dimension)-(dimension*inARow)+dimension;j=j+dimension){
            int[] col = new int[inARow];
            int counter = 0;
            for(int k=j;k<j+(dimension*inARow);k=k+dimension){
                col[counter++] = k;
            }
            solutions.add(col);
        }
    }

    //create diagonals        
    for(int i=0; i<dimension*dimension; i++){            
        for(int j=i; j<i+(dimension * inARow); j = j+dimension+1){
            System.out.println(j);
        }            
    }                

    return solutions;

Это дает мне все диагональные решения, но также и плохие, такие как 3,9,15.У меня проблемы с их устранением.

Антидиагоналы также являются решениями, поэтому 2,6,10 также будет решением, но если я получу нормальные диагонали, я, вероятно, могу сделать то же самое для антидиагоналей.

1 Ответ

1 голос
/ 13 марта 2012

Это ваш счастливый день ... Я обновил ответ, чтобы работать как общее решение для всех размеров сетки и длины

В кофейном скрипте, который создает красивый псевдокод 

w = 5 # width of the grid
h = 5 # height of the grid
l = 3 # length to capture

m = [] # matches

for i in [0..(w*h)-1] # loop through each square
    col = i % w # calculate what column we are in
    row = Math.floor i / w # calculate what row we are in
    nums = [] # re-set matched lines array
    if col < w - (l-1) and row < h - (l-1) # if there is space for diagonal right
        for j in [0..l-1] # loop until length is reached
            nums.push i+(j*w)+j # push it onto the array of squares
        m.push nums # push into the array of matched lines
    nums = []
    if col > l-2 and row < h-l+1 # if there is space for diagonal left
        for j in [0..l-1]
            nums.push i+(j*w)-j
        m.push nums

console.dir m
# or
console.log i.join "," for i in m

, который компилируется в javascript (чтобы вы могли проверить его) 

var col, h, i, j, l, m, nums, row, w, _i, _len, _ref, _ref2, _ref3;
w = 5;
h = 5;
l = 3;
m = [];
for (i = 0, _ref = (w * h) - 1; 0 <= _ref ? i <= _ref : i >= _ref; 0 <= _ref ? i++ : i--) {
  col = i % w;
  row = Math.floor(i / w);
  nums = [];
  if (col < w - (l - 1) && row < h - (l - 1)) {
    for (j = 0, _ref2 = l - 1; 0 <= _ref2 ? j <= _ref2 : j >= _ref2; 0 <= _ref2 ? j++ : j--) {
      nums.push(i + (j * w) + j);
    }
    m.push(nums);
  }
  nums = [];
  if (col > l - 2 && row < h - l + 1) {
    for (j = 0, _ref3 = l - 1; 0 <= _ref3 ? j <= _ref3 : j >= _ref3; 0 <= _ref3 ? j++ : j--) {
      nums.push(i + (j * w) - j);
    }
    m.push(nums);
  }
}
console.dir(m);
for (_i = 0, _len = m.length; _i < _len; _i++) {
  i = m[_i];
  console.log(i.join(","));
}
...