#include <cmath>
#include <cstdio>

#include <cuda_runtime.h>
#include <device_launch_parameters.h>
#include <device_atomic_functions.h>

#include "CudaSudoku_cuda.cuh"


/**
 * This function takes in a bitmap and clears them all to false.
 */
__device__
void clearBitmap(bool *map, int size) {
    for (int i = 0; i < size; i++) {
        map[i] = false;
    }
}


/**
 * This device checks the entire board to see if it is valid.
 *
 * board: this is a N * N sized array that stores the board to check. Rows are stored contiguously,
 *        so to access row r and col c, use board[r * N + c]
 */
__device__
bool validBoard(const int *board) {
    bool seen[N];
    clearBitmap(seen, N);

    // check if rows are valid
    for (int i = 0; i < N; i++) {
        clearBitmap(seen, N);

        for (int j = 0; j < N; j++) {
            int val = board[i * N + j];

            if (val != 0) {
                if (seen[val - 1]) {
                    return false;
                } else {
                    seen[val - 1] = true;
                }
            }
        }
    }

    // check if columns are valid
    for (int j = 0; j < N; j++) {
        clearBitmap(seen, N);

        for (int i = 0; i < N; i++) {
            int val = board[i * N + j];

            if (val != 0) {
                if (seen[val - 1]) {
                    return false;
                } else {
                    seen[val - 1] = true;
                }
            }
        }
    }

    // finally check if the sub-boards are valid
    for (int ridx = 0; ridx < n; ridx++) {
        for (int cidx = 0; cidx < n; cidx++) {
            clearBitmap(seen, N);

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int val = board[(ridx * n + i) * N + (cidx * n + j)];

                    if (val != 0) {
                        if (seen[val - 1]) {
                            return false;
                        } else {
                            seen[val-1] = true;
                        }
                    }
                }
            }
        }
    }


    // if we get here, then the board is valid
    return true;
}


/**
 * This function takes a board and an index between 0 and N * N - 1. This function assumes the board
 * without the value at changed is valid and checks for validity given the new change.
 *
 * board:   this is a N * N sized array that stores the board to check. Rows are stored
 *          contiguously, so to access row r and col c, use board[r * N + c]
 *
 * changed: this is an integer that stores the index of the board that was changed
 */
__device__
bool validBoard(const int *board, int changed) {

    int r = changed / 9;
    int c = changed % 9;

    // if changed is less than 0, then just default case
    if (changed < 0) {
        return validBoard(board);
    }

    if ((board[changed] < 1) || (board[changed] > 9)) {
        return false;
    }

    bool seen[N];
    clearBitmap(seen, N);

    // check if row is valid
    for (int i = 0; i < N; i++) {
        int val = board[r * N + i];

        if (val != 0) {
            if (seen[val - 1]) {
                return false;
            } else {
                seen[val - 1] = true;
            }
        }
    }

    // check if column is valid
    clearBitmap(seen, N);
    for (int j = 0; j < N; j++) {
        int val = board[j * N + c];

        if (val != 0) {
            if (seen[val - 1]) {
                return false;
            } else {
                seen[val - 1] = true;
            }
        }
    }

    // finally check if the sub-board is valid
    int ridx = r / n;
    int cidx = c / n;

    clearBitmap(seen, N);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int val = board[(ridx * n + i) * N + (cidx * n + j)];

            if (val != 0) {
                if (seen[val - 1]) {
                    return false;
                } else {
                    seen[val - 1] = true;
                }
            }
        }
    }

    // if we get here, then the board is valid
    return true;
}


/**
 * This kernel has each thread try to solve a different board in the input array using the
 * backtracking algorithm.
 *
 * boards:      This is an array of size numBoards * N * N. Each board is stored contiguously,
 *              and rows are contiguous within the board. So, to access board x, row r, and col c,
 *              use boards[x * N * N + r * N + c]
 *
 * numBoards:   The total number of boards in the boards array.
 *
 * emptySpaces: This is an array of size numBoards * N * N. board is stored contiguously, and stores
 *              the indices of the empty spaces in that board. Note that this N * N pieces may not
 *              be filled.
 *
 * numEmptySpaces:  This is an array of size numBoards. Each value stores the number of empty spaces
 *                  in the corresponding board.
 *
 * finished:    This is a flag that determines if a solution has been found. This is a stopping
 *              condition for the kernel.
 *
 * solved:      This is an output array of size N * N where the solved board is stored.
 */
