6 svar
145 visningar
dajamanté Ă€r nöjd med hjĂ€lpen!
dajamanté 5269
Postad: 2 feb 2019 Redigerad: 2 feb 2019

Nio riddare av apocalypsen 🐮

God morgon PA!

Jag försöker skriva bÀttre och undrar vilken förenklingar kan man göra med rörelser av schack bitar.

Problemet Ă€r att hitta alla sĂ€tt nio riddare kan samexistera pĂ„ en 5×55\times5 schackbrĂ€det, utan att mörda varandra, Ebony och Ivory style.

Min kod testar alla möjliga relativa steg, dvs alla "L" steg en riddare kan göra.


Jag har försökt samla mina riddare i en string av 25 char istĂ€llet och man ser att stegen som Ă€r tillĂ„tna Ă€r ±11,±9,±7,±3\pm11, \pm9, \pm7, \pm3. SĂ„ man ser att det Ă€r nĂ„got i det, men vadĂ„? Vad Ă€r den snyggaste sĂ€tt att lösa problemet?

Och jag Àr fult medveten att min kod har alldeles för mÄnga ifsatser. Om nÄgon har en bra ifsatsicide, spraya pÄ!

Laguna Online 11572
Postad: 2 feb 2019

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.

Laguna Online 11572
Postad: 2 feb 2019

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.

dajamanté 5269
Postad: 2 feb 2019

Aha! Mycket smart. Skriv om du tÀnker pÄ nÄgot annat.

Ironboy 19
Postad: 16 jun 2020 Redigerad: 16 jun 2020

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);

dajamanté 5269
Postad: 16 jun 2020

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 :)

Ironboy 19
Postad: 16 jun 2020

Hittade du nÄgon mindre bruteforcig lösning?

Svara Avbryt
Close