I'm trying to implement a function that will count how many 'n' of rooks can there be in a chess board of 'n' size without colliding in a position that can be attacked by another rook.
I have used as a base a 4*4 grid. I'm struggling with the concept to create the array and how to proceed with the recursion (it has to be done with recursion as per exercise request). My recursion is a mess and i still don't know how to fill the array in shape of [ | | | ] x4.
I've looked a lot, and this is the Queens problem (just the rooks for now) but still I don't know how to proceed. there are plenty of solutions out there, but none of them require to return a factorial integer (I have tried factorial approach and it works, but is not what the exercise need). Debug shows that solutions never gets updated and when n becomes less than one it enters an infinite loop.
function calc (size) {
// should be incremented each time a rook is placed
let rooks = 0;
// should increment and
let solutions = 0;
// where the array should populated ...?
const board = [];
function recursively (n) {
// if size becomes smaller than 1 stop recursion?
while (n > 1) {
// update solution var?
solutions = n * recursively(n -1);
}
// increment count of rooks
rooks ;
// return 0 in case there is a size of 0
return 0;
}
recursively(size);
return solutions;
}
console.log(calc(4));CodePudding user response：
This part of recursively
while (n > 1) {
// update solution var?
solutions = n * recursively(n -1);
}
Is either never going to do anything or will never escape the loop, because if n is greater than 1 you are not changing it in the function.
CodePudding user response：
In one sense, this is an extremely trivial problem, because we can see the answer at a glance. On an n x n board, when we place a Rook anywhere, we have blocked the placement of any other Rook on that row or that column, reducing the problem to (n - 1) x (n - 1), and trivially we can note that therefore on an n x n board, we can place n rooks.
So a trivial answer is
const countRooks = (n) => n
Or, if you have to use recursion, and your instructor doesn't mind a wiseass, you could write
const countRooks = (n) =>
n <= 0
? 0
: 1 countRooks (n - 1)
But let's assume that this is in preparation for a harder assignment, and that we want to do something legitimate with an actual board representation. How should we represent our board? We might try something like this:
const ourEmpty4x4Board = [
{c: 'a', r: 4, v: ' '}, {c: 'b', r: 4, v: ' '}, {c: 'c', r: 4, v: ' '}, {c: 'd', r: 4, v: ' '},
{c: 'a', r: 3, v: ' '}, {c: 'b', r: 3, v: ' '}, {c: 'c', r: 3, v: ' '}, {c: 'd', r: 3, v: ' '},
{c: 'a', r: 2, v: ' '}, {c: 'b', r: 2, v: ' '}, {c: 'c', r: 2, v: ' '}, {c: 'd', r: 2, v: ' '},
{c: 'a', r: 1, v: ' '}, {c: 'b', r: 1, v: ' '}, {c: 'c', r: 1, v: ' '}, {c: 'd', r: 1, v: ' '},
]
const ourFilled4x4Board = [
{c: 'a', r: 4, v: 'R'}, {c: 'b', r: 4, v: ' '}, {c: 'c', r: 4, v: ' '}, {c: 'd', r: 4, v: ' '},
{c: 'a', r: 3, v: ' '}, {c: 'b', r: 3, v: ' '}, {c: 'c', r: 3, v: 'R'}, {c: 'd', r: 3, v: ' '},
{c: 'a', r: 2, v: ' '}, {c: 'b', r: 2, v: ' '}, {c: 'c', r: 2, v: ' '}, {c: 'd', r: 2, v: 'R'},
{c: 'a', r: 1, v: ' '}, {c: 'b', r: 1, v: 'R'}, {c: 'c', r: 1, v: ' '}, {c: 'd', r: 1, v: ' '},
]
But that seems like a lot of work, and is somewhat difficult to work with. It has to handle the string column markers instead of looping with integers, and that's awkward; moreover, it doesn't offer us any clear way to move us toward solving the problem.
So let's try another representation. How about this?:
const ourEmpty4x4Board = [
[" ", " ", " ", " "],
[" ", " ", " ", " "],
[" ", " ", " ", " "],
[" ", " ", " ", " "],
]
const ourFilled4x4Board = [
["R", " ", " ", " "],
[" ", " ", "R", " "],
[" ", " ", " ", "R"],
[" ", "R", " ", " "],
]
This seems more helpful, so let's go with this, and we can create a empty board like this:
const createEmptyBoard = (size) =>
Array .from ({length: size}, () => Array .from ({length: size}, () => ' '))
createEmptyBoard (4)
//=> [[" ", " ", " ", " "], [" ", " ", " ", " "], [" ", " ", " ", " "], [" ", " ", " ", " "]]
That view isn't particularly helpful if we're trying to debug our work. We would like to have a quick-and-dirty board previewer as we develop the rest. While we could certainly make one that generated something like this:
--- --- --- ---
|♜ | | | |
--- --- --- ---
| | |♜ | |
--- --- --- ---
| |♜ | | |
--- --- --- ---
| | | |♜ |
--- --- --- ---
or even something more fancy, that's probably overkill. How about if we settle for something like this?:
R···
··R·
·R··
···R
Now we need a means to add a Rook to a given board. We will write a function that accepts a board, a row and a column, and returns a new board the same as the original but with a Rook at the given row and column.
This is not too hard. Something like this will do:
const addRook = (board, row, col) => {
const newBoard = board .map ((r) => [...r])
newBoard [row] [col] = 'R'
return newBoard
}
Notice that we're building a new board. The old one would still be intact. I find this a useful way to work. Your instructor may or may not agree or may find this appropriate only for later in the course. But it's the way I think.
So now we can use these tools to add some Rooks to a board:
const createEmptyBoard = (size) =>
Array .from ({length: size}, () => Array .from ({length: size}, () => ' '))
const addRook = (board, row, col) => {
const newBoard = board .map ((r) => [...r])
newBoard [row] [col] = 'R'
return newBoard
}
const display = (board) =>
board .map (row => row .join ('') .replaceAll (/\s/g, '·')) .join ('\n') '\n'
const board = createEmptyBoard (4)
console .log (display (board))
const oneRook = addRook (board, 1, 2)
console .log (display (oneRook))
const twoRooks = addRook (oneRook, 3, 3)
console .log (display (twoRooks))
const threeRooks = addRook (twoRooks, 0, 0)
console .log (display (threeRooks))
const fourRooks = addRook (threeRooks, 2, 1)
console .log (display (fourRooks)).as-console-wrapper {max-height: 100% !important; top: 0}Now we get to solving the problem. I am not going to do it for you. I'm leaving the hardest bit for you to implement. If we have a board like this:
······
·R····
······
····R·
······
··R···
and we want to place another Rook, we can look at each existing Rook in turn and eliminate their row and column from consideration:
·*····
*R****
·*····
·*··R·
·*····
·*R···
and then
·*··*·
*R****
·*··*·
****R*
·*··*·
·*R·*·
followed by
·**·*·
*R****
·**·*·
****R*
·**·*·
**R***
leaving nine squares still to fill. You could write a function that takes a board, randomly chooses one of the unfilled/unblocked squares and fills it, blocking out the squares in its row and column, and incrementing your running tally of Rooks, ending when there are no more squares left to fill. This would work fine, and it might be a good way to go.
But another way would be to actually simply eliminate the matching row and column from what you're working on. Then you could end when the board has no squares. This is slightly cleaner, so I would suggest you try to write a function eliminate which takes a board, a row, and a column, and returns a board identical to the first except that the relevant row and column are removed.
Using that, you can write a recursive function that takes a board and, if it's empty, returns zero; otherwise randomly pick the row and column for a square, eliminate that row and column, recursively call the function with this new board add one to the resulting value and returning it. If you then write one more function to accept the board size, create an empty board of that size, then call the main function with that board, returning the result, you have solved the problem.
As noted up front, though, all this can seem like an extremely roundabout way of handling what could just be countRooks = (n) => n. And it is. But what it lets you do is then with only minor changes, count all the ways of placing n Rooks on an n x n board, or on an m x n board. Or you can accept a board with some Rooks already placed and calculate how many ways there are to place more of them.