__global__
void sudokuBacktrack(int *boards,
        const int numBoards,
        int *emptySpaces,
        int *numEmptySpaces,
        int *finished,
        int *solved) {

    int index = blockDim.x * blockIdx.x + threadIdx.x;

    int *currentBoard;
    int *currentEmptySpaces;
    int currentNumEmptySpaces;


    while ((*finished == 0) && (index < numBoards)) {
    
        int emptyIndex = 0;

        currentBoard = boards + index * 81;
        currentEmptySpaces = emptySpaces + index * 81;
        currentNumEmptySpaces = numEmptySpaces[index];

        while ((emptyIndex >= 0) && (emptyIndex < currentNumEmptySpaces)) {

            currentBoard[currentEmptySpaces[emptyIndex]]++;

            if (!validBoard(currentBoard, currentEmptySpaces[emptyIndex])) {

                // if the board is invalid and we tried all numbers here already, backtrack
                // otherwise continue (it will just try the next number in the next iteration)
                if (currentBoard[currentEmptySpaces[emptyIndex]] >= 9) {
                    currentBoard[currentEmptySpaces[emptyIndex]] = 0;
                    emptyIndex--;
                }
            }
            // if valid board, move forward in algorithm
            else {
                emptyIndex++;
            }

        }

        if (emptyIndex == currentNumEmptySpaces) {
            // solved board found
            *finished = 1;

            // copy board to output
            for (int i = 0; i < N * N; i++) {
                solved[i] = currentBoard[i];
            }
        }

        index += gridDim.x * blockDim.x;
    }
}


void cudaSudokuBacktrack(const unsigned int blocks,
        const unsigned int threadsPerBlock,
        int *boards,
        const int numBoards,
        int *emptySpaces,
        int *numEmptySpaces,
        int *finished,
        int *solved) {

    sudokuBacktrack<<<blocks, threadsPerBlock>>>
        (boards, numBoards, emptySpaces, numEmptySpaces, finished, solved);
}


/**
 * This kernel takes a set of old boards and finds all possible next boards by filling in the next
 * empty space.
 *
 * old_boards:      This is an array of size sk. Each N * N section is another board. The rows
 *                  are contiguous within the board. This array stores the previous set of boards.
 *
 * new_boards:      This is an array of size sk. Each N * N section is another board. The rows
 *                  are contiguous within the board. This array stores the next set of boards.
 *
 * total_boards:    Number of old boards.
 *
 * board_index:     Index specifying the index of the next opening in new_boards.
 *
 * empty_spaces:    This is an array of size sk. Each N * N section is another board, storing the
 *                  indices of empty spaces in new_boards.
 *
 * empty_space_count:   This is an array of size sk / N / N + 1 which stores the number of empty
 *                      spaces in the corresponding board.
 */
__global__
void
cudaBFSKernel(int *old_boards,
        int *new_boards,
        int total_boards,
        int *board_index,
        int *empty_spaces,
        int *empty_space_count) {
    
    unsigned int index = blockIdx.x * blockDim.x + threadIdx.x;
    
    // board_index must start at zero 

    while (index < total_boards) {
        // find the next empty spot
        int found = 0;

        for (int i = (index * N * N); (i < (index * N * N) + N * N) && (found == 0); i++) {
            // found a open spot
            if (old_boards[i] == 0) {
                found = 1;
                // get the correct row and column shits
                int temp = i - N * N * index;
                int row = temp / N;
                int col = temp % N;
                
                // figure out which numbers work here
                for (int attempt = 1; attempt <= N; attempt++) {
                    int works = 1;
                    // row constraint, test various columns
                    for (int c = 0; c < N; c++) {
                        if (old_boards[row * N + c + N * N * index] == attempt) {
                            works = 0;
                        }
                    }
                    // column contraint, test various rows
                    for (int r = 0; r < N; r++) {
                        if (old_boards[r * N + col + N * N * index] == attempt) {
                            works = 0;
                        }
                    }
                    // box constraint
                    for (int r = n * (row / n); r < n; r++) {
                        for (int c = n * (col / n); c < n; c++) {
                            if (old_boards[r * N + c + N * N * index] == attempt) {
                                works = 0;
                            }
                        }
                    }
                    if (works == 1) {
                        // copy the whole board

                        int next_board_index = atomicAdd(board_index, 1);
                        int empty_index = 0;
                        for (int r = 0; r < 9; r++) {
                            for (int c = 0; c < 9; c++) {
                                new_boards[next_board_index * 81 + r * 9 + c] = old_boards[index * 81 + r * 9 + c];
                                if (old_boards[index * 81 + r * 9 + c] == 0 && (r != row || c != col)) {
                                    empty_spaces[empty_index + 81 * next_board_index] = r * 9 + c;

                                    empty_index++;
                                }
                            }
                        }
                        empty_space_count[next_board_index] = empty_index;
                        new_boards[next_board_index * 81 + row * 9 + col] = attempt;
                    }
                }
            }
        }

        index += blockDim.x * gridDim.x;
    }
}


