Nio riddare av apocalypsen 🐴

Roligt, jag ska titta.

Men uppgiften på kattis ser ut att vara att avgöra om en given ställning är tillåten, inte att hitta alla tillåtna ställningar?

Förresten heter schackpjäsen "springare" på svenska.

Jag tycker inte det är alldeles för många if-satser. Det är ju bara tre och de testar det som måste testas.

En optimering du kan göra är att bara titta nedåt (alltså bara ha positiva tal i relativeRow), för om det finns en konflikt uppåt så har man redan hittat den tidigare.

Aha! Mycket smart. Skriv om du tänker på något annat.

Om jag förstått dig rätt vill du ha alla möjliga lösningarna, där 9 hästar utplacerade på brädet inte kan ta varandra.

Ett sätt att göra detta är att loopa genom alla 2**25 möjliga states av brädet, tänka på dem som binärtal, tidigt ta bort de states som inte innehåller 9 stycken 1:or, sedan pröva de som blir kvar mot hur hästar får röra sig.

Jag får detta till (inkl. tid det tog för lösningen på en modest laptop):
Time taken (ms): 921
Possible board states: 33 554 432
Board states with 9 knights: 2 042 975
Possible solutions: 963
(Och sedan en lista med de 963 lösningarna.)

(Eftersom detta är en ganska bruteforcig lösning är det bra att ha snabba funktioner för att kontrollera om en viss bit är satt i ett tal och hur många satta bits som finns i ett tal, på sätt slipper man långsamma omvandlingar mellan tal och binära strängar för allt utom de 963 lösningarna.)

I JavaScript:

let bitSet = (n, k) => n & (1 << (k - 1));
let bitCount = (n) => {
  let co = 0;
  while (n > 0) { co++; n = n & (n - 1) };
  return co;
};
let startTime = Date.now();
let not9 = 0, solutions = [];
let offsets = [-2, -1, 1, 2];
for (let i = 0; i < 2 ** 25; i++) {
  // only interested in 9 knights (nine 1:s)
  if (bitCount(i) !== 9) { not9++; continue; }
  // now check if no knight can capture another
  let ok = true;
  check: for (r = 0; r < 5; r++) {
    for (c = 0; c < 5; c++) {
      if (!bitSet(i, r * 5 + c)) { continue; }
      for (ro of offsets) {
        for (co of offsets) {
          if (Math.abs(ro) === Math.abs(co)) { continue; }
          let bit = (r + ro) * 5 + c + co;
          if (bit > 0 && bit < 26 && bitSet(i, bit)) {
            ok = false; break check;
          }
        }
      }
    }
  }
  ok && solutions.push(i.toString(2).padStart(25, '0')
    .split('0').join('.').split('1').join('k'));
}
console.log('Time taken (ms): ', Date.now() - startTime);
console.log('Possible board states: ', 2 ** 25);
console.log('Board states with 9 knights: ', 2 ** 25 - not9);
console.log('Possible solutions:', solutions.length);
console.log('All solutions', solutions);

Tack för ditt svar och hjälp :). Det är en post från 2019 så den har varit löst sedan ett tag tillbaka :)

Hittade du någon mindre bruteforcig lösning?