The game

Given an   N×N   square array of zeroes or ones in an initial configuration,   and a target configuration of zeroes and ones.



The game is to transform one to the other in as few moves as possible by inverting whole numbered rows or whole lettered
columns at once   (as one move).

In an inversion.   any  1  becomes  0,   and any  0  becomes  1  for that whole row or column.



Task

Create a program to score for the Flipping bits game.

 The game should create an original random target configuration and a starting configuration.
 Ensure that the starting position is never the target position.
 The target position must be guaranteed as reachable from the starting position.   (One possible way to do this is to generate the start position by legal flips from a random target position.   The flips will always be reversible back to the target from the given start position).
 The number of moves taken so far should be shown.


Show an example of a short game here, on this page, for a   3×3   array of bits.




		;;; Flip the Bits game, CP/M version.
		;;; CP/M zero page locations
cmdln:		equ	80h
		;;; CP/M system calls
getch: 		equ	1h
putch:		equ	2h
rawio:		equ	6h
puts:		equ	9h		
		org	100h
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Retrieve command line input. If it is not correct, end.
		lxi	d,usage	; Usage string
		mvi	c,puts	; Print that string when we need to
		lxi	h,cmdln	; Pointer to command line
		mov	a,m	; Get length
		ana	a	; Zero?
		jc	5	; Then print and stop
		inx	h	; Advance to first non-space element
		inx	h
		mov	a,m	; Get first character
		sui	'3'	; Minimum number
		jc	5	; If input was less than that, print and stop
		adi	3	; Add 3 back, giving the board size
		cpi	9	; Is it higher than 8 now?
		jnc	5	; Then print usage and stop 
		sta	boardsz	; Store the board size
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Because there's no standard way in CP/M to get at any
		;;; entropy (not even a clock), ask the user to supply some
		;;; by pressing the keys on the keyboard.
		lxi	d,presskeys
		call	outs
		mvi	b,8	; we want to do this 8 times, for 24 keys total
randouter:	mvi	c,3	; there are 3 bytes of state for the RNG
		lxi	h,xabcdat+1
randinner:	push	h	; keep the pointer and counters
		push	b
waitkey:	mvi	c,rawio
		mvi	e,0FFh
		call	5
		ana	a
		jz	waitkey
		pop	b	; restore the pointer and counters
		pop	h
		xra	m	; XOR key with data
		mov	m,a
		inx	h
		dcr 	c	; Have we had 3 bytes yet?
		jnz	randinner
		dcr	b	; Have we done it 8 times yet?
		jnz	randouter
		lxi	d,welcome
		call	outs
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Generate a random board
		lxi	h,board
		lxi	b,4001h	; B=81, C=1
genrand:	call	xabcrand
		ana	c
		mov	m,a
		inx	h
		dcr	b
		jnz	genrand
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Copy board into goal
		lxi	h,board 
		lxi	d,goal
		mvi	b,64
copygoal:	mov	a,m
		stax	d
		inx	h
		inx	d
		dcr	b
		jnz	copygoal
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Do a bunch of random flips on the board (5-20)
		call	xabcrand
		ani	0Fh	; 0..15 flips
		adi	5	; 5..20 flips
		sta	sysflips
		mov	b,a	; Do that many flips
randflip:	call	xabcrand
		call 	flip 	; Unused bits in the random number are ignored
		dcr	b
		jnz	randflip 
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Print the current state
gamestate:	lxi	d,smoves
		call	outs
		lda 	usrflips
		call	outanum
		lxi 	d,sgoal
		call	outs
		lda	sysflips
		call 	outanum
		lxi	d,newline
		call	outs
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Print the current board and the goal
		;;; Print the header first
		lxi	d,sboardhdr
		call	outs		
		lda	boardsz
		lxi	d,2041h	; E=letter (A), D=space
		add	e	; Last letter
		mov 	b,a 	; B = last letter
		mvi	l,2	; Print two headers		
header:		mvi	e,'A'
		mov	a,d
		call	outaspace
