Description
Lizard Tom now has lots and lots of popcorn!
He recently learned how to play Shogi (Japanese chess), a board game where you can resurrect captured pieces and use them as your own. In his free time, he plays against Cabi in the dorm lounge (btw, this is real, you can come play with us). Dominating the board with the Ureshino-Ryū, he aspires to become the Ryuo of NTHU—one of the highest titles in the Shogi world.
One morning, a question suddenly popped into Lizard Tom's mind: On a 5x5 Shogi board, assuming no pieces can attack each other, how many possible board configurations are there if we want to additionally place N pieces consisting of Hisya (飛車, abbreviated as H), Kakugyo (角行, abbreviated as K), and Ryuo (竜王, abbreviated as R)?
No, not again...
To stop Lizard Tom from practicing counting all over again, you decide to write a program to help him calculate the answer !
Pieces attack ranges
- Hisya (H): Attacks all cells in the same row and column
- Kakugyo (K): Attacks all cells along its diagonals
- Ryuo (R): Attacks all cells in the same row and column, plus the four immediately adjacent diagonal cells.
Template Code
You're strongly suggested to understand what the template code is doing and how it works before you start. As a heartbroken lizard, Tom may not give you the complete template on Lab：（
# Feel free to modify or rewrite anything you want
graph = [0] * 29
board = ["."] * 29
dire = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
def put_H (posx: int, posy: int, status: int) -> bool:
pos = 5*(posx-1) + posy
if (status == 1):
if (graph[pos] > 0 or board[pos] != '.'):
return False
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
if (i != posy and board[row] != '.'):
return False
if (i != posx and board[column] != '.'):
return False
board[pos] = 'H'
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
graph[row] += 1
graph[column] += 1
graph[pos] -= 1
return True
else:
board[pos] = '.'
for i in range(1, 6, 1):
row = 5*(posx-1) + i
column = 5*(i-1) + posy
graph[row] -= 1
graph[column] -= 1
graph[pos] += 1
return True
def put_K (posx: int, posy: int, status: int) -> bool:
pos = 5*(posx-1) + posy
if (status == 1):
if (graph[pos] > 0 or board[pos] != '.'):
return False
for (dx, dy) in dire:
tmpx = posx + dx
tmpy = posy + dy
while (tmpx > 0 and tmpy > 0 and tmpx < 6 and tmpy < 6):
diag = 5*(tmpx-1) + tmpy
if (board[diag] != '.'):
return False
tmpx += dx
tmpy += dy
board[pos] = 'K'
graph[pos] += 1
for (dx, dy) in dire:
tmpx = posx + dx
tmpy = posy + dy
while (tmpx > 0 and tmpy > 0 and tmpx < 6 and tmpy < 6):
diag = 5 * (tmpx - 1) + tmpy
graph[diag] += 1
tmpx += dx
tmpy += dy
return True
else:
board[pos] = '.'
graph[pos] -= 1
for (dx, dy) in dire:
tmpx = posx + dx
tmpy = posy + dy
while (tmpx > 0 and tmpy > 0 and tmpx < 6 and tmpy < 6):
diag = 5*(tmpx-1) + tmpy
graph[diag] -= 1
tmpx += dx
tmpy += dy
return True
def put_R (posx: int, posy: int, status: int) -> bool:
pos = 5*(posx-1) + posy
if (status == 1):
# Do something ...
return True
else:
# Do something...
return True
def find (start: int, H: int, K: int, R: int, N: int) -> None:
if (H+K+R >= N):
# Do something ...
# Do something ...
# ===============================================
N = int(input())
tmp = input()
valid = True
for i in range(1, 26, 1):
x = (i-1)//5 + 1
y = (i-1)%5 + 1
if (tmp[i-1] == 'H'):
if (not put_H(x, y, 1)):
valid = False
elif (tmp[i-1] == 'K'):
if (not put_K(x, y, 1)):
valid = False
elif (tmp[i-1] == 'R'):
if (not put_R(x, y, 1)):
valid = False
if (valid):
find(1, 0, 0, 0, N)
Here is a quick breakdown of the provided template:
graph: A 1D array representing the 5x5 board. It tracks the attack coverage by counting how many pieces are currently attacking each cell. A value of0means the cell is safe.board: A 1D array representing the 5x5 board state. It tracks the piece currently occupying each cell ('H','K','R', or'.'for empty cells)put_H,put_K,put_R: Helper functions to update thegrapharray. Focusing atposx-rowandposy-column, pass1to thestatusargument when placing a piece (to mark its attack range), and-1when picking it up (to unmark its attack rangek). And of course,boardarray will also be updated in these functionsfind: The core backtracking function you need to complete. The parameters are:start: The 1D cell index (1 to 25) to start scanning from, ensuring you only move forward to avoid duplicate permutations leading to TLEH,K,R: Counters tracking the number of newly placed Hisya, Kakugyo, and Ryuo pieces in the current recursive path.N: The target total number of pieces to be additionally placed.
HINT
- You cannot remove the pieces originally on the board.
- No two pieces can attack each other, whether they are newly placed or originally on the board.
- The total number of newly placed pieces must be exactly N.
- If there are no valid configurations, do not output anything.
- The order of your answer will not affect the result
- Indeed, there's other solutions for this problem (e.g. use lists to record the pieces in every row, column, main diagonal, secondary diagonal, and 3x3 square.) You can try them if you want :)
Input
The input consists of two lines.
The first line is a positive integer N, representing the number of pieces to be additionally placed. (To be more precise, the newly placed pieces must satisfy H + K + R = N. The pieces originally on the board do not count.)
The second line contains a string S of length 25, which may consist of ., H, K, and R. S_i represents the state of the cell with index i: . means an empty cell, while H, K, and R represent Hisya, Kakugyo, and Ryuo, respectively.
We define the index of the cell at row x and column y (0-indexed) as 5x + y.
Output
Output all possible board configurations. For each valid configuration, output a string of length 25 followed by a newline. The formatting rules are the same as the INPUT.