StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
10878651
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
3
CommunityOwnedDate
CreationDate
2012-06-04T08:52:22.370
FavoriteCount
0
LastActivityDate
2012-06-04T20:30:30.417
LastEditDate
2012-06-04T20:30:30.417
LastEditorUserId
711085
OwnerUserId
711085
ParentId
10878617
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
<pre><code>.......E <-end ........ ........ ........ ........ ........ ........ S....... <-start </code></pre> Unfortunately you can't use "any standard path finding algorithm" because your paths might not be shortest-paths. You'd have to specifically use a naive search which considered all paths (depth-first or breadth-first, for example). However, because you don't care how you got to a tile, you can use a technique called dynamic programming. For every location (i,j), the number of ways to get there in n moves (let's call it waysi,j(n)) is: waysi,j(n) = waysi-1,j(n-1) + waysi+1,j(n-1) + waysi,j-1(n-1) + waysi,j+1(n-1) + waysi+1,j+1(n-1) + waysi-1,j+1(n-1) + waysi+1,j-1(n-1) + waysi-1,j-1(n-1) That is, the king can move from any of the adjacent squares in 1 move: waysi,j(n) = sumneighbors(i,j)(waysneighbor(n-1)) Thus you'd do, for example in python: <pre><code>SIZE = 8 cache = {} def ways(pos, n): r,c = pos # row,column if not (0<=r<SIZE and 0<=c<SIZE): # off edge of board: no ways to get here return 0 elif n==0: # starting position: only one way to get here return 1 if (r,c)==(0,0) else 0 else: args = (pos,n) if not args in cache: cache[args] = ways((r-1,c), n-1) + ways((r+1,c), n-1) + ways((r,c-1), n-1) + ways((r,c+1), n-1) + ways((r-1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c+1), n-1) return cache[args] </code></pre> Demo: <pre><code>>>> ways((7,7), 15) 1074445298 </code></pre> The above technique is called memoization, and is simpler to write than dynamic programming, because you don't need to really think about the order in which you do things. You can see the cache grow as we perform a series of larger and larger queries: <pre><code>>>> cache {} >>> ways((1,0), 1) 1 >>> cache {((1, 0), 1): 1} >>> ways((1,1), 2) 2 >>> cache {((0, 1), 1): 1, ((1, 2), 1): 0, ((1, 0), 1): 1, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((1, 1), 2): 2, ((2, 2), 1): 0} >>> ways((2,1), 3) 5 >>> cache {((1, 2), 1): 0, ((2, 3), 1): 0, ((2, 0), 2): 1, ((1, 1), 1): 1, ((3, 1), 1): 0, ((4, 0), 1): 0, ((1, 0), 1): 1, ((3, 0), 1): 0, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((4, 1), 1): 0, ((2, 2), 2): 1, ((3, 3), 1): 0, ((0, 1), 1): 1, ((3, 0), 2): 0, ((3, 2), 2): 0, ((3, 2), 1): 0, ((1, 0), 2): 1, ((4, 2), 1): 0, ((4, 3), 1): 0, ((3, 1), 2): 0, ((1, 1), 2): 2, ((2, 2), 1): 0, ((2, 1), 3): 5} </code></pre> (In python, can also use a <code>@cached</code> or <code>@memoized</code> decorator to avoid having to write the entire code in the last <code>else:</code> block. Other languages have other ways to automatically perform memoization.) The above was a top-down approach. It can sometimes produce very large stacks (your stack will grow with <code>n</code>). If you want to be super-efficient to avoid unnecessary work, you can do a bottom-up approach, where you simulate all positions the king could be, for 1 step, 2 steps, 3 steps, ...: <pre><code>SIZE = 8 def ways(n): grid = [[0 for row in range(8)] for col in range(8)] grid[0][0] = 1 def inGrid(r,c): return all(0<=coord<SIZE for coord in (r,c)) def adjacentSum(pos, grid): r,c = pos total = 0 for neighbor in [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]: delta_r,delta_c = neighbor (r2,c2) = (r+delta_r,c+delta_c) if inGrid(r2,c2): total += grid[r2][c2] return total for _ in range(n): grid = [[adjacentSum((r,c), grid) for r in range(8)] for c in range(8)] # careful: grid must be replaced atomically, not element-by-element from pprint import pprint pprint(grid) return grid </code></pre> Demo: <pre><code>>>> ways(0) [[1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]] >>> ways(1) [[0, 1, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]] >>> ways(2) [[3, 2, 2, 0, 0, 0, 0, 0], [2, 2, 2, 0, 0, 0, 0, 0], [2, 2, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]] >>> ways(3) [[6, 11, 6, 4, 0, 0, 0, 0], [11, 16, 9, 5, 0, 0, 0, 0], [6, 9, 6, 3, 0, 0, 0, 0], [4, 5, 3, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]] >>> ways(4) [[38, 48, 45, 20, 9, 0, 0, 0], [48, 64, 60, 28, 12, 0, 0, 0], [45, 60, 51, 24, 9, 0, 0, 0], [20, 28, 24, 12, 4, 0, 0, 0], [9, 12, 9, 4, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]] </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POGraph algorithm involving chess: possible paths in k moves
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USninjagecko
UserOwnerUserId
1. USninjagecko
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUndeletion
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTDownMod
CommentsPostId

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.