headerpart:	mov	a,e
		cmp	b
		jc	headerltr
		mov	a,d	; Print spaces for invalid positions
headerltr:	call	outaspace
		mov	a,e
		inr	a
		mov	e,a
		cpi	'A'+8
		jc	headerpart
		mvi	a,9
		call	outa
		dcr	l	; Print two headers (for two boards)
		jnz	header
		lxi	d,newline
		call	outs
		;;;	Then print each line of the board
		mvi 	c,0	; Start with line 0
printline:	lxi	h,board	; Get position on board
		mvi	d,2	; Run twice - print board and goal
prbrdline:	mvi	a,'1'	; Print line number
		add	c
		call	outaspace
		push	d
		mov	a,c	; Line offset in board
		rlc
		rlc
		rlc
		mov	e,a
		mvi	d,0
		dad	d	; Add line offset
		pop	d	; Restore board counter
		mvi	b,0	; Start with column 0
printcol:	lda	boardsz	; Valid position?
		dcr	a
		cmp	b
		jnc	printbit
		mvi	a,' '	; No - print space
		jmp	printpos
printbit:	mov	a,m	; Yes - print 0 or 1
		adi	'0'
printpos:	call	outaspace
		inx	h	; Next board pos
		inr 	b
		mov	a,b	; Done yet?
		cpi	8
		jnz	printcol	; If not, print next column
		mvi	a,9
		call	outa
		lxi 	h,goal	; Print goal line next
		dcr	d
		jnz 	prbrdline
		mvi	a,13	; Print newline
		call	outa
		mvi	a,10
		call	outa
		inr	c	; Next line
		lda	boardsz	; Valid line?
		dcr	a
		cmp	c
		jnc	printline
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Prompt the user for a move
		lxi	d,prompt	; Print prompt
		call	outs
readinput:	mvi	c,getch		; Read character
		call	5
		ori	32 		; Make letters lowercase
		cpi	'q' 		; Quit?
		rz
		cpi	'9'+1		; 9 or lower? assume number
		jc	nummove
		sui	'a'		; Otherwise, assume letter
		jc	invalid		; So <'a' is invalid input
		call	checkmove	; See if the move is valid
		jc	invalid		; If not, wrong input
		ori	128		; Set high bit for column flip
		call	flip		; Do the flip
		jmp	checkboard	; See if the game is won
nummove:	sui	'1'		; Board array is 0-based of course
		jc	invalid		; Not on board = invalid input
		call	checkmove	; See if the move is vali 
		jc	invalid
		call	flip 		; Do the move (high bit clear for row)
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; See if the user has won
checkboard:	lda	boardsz
		dcr	a
		mov	b,a		; B = line 
checkrow:	lda	boardsz
		dcr	a
		mov	c,a		; C = column
checkcol:	mov	a,b
		rlc			; Line * 8
		rlc
		rlc
		add	c		; + column = offset
		push	b		; Store line/column
		mvi	h,0		; Position offset
		mov	l,a
		lxi	d,board		; Get board
		dad	d
		mov	b,m		; B = board position
		lxi	d,64		; Goal = board+64
		dad	d
		mov	a,m		; A = goal position
		cmp	b		; Are they the same?
		pop 	b		; Restore line/column
		jnz	nowin		; If not, the user hasn't won
		dcr	c		; If so, try next column position
		jp	checkcol
		dcr	b		; If column done, try next row
		jp	checkrow
		;;;	If we get here, the user has won
		lxi	d,win
		jmp	outs
		;;;	The user hasn't won yet, get another move
nowin:		lxi	h,usrflips	; Increment the user flips
		inr	m
		jmp	gamestate	; Print new game state, get new move
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Invalid input: erase it, beep, and get another character
invalid:	lxi	d,nope
		call	outs
		jmp	readinput
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Check if the move in A is valid. Set carry if not.
checkmove:	mov	b,a
		lda	boardsz
		dcr	a
		cmp	b
		mov	a,b
		ret
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Flip row or column A & 7 (zero-indexed) on the board.
		;;; Bit 7 set = column, else row. 