void callBFSKernel(const unsigned int blocks, 
                        const unsigned int threadsPerBlock,
                        int *old_boards,
                        int *new_boards,
                        int total_boards,
                        int *board_index,
                        int *empty_spaces,
                        int *empty_space_count) {
    cudaBFSKernel<<<blocks, threadsPerBlock>>>
        (old_boards, new_boards, total_boards, board_index, empty_spaces, empty_space_count);
}


	.file	"tmpxft_00298190_00000000-6_CudaSudoku_cuda.cudafe1.cpp"
	.text
#APP

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2034:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2034:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z11clearBitmapPbi
	.type	_Z11clearBitmapPbi, @function
_Z11clearBitmapPbi:
.LFB2027:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2027:
	.size	_Z11clearBitmapPbi, .-_Z11clearBitmapPbi
	.globl	_Z10validBoardPKi
	.type	_Z10validBoardPKi, @function
_Z10validBoardPKi:
.LFB2028:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2028:
	.size	_Z10validBoardPKi, .-_Z10validBoardPKi
	.globl	_Z10validBoardPKii
	.type	_Z10validBoardPKii, @function
_Z10validBoardPKii:
.LFB2029:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2029:
	.size	_Z10validBoardPKii, .-_Z10validBoardPKii
	.globl	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_
	.type	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_, @function
_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_:
.LFB2056:
	.cfi_startproc
	endbr64
	subq	$184, %rsp
	.cfi_def_cfa_offset 192
	movq	%rdi, 40(%rsp)
	leaq	72(%rsp), %rdi
	movl	%esi, 36(%rsp)
	leaq	84(%rsp), %rsi
	movq	%rdx, 24(%rsp)
	leaq	56(%rsp), %rdx
	movq	%rcx, 16(%rsp)
	leaq	64(%rsp), %rcx
	movq	%r8, 8(%rsp)
	movq	%r9, (%rsp)
	movq	%fs:40, %rax
	movq	%rax, 168(%rsp)
	xorl	%eax, %eax
	leaq	40(%rsp), %rax
	movl	$1, 80(%rsp)
	movq	%rax, 120(%rsp)
	leaq	36(%rsp), %rax
	movq	%rax, 128(%rsp)
	leaq	24(%rsp), %rax
	movq	%rax, 136(%rsp)
	leaq	16(%rsp), %rax
	movq	%rax, 144(%rsp)
	leaq	8(%rsp), %rax
	movq	%rax, 152(%rsp)
	movq	%rsp, %rax
	movq	%rax, 160(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 72(%rsp)
	movq	%rax, 84(%rsp)
	movl	$1, 92(%rsp)
	call	__cudaPopCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L8
	pushq	64(%rsp)
	.cfi_def_cfa_offset 200
	leaq	_Z15sudokuBacktrackPiiS_S_S_S_(%rip), %rdi
	pushq	64(%rsp)
	.cfi_def_cfa_offset 208
	movq	100(%rsp), %rcx
	movl	108(%rsp), %r8d
	movq	88(%rsp), %rsi
	movl	96(%rsp), %edx
	leaq	136(%rsp), %r9
	call	cudaLaunchKernel@PLT
	popq	%rax
	.cfi_def_cfa_offset 200
	popq	%rdx
	.cfi_def_cfa_offset 192
.L8:
	movq	168(%rsp), %rax
	subq	%fs:40, %rax
	je	.L10
	call	__stack_chk_fail@PLT
.L10:
	addq	$184, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2056:
	.size	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_, .-_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_
	.globl	_Z15sudokuBacktrackPiiS_S_S_S_
	.type	_Z15sudokuBacktrackPiiS_S_S_S_, @function
_Z15sudokuBacktrackPiiS_S_S_S_:
.LFB2057:
	.cfi_startproc
	endbr64
	jmp	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_
	.cfi_endproc
.LFE2057:
	.size	_Z15sudokuBacktrackPiiS_S_S_S_, .-_Z15sudokuBacktrackPiiS_S_S_S_
	.globl	_Z19cudaSudokuBacktrackjjPiiS_S_S_S_
	.type	_Z19cudaSudokuBacktrackjjPiiS_S_S_S_, @function
_Z19cudaSudokuBacktrackjjPiiS_S_S_S_:
.LFB2030:
	.cfi_startproc
	endbr64
	movabsq	$4294967297, %rax
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movq	%r9, %r13
	xorl	%r9d, %r9d
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movq	%r8, %r12
	xorl	%r8d, %r8d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	movl	%ecx, %ebp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	movq	%rdx, %rbx
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
	movl	%esi, 20(%rsp)
	movq	96(%rsp), %r14
	movq	%rax, 24(%rsp)
	movl	28(%rsp), %ecx
	movq	20(%rsp), %rdx
	movq	104(%rsp), %r15
	movq	%rax, 12(%rsp)
	movl	%edi, 8(%rsp)
	movl	16(%rsp), %esi
	movq	8(%rsp), %rdi
	call	__cudaPushCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L14
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	movq	%r15, %r9
	movq	%r14, %r8
	movq	%r13, %rcx
	movq	%r12, %rdx
	movl	%ebp, %esi
	movq	%rbx, %rdi
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	jmp	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_
.L14:
	.cfi_restore_state
	addq	$40, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2030:
	.size	_Z19cudaSudokuBacktrackjjPiiS_S_S_S_, .-_Z19cudaSudokuBacktrackjjPiiS_S_S_S_
	.globl	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_
	.type	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_, @function
_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_:
.LFB2058:
	.cfi_startproc
	endbr64
	subq	$184, %rsp
	.cfi_def_cfa_offset 192
	movq	%rdi, 40(%rsp)
	leaq	72(%rsp), %rdi
	movq	%rsi, 32(%rsp)
	leaq	84(%rsp), %rsi
	movl	%edx, 28(%rsp)
	leaq	56(%rsp), %rdx
	movq	%rcx, 16(%rsp)
	leaq	64(%rsp), %rcx
	movq	%r8, 8(%rsp)
	movq	%r9, (%rsp)
	movq	%fs:40, %rax
	movq	%rax, 168(%rsp)
	xorl	%eax, %eax
	leaq	40(%rsp), %rax
	movl	$1, 80(%rsp)
	movq	%rax, 120(%rsp)
	leaq	32(%rsp), %rax
	movq	%rax, 128(%rsp)
	leaq	28(%rsp), %rax
	movq	%rax, 136(%rsp)
	leaq	16(%rsp), %rax
	movq	%rax, 144(%rsp)
	leaq	8(%rsp), %rax
	movq	%rax, 152(%rsp)
	movq	%rsp, %rax
	movq	%rax, 160(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 72(%rsp)
	movq	%rax, 84(%rsp)
	movl	$1, 92(%rsp)
	call	__cudaPopCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L17
	pushq	64(%rsp)
	.cfi_def_cfa_offset 200
	leaq	_Z13cudaBFSKernelPiS_iS_S_S_(%rip), %rdi
	pushq	64(%rsp)
	.cfi_def_cfa_offset 208
	movq	100(%rsp), %rcx
	movl	108(%rsp), %r8d
	movq	88(%rsp), %rsi
	movl	96(%rsp), %edx
	leaq	136(%rsp), %r9
	call	cudaLaunchKernel@PLT
	popq	%rax
	.cfi_def_cfa_offset 200
	popq	%rdx
	.cfi_def_cfa_offset 192
.L17:
	movq	168(%rsp), %rax
	subq	%fs:40, %rax
	je	.L19
	call	__stack_chk_fail@PLT
.L19:
	addq	$184, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2058:
	.size	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_, .-_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_
	.globl	_Z13cudaBFSKernelPiS_iS_S_S_
	.type	_Z13cudaBFSKernelPiS_iS_S_S_, @function
_Z13cudaBFSKernelPiS_iS_S_S_:
.LFB2059:
	.cfi_startproc
	endbr64
	jmp	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_
	.cfi_endproc
.LFE2059:
	.size	_Z13cudaBFSKernelPiS_iS_S_S_, .-_Z13cudaBFSKernelPiS_iS_S_S_
	.globl	_Z13callBFSKerneljjPiS_iS_S_S_
	.type	_Z13callBFSKerneljjPiS_iS_S_S_, @function
_Z13callBFSKerneljjPiS_iS_S_S_:
.LFB2031:
	.cfi_startproc
	endbr64
	movabsq	$4294967297, %rax
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movq	%r9, %r13
	xorl	%r9d, %r9d
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movl	%r8d, %r12d
	xorl	%r8d, %r8d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	movq	%rcx, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	movq	%rdx, %rbx
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
	movl	%esi, 20(%rsp)
	movq	96(%rsp), %r14
	movq	%rax, 24(%rsp)
	movl	28(%rsp), %ecx
	movq	20(%rsp), %rdx
	movq	104(%rsp), %r15
	movq	%rax, 12(%rsp)
	movl	%edi, 8(%rsp)
	movl	16(%rsp), %esi
	movq	8(%rsp), %rdi
	call	__cudaPushCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L22
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	movq	%r15, %r9
	movq	%r14, %r8
	movq	%r13, %rcx
	movl	%r12d, %edx
	movq	%rbp, %rsi
	movq	%rbx, %rdi
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	jmp	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_
.L22:
	.cfi_restore_state
	addq	$40, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2031:
	.size	_Z13callBFSKerneljjPiS_iS_S_S_, .-_Z13callBFSKerneljjPiS_iS_S_S_
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"_Z13cudaBFSKernelPiS_iS_S_S_"
.LC1:
	.string	"_Z15sudokuBacktrackPiiS_S_S_S_"
	.section	.text.startup,"ax",@progbits
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2061:
	.cfi_startproc
	endbr64
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	pushq	$0
	.cfi_def_cfa_offset 24
	xorl	%r9d, %r9d
	orl	$-1, %r8d
	pushq	$0
	.cfi_def_cfa_offset 32
	leaq	.LC0(%rip), %rdx
	movq	%rax, %rdi
	movq	%rax, %rbx
	pushq	$0
	.cfi_def_cfa_offset 40
	movq	%rdx, %rcx
	leaq	_Z13cudaBFSKernelPiS_iS_S_S_(%rip), %rsi
	pushq	$0
	.cfi_def_cfa_offset 48
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFunction@PLT
	addq	$32, %rsp
	.cfi_def_cfa_offset 16
	movq	%rbx, %rdi
	xorl	%r9d, %r9d
	pushq	$0
	.cfi_def_cfa_offset 24
	leaq	.LC1(%rip), %rdx
	orl	$-1, %r8d
	leaq	_Z15sudokuBacktrackPiiS_S_S_S_(%rip), %rsi
	pushq	$0
	.cfi_def_cfa_offset 32
	movq	%rdx, %rcx
	pushq	$0
	.cfi_def_cfa_offset 40
	pushq	$0
	.cfi_def_cfa_offset 48
	call	__cudaRegisterFunction@PLT
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	addq	$32, %rsp
	.cfi_def_cfa_offset 16
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rbx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2061:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

#ifndef CUDA_SUDOKU_CUDA_CUH
#define CUDA_SUDOKU_CUDA_CUH


#define N 9
#define n 3



void cudaSudokuBacktrack(const unsigned int blocks,
        const unsigned int threadsPerBlock,
        int *boards,
        const int numBoards,
        int *emptySpaces,
        int *numEmptySpaces,
        int *finished,
        int *solved);

void callBFSKernel(const unsigned int blocks, 
                        const unsigned int threadsPerBlock,
                        int *old_boards,
                        int *new_boards,
                        int total_boards,
                        int *board_index,
                        int *empty_spaces,
                        int *empty_space_count); 
#endif // CUDA_SUDOKU_CUDA_CUH

	.text
	.file	"CudaSudoku_cuda.hip"
	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_

	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.amdgpu_metadata
---
amdhsa.kernels:  []
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
