1. 

// Simon Baumgartner, WA

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeSet;

public class Main {

private static int SOLUTION_COUNT = 0;
private static ArrayList<Lineup> solutions;
static int FIELD_SIZE;
static int NR_OF_BISHOPS;

public static void main(String[] args) throws IOException {
long start = System.currentTimeMillis();

// BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedReader in = new BufferedReader(new FileReader("input.txt"));
String line = in.readLine();
String[] token = line.split(" ");

FIELD_SIZE = Integer.parseInt(token[0]);
NR_OF_BISHOPS = Integer.parseInt(token[1]);

while(!(FIELD_SIZE == 0 && NR_OF_BISHOPS == 0)){
Bishop.populateInstances();
solutions = new ArrayList<Lineup>();

backtrack(new Lineup());

System.out.println("all solutions (" + solutions.size() + ")");
TreeSet<Lineup> uniqueSolutions = new TreeSet<Lineup>();
uniqueSolutions.addAll(solutions);
System.out.println("unique solutions: " + uniqueSolutions.size());

line = in.readLine();
token = line.split(" ");
FIELD_SIZE = Integer.parseInt(token[0]);
NR_OF_BISHOPS = Integer.parseInt(token[1]);
SOLUTION_COUNT = 0;
}
long stop = System.currentTimeMillis();
System.out.println("Time: " + (stop - start));
}

private static void backtrack(Lineup lineup){
if(lineup.isSolution()){
solutions.add(lineup);
SOLUTION_COUNT++;
}
else{
List<Bishop> candidates = lineup.getCandidates();
if(candidates.size() > 0){
for(int i=0; i<candidates.size(); i++){
Bishop candidate = candidates.get(i);
Lineup l = (Lineup)lineup.clone();
l.addBishop(candidate);
backtrack(l);
}
}
}

}
}

class Bishop implements Comparable<Bishop>{

public int x;
public int y;
private int check1;
private int check2;

private static Bishop[][] INSTANCES;

public static void populateInstances(){
INSTANCES = new Bishop[Main.FIELD_SIZE+1][Main.FIELD_SIZE+1];
for(int i=1; i<=Main.FIELD_SIZE;i++)
for(int j=1; j<=Main.FIELD_SIZE;j++)
INSTANCES[i][j] = new Bishop(i, j);
}

public Bishop(int x, int y) {
this.x = x;
this.y = y;
this.check1 = x-y;
this.check2 = x+y;
}

public boolean beatsAt(int x, int y) {
return this.check1 == (x-y) || this.check2 == (x+y);
}


@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Bishop other = (Bishop) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

public String toString(){
return "("+x+","+y+")";
}

public int compareTo(Bishop o) {
return this.toString().compareTo(o.toString());
}

public static Bishop getBishopInstanceAt(int i, int j) {
return INSTANCES[i][j];
}
}

/**
* represents a number of bishops on a board.
*
*/
class Lineup implements Comparable<Lineup>{

Bishop[] bishops = new Bishop[Main.NR_OF_BISHOPS];
// LinkedList<Bishop> bishops = new LinkedList<Bishop>();

// int[][] bishops = new int[Main.NR_OF_BISHOPS][2];

int bishopCount;

public List<Bishop> getCandidates() {
List<Bishop> candidates = new LinkedList<Bishop>();
if(this.bishopCount >= Main.NR_OF_BISHOPS)
return candidates;

for(int i=1; i<=Main.FIELD_SIZE; i++){
for(int j=1; j<=Main.FIELD_SIZE; j++){

if(allowsBishopAt(i, j))
candidates.add(Bishop.getBishopInstanceAt(i, j));

}
}
return candidates;
}

/**
* returns whether this lineup allows the given bishop
* @param c
* @return
*/
public boolean allowsBishopAt(int x, int y) {
if(bishopCount == Main.NR_OF_BISHOPS)
return false;

for(int i = 0; i<bishopCount; i++){
Bishop b = bishops[i];
if((b.x == x && b.y == y) || b.beatsAt(x, y))
return false;
}
return true;
}

public void addBishop(Bishop bishop){
bishops[bishopCount] = bishop;
bishopCount++;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((bishops == null) ? 0 : bishops.hashCode());
result = prime * result + Main.NR_OF_BISHOPS;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Lineup other = (Lineup) obj;
if (bishops == null) {
if (other.bishops != null)
return false;
} else if (!bishops.equals(other.bishops))
return false;
return true;
}

public boolean isSolution(){
return this.bishopCount == Main.NR_OF_BISHOPS;
}

public Lineup clone(){
Lineup l = new Lineup();
l.bishops = bishops.clone();
l.bishopCount = this.bishopCount;
return l;
}

public int compareTo(Lineup o) {
return this.toString().compareTo(o.toString());
}

public String toString(){
String ret = "";
Arrays.sort(bishops);
for(Bishop co : bishops){
ret += co.toString();
}
return ret;
}
}