flip:		rlc		; Test bit 7 (and A*2)
		jc	flipcol
		;;; Flip row
		push	b	; Keep registers
		push	h
		ani	0Eh	; Get row number
		rlc		; Calculate offset, A*4
		rlc		; A*8
		mvi	b,0	; BC = A
		mov	c,a
		lxi	h,board	; Get board pointer
		dad	b	; Add row offset
		lxi	b,0801h	; Max. 8 bits, and C=1 (to flip)
fliprowbit:	mov	a,m	; Get position
		xra	c	; Flip position
		mov	m,a	; Store position
		inx	h	; Increment pointer
		dcr	b	; Done yet?
		jnz	fliprowbit
		pop	h	; Restore registers
		pop	b
		ret 
		;;; Flip column
flipcol:	push	b	; Keep registers
		push	d
		push	h
		rrc		; Rotate A back 
		ani 	7	; Get column number
		mvi	d,0	; Column offset
		mov	e,a
		lxi	h,board	; Get board pointer
		dad	d	; Add column offset
		mvi	e,8	; Advance by 8 each time through the loop
		lxi	b,0801h	; Max. 8 bits, and C=1 (to flip)
flipcolbit:	mov	a,m	; Get position
		xra	c	; Flip position
		mov	m,a	; Store position
		dad	d	; Next row
		dcr	b	; Done yet?
		jnz	flipcolbit
		pop	h	; Restore registers
		pop	d
		pop 	b
		ret
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; The "X ABC" 8-bit random number generator
xabcrand:       push	h
		lxi     h,xabcdat
                inr     m       ; X++
                mov     a,m     ; X,
                inx     h       ;
                xra     m       ; ^ C,
                inx     h       ;
                xra     m       ; ^ A,
                mov     m,a     ; -> A
                inx     h
                add     m       ; + B,
                mov     m,a     ; -> B
                rar             ; >>1 
                dcx     h
                xra     m       ; ^ A,
                dcx     h
                add     m       ; + C
                mov     m,a     ; -> C
		pop	h
                ret
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Print the string in DE. This saves one byte per call. 
outs:		mvi	c,puts
		jmp	5
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Print the number in A in decimal, preserving registers
outanum:	push	psw
		push	b
		push	d
		push	h
		lxi 	d,outabuf+3
outadgt:	mvi 	b,-1
outdivmod:	inr	b
		sui	10
		jnc	outdivmod
		adi	10+'0'
		dcx	d 
		stax	d
		mov	a,b
		ana	a
		jnz	outadgt
		call 	outs
		jmp	regrestore
outabuf:	db	'***$'	; Room for ASCII number
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Print the character in A followed by a space, preserving
		;;; registers.
outaspace:	call	outa
		push	psw
		mvi	a,' '
		call	outa
		pop	psw
		ret 
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Print the character in A, preserving all registers.
outa:		push	psw
		push	b
		push 	d
		push	h
		mov	e,a
		mvi	c,putch
		call	5
regrestore:	pop	h
		pop	d
		pop	b
		pop	psw
		ret
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Strings
usage:		db	'Usage: FLIP [3..8], number is board size.$'
presskeys:	db	'Please press some keys to generate a random state...$'
welcome:	db	'done.',13,10,13,10
		db	'*** FLIP THE BITS *** ',13,10
		db	'--------------------- ',
newline:	db	13,10,'$'
smoves:		db	13,10,13,10,'Your flips: $'
sgoal:		db	9,'Goal: $'
sboardhdr:	db	'--Board------------',9,'--Goal-------------',13,10,'$'
prompt:		db	'Press line or column to flip, or Q to quit: $'
nope:		db	8,32,8,7,'$'	; Beep and erase input
win:		db	13,10,7,7,7,'You win!$'
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;;; Data
boardsz:	ds	1		; This will hold the board size
sysflips:	ds	1		; How many flips the system did
usrflips:	ds	1		; How many flips the user did
xabcdat:	ds	4		; RNG state
board:		equ	$	
goal:		equ	board + 64	; Max. 8*8 board