Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It is BFS, but you don't search the chessboard; search the space of placements:</p> <p>Initial state: no knight is placed</p> <p>Valid move: place a knight on any unoccupied tile</p> <p>Goal state: all tiles are either occupied or attacked</p> <p>basic algorithm (BFS of the state space):</p> <ul> <li>push the initial state to the BFS queue.</li> <li>while there is something in the queue: <ul> <li>remove one state from the queue.</li> <li>for every unoccupied tile: <ul> <li>create a copy of the current state.</li> <li>add one knight to that tile.</li> <li>if the new state doesn't exist in the queue: <ul> <li>if the new state is a goal state, finish.</li> <li>else add it to the queue.</li> </ul></li> </ul></li> </ul></li> </ul> <p>Note that I'm assuming that all paths to a state are of the same length. This is true when looking for a set of placements this way, but it is not true in general. In cases where this is not true, you should store the set of all visited nodes to avoid revisiting already explored states.</p> <hr> <p>You may require the knights be added left-to-right, top-to-bottom. Then you don't need to check for duplicates in the queue. Additionally, you may discard a state early if you know that an unattacked tile cannot be attacked without violating the insertion order.</p> <p>If you don't do this and leave the duplicate check as well, the algorithm will still produce correct results, but it will do so much slower. 40 000 times slower, approximately (8!=40 320 is the number of duplicates of an 8-knight state).</p> <hr> <p>If you want a faster algorithm, look into A*. Here, one possible heuristic is:</p> <ul> <li>count the number of unattacked and unoccupied tiles</li> <li>divide the count by nine, rounding up (a knight cannot attack more than eight new tiles or occupy more than one)</li> <li>the distance (number of knights needed to be added) is no more than this number.</li> </ul> <p>A better heuristic would note the fact that a knight can only attack tiles of the same color, and occupy a tile of the opposite color. This may improve the previous heuristic slightly (but still potentially help a lot).</p> <p>A better heuristic should be able to exploit the fact that a knight can cover free spots in no more than a 5x5 square. A heuristic should compute fast, but this may help when there are few spots to cover.</p> <hr> <p>Technical details:</p> <p>You may represent each state as a 64-bit bit-mask. While this requires some bitwise manipulation, it really helps memory, and equality checking of 64-bit numbers is <em>fast</em>. If you can't have a 64-bit number, use two 32-bit numbers - these should be available.</p> <p>Circular array queue is efficient, and it's not <em>that</em> hard to expand its capacity. If you have to implement your own queue, pick this one. </p>
    singulars
    1. This table or related slice is empty.
    1. POBreadth first search: Knight cover
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJohn Dvorak
    1. USJohn Dvorak
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POBreadth first search: Knight cover
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks a lot for the detailed answer Jan. I'll read this in detail and try to come up with a simple implementation. Might take some time, as I'm new to this :)
      singulars
      1. PO
      1. USragebiswas
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload