Fudoki is a 2003 novel by American writer Kij Johnson, a (stand-alone) sequel to The Fox Woman.
Set in 12th-century Japan, it is narrated by Harueme, a dying unmarried princess in the Court of Emperor Sutoku, who gives her life story constrained as it has been by the privileges of her position. Interleaved with her own life account is a nested story drawing on elements of Japanese mythology she has written as escapism to her own frustrations. This is about the cat Kagaya-hime whose Fudoki of the title is taken to be the common narrative of cat clans which defines their shared reality. When Kagaya-hime's home, relatives and hence Fudoki are destroyed by a fire, she sets out on a journey into the unknown. She is transformed into a woman by gods to allow her to complete the journey, yet maintains cat-like behaviours and attitudes throughout. Finally reaching the end of Japan, she transforms back and becomes "The Cat Who Walked a Thousand Miles" to start a Fudoki of her own.
This book was a finalist for the World Fantasy Award and was declared one of the best science fiction/fantasy novels of 2003 by Publishers Weekly.